编程知识 cdmana.com

Operating system concept learning notes 10 CPU scheduling

Operating system concept learning notes 10

CPU Dispatch


The basis of multiprogramming operating system . By switching between processes CPU, The operating system can improve the throughput of the computer .

For a single processor system , Only one process is allowed to run at a time : Any other process must wait , until CPU Until idle can be scheduled .

The goal of multiprogramming is to have certain processes running at any time , In order to make CPU Maximize usage of . The idea of multiprogramming is simpler , When a process has to wait , The operating system will take away from the process CPU Right to use , And will be CPU Leave it to other processes .

CPU-I/O Interval period

CPU The successful scheduling of depends on the following properties of the process :

Process execution by CPU Execution cycle and I/O Waiting period form . The process switches between these two states (CPU burst—I/O bust).

Process execution from CPU Section (CPU burst) Start , After that is I/O Section (I/O burst). And then there's another one CPU Section , And then there's another one I/O Section , Go on like this , Final , final CPU The execution of an interval is terminated by a system request .

After a lot of CPU A test of the length of an interval . Found to have a large number of short CPU Intervals and a few long CPU Section .I/O Constraint programs usually have a lot of short CPU Section .CPU Constraint programs may have a small amount of length CPU Section . This distribution helps to choose the right CPU Scheduling algorithm .

CPU Program scheduling

whenever CPU Idle , The operating system must select a process from the ready queue to execute . Process selection is made by Short term scheduler (short-term scheduler) or CPU The scheduler perform . The scheduler selects a process from memory that can be executed , And distribute it CPU.

Ready queues don't have to be FIFO (FIFO) queue , It can also be a priority queue 、 Trees or simple unordered lists . However, all processes in the queue must be queued to wait in the queue CPU Up operation . The records in the queue are usually process control blocks (PCB).

Preemptive scheduling :

CPU Scheduling decisions can be made in the following 4 Under the circumstances of :

(1) When a process switches from running to waiting ( Such as :I/O request , Or call wait Waiting for a child process to terminate )

(2) When a process switches from running state to ready state ( Such as : There was an interruption )

(3) When a process switches from a waiting state to a ready state ( Such as :I/O complete )

(4) When a process terminates

For the first 1 and 4 Two cases , There is no choice but scheduling . A new process ( If a process already exists in the ready queue ) Must be chosen to execute . For the first 2 And the 3 Two cases , You can choose .

When scheduling can only take place at 1 and 4 In both cases , It's called scheduling Non preemptive (nonpreemptive) or collaborative (cooperative); otherwise , The scheduling scheme is called Snatched (preemptive). Using non preemptive scheduling , once CPU Assign to a process , Then the process will always use CPU Until the process terminates or switches to a waiting state .

