CS503 Operating Systems- Lab 1: Process management and scheduling
CS503: Operating Systems
Lab 1: Process management and scheduling [160 pts]
In this lab you will implement a two-level process scheduler and a few scheduling policies in XINU that will avoid starvation of processes and improve load balancing between processes. In addition, you will implement process ownership. At the end of this lab you will be able to explain the advantages and disadvantages of the scheduling policies implemented and evaluated in XINU.
The scheduling invariant in XINU assumes that, at any time, the highest priority process eligible for CPU service is executing, with round-robin scheduling for processes of equal priority. Under this scheduling policy, processes with the highest priority, if ready, will always be executing. As a result, processes with lower priority may never receive CPU time. Starvation is produced in XINU when we have two or more processes eligible for execution that have different priorities. For ease of discussion we call "the set of processes in the ready list and the current process" as eligible processes.
In this lab, all processes in XINU will be put into one of the two scheduling groups: Shortest Remaining Time First (SRTF) group and Multilevel Feedback Queue Scheduler (MFQS) group. Within each group, processes will be scheduled using a different scheduling policy.
When resched() is invoked, it should first decide which group should occupy the CPU. Then it picks up a process from this group to run. In this lab, the scheduler should run an Round Robing Scheduler to pick the group. After the group is decided, it should pick up one process in this group using the group-specific scheduling policy. For the Shortest Remaining Time Scheduler group, the kernel should apply the SRTF Scheduler; for the Multilevel Feedback Queue Scheduler group it should apply the MFQS Scheduler. In the following sections we will introduce the three scheduling policies.
Readings
Read the following documents and follow the instruction in the setup guide: . XINU setup. . Chapters 3, 4, 5, and 6 from the XINU textbook. . Optional: Chapters 6, 7 and 9 of the OSTEP recommended book. . Files to read before start: reched.c (Most code you write will be in this file), Initialize .c, process.h, queue.h/c, kill.c, geitem.c, ready.c
System call interface changes
This section describes the kernel interface changes required for applications to use the functions described in the next sections and to grade the lab assignments.
Assigning processes to scheduling groups
You will need to modify the existing create() system call, such that it has the following format: create(void *funcaddr, uint32 ssize, int group, pri16 priority, ... ) Please add a new argument, group, to the create system call (before priority). group should be either SRTFSCHED or MFQSCHED.
Lead TA: Bilal Naeem Recommended: As you implement the different components of the lab, make sure you implement your own test cases. Try to create simple test cases so that you can predict the expected result and reason about your code when it fails. Think hard about the test cases you need to create to ensure that you do not forget to test any aspect of the new functions
Reminder: You are required to commit and push your changes frequently (e.g., at least every couple of hours of work or more often) to the GitHub Classroom git repository assigned to you. This will be important to help you recover from bad changes, communicate with your TA, and enforce the course policies. Failure to comply with this requirement in any assignment will result in lost points or a zero grade in the assignment. Academic honesty: Do not share your code during the assignment or even after the assignment. In particular, do not publish it on GitHub or through other means. Do not read other people's code at all. In addition, please make sure that you understand and comply with the course policy on academic honesty as announced in class.
For processes created by XINU by default (e.g., main, null), you should assign them to the respective group as specified by the system_processes_group_mfqs global variable. Setting user ID Create the system call setuid that receives the new uid: setuid(int newuid) Shortest remaining time scheduler Please add a new system call create_srtf() with the following format pid32 create_srtf(void funcaddr, uint32 ssize, int group, pri16 priority, char name, uint32 burst, uint32 nargs, ...) Create a file named create_srtf.c under system folder Add a field uint32 prburst to the struct procent in process.h Other functions Create the system call chnice that changes the process niceness: chnice(pid32 p, int nice) Create the system call getrecentcpu() , which should return the recent_cpu, using the fixed-point type provided by the qmath library, for processes in the MFQS group: fix16_t getrecentcpu(pid32 p) Create the system call getloadavg() which should return the load_avg using the fixed-point type provided by the qmath library: fix16_t getloadavg() Additional notes The resched() function will be invoked for scheduling a process to run. Most of your work to implement scheduling policies will be done inside this function. So please understand each line of code of this system call before you start to implement. One thing to note is that for this lab, the most important aspect is correctness, the efficiency of the scheduling algorithm is secondary. Therefore, you can share the ready list for both scheduling policies. Make sure you run make clean or make rebuild after modifying any files under include folder
- Round Robin Scheduler [20 pts] Overview The scheduling policy for process group scheduling is the Round Robin scheduler. On each rescheduling operation, the scheduler should pick a group based on round-robin. For example, if the last group that was scheduled was the SRTF group, the next group to be scheduled should be the MFQS group. Define a global variable int system_processes_group_mfqs and initialize it to value 0. When the variable has value 0, processes created by the XINU system (e.g., create process, main process, null process) should be placed in the SRTF group. When it has a non-zero value, those processes should be placed in the MFQS group. However, application processes should always be created in the group specified by the application when calling the create system call, as described later.
- Shortest Remaining Time First Scheduler [50pts] In this part, you will implement a scheduler using the SRTF algorithm (Shortest Remaining Time First) that determines when a process can be scheduled based on the remaining burst time required to finish the task. By using the shortest remaining time scheduler, each process will be assigned a burst time upon creation. The scheduler will let the process with the shortest burst run first, after a certain amount of CPU time, any process with the shortest burst time in the ready queue will be selected, and the scheduler will send the current process back to the ready queue and let the new process with shortest burst time be the current process and use the CPU time. To better explain this algorithm, we have the following example:Please check ED frequently for the latest update.
Process ID Burst Time Arrival Time 1 9 0 2 6 2 3 2 5 Process 1 will be executed at the beginning since the earliest arrival time. Process 2 arrives at the 2nd unit of CPU time with less burst time (process 1 burst time is 7 at this moment ), process 2 will be executed in the next unit of CPU time. After 3 units of CPU time, process 3 arrives with burst time 2 which is less than the currently running process 2 (burst time 6-3=3). So process 3 will then be executed in the next unit of CPU time. Once the process burst time reaches 0, the process will be put back in the ready queue (In your implementation, the scheduler will reassign burst time for those processes). The schedule always selects the process with the shortest burst time in the ready queue and runs that process for the next time slice (By default, the time slice in xinu is 2 milliseconds. You can change that by modifying QUANTUM). Our testcases won't change QUANTUM value, just make sure that your implementation works with the default value of QUANTUM. Please change QUANTUM back to 2 when you turn in. Implementation sketch To implement this scheduler, add a field called prburst under the process struct procent . To enable this feature, you will need to write a new file under the system folder and name it create_srtf.c . The new create function takes one more argument to get the burst time for the process. Please add a new argument uint32 burst to the system call create_srtf() . For the original create system call, initialize prburst to 0. According to the policy, the shortest remaining time first schedule does the following: Each time the resched function is called, decrement the old processʼs burst time by 1. Always select the process with the shortest burst time in the ready queue for the next time slice. For two or more processes with same burst time(shortest), use the first one you found from the search result. If any process's burst time reaches 0, assign new burst time using burst = 100 - (priority/10) In case of a burst tie, the scheduler should chose the process that was first added to the ready list (of those tied). If none of the processes in the ready list have shorter burst time than the current process, let the current process continue running. Note that all processes created by the original create system call always have 0 burst time when created, which means the scheduler needs to assign them new burst time before adding them to the ready queue. Benchmark sketch To evaluate the shortest time first scheduler, you will need to experiment with several situations: The process with a higher burst time is created and resumed before the process with a lower burst time. The process with a lower burst time is created and resumed before the process with a higher burst time. Create multiple processes with different burst time and same burst time. All processes have 0 burst time.
- Multilevel Feedback Queue Scheduler [70 pts] The Multilevel Feedback Queue scheduling algorithms decide how to schedule processes using several queues to store the list of eligible processes. Conceptually, these queues are ranked, i.e., processes in Q(i) have higher priority over processes in Q(i+1). In practice, each queue can be mapped to a priority . However, the assignment of processes to queues is not fixed -- the Multilevel Feedback Queue scheduler, unlike Multilevel Queue scheduling, dynamically reassigns processes to queues depending on their runtime behavior. Thus, depending on the scheduling algorithm, processes can be promoted to higher priority queues or demoted to lower-priority queues according to process behavior and scheduler parameters. This design ensures that Multilevel Feedback Queue scheduler schemes are highly flexible and can express a wide range of scheduling policies. The scheduling policy you will implement leverages the concept of niceness, which is commonly used in Unix-based operating systems. Niceness (N_i) is an integer and a property of each process that ranges from -20 to +20. Positive numbers contribute to decrease the priority of a process and negative numbers contribute to increase it. Hence, processes with a high N_i are "nice" because the user is decreasing the process priority and making more likely that other processes will be able to use the CPU. By default, new processes start with niceness of 0 (i.e. N_i = 0). The system call chnice() that you will implement modifies the niceness of a given process. In addition to niceness, this scheduler requires the computation of three fields: (a) priority_i , which specifies the queue of a process, (b) recent_cpu_i , which measures the process CPU usage, (c) load_avg , which measures the overall system load (i.e., it is a system-wide property). priority_i is an integer, but recent_cpu_i and load_avg are real numbers. The MFQS scheduling algorithm schedules processes in the same queue using round-robin and it always picks to run a process of the highest priority queue that has at least one process. Processes are assigned to different queues by calculating for all non-null processes the following formula at every 10 ms:
priority_i := 100 - (recent_cpu_i / 2) - (N_i 2) In addition, the priority value needs to be within the range of 0 and 100. Thus, the actual priority of a process will be capped with priority_i = min(max(priority_i,0),100) . The priority of a process is also immediately calculated when a process is created and when its nice value changes. When a process is created your scheduler should ensure recent_cpu_i = 0 . Subsequently, for every timer interrupt the recent_cpu_i of the current process is incremented by 1, i.e. recent_cpu_i is updated on every clock handler call. Furthermore, on every second the recent_cpu_i of every non-null process of the scheduling group is updated using the following formula: recent_cpu_i := (2load_avg)/(2load_avg + 1) recent_cpu_i + N_i The load_avg is calculated every second (not more often, not less). The formula to compute load_avg relies on n_ready_processes , which is the number of processes in the ready list of the MFQS scheduler: load_avg := (59/60) load_avg + (1/60) n_ready_processes load_avg = 0 at boot time. This field will keep track of the average load of the system using a moving average approach, which ensures that load_avg will reflect not just the current system usage but also the past system usage. Further, the moving average approach also ensures that more weight is given to the more recent system usage than to the less recent. The null process always has priority 0, thus its recent_cpu_i does not need to be computed. It is however calculated for every non- null process. For grading purposes, if load_avg , recent_cpu_i , priority_i , need to be updated simultaneously, it is recommended to update load_avg first. After that, use the new load_avg to update recent_cpu_i . Finally, use the new recent_cpu_i to update priority_i . Be aware that a rapid increase in the value of recent_cpu_i can result in the priority dropping to 0. You need to implement round- robin between processes with priority 0. Implementation sketch Since the queue mechanism of XINU already schedules processes with the same priority using a round-robin algorithm you can use a single queue(readylist) for the entire ready list of this scheduler as long as you update the priority according to the schedule policy. Given that XINU does not support floating point, use the fixed-point libraries provided, which rely on integer operations, to implement the scheduler formulas that involve fractions (fix16.tgz). Please download this file fix16.tgz and extract it under xinu- cs503-fall2023/include directory(tar -xf fix16.tgz). You also need to include this file where you add your fix16_t type variables. To ensure more predictable behavior under the grading test cases, ensure the above formulas are all executed at the same moment for different processes and that different formulas are synchronized. For instance, where T is the time since the system booted, (a) at T = 0.010s, 0.020s,... update all the priority_i fields for all processes, (b) at T = 1s, 2s,... update all processes recent_cpu_i using the load_avg formula and (c) at T = 1s, 2s,... update the load_avg . Benchmark sketch To evaluate the Multilevel Feedback Queue Scheduler, you will need to experiment situations:considering when some processes in this group are executed late or are blocked and come back later. You will have to devise your own test cases for MFQS as well. Try to test your scheduler in a variety of cases, e.g. test your scheduler in cases where all processes have high niceness, low niceness or a mix of it. Similarly, test with a set of processes containing a mix of high and low cpu loads. Ensure that you implement getrecentcpu() and getloadavg() functions, which are important to grade the assignments. To simplify changes to the default XINU process priority type (i.e., pri16) in this lab, you do not need to ensure that the getprio() system call works.
- Process ownership [20 pts] In XINU the concept of process owner does not currently exist. As a result, all processes have the same capabilities and can for instance terminate any other process. To prevent this, in this lab you will create the concept of a process owner and the concept of a privileged user, i.e., the root user. To implement this you will need to add a field to the process table uid, an integer, that represents the user ID. Assume that any user ID is valid and define the root user by uid == 0 . When a process creates a new process, the new process should have the same owner as the process that invoked the create system call (i.e., new processes inherit ownership). To modify the process owner of the currently running process, a process must call a new system call:
setuid(int newuid) Only a root process can change its ownership. If the ownership change is allowed, the setuid system call should return success (even if a root process tries to change to root) and change the uid of the process that invoked it. Otherwise, it should return an error(SYSERR) and not change the uid of the process. If any non-root process calls setuid, you should return error. Ensure that non-root users can only perform the following process management operations on processes that are owned by them (i.e., target process uid is the same as the currently running process uid): kill(), suspend() and resume() . Root users can make operations on processes of other users. For this lab, process ownership only restricts these three system calls. Turn-in instructions
- Format for submitting: For problems where you are asked to print values using kprintf() or printf(), use conditional compilation (C preprocessor directives #if and #define) with macro XTEST set to 1 or 0 (in include/process.h) to effect print/no print. I.e., XTEST==1: print assignment messages, XTEST==0: do not print assignment messages. Set XTEST to 1 before submission. For your own debug statements, do the same with macro XDEBUG. I.e., XDEBUG==1: print your debug messages, XDEBUG==0: do not print your debug messages. Before submitting your assignment, you can use the check.py script to make sure that your code uses XTEST and XDEBUG properly. In case, you think the script is not working properly, please contact your TAs as soon as possible.
- Before submitting your work, make sure to double-check the Ed discussion to ensure that additional requirements and instructions have been followed.
- Please make sure to disable all debugging output before submitting your code.
- Electronic turn-in instructions: . Go to the xinu-cs503-fall2023/compile directory and run make clean . . Go to the directory of which your xinu-cs503-fall2023 directory is a subdirectory. E.g., if /homes/bob/xinu-cs503-fall2023 is your directory structure, go to /homes/bob. (Note: please do not rename xinu-cs503-fall2023 or any of its subdirectories.) . Type the following command to turn in the files: turnin -c cs503 -p lab1 xinu-cs503-fall2023 . List and check the submitted files with the following command: turnin -c cs503 -p lab1 -vEarly Submission Bonus: Projects delivered 5 full days before the official lab due date receive 10 bonus points as long as they score at least 50% of the assignment total points (without any bonus). It is not necessary to inform the teaching staff ahead of time; students only need to submit before the bonus cutoff date to be considered for this bonus. Late Submission Policy: You can use a total of 3 late days throughout the course. Refer to the course syllabus on Brightspace for the details on late submission policy.
