Operating System Learning Notes (3) Process Scheduling, Synchronization/mutual exclusion and Deadlock
A previous blog has talked about the meaning of the existence of a process and why we need to come up with the concept of a process.
But then there are several consecutive problems, which are also several problems encountered by multichannel concurrency:
- When multiple processes are concurrent, how to schedule and what are the principles of scheduling?
- What if there are interdependencies between multiple processes, such as synchronization and mutual exclusion?
- What if there is a circular dependency due to a dependency relationship, which may lead to a deadlock?
In this blog we will explain the first problem, which is how processors are scheduled.
Concept of dispatch
In multiprogramming, the number of processes is often more than the number of processors, so it is inevitable that processes contend for processors. Processor scheduling is to allocate processors, that is, in the Ready Queue, a process is selected according to a certain algorithm to process and assign it to run, so as to achieve concurrent execution of processes.
Hierarchy of scheduling
A job often goes through three levels of scheduling from submission to completion, as shown in the figure:
Advanced Scheduling (Job Scheduling)
According to certain principles, one or more jobs in the backup queue on the external memory are selected, necessary resources such as memory, input and output devices are allocated to them, and corresponding processes are established to enable them to obtain the power of competing processors. In short, job scheduling is the scheduling between memory and secondary storage. Each job is only transferred in once and out once.
Most of the multi-channel batch processing systems are equipped with job scheduling, and other systems usually do not require job scheduling.
Intermediate Scheduling (Memory Scheduling)
The purpose of introducing intermediate scheduling is to improve memory utilization and system throughput. For this reason, those processes that are temporarily unable to run are transferred to external memory to wait. At this time, the state of the process is called pending state. When they have running conditions and the memory is slightly idle, there is intermediate scheduling to decide which ready processes on external memory that have running conditions are transferred back to memory, change their state to ready state, and hang on the Ready Queue Wait.
Either the ready state for a long time or the blocking state for a long time may be suspended. Intermediate scheduling is actually a swap in storage management.
Low-level scheduling (process scheduling)
Select a process from the Ready Queue according to some algorithm and assign a processor to it. Process scheduling is the most basic scheduling.
Links to three-level dispatch
Job scheduling selects a batch of jobs from the backup queue in the outer village to enter memory, creates processes for them, and these processes are sent to the Ready Queue. Process scheduling selects one from the Ready Queue, changes its state to running state, and allocates the CPU to it. Intermediate scheduling is to improve memory utilization and hang up those processes that cannot run for the time being.
Job scheduling prepares processes for activity, and process scheduling keeps processes active.
- Intermediate scheduling suspends processes that are temporarily unable to run, between job scheduling and process scheduling.
- The least number of job schedules and the most number of process schedules.
- Process scheduling is the most basic and indispensable.
Objectives of process scheduling
Different scheduling algorithms have different characteristics, in the choice of algorithm, we need to consider its performance, people have a lot of evaluation criteria, the most important are:
CPU utilization
Keep the CPU as “busy” as possible to maximize the utilization of this resource. CPU utilization is calculated as follows:
throughput
The number of jobs completed by the CPU per unit time
Turnaround time
Refers to the sum of the time elapsed from job submission to job completion. It is the sum of the time spent waiting for the job, queuing in the Ready Queue, running on the processor, and input and output
Waiting time
The sum of the time the job is waiting for the processor. The longer the wait time, the lower the Customer Satisfaction Score. The processor scheduling algorithm does not actually affect job execution or input and output time.
Response time
Refers to the time from the user’s submission to the system’s first response.
Implementation of scheduling
Scheduler (Scheduler)
In the operating system, the component used to schedule and dispatch CPUs is called a scheduler, which usually consists of three parts
- Queue. Arrange all ready processes in the system into one or more queues according to a certain strategy for the scheduler to select. Whenever a process transitions to the ready state, the queuer inserts it into the corresponding Ready Queue.
- Dispatcher. According to the process selected by the scheduler, remove it from the Ready Queue and allocate the CPU to the new process.
- Context switcher. When switching processors, two pairs of contexts will be switched. The first pair saves the context of the current process to the PCB, and then loads the context of the dispatcher so that the dispatcher can run; the second pair removes the dispatcher context and loads the CPU field information of the newly selected process into the respective registers of the processor.
During context switching, a large number of load and store instructions are required to save the contents of the registers, so it will take more time. There are now hardware methods to reduce context switching time. Usually two sets of registers are used, one for the kernel and one for the user. In this way, when context switching, only the pointer needs to be changed to point to the current register group.
Scheduling timing, switching and process
The scheduler is a system kernel program. It is possible to run the scheduler only after the event requested for scheduling occurs. Process switching will only be performed after a new ready process is scheduled. In theory, these three things should be executed in order. But in fact, during the operation of the operating system kernel program, if the process scheduling factor occurs at a certain time, it may not be scheduled and switched immediately.
Cases where process scheduling and switching cannot be performed are:
- During the process of processing an interrupt.
- The process is in the critical section of the operating system kernel. After entering the critical section, it needs exclusive access. In theory, it must be locked to prevent other parallel processes from entering. It should not switch to other processes before unlocking to speed up the release of the critical section.
- Other atomic operations that require complete blocking of interruptions. Such as locking, unlocking, interrupting to protect the scene, resuming and other atomic operations. In atomic operations, even interrupts should be shielded, let alone process scheduling and switching.
When process scheduling should be performed:
- If a scheduling condition occurs and the current process cannot continue running, it can be scheduled and switched immediately. If the operating system only schedules processes in this case, it is non-deprivation scheduling.
- After the interrupt processing is completed or the self-trapping processing is completed, before returning to the execution site of the User Mode program of the interrupted process, if the request scheduling flag is placed, the process scheduling and switching can be carried out immediately. If the operating system supports the running scheduler in this case, deprivation scheduling is realized.
Process scheduling method
The so-called process scheduling method refers to when a process is running on the processor, if there is a more important or urgent process that needs to be processed, it is divided into Non-Preemptive Scheduling (applicable to most batch processing systems, but not applicable to Time-sharing systems and most real-time systems) and Preemptive Scheduling.
Wandering process
During process switching, if there is no ready process in the system, the idle process will be called. If no other process is ready, the process will continue to run. The idle process has the lowest priority and is only called when there is no ready process.
It does not require resources other than CPU, so it will not be blocked
Scheduling of two threads
User-level threads. Since the kernel is unaware of the existence of threads, the kernel still selects a process and gives time control as before. It is up to the scheduler in the process to decide which thread to run
Kernel-level thread scheduling. The kernel selects a specific thread to run, usually regardless of which process the thread belongs to. The selected thread is assigned a time slice, and if the time slice is exceeded, it is forced to suspend.
Typical scheduling algorithm
First-Come First-Service (FCFS) algorithm
The simplest scheduling algorithm can be used for both job scheduling and process scheduling.
In job scheduling, the algorithm selects one or more jobs from the backup job queue at a time, transfers them into memory, allocates necessary resources, creates processes, and puts them into the Ready Queue.
In process scheduling, the FCFS scheduling algorithm selects the process that enters the queue first from the Ready Queue each time, assigns the processor to it, puts it into operation, and releases the processor only when the operation is completed or blocked for some reason.
FCFS is an inalienable algorithm. On the surface, it is fair to all jobs, but if a long job arrives at the system first, it will make many short jobs wait for a long time, so it cannot be used as the main scheduling strategy for time-sharing systems and real-time systems…
FCFS is characterized by simplicity, but low efficiency, which is beneficial to long jobs. It is beneficial to CPU busy type, but not conducive to I/O busy type.
Short job first (SJF) algorithm
When scheduling a job, select a job with the shortest estimated running time from the backing queue. When scheduling a process, select a process with the shortest estimated running time from the Ready Queue
SJF has the lowest average wait time and average turnaround time, but it also has disadvantages:
- Unfavorable for long work, may lead to hunger
- Completely without considering the urgency of the job
- The length of the job is determined according to the estimated time provided by the user, and the user may intentionally or unintentionally shorten the estimated running time of his job, resulting in the algorithm not necessarily being short job first
Priority scheduling algorithm
Priority scheduling algorithm can be used for both job scheduling and process scheduling.
According to whether the higher priority process can preempt the currently executing process, the scheduling algorithm can be divided into two types:
- Non-preemptive priority scheduling algorithm.
- Preemptive priority scheduling algorithm.
According to whether the priority can be changed, the priority can be divided into the following two types:
- Static priority. Priority is determined when creating a process, mainly based on process type, resource requirements, user requirements, etc.
- Dynamic priority. During operation, the priority can be dynamically adjusted, mainly based on the length of CPU time, ready process waiting for CPU time, etc.
High response ratio first algorithm
Combining FCFS and SJF algorithms, the waiting time and estimated running time of each job are considered.
According to the formula:
- The same job waiting time, the shorter the required service time, the higher the response ratio, which is conducive to short jobs, similar to SJF
- Require the same service time, the longer the waiting time, the higher the response ratio, similar to FCFS
- For long jobs, the response of the job is improved by the increase in waiting time, and the waiting time is long enough to obtain the processor, overcoming the phenomenon of hunger
Time slice rotation scheduling algorithm
Suitable for time-sharing systems. After using a time slice, even if the process has not finished executing, the processor must be released to the next ready process, and the stripped process returns to the end of the Ready Queue.
If the time slice is too large, it will degenerate into FCFS, and if it is too small, it will lead to frequent switching.
Multilevel queue scheduling algorithm
Among the previous algorithms, since only one process Ready Queue is set in the system, that is, the scheduling algorithm is fixed and single, which cannot meet the different requirements of different users in the system for the process scheduling strategy. In multiprocessor systems, this single scheduling policy implementation mechanism is more prominent, and the multi-level queue scheduling algorithm can make up for this shortcoming to a certain extent.
Each processor is provided with a separate Ready Queue, and each queue implements a different scheduling algorithm.
Multi-level feedback queue scheduling algorithm (merging all previous algorithms)
It is the synthesis and development of time slice rotation scheduling algorithm and priority scheduling algorithm. By dynamically adjusting the process priority size and time slice size, the multi-level feedback queue can take into account various system goals.
The implementation ideas are as follows:
- Set multiple Ready Queues and set different priorities for each queue, the first set of queues has the highest priority and decrements in turn
- Give each queue process a different time slice to run, the higher the priority, the smaller the time slice
- Take FCFS in each team. After the new process enters memory, it is first placed at the end of the first-level queue. When it is the process’s turn to execute, if it can be completed within the time slice, it will be evacuated from the system. If not, it will be transferred to the second-level queue. If it is still not completed, continue to push back until it drops to the nth-level queue, and the time slice rotation method is adopted in the nth-level queue.
- Scheduling by queue priority. Only when the first level queue is empty will the second level queue be scheduled. If the processor is executing a process in the i-th level queue and a new process enters any higher priority queue, the current process must be immediately placed at the end of the i-th level queue and the processor must be reassigned to a higher priority process.
Process switching
Process switching is implemented under the support of the kernel, so it can be said that any process runs under the support of the operating system kernel and is closely related to the kernel
Context switch
Switching the CPU to another process requires saving the current process state and restoring the state of another process. This task is called context switching. Context refers to the contents of the CPU registers and program counters at a certain moment. When context switching is performed, the memory will save the state of the old process in its PCB. The process is as follows:
Suspends a process, saves the CPU context, including program counters and other registers
- Update PCB information
- Move the PCB of the new process into the corresponding queue, such as ready, blocked in an event, etc
- Select another process to execute and update its PCB
- Jump to the location pointed by the program counter in the PCB of the new process for execution
- Reply to handler context
Consumption of context switch
Context switching is computationally intensive, i.e. it requires considerable CPU time, so context switching means a lot of CPU time for the system. Some processors provide multiple register groups, so context switching only requires a simple change in the pointer of the current register group.
Context switching and mode switching
When switching modes, the CPU may logically still be executing the same process. User processes are initially in User Mode. If they enter the nuclear state due to an interrupt or exception, they will return to the process that User Mode just aborted after execution. Switching between User Mode and Kernel Mode is called a mode switch rather than a context switch, and does not change the current process.
Context switching can only occur in kernel mode.