-
Notifications
You must be signed in to change notification settings - Fork 1
/
chapter05.html
3882 lines (2839 loc) · 113 KB
/
chapter05.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html>
<head>
<title>CPU Scheduling</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<link href="css/slides.css" rel="stylesheet" type="text/css" />
<style>
table, th, td {
border: 1px solid black;
}
</style>
</head>
<body>
<textarea id="source">
class: center, middle, title-slide
## CSCI 340 Operating Systems
<br>
## Chapter 5: CPU Scheduling
.author[
Stewart Weiss<br>
]
.license[
Copyright 2020 Stewart Weiss. Unless noted otherwise all content is released under a
[Creative Commons Attribution-ShareAlike 4.0 International License](https://creativecommons.org/licenses/by-sa/4.0/).
Background image: roof of the EPIC Museum, Dublin, by Stewart Weiss.
]
---
name: cc-notice
template: default
layout: true
.bottom-left[© Stewart Weiss. CC-BY-SA.]
---
name: tinted-slide
template: cc-notice
layout: true
class: tinted
---
name:toc
### Table of Contents
[Prologue: About Scheduling](#prologue-1)<br>
[Prologue: About CPU Schedulers](#schedulers)<br>
[Prologue: Processes and Threads](#terminology)<br>
[About This Chapter](#about-chapter)<br>
[Chapter Objectives](#objectives)<br>
[CPU Scheduling Overview](#concepts)<br>
[Model of Process Execution](#burst-cycle)<br>
[The CPU-I/O Burst Cycle](#cpu-burst-cycle)<br>
[CPU-Bound and I/O-Bound Processes](#process-mixes)<br>
[CPU Burst Lengths](#process-mix)<br>
[CPU Scheduler Queues](#cpu-scheduler-queues)<br>
[Scheduling Decision Modes](#scheduling-decision-mode)<br>
[Non-Preemptive Scheduling](#nonpreemptive-scheduling)<br>
[Preemptive Scheduling](#preemptive-scheduling)<br>
[Preemption and the Kernel](#preemptive-kernel)<br>
[Kernel Preemption Example](#preemption-example)<br>
[Preemptive Kernels](#preemptive-kernels)<br>
[Context Switching](#context-switching)<br>
[The Dispatcher](#dispatcher)<br>
[CPU Scheduling Criteria](#scheduling-objectives)<br>
[Other CPU Scheduling Criteria](#scheduling-objectives-2)<br>
---
### Table of Contents
[Optimization](#optimization)<br>
[A Model for Evaluating Scheduling Algorithms](#evaluation-model)<br>
[Gantt Charts](#gantt-chart-example)<br>
[First-Come-First-Served (FCFS) Scheduling](#fcfs-1)<br>
[FCFS Example](#fcfs-example)<br>
[FCFS Simulation](#fcfs-1)<br>
[FCFS and Order of Arrivals](#fcfs-example-2)<br>
[FCFS and Order of Arrivals](#fcfs-example-2-analysis)<br>
[FCFS and Order of Arrivals](#fcfs-example-2-analysis-2)<br>
[The Convoy Effect](#convoy-effect)<br>
[Shortest Job First (SJF) Scheduling](#sjf-intro)<br>
[Shortest Job First Example](#sjf-example)<br>
[SJF Simulation](#sjf-1)<br>
[Shortest Job First Performance](#sjf-prediction)<br>
[Implementing Shortest Job First](#sjf-implementation)<br>
[Exponential Averaging](#exponential-average)<br>
[Exponential Averaging In General](#exponential-average-2)<br>
[Shortest Remaining Time First Scheduling](#shortest-remaining-time-first)<br>
[SRTF Example](#srtf-example)<br>
[SRTF Simulation](#srtf-simulation-0)<br>
[SRTF Simulation Analysis](#srtf-simulation-9)<br>
[Round Robin (RR) Scheduling](#round-robin-intro)<br>
[Round Robin Example](#rr-example)<br>
---
### Table of Contents
[RR Simulation Analysis, Q = 3](#rr-simulation-9)<br>
[Summary Table](#rr-summary)<br>
[RR Example With Small Quantum](#rr-quantum1)<br>
[Summary Table](#rr-summary)<br>
[Round Robin: Burst Length Smaller than Quantum](#round-robin-issues)<br>
[Round Robin: Burst Length Greater than Quantum](#round-robin-issues-2)<br>
[Round Robin Observations](#rr-observation)<br>
[Round Robin's Bias](#rr-design)<br>
[The Quantum Length](#rr-quantum-length)<br>
[The Effect of Context Switches](#rr-quantum-length)<br>
[Priority Scheduling](#priority-scheduling)<br>
[Priority Scheduling and Preemption](#priority-scheduling-types)<br>
[Priority Scheduling Example](#ps-example)<br>
[Nonpreemptive Priority Scheduling Analysis](#ps-simulation-summary)<br>
[Preemptive Priority Scheduling](#ps-preemptive)<br>
[Preemptive Priority Scheduling Example](#ps-preemptive-example)<br>
[Priority Scheduling with Round Robin](#ps-rr-intro)<br>
[Priority-RR Example](#ps-rr-intro)<br>
[Multilevel Queue Scheduling](#multilevel-queues)<br>
[Process Scheduling Classes](#multilevel-queue-classes)<br>
[Process Migration](#process-migration)<br>
[Multilevel Feedback Queue (MLFQ)](#multilevel-feedback-queues-2)<br>
[MLFQ Downward Migration Example](#mlfq-example)<br>
---
### Table of Contents
[Scheduling Contention Scope](#thread-scheduling-intro)<br>
[System Contention Scope (SCS)](#system-contention-scope)<br>
[Process Contention Scope (PCS)](#process-contention-scope)<br>
[A Visual Comparison](#contention-scope-comparison)<br>
[A Pthreads Example](#pthreads-example)<br>
[Pthreads Example Code](#pthreads-contention-example)<br>
[Multiprocessor Scheduling Issues](#multiprocessor-scheduling)<br>
[Logical Versus Physical Processors](#logical-processors)<br>
[Logical Processor Examples](#logical-processor-examples)<br>
[Multiprocessors Revisited](#multiprocessor-scheduling-context)<br>
[Asymmetric Multiprocessing System Scheduling](#asymmetric-multiprocessing)<br>
[Symmetric Multiprocessor Scheduling](#symmetric-multiprocessors)<br>
[A Shared Ready Queue Solution](#shared-queue)<br>
[Per-Processor Ready Queues](#private-queues)<br>
[Per-Processor Ready Queues](#private-queue-trade-offs)<br>
[Load Balancing](#load-balancing)<br>
[Migration Issues](#migration)<br>
[How Does the Scheduler Run?](#scheduler-implementation)<br>
[Processor Affinity](#affinity)<br>
[NUMA Nodes](#numa-issues)<br>
[Hardware Multithreading: Motivation](#multithreading-motivation)<br>
[Hardware Multithreading: Introduction](#multithreading-intro)<br>
[Hardware Multithreading Visualized](#multithreading-visualized)<br>
---
### Table of Contents
[Types of Hardware Multithreading](#multithreading-types)<br>
[Hardware Multithreading and Scheduling](#hardware-multithreading-scheduling)<br>
[Linux Task Scheduling](#linux-scheduling-1)<br>
[Linux Task Scheduling](#linux-scheduling-2)<br>
[Completely Fair Scheduler: Concepts](#linux-scheduling-3)<br>
[Completely Fair Scheduler: Red Black Tree](#linux-scheduling-4)<br>
[Completely Fair Scheduler: Scheduling Classes](#linux-scheduling-5)<br>
[Real Time Scheduling](#real-time-scheduling)<br>
[References](#references)<br>
<!--TOC_END-->
---
name: prologue-1
### Prologue: About Scheduling
In Chapter 3 we introduced core concepts of scheduling and in particular
we discussed .greenbold[process scheduling] in the context of our study of processes.
--
Recall that there are three levels of process scheduling:
- .bluebold[Long-term scheduling]:
decision about which processes/jobs should be admitted into the system
- .bluebold[Medium-term scheduling]:
decision about which processes should be memory-resident
- .bluebold[Short-term scheduling]:
decision about which processes should run on a processor
--
.bluebold[CPU scheduling] refers to the short-term scheduling of processes or threads onto the
.greenbold[CPU] specifically.
---
name: schedulers
### Prologue: About CPU Schedulers
A .bluebold[CPU scheduler] is a program that performs scheduling onto the CPU.
A .bluebold[CPU scheduling algorithm] is an algorithm used by a CPU scheduler to decide which
process or thread should run on an available CPU.
--
The objective of scheduling in general, and CPU scheduling in particular,
is to .greenbold[improve performance] in one way or another. Performance objectives vary:
- .redbold[maximizing utilization] (of the CPU or memory)
- .redbold[maximizing throughput] (of processes, threads, or jobs)
- .redbold[minimizing response time] (of processes or threads)
--
These objectives are often in conflict with each other.
CPU schedulers balance these objectives depending on various criteria that
operating system designers impose on them.
---
name: terminology
### Prologue: Processes and Threads
Having to repeatedly write "processes or threads" in these notes about scheduling
is laborious and wasteful of the precious slide real estate.
Most of the time it does not matter whether the entity being scheduled is a process
or a thread.
In Linux, the problem is solved by calling processes and threads, tasks. But
deviating from standard language might throw the reader off.
Therefore, in these slides, we use the word "process" to mean either a process or a thread
that can be scheduled onto a processor.
When we talk about the particular issues involved in scheduling threads specifically,
we will use the term "thread" instead of process.
---
name: about-chapter
### About This Chapter
This chapter covers CPU scheduling.
The general topics that it covers are:
- Basic scheduling concepts
- CPU scheduling criteria
- CPU scheduling algorithms
- Thread scheduling
- Multiprocessor scheduling
- Scheduling in Linux
---
name: objectives
### Chapter Objectives
You should be able to
--
- describe various CPU scheduling algorithms and how they differ;
--
- apply CPU scheduling algorithms to systems of processes in various states of execution;
--
- assess CPU scheduling algorithms based on various scheduling criteria;
--
- explain the additional complexity in scheduling in multiprocessor and multicore computers;
--
- explain the particular issues involved in scheduling threads onto cores;
--
- describe the scheduling algorithms used in the __Linux__ operating system.
---
name: concepts
### CPU Scheduling Overview
All modern systems are .greenbold[multiprogramming systems], which, if you recall,
means that multiple processes are memory-resident.
--
In these systems, to maximize CPU utilization and keep throughput high, the operating system tries
to keep the CPU busy doing useful work all of the time.
--
When a process running on a processor issues a request to wait for an event such as I/O,
to keep that processor busy the operating system wants to replace the process
with a memory-resident process that can do useful work.
--
The .greenbold[CPU scheduler] is the operating system component that makes the decision about
which process to .redbold[schedule onto the processor].
---
name: burst-cycle
### Model of Process Execution
A process can execute two types of instructions:
- those that cause it to .greenbold[wait for services], such as system calls for I/O or other services,
which we call .bluebold[blocking] or .bluebold[wait] instructions, and
- those that complete their execution without causing the process to block,
which we call .bluebold[compute] instructions (such as .fixedblue[add],
.fixedblue[subtract], .fixedblue[load], .fixedblue[store].)
--
Therefore, the execution of a process can be modeled as a sequence of compute and wait
instructions. Let .red[W] and .green[C] denote wait and compute instructions respectively.
Then we can represent any portion of a process's execution by a string
of .red[W]'s and .green[C]'s such as the following
.green[CCCCCCC].red[W].green[CCCCCCC].red[W].green[CCC].red[W].green[CCC]
.red[W].green[CCC].red[W].green[CCCCCCCCCCCCCCCCCCCC].red[W].green[CCCCCCCCCCC]...
--
A .bluebold[CPU burst] is the period of time during which the process executes
only consecutive compute instructions up to and including the wait, such as
.green[CCCCCCCCCCCCCCCCCCCC].red[W]
The period of time immediately after a wait instruction until the process
is ready to run again is called an .bluebold[I/O burst]. It is called this because
most waits of long duration are for I/O.
---
name: cpu-burst-cycle
### The CPU-I/O Burst Cycle
The preceding discussion shows that a process goes through a sequence of
cycles of CPU bursts followed by I/O bursts until it terminates with a CPU burst.super[1].
.footnote[
1 The instruction that causes it to terminate is not a wait instruction.
]
.left-column-large[
When a process executes a blocking instruction, it is unable to do anything while waiting for the I/O to
complete.
It is a waste of CPU cycles to keep this waiting process on the CPU,
so usually it is removed from the CPU.
When it is removed from the CPU, the CPU scheduler has to decide with which process
to replace it.
]
.right-column-small[
<img src="figures/cpu-io-burst.png" width=48% alt="CPU I/O Burst">
]
--
.left-column-large[
.lightgreenbox[
Some processes spend a long time in CPU bursts and make few I/O requests. They are
called .bluebold[compute-bound] processes.
Others compute very little, and as soon as they get the processor, they issue an
I/O request; these are called .bluebold[I/O bound] processes.
]
]
---
name: process-mixes
### CPU-Bound and I/O-Bound Processes
Processes are called CPU-bound because they need the processor much more
than they need the I/O devices. They are "bound" to the CPU.
Processes are called I/O-bound because they are issuing I/O requests so
frequently that they spend more time waiting for the I/O devices to work for them
than they do on the processor. They are "bound" to the I/O system.
--
Once a CPU-bound process is given a processor, it uses it for a relatively long time
before it issues a blocking instruction.
In contrast, an I/O-bound process will very quickly issue a wait.
--
Scheduling decisions often look at a process's history of CPU burst lengths
to decide whether it is likely to stay on the processor a long time or issue a
wait quickly.
- If it has a history of just a few long CPU bursts, it is likely to have a long one again.
- If it has a history of many short bursts, it is likely to be short again.
--
Many schedulers give preference to I/O bound processes, as you will see shortly.
---
name: process-mix
### CPU Burst Lengths
Because a process that is waiting for I/O is not on the processor,
the length of its I/O burst is not a factor in how the scheduler makes any decisions.
In contrast, the lengths of CPU bursts can help guide scheduling algorithms.
---
name: cpu-scheduler-queues
### CPU Scheduler Queues
The CPU scheduler maintains one or more .redbold[queues] of processes that are ready to run.
- These queues are called .bluebold[ready queues].
- Ready queues are not necessarily .redbold[First-In-First-Out] (.redbold[FIFO])
queues, though they might be.
- They might also be .greenbold[priority queues], .greenbold[trees] or even .greenbold[unordered lists].
--
#### Queue Implementation
Queues of processes usually .redbold[do not contain copies] of process control blocks;
this would be wasteful of memory and time.
--
One alternative is that they contain pointers to the PCBs that are stored in the Process Table.
--
Another alternative is that the PCBs themselves contain various members that are
PCB pointers that can be used to link them up into various linked lists.
The __Linux__ .fixedblue[task_struct] is organized in this latter way.
---
name: scheduling-decision-mode
### Scheduling Decision Modes
The scheduler runs when it needs to select a process to run on the processor.
The .bluebold[scheduling decision mode] specifies the times at which the
selection of a process to run is made.
This decision can take place at the following times:
--
1. When the running process's state changes from .redbold[running to blocked] because it
issued an I/O request or some other .redbold[wait] instruction.
--
2. When the running process's state changes from .redbold[running to ready]
because an .redbold[interrupt] such as a timer interrupt occurred.
--
3. When a .redbold[ready queue's contents change] because either a
process moved from the blocked state to the ready state as a result of an .redbold[event completion]
or because a .redbold[new process was created] and was placed in the queue.
--
4. When the running process terminates.
--
.lightgreenbox[
If a scheduling decision is made .redbold[only under conditions 1 and 4], the
scheduling is called .bluebold[nonpreemptive scheduling].
If it is made under .redbold[any of the above conditions], it is called .bluebold[preemptive scheduling].
]
---
name: nonpreemptive-scheduling
### Non-Preemptive Scheduling
In .bluebold[nonpreemptive scheduling], once a process is given the processor, it holds it
until it .redbold[voluntarily relinquishes] it by terminating or by executing a blocking
instruction.
--
Consider the case of a process .greenbold[computing the first ten billion digits of $\pi$],
storing them in an array.
- It will not make any blocking system calls (I/O) until it completes its computation
and is ready to write out the array.
--
- In nonpreemptive scheduling, it will be allowed to hold the processor until it
is ready to write out its data. .redbold[No other process can run until this happens].
--
- This causes .redbold[poor response time] for all other processes, which are stuck in the
ready queue waiting to run.
- This results in .redbold[unpredictable response and turnaround times] for processes in general.
--
Why would an operating system use nonpreemptive scheduling?
--
   .red[Because it easier to implement than preemptive scheduling.]
---
name: preemptive-scheduling
### Preemptive Scheduling
In .bluebold[preemptive scheduling], a process can be removed from the CPU
involuntarily, meaning not as a result of any action it takes. This can happen because of a
timer interrupt, or because some other event takes place that causes the scheduler to run.
.redbold[Almost all modern operating systems use preemptive scheduling.]
--
- It makes it possible to provide .greenbold[good response time] for all processes.
- It makes it possible to provide .greenbold[fairness],
so that processes get their fair share of time on the processor.
--
But preemptive scheduling introduces other problems:
--
- Because processes can be removed from the processor whenever a timer interrupt occurs
or the ready queue updates,
the scheduler can run very frequently. As a result, it must be designed to run very quickly and
efficiently.
--
- Because processes can be interrupted in the middle of their computations,
variables that are shared among processes can become corrupted more easily
than in nonpreemptive scheduling.
--
- Because a process could get preempted while it is in kernel code, a decision has
to be made whether to allow this.
---
name: preemptive-kernel
### Preemption and the Kernel
Suppose scheduling is preemptive, and that
a process makes a system call and the kernel runs on its behalf
and gets preempted.
--
   .red[ Why is this a problem?]
--
- During the processing of the system call, the kernel may be changing the contents
of a kernel data structure, such as a linked list of open files.
--
- When it is preempted, the data structure is left in a semi-updated state.
--
- Some other process can run, make a system call, and the kernel will run again,
possibly trying to modify the incomplete update of the same data structure.
.redbold[The kernel data structure gets corrupted.]
--
- With preemptive scheduling, the kernel needs to be designed to prevent this type of
data corruption, making it more complex.
--
- Kernels can be designed to be .greenbold[preemptive] or .greenbold[nonpreemptive].
- A .bluebold[nonpreemptive kernel] does not allow the scheduler to preempt a process
in a system call until it exits kernel mode, blocks, or voluntarily
relinquishes control of the CPU. _The kernel code is simpler but less
efficient_.
- A .bluebold[preemptive kernel] allows preemption but is designed so that no
data is corrupted.
.redbold[Preemptive kernels are necessary when processes can have real deadlines.]
---
name: preemption-example
### Kernel Preemption Example
Consider this scenario:
1. Process A causes some exception (makes a system call or executes code that causes the exception.)
--
2. The kernel starts running in kernel mode and enters the exception handler
on behalf of process A.
--
3. An interrupt occurs, the interrupt handler awakens a higher priority process B
to service the interrupt, moving B from some waiting state to the ready queue.
--
.redbold[If the kernel is preemptive], then it will stop executing on A's behalf:
the exception handler running for A is stopped, a switch occurs to process B,
and when B is finished, the exception handler for A resumes.
.redbold[If the kernel is nonpreemptive], it will continue executing on behalf of A until
the exception handler finishes, or it voluntarily gives up the CPU.
---
name: preemptive-kernels
### Preemptive Kernels
A preemptive kernel must be carefully designed to prevent corruption of data.
.greenbold[It has to work even if interrupts occur in kernel code and context switches take place],
.greenbold[so that multiple processes might be executing kernel code concurrently].
--
- Interrupts happen frequently in operating systems, and can happen when the
kernel is executing.
--
- The kernel is allowed to be interrupted almost any time because the interrupt might
be important and should not be ignored by the kernel. For example,
movie players, device drivers, environmental monitors need timely service and
cannot be delayed waiting for processes running in kernel mode.
--
- The kernel needs to handle these interrupts, otherwise input might be lost or
output overwritten.
--
- Preemptive kernels use several techniques to make them .redbold[safe to reenter]:
- .redbold[disabling interrupts] at entry and re-enabling interrupts at exit
of the sections of code in interrupt handlers.
- .redbold[making such code sections in interrupt handlers very short],
so that the amount of time during which interrupts are
disabled is small.
- using .greenbold[locks and other synchronization mechanisms] to prevent data corruption.
---
name: context-switching
### Context Switching
Once the scheduler has chosen a process to run on the CPU, the CPU must be given
to that process. In Chapter 3, we explained that this requires what is called
a .bluebold[context switch] (see [Context Switch](chapter03.html#context-switch)
to review.)
--
Although each process has its own address space,
.greenbold[all processes share the CPU registers].
Therefore, to remove a process from the CPU
and resume another, the kernel must
- save the register contents of the process leaving the CPU and
- restore the registers with the contents they had when the
process to be resumed was removed from the CPU.
--
The .bluebold[dispatcher] is the kernel routine that performs the
context switch.
---
name: dispatcher
### The Dispatcher
.lightgreenbox[
The dispatcher is invoked by the CPU scheduler and does the following:
- It switches the context from the currently running process to the new one.
- It then changes the processor mode to user mode, since it runs in kernel mode.
- It loads the instruction register with the location in the new process at which
it should start or continue its execution.
]
--
The amount of time between when a process is selected to run and when it begins
running is called the .bluebold[dispatch latency].
To reduce dispatch latency, the dispatcher must be extremely fast since it is executed so frequently.
In __Linux__, the .fixedblue[vmstat ] command displays various system statistics.
The command .fixedblue[vmstat 1 3] reports the averages per second since boot, followed by the stats for the past
two one-second intervals.
The following command pipes .fixedblue[vmstat]'s output into .fixedblue[awk],
displaying just the number of context switches for the
past .greenbold[three] one-second intervals:
```bash
$ vmstat 1 4 | awk 'BEGIN { getline } {gsub("cs","Context Switches",$12); print $12}'
Context Switches
7
9175
9168
```
---
name: cpu-schedulers
layout: false
class: center, middle, inverse
## CPU Scheduling Algorithms
In this section we examine various CPU scheduling algorithms and
the criteria by which they can be evaluated.
---
template: tinted-slide
layout: true
---
name: scheduling-objectives
### CPU Scheduling Criteria
.bluebold[Scheduling criteria] are the objectives of scheduling algorithms.
They can be classified as .greenbold[system-oriented]
or .greenbold[user-oriented] or both. The most important criteria are:
--
#### System-Oriented:
- .redbold[Maximize processor utilization], the fraction of processor time spent executing user processes;
- .redbold[Maximize throughput], the number of processes completing per unit time.
<hr>
--
#### User-Oriented
- .redbold[Minimize response time], the time from the user's issuing a request until output starts to appear;
- .redbold[Minimize turnaround time], the time from the submission of a job or process until it completes;
---
name: scheduling-objectives-2
### Other CPU Scheduling Criteria
The .bluebold[service time] of a process is the total amount of time it uses on
the processor.
The total time that a process spends in the ready queue waiting for a processor is called its
.bluebold[waiting time].
One other scheduling objective is to
- .redbold[minimize waiting time].
The waiting time is directly related to the turnaround time. The turnaround time is the sum of
the waiting time and the service time of the process.
--
More useful than turnaround time is .bluebold[normalized turnaround time], which is the ratio of the
turnaround time to the process's service time. If normalized turnaround time is 1.0, the process did not
wait at all. If it is very large, it spent a long time not getting serviced.
---
name: optimization
### Optimization
It is not possible to achieve all of these objectives simultaneously.
.redbold[ It is an optimization problem.]
This means we try to approximately maximize one property and approximately minimize
another.
For each of these criteria, the question is should we optimize the
maximum, minimum, or average measure of the property.
.redbold[Examples]
- We want to minimize response time.
Should we minimize the .greenbold[maximum response time] or the .greenbold[average response time]?
- We want to minimize waiting time.
Should we minimize .greenbold[maximum waiting time] or .greenbold[average waiting time]?
--
In interactive systems, .greenbold[reliability and predictability] are important.
- .bluebold[Predictability] is the amount of variation around a mean,
so .redbold[minimizing the variance] in response times is more important than minimizing the mean,
maximum, or minimum response time.
---
name: evaluation-model
### A Model for Evaluating Scheduling Algorithms
A simple way to evaluate and compare scheduling algorithms is to
model each process as a sequence of CPU bursts of known lengths, simulate
the scheduling algorithm using these bursts, and
measure their average wait times.
From average waiting times, we can compute their response and turnaround times.
--
We can use a .greenbold[Gantt chart] to evaluate an algorithm.
- A .bluebold[Gantt chart] is a type of bar chart that visualizes a work schedule.
- It has time along the horizontal axis, and a bar for each distinct work unit, laid out
on the timeline, as depicted below. In general, work units can overlap in time.
.center[
<img src="figures/gantt-0.png" width=80% alt="Sample Gantt chart">
]
---
name: gantt-chart-example
### Gantt Charts
When we are simulating processes that all execute on the same processor,
the work units cannot overlap. Suppose that four processes are scheduled
one after the other as shown below.
.center[
<img src="figures/gantt-example-2.1a.png" width=80% alt="Sample Gantt chart">
]
The chart can be redrawn so that the processes are positioned side by side.
This saves space.
.center[
<br>
<img src="figures/gantt-example-2.2a.png" width=80% alt="Sample Gantt chart">
]
---
name: fcfs-1
### First-Come-First-Served (FCFS) Scheduling
The .bluebold[First-Come-First-Served] (.bluebold[FCFS]) scheduling algorithm
is a .redbold[nonpreemptive] algorithm. (Scheduling decisions take place only
when processes block themselves or terminate.)
--
- In First-Come-First-Served scheduling, processes arrive and are placed at the
rear of a FIFO queue at the time they arrive.
--
- When the scheduler needs to select a process to run, it always selects
the process at the front of the queue.
--
- If the running process blocks by issuing a wait instruction, it is placed at the rear
of the queue when it returns from the wait queue.
--
- If it terminates, it leaves the system.
--
To evaluate FCFS scheduling, we assume that we always know the lengths of all of a process's
CPU bursts. The service time of a process is the sum of all of its CPU bursts.
---
name: fcfs-example
### FCFS Example
To evaluate a nonpreemptive scheduling algorithm, we simulate it on a
set of processes whose arrival and service times are known.
For this example, we use the following table:
.centered_60[
| Process | Arrival Time | Service Time |
|:---:|:---:|:---:|
| P1 | 0 | 3 |
| P2 | 2 | 6 |
| P3 | 4 | 4 |
| P4 | 6 | 5 |
| P5 | 8 | 2 |
]
We use a Gantt chart and a ready queue to apply FCFS to this set of processes
in the next few slides.
---
name: fcfs-1
### FCFS Simulation
P1 arrives at time 0, is placed on processor immediately, and finishes at time 3.
P2 arrives at time 2 and is queued.
.centered_80[
| Process | Arrival Time | Service Time | Start Time | Finish Time | Waiting Time |
|:---:|:---:|:---:|:---:|:---:|:---:|
| .redbold[P1] | 0 | 3 | .redbold[0] | .redbold[3] | .redbold[0] |
| P2 | 2 | 6 | | | |
| P3 | 4 | 4 | | | |
| P4 | 6 | 5 | | | |
| P5 | 8 | 2 | | | |
]
The Gantt chart at time 3:
.center[
<img src="figures/fcfs-1.0.png" width=80% alt="Gantt chart">
]
---
name: fcfs-2
count: false
### FCFS Simulation
P2 is placed on processor at time 3 and finishes at time 9.
P3, P4, and P5 arrive while P2 runs and are queued.
.centered_80[
| Process | Arrival Time | Service Time | Start Time | Finish Time | Waiting Time |
|:---:|:---:|:---:|:---:|:---:|:---:|
| P1 | 0 | 3 | 0 | 3 | 0 |
| .redbold[P2] | 2 | 6 | .redbold[3] | .redbold[9] | .redbold[1] |
| P3 | 4 | 4 | | | |
| P4 | 6 | 5 | | | |
| P5 | 8 | 2 | | | |
]
The Gantt chart at time 9:
.center[
<img src="figures/fcfs-1.1.png" width=80% alt="Gantt chart">
]
---
name: fcfs-3
count: false
### FCFS Simulation
P3 is placed on processor at time 9 and finishes at time 13.
P4 and P5 continue to wait in the ready queue.
.centered_80[