Operating System

Nguyen Tri Thanh

ntthanh@vnu.edu.vn

1
2
 Review
• Which of the following is not a part of an OS
kernel ?
A. Process management
B. Network management
C. Memory management
D. Database management systems

3
 Review
• Which of the following should NOT be fixed in
an OS?
A. SATA driver (a disk driver)
B. Process management module
C. Network management
D. Memory management

4
 Review
• Which of the following is incorrect about a
time sharing OS?
A. Allow multiple processes to run on a single CPU
machine
B. Utilize resources more effectively
C. Only utilize CPU more effectively
D. Even suitable for multi-CPU machines

5
 Review
• Which of the following is incorrect about a
batch OS?
A. A simple type of OSes
B. It works in First-comes-first-served order
C. Allow multiple users to use the system
concurrently
D. Not the same as multiprogramming systems

6
 Review
• Which of the following is incorrect about a
multi-user OS?
A. Allow multiple processes to run on a single CPU
machine
B. Allow each user run multiple processes
C. Allow multiple users to use the system
concurrently
D. Be the same as multiprogramming systems

7
 Review
• Which of the following devices DOESN’T have
an embedded system?
A. mp3 player
B. TV
C. calculator
D. laptop

8
Process and Process
Scheduling

9
 Objectives
• Present what a process is
• Present process scheduling approaches
• Scheduling in multi-queue systems
• Implement the scheduling algorithms

10
 Reference
• Chapter 3, 6 of Operating System Concepts

11
 Question
• What is a process?
A. A file on disk
B. An application
C. A program running on the system
D. A library
• Job, task and process may be used
interchangeably

12
Process statistic

13
Process statistic

14
Process statistic

15
 Process classification
Processes are classified into 2 categories
A. System processes
 Created by system account
 Run essential services
B. User processes
 Created by user accounts
 Usually are application processes (Word, Excel, YM,…)

16
 Question
What is the correct relation among application,
process and program concepts
A. An application may have multiple processes, a
process may have multiple programs
B. An application only has one program, a program
only has one process
C. An application may have multiple programs, a
program may have multiple processes
D. An application may have many programs, a
program only has one process
17
 Question
Select the best description of resources a pure
computer may have
A. CPU, RAM and anything that can connect to the
computer, such as CD, network card, …
B. CPU, RAM, Disks
C. CPU, RAM, Disk, printer
D. CPU, RAM, Disk, printer, monitor

18
Process structure
• A process at least consists of
1. A program counter
(Instruction Pointer)
2. Text (code)
3. Stack + Heap
4. Data section
• Other information is included
• The process structure is
different among OSes
19
Process structure

20
Process structure

21
 X86-64 Intel registers

https://en.wikipedia.org/wiki/X86

22
 Process control block (PCB)
Information associated with each process
– Process state
– Program counter
– CPU registers
– CPU scheduling information
– Memory-management information
– Accounting information
– I/O status information
• PCB is different among OSes
23
 Process states
• A process has many states during its life

• The number of states is different among

OSes
24
 Process states
• New
– a new process is initiated
• Running
– Process instructions are being run
• Waiting
– Process is waiting for a certain resource or event
• Ready
– Process just waits for its turn to run
• Terminated
– The process completes
25
 CPU And I/O Bursts
• Burst – a time span (duration)
• Two burst types
– IO burst
– CPU burst

26
 Process classification
• CPU-bound process
– uses CPU a lot (for computation)
• IO-bound process
– does IO a lot (data manipulation)
• These types of processes affect schedulers

27
Process classification

28
Process classification

29
Process classification

30
Process classification

31
Process classification

32
Process classification

33
 Process context switch
• Context switch
– CPU stops current process and runs another one
• Progress steps
– save the state of the current process
– put it into the READY/WAITING queue
– pick the target process
– restore the state of the target process
– run the target process

34
Process context switch

35
 Question
• Which of the following is incorrect about
context switch?
A. the steps of changing from current process to
the target one
B. the current process will be put into the waiting
queue
C. the target process will be run
D. the state of the current process will be saved

36
Process scheduling
introduction

37
 Problem
• You have 5 exams within a week
– How do you manage to study?
• You have serveral courses to select
• A shop saler has many customers waiting
– How does he/she do?
• At a buffet where sereral disks are availble
– How do you eat?
• A CPU has several processes
– How does it run them