There is a price for preemptive scheduling to share data ( If it's locked ) Of , New mechanisms are needed to coordinate access to shared data .

Preemption also affects the design of the operating system kernel . When processing system calls , The kernel process may be busy . These activities may involve changing important kernel data ( Such as I/O queue ).  

Because by definition, interrupts can happen at any time , And it can't always be ignored by the kernel , So the code segment affected by the interrupt must be protected to avoid simultaneous access to . The operating system needs to be able to receive interrupts at any time , Otherwise the input will be lost or the output will be rewritten . In order that these code segments are not accessed by multiple processes at the same time , Stop interruptions when entering , And when you exit, you have to allow interrupts again .

Dispatchers

Dispatchers (dispatch) It's a module , Used to put CPU Control is given to the process selected by the short-term scheduler .

Its functions include :

  • Switch context
  • Switch to user mode
  • Jump to the right place for the user , To restart the program .

The time taken by the dispatcher to stop one process and start another is called dispatch delay (dispatch latency).

Scheduling criteria

For comparison CPU The criteria proposed by the scheduling algorithm :

  • CPU Usage rate : Need to make CPU Be as busy as possible
  • throughput : The number of processes completed in a unit of time
  • Turnaround time : The time period from process submission to process completion is called turnaround time , Turnaround time is the sum of all time periods , Including waiting to enter memory 、 Wait in the ready queue 、 stay CPU On execution and I/O perform
  • Waiting time : The sum of the time spent waiting in the ready queue
  • response time : The time from submitting the request to generating the first response

Need to make CPU Maximize usage and throughput , And make turnaround time 、 Minimize waiting time and response time . In most cases, the average needs to be optimized , Sometimes it is necessary to optimize the maximum or minimum value , Not the average .

Scheduling algorithm

First come, first served scheduling

The simplest CPU The scheduling algorithm is First come, first served algorithm (First-Come,First-Served scheduling): Ask first CPU The process is assigned to CPU.FCFS Strategies can be used FIFO Queue is easy to implement . When a process enters the ready queue , Its PCB Link to the end of the queue . When CPU Idle ,CPU Assigned to processes at the head of the queue , Then the running process is removed from the queue .

FCFS The code for the strategy is simple and easy to understand , But with FCFS The average waiting time for a policy is usually longer . When a process CPU Interval time varies greatly , The average waiting time varies greatly .

For example, the following example

process

Interval time

P1

24

P2

3

P3

3

If according to P1 P2 P3 Arrive in order ,Gantt The graph is as follows :

Average waiting time :(0+24+27)/3 = 17

If the P2 P3 P1 Arrive in order ,

Average waiting time :(0+3+6)/3 = 3

In addition, consider the performance in the dynamic situation , Let's say I have a CPU Constraining processes and a lot of I/O Constrain the process ,CPU The constraint process moves back to the ready queue and is assigned to CPU. Again, all of I/O The process will wait in the ready queue CPU The completion of the process . Since all other processes are waiting for a large process to release CPU, This is called an escort effect (convoy effect). Compared to having a shorter process execute first , And that leads to CPU And the equipment utilization rate has become very low .

FCFS The scheduling algorithm is not preemptive . For time sharing systems ( Each user needs to wait for a certain amount of time CPU Time ) It's particularly troublesome . Allow a process to hold CPU Too much time is a serious mistake .

Shortest job first scheduling (shortest-job-first scheduling,SJF)

Link each process to the next CPU Intervals are related to each other . When CPU For free time , It will be assigned to have the shortest CPU The process of the interval . If two processes have the same length , Then you can use FCFS Dispatch to handle . Be careful , A more appropriate expression is the shortest next CPU Interval algorithm , This is because the next one in the scheduling check process CPU The length of the interval , Instead of the total length .

For example, the following example

process

Interval time

P1

6

P2

8

P3

7

P4

3

SJF: (0+3 + 9 + 16)/4 = 7

FCFS: (0+6+14+21)/4 = 10.25

SJF The average waiting time of the algorithm is the smallest .SJF The real difficulty of the algorithm is how to know the next CPU The length of the interval . For the long run of batch systems ( Homework ) Dispatch , You can take the process time limit set by the user to submit the job as the length .SJF Scheduling is often used for long-term scheduling .

It can't be in the short term CPU It is implemented at the scheduling level . We can predict the next CPU Section . Think of the next CPU The length of the interval is similar to the previous one . So by calculating the next CPU An approximation of the length of the interval , Can choose to have the shortest prediction CPU Interval to run . next CPU Intervals are usually predictable as before CPU Cut it, measure the length Exponential average (exponential average).

SJF The algorithm may be preemptive or non preemptive . preemption SJF The algorithm can preempt the current running process , It's not preemptive SJF The algorithm allows the current process to complete its first CPU Section . preemption SJF Sometimes called scheduling The shortest remaining time is first scheduled (shortest-remaining-time-first scheduling).

For example, the following example

process

Arrival time

Interval time

P1

0

P2

1

P3

2

P4

3

according to Gantt chart :

Average waiting time :

(0+0+(5-3)+(10-1)+(17-2))/4 = 26/4 = 6.5

non-preemptive SJF:

(0+(8-1)+(12-3)+(17-2))/4 = 7.75

Priority scheduling (priority scheduling algorithm)

SJF The algorithm can be used as a special case of general priority scheduling algorithm . Each process has a priority associated with it , The process with the highest priority is assigned to CPU. Processes with the same priority press FCFS Sequential scheduling .SJF, Its priority (p) For the next CPU The reciprocal of the interval .CPU The larger the range , The lower the priority , vice versa .

Priority is usually a fixed interval of numbers , Such as 0~7, But the number size and the priority level are not conclusive .

For the following example , Suppose the smaller the number, the higher the priority

process

Interval time

priority

P1

10

P2

1

P3

2

P4

1

P5

5

The average waiting time is :

(0+1+6+16+18)/5 = 8.2

Priorities can be defined internally or externally . Internally defined priorities use some measurement data to calculate process priorities . External priorities are defined by criteria outside the operating system , Such as the importance of the process .

Priority scheduling can be preemptive or non preemptive .

An important problem of priority scheduling algorithm is Infinite blocking (indefinite blocking) or hunger (starvation). It works but lacks CPU A process that can be considered blocked , It's waiting for CPU. The priority scheduling algorithm will make a low priority infinite wait CPU.

One of the priorities of the process is to wait Ageing (aging). Aging is a technology , To gradually increase the priority of processes waiting in the system for a long time .

Rotation scheduling (round-robin,RR)

Designed specifically for time sharing systems . It is similar to FCFS Dispatch , But added preemption to switch processes . Define a smaller unit of time , be called Time slice (time quantum,or time slice). Use the ready queue as a circular queue .CPU Scheduler loop ready queue , Assign no more than one time segment to each process CPU.

The new process is added to the end of the ready queue .CPU The scheduler selects the first process from the ready queue , Set timer to interrupt after a time slice , Redistribute the process . Then there are two possible scenarios . The process may only need to be smaller than the time slice CPU Section . In this case , The process itself releases itself CPU. The scheduler then processes the next process in the ready queue . otherwise , If the current running process CPU The interval is longer than the time slice , The timer interrupts to generate an operating system interrupt , Then the context switches , Add the process to the end of the ready queue , next CPU The scheduler selects the next process in the ready queue .

RR The average waiting time for a policy is usually longer

For example, the following example , Use 4ms Time slice

process

Interval time

P1

24

P2

3

P3

3

Draw Gantt chart :

Average waiting time :

(0+4+7+(10-4))/3 = 5.66

If you're ready , So every process gets 1/n Of CPU Time , Its length does not exceed q Time unit . Every process has to wait CPU It won't take more than (n-1)q Time units , Until its next time slice .

RR The performance of the algorithm largely depends on the size of the time slice . In extreme cases , If the time slice is very large , that RR Algorithm and FCFS Algorithm is the same . If the time slice is small , that RR The algorithm is called Processor sharing ,n Each process has its own processor for the user , Speed is true processor speed 1/n.

Small time slices increase the number of context switches , therefore , I hope the time slice is longer than the context switch time , in fact , Most modern operating systems , Context switching takes only a small part of the time slice .

Turnaround time also depends on the size of the time slice .

Multi level queue scheduling (Multilevel Queue Scheduling)

The front desk ( Interaction ) Process and background ( The batch ) process . These two different types of processes have different response time requirements , There are also different scheduling needs . Compared to the background process , The foreground process should be higher ( Or external definition ) The priority of the .

Multilevel queue scheduling algorithm Divide the ready queue into separate queues . According to the properties of the process , Such as memory size and so on , A process is permanently assigned to a queue ( Low scheduling overhead but not flexible ), Each queue has its own scheduling algorithm . The foreground queue may use RR Algorithm for scheduling , Background scheduling may be used FCFS Algorithm for scheduling .

in addition , There must be scheduling between queues , Usually, fixed priority preemption scheduling is used , For example, the foreground queue can have an absolute priority over the background queue . Another possibility is to divide time slices between queues, such as , The foreground queue can have 80% Time spent between processes RR Dispatch , And the background queue can have 20% Of CPU Time Adoption FCFS Algorithm scheduling process .

Multi level feedback queue scheduling (Multilevel Feedback-Queue Scheduling)

Contrary to multi-level queue scheduling , Multi level feedback queue scheduling Allow processes to move between queues . The main idea is based on different CPU The characteristics of an interval to distinguish between processes . If the process uses too much CPU Time , Then it may be moved to a lower priority queue . This program will I/O Constraints and interaction processes remain in higher priority queues . Besides , Processes that wait too long in a lower priority queue are moved to a higher priority queue . This form of aging tissue starvation occurs .

Usually , The multistage feedback queue scheduler can be defined by the following parameters :

  • Number of queues .
  • Scheduling algorithm for each queue .
  • The method used to determine when to upgrade to a higher priority queue .
  • The method used to determine when to demote to a lower priority queue .
  • A method used to determine which queue a process should enter when it needs a service .

Multiprocessor scheduling (Multiple-Processor Scheduling)

If more than one CPU, be Load distribution (load sharing) Make it possible . The main discussion is the same function of processor ( Or isomorphism ) The system of , Any processor can be used to run any process in the queue .

Multiprocessor scheduling method

In a multiprocessor ,CPU One way to schedule is to have a processor ( master server ) Handle all scheduling decisions 、I/O Processing and other system activities , Other processors only execute user code . such Asymmetric processing (asymmetric multiprocessing) It's easier , Because only one processor has access to the system data structure , Reduces the need for data sharing .

Another way is to use Symmetric multiprocessing (symmetric multiprocessing,SMP) Method , That is, each processor schedules itself . All processes may be in a common ready queue , Or each processor has its own private ready queue . in any case , Scheduling checks the common ready queue by each processor and selects a process to execute . If multiple processors attempt to access and update a common data structure , So every processor has to be programmed : You have to make sure that both processors cannot choose the same process , And the process is not lost from the queue .

Processor affinity

When a process moves to another processor , The contents of the cache of the first processor to be migrated must be invalid , The cache on the second processor to be migrated needs to be rebuilt . Due to the high cost of invalidation or refactoring , thus SMP Trying to make a process run on the same processor , This is called processor affinity , That is, a process needs to have an affinity to other processors running on .

Several forms of processor affinity :

  • soft affinity (soft affinity, The operating system has a policy of trying to keep a process running on the same processor , But there's no guarantee )
  • Hard affinity (hard affinity, Allows the process to specify that it is not allowed to move to other processors ), Such as LINUX

Load balancing (load balancing)

Load balancing tries to distribute the workload equally to SMP On all processors in the system . It's usually only necessary for processors that have their own private executable processes , In systems with a common queue , There is usually no need for load balancing , Because once the processor is idle , An executable process is immediately removed from the ready queue .

The two methods :push migration and pull migration, about push migration, A specific task periodically checks the load on each processor , If you find an imbalance , By moving processes from overloaded processors to ( Or push it to ) Idle or not too busy processors , So that the load is evenly distributed , When idle processors push from a busy processor pull A waiting task , happen pull migration.push migration and pull migration We can't repel each other .

Load balancing offsets processor affinity .

Symmetric multithreading

Provide multiple logic ( Not physical ) To run a few threads , It's called symmetry Multithreading (SMT), or hyper-threading (hyperthreading) technology .

SMT The idea is to generate multiple logical processors on the same physical processor , Even if the system only has a single processor , Each logical processor has its own architecture state , Includes general purpose and machine status registers . Each logical processor is responsible for its own interrupt handling , This means that the interrupt is sent to and processed by the logical processor , Each logical processor shares the resources of its physical processor , Such as cache or bus .

SMT It's hardware, not software . The hardware should provide a representation of the architecture state of each logical processor and interrupt handling methods . The scheduler first tries to schedule different threads to each physical processor , Instead of scheduling to different logical processors on the same physical processor .

Thread scheduling

The system schedules kernel threads , Not the process . User threads are managed by the thread library , The kernel doesn't understand them . User threads must eventually be mapped to the corresponding kernel level threads , Although this mapping may be indirect , It's possible to use lightweight processes (LWP).

Scope of competition

One of the differences between user threads and kernel threads is how they are scheduled . The first mock exam is to implement the many to one model and many to many model system , The thread library schedules user level threads to a valid LWP Up operation , This is known as Process competition scope (process-contention scope,PCS) Method , because CPU Competition occurs between threads belonging to the same process . To decide which kernel thread to schedule to CPU, The kernel uses The scope of system competition (system-contention scope,SCS) Method to do , competition CPU It happens in all threads of the system , A system that uses a one-to-one model , Scheduling uses only SCS Method .

PCS It's done according to priority .

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

版权声明
本文为[The struggling rabbit of florist]所创,转载请带上原文链接,感谢

Scroll to Top