The "Operating System" course design assignment at the end of 2024 simulates process scheduling
Apply and simulate five different process scheduling algorithms for N processes, including first come first served (FCFS), short process priority (SJF), time slice rotation (RR), high response ratio priority (HRRN), and dynamic priority scheduling ( PR).
Each process is identified by a process control block (PCB). The structure of the PCB contains the following fields: (a) process identification number ID; (b) process arrival time ARRIVETIME; (c) process priority PRIORITY; (d) process running total Time ALLTIME; (e) Process running time CPUTIME; (f) Process waiting time Wait_Time; (g) Process response ratio Res_Ratio; (h) Process status STATE. In the dynamic priority scheduling algorithm, the priority adjustment rule is: for every time slice the process waits for in the ready queue, the priority number increases by 1; for every time slice it runs, the priority number decreases by 3. In order to observe the scheduling process of the process, the program needs to display the status of each process in each time slice, including the running process, the process in the ready queue and the process in the blocking queue, to reflect the process's ready state, execution state and Blocked state.
Source code github link:
/yaqli-1024/process-scheduling-algorithm
1. Data structure design
1. Process control block (PCB) structure
The PCB structure is the core data structure of this code and is used to store process-related information:
(1) ProcessId: The unique identifier of the process.
(2) ARRIVETIME: The time when the process reaches the system.
(3) PRIORITY: The priority of the process. The larger the value, the higher the priority.
(4) ALLTIME: The total CPU time required by the process.
(5) CPUTIME: CPU time already occupied by the process.
(6) Wait_Time: The time the process waits in the ready queue.
(7) Res_Ratio: The response ratio of the process, used for high response ratio priority scheduling algorithm.
(8) STATE: The current state of the process (ready, running, blocked).
The PCB structure also contains two constructors: a default constructor that initializes all member variables to 0, and a parameterized constructor that allows specific member variables to be initialized.
2. Sorting function
Multiple sorting functions are provided for different process scheduling algorithms:
(1) SortPCB_ARRIVETIME: Sort by process arrival time, used for first come first served (FCFS) algorithm.
(2) SortPCB_ALLTIME: Sort by the CPU time required by the process, used for the short process first (SJF) algorithm.
(3) SortPCB_PRIORITY: Sort by process priority, used in the dynamic priority scheduling (PR) algorithm. If the priorities are the same, they are sorted by arrival time.
(4) SortPCB_Res_Ratio: Sort by process response ratio, used for high response ratio first (HRRN) algorithm.
3. Linked list node (Node) structure
The Node structure is used to build a linked list. Each node contains a PCB data and a pointer pNext pointing to the next node. It has two constructors: a default constructor and a parameterized constructor.
4. Linked list (NodeList) class
The NodeList class is used to manage the linked list of process control blocks and includes the following functions:
(1) Constructor: Initialize the linked list.
(2) Copy constructor: copy linked list.
(3) Destructor: Destroy the linked list and release memory.
(4) isEmpty: Check whether the linked list is empty.
(5) getLength: Get the length of the linked list.
(6) get_X_PCB: Get the PCB at a specific position in the linked list.
(7) get_X_Node: Get the Node at a specific position in the linked list.
(8) Print: Print all PCB data in the linked list.
(9) InsertData: Insert data into the linked list, and you can choose whether to reorder it.
(10) Delete_X_PCB: Delete the PCB at a specific position in the linked list.
(11) SortList: Sort the linked list according to the set comparison function.
(12) ComparePCB: Set the comparison function used for sorting.
(13) getHeadNode: Get the head node of the linked list.
2. Algorithm design
Use natural language to describe algorithms
1. First come, first served algorithm (FCFS)
(1) The algorithm first checks whether the incoming process list is empty. If not empty, sort the linked list according to the arrival time of the process.
(2) In the realize method, initialize the current time to 0.
(3) Process each process in the queue in a loop. The first process in the queue is executed first.
(4) For each process, if its arrival time is greater than the current time, the algorithm will wait until the process arrives.
(5) Once the process arrives, set its status to execution state.
(6) Delete the process from the ready queue.
(7) Execute the process until completion and update the current time.
(8) Output the status of the currently executing process and the ready queue in each time slice.
(9) After completing the process execution, output the completed process information.
(10) Select the first process in the current ready queue and execute it, jump to step 4.
(11) If the linked list is empty, output a prompt message and end.
2. Short Process First Algorithm (SJF)
(1) First check whether the incoming process list is empty. If it is not empty, the linked list is sorted according to the arrival time of the process (ARRIVETIME).
(2) In the realize method, initialize the current time to 0. Create an empty ready queue ready_List to store processes that arrived within the current time but have not yet been executed. Extract the first process p from the process list and schedule it according to its arrival time.
(3) Enter the main loop: In a loop, process each process in the linked list until both the main linked list and the ready queue are empty.
(4) If the current time now is less than the arrival time of the first process: the system enters the idle state, outputs the status of "no process is currently executing", and prints the ready queue status in the current time slice (may be empty). Update the current time now to the arrival time of the first process.
(5) Execute the current process: Set the status of the current process p to "execution state" (STATE = 1) and start running the process. During the execution time period, the status of each time slice is recorded.
(6) Update the ready queue: Traverse the main linked list and add new processes with arrival times within the range of [ARRIVETIME, ARRIVETIME + ALLTIME] to the ready queue. Make sure to only add processes that are not in the ready queue to avoid duplication. Sort these processes according to execution time.
(7) After the current process is completed, delete the completed process p from the main linked list and output the completion information. Update the current time now to now + .
(8) If the ready queue is not empty, select the process with the shortest execution time as the next scheduling object. When both the main linked list and the ready queue are empty, the scheduling loop ends and the algorithm execution is completed.
3. Time slice rotation scheduling algorithm (RR)
(1) Initialization: When creating an RR class instance, the algorithm first checks whether the incoming process list is empty. If it is not empty, sort the linked list according to the process arrival time (ARRIVETIME) and call the SortList function to complete the initialization.
(2) Create an empty ready queue ready_List to store processes that arrived before the current time and have not yet completed. Processes in the ready queue are ordered by arrival time.
(3) Enter the main loop: The main loop processes all unfinished processes in sequence until the main linked list and ready queue are empty.
(4) Traverse the main linked list, add processes whose arrival time is less than or equal to the current time now to the ready queue, and delete these processes from the main linked list. Set the status of the added process to "ready" (STATE = 0).
(5) Processing idle time: If the ready queue is empty, check whether there are any unarrived processes in the main linked list. If there is a process that has not arrived, jump to the arrival time of the next process and record the system idle state during the period.
(6) Remove the first process from the ready queue and set its status to "execution state" (STATE = 1). Execute the current process for a time slice (length 1). Record the status of the current time slice, increment the current time now and update the process's elapsed execution time CPUTIME.
(7) Check whether the process is completed: If the execution time CPUTIME of the current process is less than the total execution time ALLTIME, set its status to "ready state" (STATE = 0) and re-add it to the end of the ready queue. If the current process has completed, output the completion information of the process and no longer put it back into the ready queue.
(8) Continue processing the next time slice. If the ready queue is not empty, remove the next process from it and repeat steps 6 and 7. If the ready queue is empty but there are still unarrived processes in the main linked list, jump to the next arriving process time and repeat steps 4 and 5.
(9) When the main linked list and ready queue are both empty, the scheduling cycle ends and the algorithm execution is completed.
4. High response ratio priority algorithm (HRRN)
(1) Initialization: Construct a process list (list) in which the processes are sorted according to arrival time (ARRIVETIME). Set up an empty ready queue (ready_List) to store processes to be executed during scheduling. The ready queue is sorted based on the response ratio (Res_Ratio) of the process, with high response ratio given priority.
(2) Check whether the process list is empty. If it is not empty, get the first arriving process in the process list, set its status to "execution state" (STATE=1), and record the current time as now.
(3) Check whether any process arrives within the execution time range of the currently executing process (i.e. ARRIVETIME is within [now, now + ALLTIME]). Add processes that meet the conditions and are not in the ready queue to the ready queue. If the current time does not reach the arrival time of the next process, the system will wait. At this time, the status of each idle time slice is output.
(4) Execute the current process and update the current time now and the completion status of the process. Output the status of each execution time slice.
(5) The completed process will be removed from the queue. For each process in the ready queue, calculate its waiting time (Wait_Time) and response ratio (Res_Ratio). The response ratio calculation formula is: response ratio = (waiting time + required service time) / required service time. Sort the ready queue according to response comparison.
(6) Select the process with the highest response ratio from the ready queue for execution, and set it to "execution state" (STATE=1). If the ready queue is empty, the next arriving process is fetched from the list for scheduling.
(7) When list and ready_List are both empty, the algorithm ends.
5. Dynamic priority scheduling algorithm (PR)
(1) Initialization: All processes are sorted according to arrival time (ARRIVETIME) and stored in a main queue, called list. At the same time, define an initially empty ready queue ready_List, sorted according to priority, and used to store processes that have arrived but have not yet been executed. The initial priority of each process is set to 50 and the time slice size is fixed to 1.
(2) Take out the process with the highest priority from ready_List and execute it (sorted according to the current priority, the higher the priority, the greater the value). The state of the current process is set to "execution state" (STATE=1), and it executes for a time slice or the remaining time until its completion (whichever is the minimum).
(3) Update priority: The priority of the currently executing process is reduced by 3 for each execution time slice. The priority of all other processes in the ready queue increases by 1 with each elapsed time slice.
(4) If the CPU time of the currently executing process reaches the total execution time (ALLTIME), it is marked as completed and removed from the schedule. Otherwise, it is re-added to the end of the ready queue and the status is marked as "ready" (STATE=0).
(5) After each time slice ends, the ready queue is re-sorted according to priority to ensure that the process with the highest priority is executed first in the next time slice.
(6) Select the process with the highest priority in the ready queue for execution, and repeat steps 2-6.
(7) When the main queue list and ready queue ready_List are both empty, it means that all processes have completed execution and the algorithm ends.
6. System test code (main)
Select a process scheduling algorithm by entering a number, run it and see the results.
3. Display of running results
1. First come, first served algorithm (FCFS)
2. Short Process First Algorithm (SJF)
3. Time slice rotation scheduling algorithm (RR)
4. High response ratio priority algorithm (HRRN)
5. Dynamic priority scheduling algorithm (PR)