38
Problem

39
 Problem

How to run these

processes?

40
 Question
Which best describes the reason why we need
process scheduling?
A. Because we have many processes
B. Because we have many processes and want
them to be treated fairly
C. Many reasons
 Many processes
 Utilize resources effectively
 Don’t let users wait
 …
D. Because we want to utilize RAM effectively 41
 Queue
• When there are several people waiting at
the counter (in a supermarket)
– What do they do?

42
Queue

43
Queue

44
Queue

45
Queue

46
Queue

47
Queue

48
Queue

49
 Queue

Queue is the input/output

of a process scheduler

50
 Different schedulers
• Long-term scheduler (or job scheduler)
– selects which processes should be brought into the ready
queue
• Short-term scheduler (or CPU scheduler)
– selects which process should be executed next
• Medium-term scheduler
– selects which process to temporarily swap out (of the
MEM)

51
 Different schedulers

Where is the position of the 3 schedulers?

52
Scheduling in Batch Systems

Three level scheduling

53
 Question
What is wrong when the CPU scheduler is
called?
A. A process changes from RUNNING to READY
B. A process is stopped
C. A process is admitted
D. A different process will be run

54
Position of CPU scheduler

55
 Dispatcher
• Dispatcher module gives control of the CPU
to the process selected by the short-term
scheduler; this involves:
– switching context
– switching to user mode
– run the process
• Dispatch latency – time it takes for the
dispatcher to stop one process and start
another running
56
Dispatcher

57
CPU scheduling

58
 CPU scheduling
What is CPU scheduling?
A. Select program to be initialized
B. Select process to swap out
C. Select process to change into the idle state
D. Select process to run

59
CPU scheduling

60
 CPU scheduling
Where is the position of CPU scheduler?
A. Between NEW and READY states
B. Between RUNNING and READY states
C. Between RUNNING and TERMINATED states
D. Between RUNNING and WAITING states

61
 CPU scheduler type
• Non pre-emptive
– running process has privilege to use CPU until it
terminates or changes into WAITING state
– Ex: Apple Macintosh, Windows 3.1
• Pre-emptive
– running process may be forced to release CPU
– Ex: Current Windows versions, Linux, Unix
• Which type is more effective?

62
Question

63
 Question
• Which is correct about non-preemptive scheduler?
A. no arc from RUNNING to READY states
B. no arc from RUNNING to WAITING states
C. no arc from WAITING to READY states
D. no arc from READY to RUNNING states

64
 First comes first served (FCFS)
• Use FIFO queue
• Process at the head of the queue is run first

65
First comes first serves (FCFS)
Process Burst Time
P1 24
P2 3
P3 3
• Suppose that the processes arrive in
the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1 P2 P3

0 24 27 30

66
 Shortest Job First (SJF)
• Also called Shortest Job Next (SJN)
• Shortest job in the queue is selected to be
run
• There are two flavors
– Non-preemptive
– Preemptive (Shortest Remaining Time First –
SRTF)

67
Shortest Job First (SJF)

68
Shortest Job First (SJF)

Let me
go first

69
Example of Non-Preemptive SJF
Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4

P1 P3 P2 P4

0 3 7 8 12 16

70
Example of Preemptive SJF
Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4

P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

71
 Next CPU burst estimation
• What if we don’t know the length of burst
time?
• Can only estimate
• Can be done by using the length of previous
CPU bursts, using exponential averaging
1. t n  actual length of n th CPU burst
2.  n 1  predicted value for the next CPU burst
3.  , 0    1
4. Define :  n 1   t n  1    n . 72
 Examples
•  =0
– n+1 = n
– Recent history does not count
•  =1
– n+1 =  tn
– Only the actual last CPU burst counts
• If we expand the formula, we get:
n+1 =  tn+(1 - ) tn -1 + …
+(1 -  )j  tn -j + …
+(1 -  )n +1 0
• Since both  and (1 - ) are less than or equal to 1, each
successive term has less weight than its predecessor 73
 Round Robin (RR)
• Each process gets a small unit of CPU time
– time quantum (usually 10-100 milliseconds)
– After time quantum, the process is preempted
and added to the end of the READY queue.
• Performance
– q large  FIFO
– q small  q must be large with respect to
context switch, otherwise overhead is too high

