-
Notifications
You must be signed in to change notification settings - Fork 1
/
chapter03.html
2451 lines (1757 loc) · 75.4 KB
/
chapter03.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>Processes</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<link href="css/slides.css" rel="stylesheet" type="text/css" />
</head>
<body>
<textarea id="source">
class: center, middle, title-slide
## CSCI 340 Operating Systems
<br>
## Chapter 3: Processes
.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
[About This Chapter](#summary)<br>
[Chapter Objectives](#objectives)<br>
[Background](#process-background)<br>
[The Process Abstraction](#process-abstraction)<br>
[Processes, Concretely](#process-concretely)<br>
[The Memory Image](#mem-image)<br>
[From File to Process](#process-creation)<br>
[Mapping the File to Memory](#elf-to-mem)<br>
[Process Context](#process-context)<br>
[Process Execution State](#process-context-2)<br>
[Process State Transitions](#state-transitions)<br>
[The Process Control Block](#pcb)<br>
[The Contents of a PCB](#pcb-contents)<br>
[The Linux .fixed[task_struct]](#pcb-linux)<br>
[What is Scheduling?](#scheduling-overview)<br>
[Process Scheduling](#scheduling)<br>
[Types of Process Scheduling](#scheduling-2)<br>
[Medium-Term Scheduling](#medium-term-scheduler)<br>
[The Swapper](#medium-term-scheduler-2)<br>
[The Short-Term, or CPU, Scheduler](#process-scheduler-1)<br>
[Queuing of Processes](#process-queues)<br>
---
### Table of Contents
[Context Switch](#context-switch)<br>
[Exceptions and Interrupts Revisited](#exceptions-revisited)<br>
[Interrupts, System Calls, and Context Switches](#mode-changes)<br>
[Process Creation Terminology](#process-creation-1)<br>
[Viewing the Process Tree](#process-tree)<br>
[Process Creation](#process-creation-2)<br>
[The Magic of .fixedblue[fork()]](#fork)<br>
[The .fixedblue[fork] System Call](#fork-2)<br>
[A .fixedblue[fork()] Example](#fork-demo)<br>
[Overhead of .fixedblue[fork()]](#fork-overhead)<br>
[The UNIX .fixedblue[execve] System Call](#exec-calls)<br>
[Process Termination](#process-termination)<br>
[The .fixedblue[wait()] System Call](#wait-call)<br>
[Process Termination Issues](#process-termination-2)<br>
[How a Shell Works](#shell-example)<br>
[Concurrency](#concurrency)<br>
[Cooperating Processes](#cooperating-procs)<br>
[Reasons for Processes to Cooperate](#cooperating-procs-2)<br>
[Example: The Chrome Browser](#browser-example)<br>
[Interprocess Communication Methods](#ipc-types)<br>
[The Shared Memory Model](#shared-mem-model)<br>
[Shared Memory Support in Linux](#shared-mem-support)<br>
[The Message-Passing Model](#message-passing-1)<br>
---
### Table of Contents
[Message Passing Implementation](#message-passing-2)<br>
[IPC Models Visualized](#ipc-types-2)<br>
[Issues In Message Passing](#message-passing-issues)<br>
[Direct Communication](#direct-communication)<br>
[Indirect Communication](#indirect-communication)<br>
[Synchronous Operations](#message-passing-synch)<br>
[Asynchronous Operations](#message-passing-asynch)<br>
[Buffering in Message-Passing](#buffering)<br>
[Pipes](#pipes-1)<br>
[Pipes Named and Unnamed](#pipes-2)<br>
[Unnamed Pipes](#unnamed-pipes)<br>
[Using Unnamed Pipes](#unamed-pipes-2)<br>
[Drawbacks of Unnamed Pipes](#unnamed-pipes-3)<br>
[Named Pipes](#named-pipes)<br>
[Creating and Using Named Pipes](#name-pipes-2)<br>
[Producer Consumer Problem](#producer-consumer-problem)<br>
[Producer Consumer Examples](#prod-cons-2)<br>
[Producer Consumer Problem: Shared Memory](#shared-mem-prod-consumer)<br>
[Shared Memory Producer Code](#shared-mem-producer-1)<br>
[Shared Memory Consumer Code](#shared-mem-consumer-1)<br>
[Correctness of Shared Memory Solution](#shared-mem-prod-consumer-2)<br>
[Producer Consumer Problem: Message-Passing](#message-passing-prod-cons)<br>
[Message-Passing Producer Code](#message-passing-producer-1)<br>
---
### Table of Contents
[Conclusion](#conclusion)<br>
[References](#references)<br>
<!--TOC_END-->
---
name: summary
### About This Chapter
In Chapter 1, one of the first statements made about operating systems was
that,
> "_the operating system alone must enable and control the execution of
> all other software on the computer._"
--
It was also pointed out that among the most common and important
services provided by operating systems are
* _loading and executing programs, providing synchronization, and
inter-process communication._
--
Central to these ideas is the concept of a running program, otherwise known
as a .bluebold[process].
.redbold[The most fundamental part of the study of operating systems is the study of processes].
Studying processes is the purpose of this chapter, which covers the following topics:
- Process concept and representation
- Process scheduling
- Operations on processes
- Inter-process communication (IPC)
- IPC in shared-memory computer systems
- IPC in message-passing computer systems
- Examples of specific IPC systems
---
name: objectives
### Chapter Objectives
You should be able to
- identify the individual components of a process and explain how they are
represented in an operating system.
- describe the disk representation of a process and the typical memory image of a
process.
- explain the various ways in which processes are scheduled in an operating system.
- describe how processes are created and terminated in an operating system,
including all parts of the system call API related to process creation and
termination.
- identify and describe various methods of inter-process communication.
- contrast inter-process communication using shared memory and message passing.
- explain simple shared memory IPC programs and message-passing programs.
---
name: process-concept
layout: false
class: center, middle, inverse
## The Process Concept
We explore the process as an abstraction and as a concrete entity in a
computer system.
---
template: tinted-slide
layout: true
---
name: process-background
### Background
For simplicity, assume a computer has a single CPU.
This computer can do many things ".greenbold[at the same time]." It can be running many user programs,
printing, reading from a disk, and writing to a network connection, all simultaneously.
--
But there is just a single CPU, which can only execute one program at any instant of
time. The illusion of several things happening at once occurs because the
.redbold[CPU is switched between tasks so frequently that it seems as if they all happen at once].
The switching is "under human radar", so to speak.
--
Operating system designers invented the concept of a .greenbold[process] so that they could
reason about this activity and understand how to control it and ensure that
everything was running correctly.
--
In this so-called .bluebold[process model], everything running in the computer is part of
a distinct sequential process. We are about to make this precise.
---
name: process-abstraction
### The Process Abstraction
Simply put, .redbold[a process is a program in execution.]
This is true whether it is a user program or a system program.
--
A process is the .greenbold[unit of execution] managed by the kernel.super[1].
.footnote[
1. In a batch system, the unit of execution is called a .bluebold[job].
In Linux, the unit of execution is called a .bluebold[task].
]
--
This means that the kernel manages individual processes,
performing all operations on them such as running them, giving them resources they need,
deciding when they should be terminated, and so on.
---
name: process-concretely
### Processes, Concretely
Processes exist as concrete things - they use memory and other resources.
The first question is, .redbold[what things that make up a process use memory?]
--
- the program code, also called the .bluebold[text segment]
--
- the .bluebold[stack contents]: function parameters, return addresses, and local variables
--
- the .bluebold[data segment], which contains global variables and constants
--
- the .bluebold[heap], which contains the memory dynamically allocated at run-time
by this process
--
- other resources such as structures representing open files and devices, command-line arguments,
environment values, and much more.
--
The memory associated with a process is called its .bluebold[memory image].
---
name: mem-image
### The Memory Image
A simplified diagram of a process's memory image, based on __ELF__, is shown here.
.left-column-larger[
{{content}}
]
.right-column-smaller[
<img src="figures/memlayout_simple.png" width=110% alt="memory layout">
]
---
name: memory-image-1
template: mem-image
- The text segment is at the bottom of the address space.
- There are two data segments: initialized data, such as global
constants, and uninitialized data, such as uninitialized global variables, called the <span class=fixedblue>bss</span>.
- Command line arguments and environment strings are in the highest part
of user addressable memory; the stack begins directly below them,
growing downward, towards the <span class=fixedblue>bss</span>.
- The heap is the free space below the stack and above the <span class=fixedblue>bss</span>. This is where
dynamically-allocated variables are stored.
---
name: memory-image-1
template: mem-image
<span class=redbold>Exercise</span>:
Indicate where each variable in the program below is located in the memory image.
```C
#include <stdio.h>
int numargs;
const int MAX = 10;
int main( int argc, char* argv[], char** envp)
{
int * stuff;
int i;
numargs = argc;
stuff = (int *) malloc(sizeof(int)*MAX);
for ( i = 0; i < MAX; i++ )
stuff[i] = i*i;
return numargs;
}
```
<!-- -->
---
template: tinted-slide
layout: true
---
name: process-creation
### From File to Process
.redbold[An executable program residing on a disk is not a process]; when it is run,
a process is created to run it. It is like the DNA for a process - it contains
some of the information needed to create a process, which is like a living thing.
- A single program can be run multiple times by the same or different users.
Each run results in the creation of a different process.
A good example is .fixedblue[bash] in Linux. On a busy computer,
dozens of users might be running .fixedblue[bash] simultaneously. Each user's run of it
is performed by a unique process.
- Try this out: login to a multi-user system running Linux.super[1], and type
```bash
ps -ef | grep bash
```
You will see how many processes are running .fixedblue[bash].
.footnote[
1 On the Hunter system, remotely login to .fixedblue[eniac] using .fixedblue[ssh] to try this.
]
--
How is the information to create a process stored in an executable file?
--
- The format of the executable program file depends on the operating system
(see [Chapter 2, Portability](chapter02.html#portability));
in __POSIX__ systems such as Linux, it is .greenbold[ELF].
---
name: elf-to-mem
### Mapping the File to Memory
The executable file on disk is used by the kernel to create a process.
It is not loaded into memory in a single continuous piece; it contains
tables that allow the kernel to assemble various sections into a memory image.
.left-column-small[
The kernel also allocates more memory directly above the user addressable part,
for the kernel's use.
This includes a kernel stack, and other data structures that the kernel uses
to manage the process.
]
.right-column-large[
<img src="figures/memlayout.png" width=70% alt="memory layout">
]
---
name: process-context
### Process Context
The memory image of a process is not by itself a complete characterization of
the process.
The .bluebold[process context] is the set of all information required to
completely represent a process. It contains much more than the memory image.
--
- For one, a process has CPU resources
such as the current .bluebold[processor state], which includes the .greenbold[program counter],
registers, including the stack pointer, and so on.
The complete set of data that is stored in the CPU registers is called the
.bluebold[hardware context] of the process.
--
- It has many different identifiers such as its own unique identifier, its parent's
id, and so on.
--
- A process can have resources such as .greenbold[open files], virtual .greenbold[terminal devices],
and .greenbold[open directories].
--
- It has many different kinds of .greenbold[process attributes] such as
.greenbold[priority levels] associated with it, as well as information
about how it handles various .greenbold[signals].
---
name: process-context-2
### Process Execution State
One of the most important attributes of a process is its .bluebold[execution state].
During its lifetime, the execution state of a process changes as
various events and actions take place. At any instant of time, the process can be in
exactly one of several possible different states of execution:
--
- .redbold[new]: It is newly created but not completely loaded into memory and ready to run.
- .redbold[ready]: It is ready to run. It just needs to be given the CPU to run.
- .redbold[running]: It has acquired the CPU and is running.
- .redbold[waiting]: It has made a request for service and is waiting for some
event to occur and is therefore not able to use the processor.
- .redbold[terminated]: It has finished execution.
--
.redbold[What actions and events cause it to change from one state to another?]
---
name: state-transitions
### Process State Transitions
---
name: transitions-all
template: state-transitions
.center[
<img src="figures/state-transitions.png" width=80% alt="process state transitions">
]
The complete set of transitions (ignoring .greenbold[process suspension]) is
depicted in the above .bluebold[state transition diagram]. The arrows from one
state to another are labeled by the events or actions that cause the process
to transition from the source state to the target state.
The next few slides explain these transitions.
---
name: transition-1
template: state-transitions
.center[
<img src="figures/state-transitions-new.png" width=80% alt="process state transitions">
]
A process starts out in the .redbold[new] state.
---
name: transition-2
template: state-transitions
.center[
<img src="figures/state-transitions-admit.png" width=80% alt="process state transitions">
]
When it is loaded into memory, or .bluebold[admitted] into the system, it enters
the .redbold[ready] state.
---
name: transition-3
template: state-transitions
.center[
<img src="figures/state-transitions-dispatch.png" width=80% alt="process state transitions">
]
When it is scheduled to run, or
.bluebold[dispatched], it transitions to the .redbold[running] state.
---
name: transition-4
template: state-transitions
.center[
<img src="figures/state-transitions-io-wait.png" width=80% alt="process state transitions">
]
When it makes a request to the kernel that cannot be satisfied immediately, such as
for I/O, it is removed from the processor and
transitions to the .redbold[waiting] state.
---
name: transition-5
template: state-transitions
.center[
<img src="figures/state-transitions-io-complete.png" width=80% alt="process state transitions">
]
When the event for which it is waiting completes, it is no longer
in the waiting state and transitions back to the .redbold[ready] state.
---
name: transition-6
template: state-transitions
.center[
<img src="figures/state-transitions-dispatch.png" width=80% alt="process state transitions">
]
It will then be scheduled to run again, i.e., it is
.bluebold[dispatched], and transitions again to the .redbold[running] state.
---
name: transition-7
template: state-transitions
.center[
<img src="figures/state-transitions-preempt.png" width=80% alt="process state transitions">
]
Sometimes a process might be removed from the processor, usually because
an interrupt from a timer or some other event takes place and the kernel must
handle that event. In this case we say it is
.bluebold[preempted], and transitions back to the .redbold[ready] state.
---
name: transition-8
template: state-transitions
.center[
<img src="figures/state-transitions-dispatch.png" width=80% alt="process state transitions">
]
Eventually it will then be scheduled to run again, i.e., it is
.bluebold[dispatched], and transitions again to the .redbold[running] state.
---
name: transition-9
template: state-transitions
.center[
<img src="figures/state-transitions-exit.png" width=80% alt="process state transitions">
]
This time it finishes execution and
.bluebold[exits], transitioning to the .redbold[terminated] state.
---
template: tinted-slide
layout: true
---
name: pcb
### The Process Control Block
The preceding discussion about the states of a process shows that processes
can be running and then not running and then running again.
--
This implies that when the kernel needs to remove a process from a processor,
.redbold[it has to be able to restore the process in the exact state it was in when it was removed.]
--
This implies in turn that the kernel needs a .greenbold[data structure] into which it can save
the context of a running process and from which it can restore that context when
the process runs again.
--
This data structure must contain enough information about a process so that
the kernel can thoroughly manage the process.
This includes things such as how much CPU time it has used so far, or how often
it needed I/O. It uses this type of information to make various decisions about
scheduling the process and allocating resources to it.
--
This data structure is usually called a .bluebold[Process Control Block], or .bluebold[PCB]
for short. The kernel maintains a PCB for every process that has been created and not yet
destroyed.
--
.redbold[To manage every process, the kernel needs a unique way to identify each of them.]
Most operating systems associate a unique positive integer to each process, which is
called its .bluebold[process id]. This process id is an important piece of data.
---
name: pcb-contents
### The Contents of a PCB
The information contained in a process control block includes (but is not limited to)
the following:
- .red[process execution state]: running, ready, waiting, and so on.
- .red[process identifiers]: process id and "related process identifiers"
- .red[hardware context]: this consists of
- .red[program counter]: location of next instruction to execute
- .red[CPU registers]: contents of all other registers used by the process
- .red[CPU scheduling information]: execution priorities, scheduling queue pointers
- .red[memory management information]: maps of all memory allocated to the process
- .red[accounting information]: CPU usage, clock time elapsed since start, time limits
- .red[I/O status information]: resources and I/O devices held by process,
list of open files
- .red[related process lists]: pointers to list of children, siblings, parent
--
The contents depend on the operating system, but in all cases, there is usually
much more than this in an actual implementation.
---
name: pcb-linux
### The Linux .fixed[task_struct]
In Linux, processes are called .bluebold[tasks], the PCB is called a
.bluebold[process descriptor] and it is
represented by a .fixedblue[C] struct called the .fixedblue[task_struct].
The .fixedblue[task_struct] is a very large structure, with over one hundred
members. Linux maintains a linked list of them.
To give you an idea of how the various items of information are represented, below
is a tiny out-of-order slice of the Linux .fixedblue[task_struct].
```C
struct task_struct {
...
volatile long state; /* process state */
pid_t pid; /* process id */
pid_t `tgid`; /* `thread group id` */
struct list_head children; /* list of children */
struct list_head sibling; /* next sibling pointer */
struct mm_struct *mm; /* memory management info */
struct fs_struct *fs; /* filesystem information: */
struct files_struct *files; /* open file information: */
...
};
```
--
You may wonder what a .redbold[thread group id] is. In the next chapter, you will learn
about .greenbold[threads].
They play an important role in modern programming and in operating systems.
---
name: task_struct-activity
count: false
class: breakout
### A .fixedblue[task_struct] Activity
- The actual Linux .fixedblue[task_struct] source code is available on our server.
- Login to .fixedblue[eniac.cs.hunter.cuny.edu] and then login to
any of the .fixedblue[cslab] hosts using .fixedblue[ssh].
- Navigate to the directory
.fixedblue[/data/biocs/b/student.accounts/cs340_sw/resources].
- Open the file .fixedblue[sched.h] using any editor such as .fixedblue[pico],
.fixedblue[nano], .fixedblue[emacs], or .fixedblue[vim].
- Search for the beginning of the structure (.fixedblue[struct task_struct]) and then
try to find all members of this structure that are linked lists.
Name at least five of them and describe what they contain.
---
name: scheduling-overview
### What is Scheduling?
In computer science in general, .bluebold[scheduling] refers to the act of
assigning resources to units of work that must be completed.
In the context of operating systems, the "work" units are usually either
.greenbold[threads].super[1], .greenbold[processes], or .greenbold[jobs], and the
resources can be .greenbold[disk storage], .greenbold[memory], or
a .greenbold[processing unit] such as a CPU or core.
.footnote[
1 Threads are covered in Chapter 4.
]
In this chapter we discuss .greenbold[process scheduling].
---
name: scheduling
### Process Scheduling
Recall from [Chapter 1](chapter01.html#multiprogramming-1) that the
purpose of multiprogramming is to ensure that at all times, a process
is running on every CPU, in order to maximize CPU utilization.
Recall too that the objective of time-sharing systems
is to allow users to interact with their programs as if they were the only program running.
Achieving both simultaneously is tricky business:
- The mix of processes that use the CPU must be carefully controlled. There needs to be a mix of the right
processes in memory, not too many, not too few, and the order in which they use the
CPU should be just right as well.
- All of these decisions affect the above objectives.
--
.bluebold[Process scheduling] in general refers to various decisions
about the disposition of processes in the computer system.
---
name: scheduling-2
### Types of Process Scheduling
There are three levels of process scheduling:
- .redbold[long-term scheduling]: the decision about which processes are admitted
into system (usually just in batch systems).
- .redbold[medium-term scheduling]: the decision about which processes are memory-resident.
- .redbold[short-term scheduling]: also called .redbold[CPU scheduling],
the decision about which memory resident process gets the CPU next.
Long-term scheduling is used in batch systems to decide the order in which various
jobs should be executed. We will not discuss it here.
Medium-term and short-term scheduling are relevant to interactive computer
systems and we focus our attention on these.
---
name: medium-term-scheduler
### Medium-Term Scheduling
Medium-term scheduling refers to the decision about .redbold[how many] and .redbold[which]
processes should be in memory. These are important decisions:
- if too few processes are in memory, the CPU might be idle, and
- if too many, then processes might not have enough memory to perform well.
The number of processes currently in memory is called the .bluebold[degree of multiprogramming].
- One purpose of medium-term scheduling is to control the degree of multiprogramming.
- Another purpose is to ensure a .redbold[good mix of processes].
--
Some processes .redbold[make heavy use of I/O devices] -
they run briefly and immediately issue I/O requests.
They are called .bluebold[I/O-bound] processes.
Others are very .redbold[compute-intensive] - they spend little time making I/O requests,
spending most of their time doing a lot of computing. They are called .bluebold[compute-bound]
processes.
Ensuring a good mix of processes means having a mix of I/O-bound and compute-bound
processes that will keep the CPU busy while keeping .greenbold[response times] low.
.bluebold[Response time] is the time between when a request is made to a process
and that process responds to that request.
---
name: medium-term-scheduler-2
### The Swapper
In interactive computer systems, where users use shells to issue
commands and run applications and other programs, processes are
automatically loaded into memory, so there is no explicit scheduler
that .redbold[puts] processes into memory.
--
On the other hand, processes are removed from memory for various reasons, such
as because there are too many processes in memory and none of them have enough
memory for their needs.
In this case, decisions must be made as to which processes to remove and when to
return them to memory. The .bluebold[swapper] is a kernel process that does this.
Because this is really an issue regarding memory management, further explanation
and discussion is delayed until Chapter 9.
---
name: process-scheduler-1
### The Short-Term, or CPU, Scheduler
The objective of the CPU scheduler is to .redbold[maximize CPU utilization] while
keeping the process .redbold[response times as short as possible].
--
To achieve this, the kernel maintains several process queues:
- The .redbold[ready queue] contains the set of all memory-resident processes.super[1]
that are ready to execute but not running.
- For each device, a .redbold[wait queue], which contains the processes.super[1] waiting
for an event related to that device. For example, the wait queue for a disk drive
contains the processes waiting for data from that disk.
.footnote[
1 When we say a queue contains processes, we mean it contains pointers to their process
control blocks.
]
--
.redbold[The CPU scheduler selects processes from the ready queue to run on an available CPU.]
In an interactive system, the CPU scheduler runs very frequently, because it
cannot let any process run for too long, otherwise the response times for
the remaining processes would be unacceptably long.
Because it runs so frequently, it must be extremely fast, otherwise the overhead of
scheduling decreases CPU utilization, decreases throughput, and increases response times.
--
CPU scheduling is explored in detail in Chapter 5.
---
name: process-queues
### Queuing of Processes
A process in the ready queue eventually is scheduled to run on a CPU. When it runs, suppose it
initiates an I/O request. The kernel moves it to a wait queue for the device.
--
Eventually, it gets serviced and it moves to the rear of the ready queue.
--
In general, processes run, make requests for service, wait, run again, and so on, until eventually they
terminate. This means that they move from one queue to another over their lifetimes.
--
A .bluebold[queuing diagram] is a directed graph with two types of nodes: queue-nodes and
resource-nodes. Some edges are labeled by the actions that cause the transitions.
A queuing diagram for our simple system is below.
.center[
<img src="figures/queuing-diagram.png" width=75% alt="queuing diagram">
]
---
name: context-switch
### Context Switch
Events occur that require that the currently running process be removed
from the CPU and another one run. .redbold[How does this happen?]
--
The system (part hardware and part software) needs to save the current .greenbold[context]
of the process before it removes it, so that when it runs again, it can restore the process to the
exact state that it was in when it was interrupted.
Recall from the [Process Context slide](#process-context) that the context includes the
values of all registers, the process state, and memory-management information.
--
Changing the state of the CPU from one context (i.e., process) to another
is called a .bluebold[context switch].
It consists of two steps: .bluebold[save the old context] and .bluebold[load the new context].
- In general, the context of a process is saved in its PCB. When it runs
again, the PCB is used to restore the process to its previous state.
- Context switching time varies from machine to machine. It depends on memory speed,
size of register set, and whether the architecture has special hardware instructions to copy register sets.
In general it is costly.
- To reduce its overhead, some systems keep multiple sets of registers for each CPU
so that the old process context does not need to be saved.
---
name: exceptions-revisited
### Exceptions and Interrupts Revisited
Now that you understand what a process is, the distinction between
exceptions and interrupts should be clarified.
When a .greenbold[process causes an exception], and the kernel runs,
.redbold[it is still running on behalf of that process]. There is no context switch.
The only change is that the .redbold[hardware context] is changed:
- the mode is switched to kernel mode,
- the registers are saved, kernel code runs,
- registers are restored,
- the mode is switched to user mode.
While the kernel code is being executed, it is still associated with the process
that caused it to run.
When an .greenbold[interrupt occurs], it is different. It is not the result of the current process's
having done something.
- It might be that data is ready for some other process, or that the
process's time quantum expired and a new process must be run.
- This might cause a context switch. Whether it does or does not depends on the
type of interrupt and how the particular operating system handles the interrupt.
---
name: mode-changes
### Interrupts, System Calls, and Context Switches
It can be confusing to sort out the differences between
interrupt handling, system call handling, and the role of context switches in
all of these.
The figure below shows how they differ in a system such as Linux.super[1].
.footnote[
1 It is somewhat more complicated than this - there are more cases to consider.
]
.center[
<img src="figures/user-kernel-transitions.png" width=90% alt="User to Kernel Mode">
]
.smaller[
- A system call .redbold[that does not invoke the CPU scheduler] executes in the
same context as the process; there is no context switch.
- A timer interrupt .redbold[causes the CPU scheduler to run] in the
same context as the process; the scheduler may choose a new process; this is a context
switch.
- An interrupt from a device .redbold[causes the interrupt handler to run]; if it needs to
call the scheduler, there is a context switch, otherwise there is not.
]
---
name: process-operations
layout: false
class: center, middle, inverse
## Process Operations
Processes can create new
processes dynamically and can terminate themselves.
We explore how operating systems support
dynamic process creation and termination.
---
template: tinted-slide
layout: true