C++代写 | Operating System代写 | 作业Linux – 这是一个机遇XV6操作系统展开的OS的代写任务，主要考察system call方面的知识
OPERATING SYSTEMS assignment SYSTEM CALLS
Introduction
Throughout this course we will be using a simple, UNIX like teaching Operating System called xv6:
https://pdos.csail.mit.edu/6.828/2017/xv6.html
The xv6 OS is simple enough to cover and understand within a few weeks yet it still contains the important
concepts and organizational structure of UNIX. To run it, you will have to compile the source files and use
the QEMU processor emulator (installed on all CS lab computers).
- xv6 was (and still is) developed as part of MITs 6.828 Operating Systems Engineering course.
- You can find a lot of useful information and getting started tips here: https://pdos.csail.mit.edu/6.828/2017/overview.html
- xv6 has a very useful guide. It will greatly assist you throughout the course assignments: https://pdos.csail.mit.edu/6.828/2017/xv6/book-rev10.pdf
- You may also find the following useful: https://pdos.csail.mit.edu/6.828/2017/xv6/xv6- rev10.pdf
In this assignment we will extend xv6 to support history within the shell process, operating system global
variables and multiple scheduling policies.
You can download xv6 sources for the current work by executing the following command:
git clone http://www.cs.bgu.ac.il/~os182/git/Assignment
Task 0: Running xv
Begin by downloading our revision of xv6, from our course Assignment repository:
- Open a shell and traverse to a directory in your computer where you want to store the sources for the OS course. For example, in Linux: mkdir ~/os cd ~/os
- Execute the following command: git clone http://www.cs.bgu.ac.il/~os182/git/Assignment cd Assignment
- Run xv6 on top of QEMU by calling (note that this line also cleans and builds your code): make clean qemu
Task 1: Wa rm up (HelloXV6)
1.1 Shell history
In this task we will alter one of the user processes in the xv6 package. Note that the package
contains both kernel files and user programs. While they are in the same folder, user programs are
compiled separately from kernel code. Refer to the Makefile and answer the following question:
Where are the user programs / kernel compilation commands?
History of past shell commands allows terminal users to evaluate multiple requests very fast
without re-writing the entire command. In this part of the assignment, you will have to implement
the command save mechanism and retrieval.
Once the history feature is implemented, we need a way of accessing it. You will implement two shell commands that do so:
- A history command, which will print the history of the shell
- A history -l ## command, which will run the command previously executed in the shell, that appears at line ## of the history.
- The history should support command lines of up to 128 characters.
- Your implementation should support a maximum of 16 commands. To do so, you can add the following definition to your code: #define MAX_HISTORY 16.
- This task should be implemented in the shell program code (see sh.c).
1.2 Global variables
Variables allow the user to replace complex commands with shorter commands that are easier to remember. In this task we will add support of global variable, allowing setting and reading them. We will implement this feature in the kernel. To assign a value to a variable in the shell, we will use the syntax:
To support the above, you will implement three system calls:
1) int setVariable(char* variable, char* value) input :
- char* variable A pointer to a buffer that will hold the name of the variable. Assume max buffer size of 32, containing English characters only (a-z, A-Z).
- char* value A pointer to a buffer that will hold the value assigned to the variable. Assume max buffer size of 128, which may contain any character Output :
- 0 Variable set correctly
- – 1 No room for additional variables
- – 2 Input is illegal
2) int getVariable(char* variable, char* value) input :
- char* variable A pointer to a buffer that will hold the name of the variable.
- char* value A pointer to a variable that will get the value of the variable. Output :
- 0 Variable retrieved correctly
- – 1 No variable with the given name
3) int remVariable(char* variable) input :
- char* variable A pointer to a buffer that will hold the name of the variable to be removed. Output :
- 0 Variable removed successfully
- – 1 No variable with the given name
Note: the variables are accessible from any process via system calls and managed by the kernel. Still, you will need to change the shell implementation to identify the variable assignment and replace variables with their values when they are used by shell commands.
- Your implementation should support a maximum of 32 variables. To do so, you can add the following definition to your code: #define MAX_VARIABLES 32.
- This task should be implemented in the shell program code (see sh.c) and in kernel code.
1.3 Shell usage example
$ x=Hello $ y=everyone $ echo $x $y Hello everyone $ history
- x=Hello
- y=everyone
- echo $x $y
- history $ x=Goodbye $ w=$x$y $ echo $w Goodbyeeveryone $ z=history -l 3 $ echo $z history -l 3 $ $z Goodbye everyone
Task 2: Performance Measures
Before implementing various scheduling policies, we will create the infrastructure that
will allow us to examine how they affect performance under different evaluation metrics.
The first step is to extend the proc struct located at proc.h (line 38 ). Extend the proc struct
by adding the following fields to it: ctime , etime , iotime and rtime. These will respectively
represent the creation time, end time, the total time of waiting for I/O, and the total running time of the
process.
Upon the creation of a new process the kernel will update the process creation time. The
run time should be incremented by updating the rtime field of the current process whenever a clock tick
occurs. I/O time should be updated on every clock tick when a process is waiting for I/O (you
can assume that the process is waiting for I/O in case the process’ state is SLEEPING).
Finally, care should be taken in marking the end time of the process (note: a process may
stay in the ZOMBIE state for an arbitrary length of time. Obviously, this should not affect
the process turnaround time, wait time, etc).
Since all this information is retained by the kernel, we are left with the task of
extracting this information and presenting it to the user. To do so, create a new system
call wait2 which extends the wait system call.
int wait2(int pid, int* wtime, int* rtime, int* iotime) input :
- Int pid The process ID to wait for
- int* wtime A pointer to an integer that will hold wait time (= ).
- int* rtime A pointer to an integer that will hold run time.
- Int* iotime A pointer to an integer that will hold io time. Output :
- 0 Process ID of caught child
- – 1 Process pid does not exist
Task 3: Scheduling Policies
Scheduling is a basic and important facility of any operating system. The scheduler must satisfy several conflicting objectives: fast process response time, good throughput for background jobs, avoidance of process starvation, reconciliation of the needs of low priority and high-priority processes, and so on. The set of rules used to determine when and how to select a new process to run is called a scheduling policy.
First, you need to understand the current scheduling policy. Locate it in the code and try to answer the following questions:
- which process does the policy select for running?
- What happens when a process returns from I/O?
- what happens when a new process is created and when / how often does scheduling takes place?
Second, change the current scheduling code so that swapping out running processes will be done every quantum (measured in clock ticks) instead of every clock tick. Add the following line to param.h and initialize the value to 5.
#define QUANTUM <int value>
In the next part of the assignment you will need to add four different scheduling policies in addition to the existing policy. Add this policies by using the C preprocessing abilities.
Tip: You should read about #IFDEF macros. These can be set during compilation by gcc (see
http://gcc.gnu.org/onlinedocs/cpp/Ifdef.html)
Modify the Makefile to support SCHEDFLAG a macro for quick compilation of the appropriate scheduling scheme. Thus the following line will invoke the xv6 build with the First Come First Serve scheduling:
make qemu SCHEDFLAG=FCFS
The default value for SCHEDFLAG should be DEFAULT (in the Makefile!).
3.1. Default policy (SCHEDFLAG=DEFAULT):
Represents the currently implemented scheduling policy.
3.2. First Come First Serve (SCHEDFLAG=FCFS):
This is a non-preemptive policy. A process that gets the CPU runs until it no longer needs it (yield / finish / blocked). Yielding the CPU forces the process to the end of the line.
3.3. Shortest Remaining Time (SCHEDFLAG=SRT):
This is a preemptive version of SJF. Each time the scheduler needs to select a new process it will select the process with minimal approximated run time. In case of a tie, the first process in the array that tied will be selected.
Let A 1 be the approximated run time for a new process. Initially, A 1 =QUANTUM. If the process runs for A 1 clock ticks, then the new approximate run time is A 2 =A 1 +A 1. In general: Ai+1=Ai+Ai. Support the parameter by adding the following line to param.h and initizlize the value to 0.5.
#define ALPHA
Use the rtime parameter from Task 2 to decide if the approximate run time should be updated. The update should occur any time a process is returning (yield, blocked). Calling fork should reset approximate run time to the initial value A 1.
3.4. Completely Fair Schedular with Priority decay (SCHEDFLAG=CFSD):
A preemptive policy inspired by linux CFS (this is not actual CFS). Each time the scheduler needs to select
a new process it will select the process with the minimum run time ratio: +^ . Note that
wtime as referenced here is calculated using the current time and not using etime since the process didnt end yet. In case of a tie, the first process in the array that tied will be selected.
Decay factor is defined using process priority. We will support three priority levels:
- High priority Decay factor = 0.
- Normal priority Decay factor = 1
- Low priority Decay factor = 1.
Priority will be set by a new system call you will add that will change the priority of the current process.
int set_priority(int priority) input :
- Int priority The new priority value for the current process (1-3) Output :
- 0 New priority was set
- – 1 Illegal priority value
Note: The priority of the initial process is Normal. Calling fork should copy the parents priority to the child. Calling exec should not change process priority.
Task 4 : Sanity test
Create a user program called SchedSanity that generates a small number of sub processes (using fork ) of these 4 types:
1) Calculation only These processes will perform a simple calculation within a medium sized l oop 2) Calculation only These processes will perform simple calculation within a very large loop 3) Calculation + IO These processes will perform printing to screen within a medium sized loop 4) Calculation + IO These processes will perform printing to screen within a very large loop
The parent process should collect process information using wait2 and print averages for each type at the end of the run. You will have to explain to the tester what you did and why different types of scheduling gave different results. Play with the loop sizes to generate a noticeable difference. For the CFSD, add process priorities. The application must create all off the sub processes before waiting for them.
Submission Guidelines
Make sure that your Makefile is properly updated and that your code compiles with no warnings
whatsoever. We strongly recommend documenting your code changes with comments these are often
handy when discussing your code with the graders.
Due to our constrained resources, assignments are only allowed in pairs. Please note this important point
and try to match up with a partner as soon as possible.
Submissions are only allowed through the submission system. To avoid submitting a large number of xv
builds, you are required to submit a patch (i.e. a file which patches the original xv6 and applies all your
changes). You may use the following instructions to guide you through the process:
Back-up your work before proceeding!
Before creating the patch review the change list and make sure it contains all the changes that you applied
and nothing more. Modified files are automatically detected by git but new files must be added explicitly
with the git add command:
> git add. Av; git commit m commit message
At this point you may examine the differences (the patch):
> git diff origin
Once you are ready to create a patch, simply make sure the output is redirected to the patch file:
> git diff origin > ID1_ID2.patch
- Tip: Although grades will only apply your latest patch, the submission system supports multiple uploads. Use this feature often and make sure you upload patches of your current work even if you havent completed the assignment.
Finally, you should note that the graders are instructed to examine your code on lab computers only!
We advise you to test your code on lab computers prior to submission. In addition, after submission:
**1. Create a new clean folder
- Git clone xv6 from the assignment page
- Download your submitted assignment
- Apply the patch from (3) to the newly cloned copy from (2)
- Compile it
- Make sure everything runs and works**
Tips and getting started
Take a deep breath. You are about to delve into the code of an operating system that already contains
thousands of code lines. BE PATIENT. This takes time!
Debugging
You can try to debug xv6s kernel with gdb (gdb/ddd is even more convenient). You can read more about
this here: http://zoo.cs.yale.edu/classes/cs422/2011/lec/l2-hw
Working from home
The lab computers should already contain both git and qemu. We will only be able to support technical
problems that occur on lab computers. Having said that, students who wish to work on their personal
computers may do so in several ways:
- Connecting from home to the labs: o Install PuTTY (http://www.chiark.greenend.org.uk/~sgtatham/putty/). o Connect to the host: lvs.cs.bgu.ac.il, using SSH as the connection type. o Use the ssh command to connect to a computer running Linux (see http://oldweb.cs.bgu.ac.il/facilities/labs.html to find such a computer). o Run QEMU using: make qemu-nox. o Tip: since xv6 may cause problems when shutting down you may want to consider using the screen command:
screen make qemu-nox
- Install Linux and QEMU on your own PC.
- Again, we will not support problems occurring on students personal computers.