74
 Round Robin

Time
Users

Workstation

Workstation Computer

75
 Round Robin

Time
Users

Workstation

Workstation Computer

76
 Round Robin

Time
Users

Workstation

Workstation Computer

77
 Example of RR
Process Burst Time
P1 53
P2 17
P3 68
P4 24
• Quantum is 20
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162

78
 Priority Scheduling
• A priority number (integer) is associated with each
process
• The CPU is allocated to the process with the
highest priority (smallest integer  highest priority)
– Preemptive
– Non-preemptive
• SJF is a priority scheduling where priority is the
predicted next CPU burst time
• Problem  Starvation (low priority processes may
never execute)
• Solution  Aging (as time progresses increase the
priority of the process) 79
 Multilevel Queue
• Ready queue is partitioned into separate queues
– foreground (interactive)
– background (batch)
• Each queue has its own scheduling algorithm
– foreground – RR
– background – FCFS

80
 Multilevel Queue (cont’d)
• Scheduling must be done between the queues
– Fixed priority scheduling
• (i.e., serve all from foreground then from
background)
• Possibility of starvation
– Time slice
• each queue gets a certain amount of CPU time which
it can schedule amongst its processes
– i.e., 80% to foreground in RR
– 20% to background in FCFS

81
Multilevel Queue Scheduling

82
 Multilevel Feedback Queue
• A process can move between the various queues
– aging can be implemented this way
• Multilevel-feedback-queue scheduler defined by
the following parameters
– number of queues
– scheduling algorithms for each queue
– method used to determine when to upgrade a process
– method used to determine when to demote a process
– method used to determine which queue a process will
enter when that process needs service

83
 Example
• Three queues:
– Q0 – RR with time quantum 8 milliseconds
– Q1 – RR time quantum 16 milliseconds
– Q2 – FCFS
• Scheduling
– A new job enters queue Q0. When it gains CPU, job
receives 8 milliseconds. If it does not finish in 8
milliseconds, job is moved to queue Q1.
– At Q1 job receives 16 additional milliseconds. If it still
does not complete, it is preempted and moved to queue
Q2.
84
Example

85
 Multiple-Processor Scheduling
• CPU scheduling more complex when
multiple CPUs are available
– Homogeneous processors within a
multiprocessor
– Load sharing
• Asymmetric multiprocessing
– only one processor accesses the system data
structures, alleviating the need for data
sharing

86
 Scheduling criteria
• CPU utilization
– keep the CPU as busy as possible
• Throughput
– # of complete processes per time unit
• Turnaround time
– amount of time to execute a particular process
• Waiting time
– amount of time waiting in the ready queue
• Response time
– amount of time it takes from when a request was
submitted until the first response is produced, not
output (for time-sharing environment) 87
 Question
Which is incorrect about scheduling
optimization?
A. Maximize turnaround time
B. Maximize throughput
C. Minimize waiting time
D. Minimize response time

88
First comes first serves (FCFS)
Process Burst Time
P1 24
P2 3
P3 3
• Suppose that the processes arrive in
the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1 P2 P3

0 24 27 30

89
 Question
Which is the total waiting time in FCFS
example?
A. 21
B. 31
C. 41
D. 51

90
 Question
Which is the average waiting time in FCFS
example?
A. 15
B. 16
C. 17
D. 18

91
 Question
Which is the throughput in FCFS example?
A. 0.1
B. 0.2
C. 0.3
D. 0.4

92
Example of Non-Preemptive SJF
Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4

P1 P3 P2 P4

0 3 7 8 12 16

93
 Question
Which is the total waiting time in non-
preemptive SJF example?
A. 15
B. 16
C. 17
D. 18

94
 Question
Which is the average waiting time in the non-
preemptive SJF example?
A. 2
B. 3
C. 4
D. 6

95
 Question
Which is the throughput in the non-
preemptive SJF example?
A. 0.65
B. 0.25
C. 0.35
D. 0.45

96
Example of Non-Preemptive SJF
Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4

P1 P3 P2 P4

0 3 7 8 12 16

97
 Question
What is the turnaround time of P2 in the SJF
example?
A. 6
B. 8
C. 10
D. 12

98
 Question
What is the response time of P2 in the SJF
example?
A. 6
B. 8
C. 4
D. 0

99
100
Question?
101