�ݺ�ߣ

Operating
Systems
Lecture 18
Syed Mansoor Sarwar

Agenda for Today
 Review of previous lecture
 UNIX System V scheduling

 Algorithm evaluation

 Process synchronization

 Recap of lecture

19 September 2012 © Copyright Virtual University of
Pakistan

Review of Lecture 17
 Multi-level queues scheduling
 Multi-level feedback queues
scheduling
algorithm

Pakistan

UNIX System V
Scheduling Algorithm
 Every second, the priority number of all
those processes that are in the main
memory and ready to run is updated by
using the following formula:
Priority# = (Recent CPU Usage)/2 + Thr. Pri.+ nice
 Threshold priority and nice values are
always positive to prevent a user from
migrating out of its assigned group
Pakistan

UNIX System V Example
PA PB PC
CPU CPU CPU
Time Priority Count Priority Count Priority Count
60 0 60 0
0 60 0
1
…
60
75 30 60 0
1 1 60 0
…
30 60
2 67 15 75 30 60 0
1
…
30
15 60
3 63 7 67 75
8 30
…
67 30
4 76 33 63 7
8
67 15
…
67
68
19 September 2012
5 16© Copyright Virtual University of
76 33 7
63
Pakistan

Round Robin Scheduling
and Process Priorities
60
Higher Priority

B

B A

A
A
1 2 3

B A B B A runs first
A

4 Pakistan
5 6

Algorithm Evaluation
 Analytic Evaluation
 The algorithm and some system
workload are used to produce a
formula or number which gives the
performance of the algorithm for that
workload.
 Deterministic modeling
 Queuing models
 Implementation
Pakistan

Deterministic Modeling
 Predetermined workload and
performance of each algorithm for
that workload. Use of Gantt charts.
 Simple and fast
 Exact numbers for comparison
 Requires exact input
 Performance figures may not be
true in general
Pakistan

Deterministic Modeling
 Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
 Gantt chart
P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

19Average waiting time =University of1 + 0 +2)/4 = 3
September 2012 © Copyright Virtual
(9 +
Pakistan

Queuing Modeling
 Computer system viewed as a
network of queues and servers:
ready queue, I/O queue, event
queues, CPUs, I/O device
controllers, etc.
 Input: Arrival and service rates
 Output: CPU utilization, average
queue length, average
waiting time, …
Pakistan

Queuing Modeling
Little’s Formula:
n = λ* W
where
n = average queue length
λ = average arrival rate
W = average waiting time in a
queue
Pakistan

Queuing Modeling
Let the average job arrival rate be 0.5
Algorithm Average Wait Average Queue
Time Length(n)
W=tw
FCFS 4.6 2.3
SJF 3.6 1.8
SRTF 3.2 1.6
RR (q=1) 7.0 3.5
RR (q=4)
19 September 2012
6.0
© Copyright Virtual University of
3.0
Pakistan

Queuing Modeling
 Complicated mathematics
 Distributions (Poisson, uniform,
exponential, etc) for the arrival and
departure rates can be difficult to
work with
 Assumptions may not be accurate
 Approximation of the real system
Pakistan

Simulation
 Programming model for the
computer system
 Workload generated by
assuming some distribution and
a random number generator, or
by collecting data from the
actual system.
Pakistan

Simulation
 Characteristics
Expensive: hours of
programming and execution
time
May be erroneous because
of the assumptions about
distributions
Pakistan

Simulation

Pakistan

Implementation
 Best
 Most expensive
 Good option due to Open
Source kernels such as Linux

Pakistan

Process
Synchronization
 Concurrent access to shared
data may result in data
inconsistency.
 Maintaining data consistency
requires mechanisms to ensure
that cooperating processes
access shared data
sequentially.
Pakistan

Bounded-Buffer Problem
Shared data
#define BUFFER_SIZE 10
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0, out = 0;
int counter = 0;
Pakistan

Producer process
item nextProduced;
…
while (1) {
while (counter == BUFFER_SIZE) ;
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
Pakistan

Consumer process
item nextConsumed;
while (1) {
while (counter == 0) ;
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
}
Pakistan

 “counter++” in assembly language
MOV R1, counter
INC R1
MOV counter, R1

 “counter--” in assembly language
MOV R2, counter
DEC R2
MOV counter, R2
Pakistan

 If both the producer and consumer
attempt to update the buffer
concurrently, the machine language
statements may get interleaved.
 Interleaving depends upon how the
producer and consumer processes
are scheduled.
Pakistan

 Assume counter is initially 5. One
interleaving of statements is:

producer: MOV R1, counter (R1 = 5)
INC R1 (R1 = 6)
consumer: MOV R2, counter (R2 = 5)
DEC R2 (R2 = 4)
producer: MOV counter, R1 (counter = 6)
consumer: MOV counter, R2 (counter = 4)

 The value of count may be either 4 or
6, where the correct resultofshould be 5.
19 September 2012 © Copyright Virtual University
Pakistan

Process
Synchronization
 Race Condition: The situation
where several processes access
and manipulate shared data
concurrently, the final value of the
data depends on which process
finishes last.
Pakistan

Process
Synchronization
 Critical Section: A piece of code
in a cooperating process in which
the process may updates shared
data (variable, file, database, etc.).
 Critical Section Problem:
Serialize executions of critical
sections in cooperating processes
Pakistan

Solution of the Critical
Problem
 Software based solutions
 Hardware based solutions
 Operating system based
solution

Pakistan

Structure of Solution
do {
entry section
critical section
exit section

reminder section
} while (1);
Pakistan

Recap of Lecture

 Algorithm evaluation

 Process synchronization

 Recap of lecture

Pakistan

�ݺ�ߣ

os lacture

More Related Content

os lacture