OPERATING SYTEMS

B.TECH II YR (TERM 08-09)

UNIT 3 PPT SLIDES
m
o
c
.
TEXT BOOKS:
rs

e
e
in

Operating System Concepts- Abraham Silberchatz,

Peter B. Galvin, Greg Gagne 7th Edition, John
Wiley
Operating systems- A Concept based ApproachD.M.Dhamdhere, 2nd Edition, TMH.

g
n

E
O

o
D

a
a
F

No. of slides: 42

INDEX
UNIT 3 PPT SLIDES
S.NO.
1.
2.
3.
4.
5.
6.
7.
8.

TOPIC

LECTURE NO. PPTSLIDES

Process synchronization
critical- section prob,
Petersons Solution
synchronization Hardware
Semaphores
Monitors
atomic transactions
Case study
REVISION

L17
L18

g
n

e
e
in

E
O

a
a
F

o
D

c
.
rs

L19
L20
L21
L22
L23

m
o

L17.1 to L17.4
L18.1 to L18.3

L19.1 to L19.7
L20.1 to L20.11
L21.1 to L21.4
L22.1 to L22.8
L23.1 to L23.3

Process synchronization
Concurrent access to shared data may result in
data inconsistency
Maintaining data consistency requires mechanisms
to ensure the orderly execution of cooperating
processes
Suppose that we wanted to provide a solution to the
consumer-producer problem that fills all the buffers.
We can do so by having an integer count that keeps
track of the number of full buffers. Initially, count is
set to 0. It is incremented by the producer after it
produces a new buffer and is decremented by the
consumer after it consumes a buffer.

m
o

c
.
rs

e
e
in

g
n

E
O

a
a
F

o
D

Producer
while (true) {

m
o

c
/* produce an item and put.in
s
r
nextProduced */
e
e
n
i
while (count == BUFFER_SIZE)
g
n
E
; // do O
nothing
o
buffer
[in]
=
nextProduced;
D
a
a
F in = (in + 1) % BUFFER_SIZE;
count++;
}

Consumer

m
o

while (true) {
while (count == 0)
; // do nothing
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;

c
.
rs

e
e
in

g
n

E
O

a
a
F

o
D/* consume the item in

nextConsumed
}

Race Condition
count++ could be implemented as
register1 = count
register1 = register1 + 1
count = register1
count-- could be implemented as

m
o

e
e
in

c
.
rs

register2 = count
register2 = register2 - 1
count = register2
Consider this execution interleaving with count = 5 initially:
S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}

g
n

E
O

a
a
F

o
D

Solution to Critical-Section
Problem
1.Mutual Exclusion - If process Pi is executing in its critical section,

m
o

then no other processes can be executing in their critical

sections
2. Progress - If no process is executing in its critical section and
there exist some processes that wish to enter their critical
section, then the selection of the processes that will enter the
critical section next cannot be postponed indefinitely
3. Bounded Waiting - A bound must exist on the number of times
that other processes are allowed to enter their critical sections
after a process has made a request to enter its critical section
and before that request is granted
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the N processes

c
.
rs

e
e
in

g
n

E
O

a
a
F

o
D

Petersons Solution
Two process solution
Assume that the LOAD and STORE
m
instructions are atomic; that is, cannot
be
o
c
.
interrupted.
s
r
e variables:
The two processes share e
two
int turn;
Boolean flag[2]

n
i
g

n
E

O
o
The variable
turn indicates whose turn it is to
D
acritical section.
enter the
a
F

The flag array is used to indicate if a process

is ready to enter the critical section. flag[i] =
true implies that process Pi is ready!

Algorithm for Process Pi

m
do {
o
c
.
flag[i] = TRUE;
s
r
e
e
turn = j;
n
i
g
while (flag[j]n&& turn == j);
E
O
critical
section
o
D
a
flag[i] = FALSE;
a
F
remainder section
} while (TRUE);

Synchronization Hardware
Many systems provide hardware support for
critical section code
Uniprocessors could disable interrupts
m

o
c
.
s

Currently running code would execute without

preemption
Generally too inefficient on multiprocessor
systems

r
e

e
in

g
n

E
O

Operating systems using this not broadly scalable

o
Modern machines
provide special atomic
D
hardware
aainstructions
F
Atomic = non-interruptable

Either test memory word and set value

Or swap contents of two memory words

Solution to Critical-section Problem

Using Locks
do {
m
o
c
.
acquire lock
s
r
critical section ee
n
i
release lock ng
E
O
remainder
section
o
aD
} whilea(TRUE);

TestAndndSet Instruction
Definition:

m
o

c
.
s
boolean TestAndSet (boolean
*target)
r
e
e
{
n
i
g
boolean rv =n*target;
E
*targeto=OTRUE;
D rv:
return
a
a
}F

Solution using TestAndSet

Shared boolean variable lock., initialized to false.
Solution:

m
o

c
.
rs

do {

e
e
in

while ( TestAndSet (&lock ))

; // do nothing
//

g
n

E
O

critical section

o
D

a
a
F

lock = FALSE;
//

} while (TRUE);

remainder section

Swap Instruction
Definition:

c
.
rs

e
e
n
i
void Swap (boolean *a, boolean
*b)
g
n
{
E
O
boolean
temp
= *a;
o
*aa=D
*b;
a
F *b = temp:
}

m
o

Solution using Swap

Shared Boolean variable lock initialized to FALSE;
Each process has a local Boolean variable key
Solution:
do {
key = TRUE;
while ( key == TRUE)
Swap (&lock, &key );

c
.
rs

e
e
in

//

g
n

E
O

o
D

critical section

a
a
F

lock = FALSE;
//

} while (TRUE);

m
o

remainder section

Bounded-waiting Mutual Exclusion with TestandSet()

do {
waiting[i] = TRUE;
key = TRUE;
while (waiting[i] && key)
key = TestAndSet(&lock);
waiting[i] = FALSE;
// critical section
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = FALSE;
else
waiting[j] = FALSE;
// remainder section
} while (TRUE);

e
e
in

c
.
rs

g
n

E
O

a
a
F

o
D

m
o

Semaphore
Synchronization tool that does not require busy waiting
Semaphore S integer variable
Two standard operations modify S: wait() and signal()
Originally called P() and V()
Less complicated
Can only be accessed via two indivisible (atomic)
operations
wait (S) {
while S <= 0
; // no-op
S--;
}
signal (S) {
S++;

m
o

c
.
rs

e
e
in

g
n

E
O

a
a
F

o
D

Semaphore as General Synchronization Tool

Counting semaphore integer value can range over an unrestricted
domain
Binary semaphore integer value can range only between 0
and 1; can be simpler to implement
Also known as mutex locks
Can implement a counting semaphore S as a binary semaphore
Provides mutual exclusion
Semaphore mutex; // initialized to 1
do {
wait (mutex);
// Critical Section
signal (mutex);
// remainder section
} while (TRUE);

m
o

c
.
rs

e
e
in

g
n

E
O

a
a
F

o
D

Semaphore Implementation
Must guarantee that no two processes can execute wait () and
signal () on the same semaphore at the same time
Thus, implementation becomes the critical section problem
where the wait and signal code are placed in the crtical section.
Could now have busy waiting in critical section
implementation
But implementation code is short
Little busy waiting if critical section rarely occupied
Note that applications may spend lots of time in critical sections
and therefore this is not a good solution.

m
o

c
.
rs

e
e
in

g
n

E
O

a
a
F

o
D

Semaphore Implementation with no Busy waiting

With each semaphore there is an associated

waiting queue. Each entry in a waiting queue
m
has two data items:
o

c
.
rs

value (of type integer)

pointer to next record in the list

e
e
in

g
n

E
O
Two operations:
o
D the process invoking the operation
block a
place
a
F appropriate waiting queue.
on the
wakeup remove one of processes in the
waiting queue and place it in the ready queue.

Semaphore Implementation with no Busy waiting

Implementation of wait:
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
}
}
Implementation of signal:

m
o

c
.
rs

e
e
in

g
n

E
O

o
D

signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}

a
a
F

Deadlock and Starvation

Deadlock two or more processes are waiting indefinitely for
an event that can be caused by only one of the waiting
processes
Let S and Q be two semaphores initialized to 1
P0
P1
wait (S);
wait (Q);
wait (Q);
wait (S);
.
.
.
.
.
.
signal (S);
signal (Q);
signal (Q);
signal (S);
Starvation indefinite blocking. A process may never be
removed from the semaphore queue in which it is suspended
Priority Inversion - Scheduling problem when lower-priority
process holds a lock needed by higher-priority process

m
o

c
.
rs

e
e
in

g
n

E
O

a
a
F

o
D

Bounded-Buffer Problem

N buffers, each can hold one item

Semaphore mutex initialized to the value 1
m
o
Semaphore full initialized to the value
0
c
.
s
r
Semaphore empty initialized
to
the
value
N.
e
e

n
i
g

n
E

O
o

D
a
a

Bounded Buffer Problem (Cont.)

The structure of the producer process

do {

// produce an item in nextp

wait (empty);
wait (mutex);
// add the item to the buffer
signal (mutex);
signal (full);
} while (TRUE);
The structure of the consumer process
do {
wait (full);
wait (mutex);
// remove an item from buffer to nextc
signal (mutex);
signal (empty);
// consume the item in nextc
} while (TRUE);

c
.
rs

m
o

e
e
in

g
n

E
O

a
a
F

o
D

Readers-Writers Problem
A data set is shared among a number of concurrent processes
Readers only read the data set; they do not perform any
updates
Writers can both read and write

m
o

c
.
Problem allow multiple readers to readratsthe same time.
e data at the same
Only one single writer can access the
shared
e
n
i
time
g
n
Shared Data
E
O
Data set
o
D initialized to 1
Semaphoreamutex
a
Semaphore
F wrt initialized to 1
Integer readcount initialized to 0

Readers-Writers Problem
The structure of a writer process
do {
wait (wrt) ; // writing is performed
signal (wrt) ;
} while (TRUE);
The structure of a reader process
do {
wait (mutex) ;
readcount ++ ;
if (readcount == 1)
wait (wrt) ;
signal (mutex) //reading is performed
readcount - - ;
if (readcount == 0)
signal (wrt) ;
signal (mutex) ;
} while (TRUE);

m
o

c
.
rs

e
e
in

g
n

E
O

aa

o
D

wait (mutex) ;

Dining-Philosophers Problem
Shared data
Bowl of rice (data set)
Semaphore chopstick [5] initialized to 1

do {

e
e
in

c
.
rs

wait ( chopstick[i] );
wait ( chopStick[ (i + 1) % 5] );
// eat

E
O

g
n

o
signal (D
chopstick[i] );
a(chopstick[ (i + 1) % 5] );
signal
a
F
// think

} while (TRUE);

m
o

Monitors
A high-level abstraction that provides a convenient
and effective mechanism for process synchronization
Only one process may be active within the monitor at
a time

m
o

monitor monitor-name
{
// shared variable declarations
procedure P1 () { . }

g
n

e
e
in

E
O

o
D

a
a
F

procedure Pn () {}
Initialization code ( .) { }

c
.
rs

Solution to Dining Philosophers

monitor DP
{
enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];
void pickup (int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING) self [i].wait;
}
void putdown (int i) {
state[i] = THINKING;
// test left and right neighbors
test((i + 4) % 5);
test((i + 1) % 5);
}
void test (int i) {
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING ;
self[i].signal () ;
} }
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
} }

e
e
in

c
.
rs

g
n

E
O

a
a
F

o
D

m
o

 Each philosopher I invokes the operations pickup() and putdown() in the

following sequence:
DiningPhilosophters.pickup (i);
EAT
DiningPhilosophers.putdown (i);
Monitor Implementation Using Semaphores Variables
semaphore mutex; // (initially = 1)
semaphore next; // (initially = 0)
int next-count = 0;
Each procedure F will be replaced by

wait(mutex);

body of F;

if (next_count > 0)
signal(next)
else
signal(mutex);

m
o

c
.
rs

e
e
in

g
n

E
O

o
D

a
a
F

Mutual exclusion within a monitor is ensured.

Monitor Implementation
For each condition variable x, we have:

m
o

semaphore x_sem; // (initially = 0)

int x-count = 0;

c
.
rs

e
e
in

The operation x.wait can be implemented as:

g
n

E
O

x-count++;
if (next_count > 0)
signal(next);
else
signal(mutex);
wait(x_sem);
x-count--;

a
a
F

o
D

Atomic Transactions

m
System Model
o
c
.
Log-based Recovery
s
r
e
e
Checkpoints
n
i
g
n
Concurrent Atomic
E Transactions
O
o

D
a
a

System Model
Assures that operations happen as a single logical unit of
work, in its entirety, or not at all
Related to field of database systems
Challenge is assuring atomicity despite computer system
failures
Transaction - collection of instructions or operations that
performs single logical function
Here we are concerned with changes to stable storage
disk
Transaction is series of read and write operations
Terminated by commit (transaction successful) or abort
(transaction failed) operation
Aborted transaction must be rolled back to undo any
changes it performed

m
o

c
.
rs

e
e
in

g
n

E
O

a
a
F

o
D

Log-Based Recovery
Record to stable storage information about all modifications
by a transaction
Most common is write-ahead logging
Log on stable storage, each log record describes single
transaction write operation, including
Transaction name
Data item name
Old value
New value
<Ti starts> written to log when transaction Ti starts
<Ti commits> written when Ti commits
Log entry must reach stable storage before operation on data
occur

m
o

c
.
rs

e
e
in

g
n

E
O

a
a
F

o
D

Checkpoints
Log could become long, and recovery could take long
Checkpoints shorten log and recovery time.
Checkpoint scheme:
1. Output all log records currently in volatile storage to stable
storage
2. Output all modified data from volatile to stable storage
3. Output a log record <checkpoint> to the log on stable
storage
Now recovery only includes Ti, such that Ti started executing
before the most recent checkpoint, and all transactions after
Ti All other transactions already on stable storage

m
o

c
.
rs

e
e
in

g
n

E
O

a
a
F

o
D

Concurrent Transactions
Must be equivalent to serial execution
m
serializability
o
c
.
s
Could perform all transactions
in critical
r
e
e
section
n

i
g
Inefficient, too restrictive
n
E
O
Concurrency-control
algorithms provide
o
D
serializability
a
a
F

Serializability

Consider two data items A and B

Consider Transactions T0 and T1
m
o
c
.
Execute T0, T1 atomically
s
r
e
Execution sequence calledeschedule
n
i
g
Atomically executed n
transaction
order called
serial schedule OE
o
D
For N transactions,
there are N! valid serial
a
a
F
schedules

Locking Protocol
Ensure serializability by associating lock with
each data item

m
o

Follow locking protocol for access control

c
.
rs

Locks

e
e
in

Shared Ti has shared-mode lock (S) on item Q, Ti

can read Q but not write Q
Exclusive Ti has exclusive-mode lock (X) on Q, Ti
can read and write Q

g
n

E
O

o
D

a
a
Require
Fevery transaction on item Q acquire

appropriate lock
If lock already held, new request may have to
wait

Two-phase Locking Protocol

Generally ensures conflict serializability
m
o
c
.
Each transaction issues lock s
and
unlock
r
requests in two phases ee

n
i
Growing obtainingg
locks
n
E
Shrinking releasing
locks
O
o deadlock
Does not D
prevent
a
a
F

Solaris Synchronization
Implements a variety of locks to support
multitasking, multithreading (including realtime threads), and multiprocessing om
c
.
s
Uses adaptive mutexes for efficiency
when
r
e
e
protecting data from shortncode segments
i
g
Uses condition variables
and readers-writers
n
E
locks when longer
sections of code need
O
o
D
access to data
a
a
F
Uses turnstiles
to order the list of threads
waiting to acquire either an adaptive mutex or
reader-writer lock

Windows XP Synchronization
Uses interrupt masks to protect access
to
m
o
c
global resources on uniprocessor
systems
.
s
r
e
Uses spinlocks on multiprocessor
systems
e
n
i
Also provides dispatcher
objects
which
g
n
E
may act as either
mutexes and
O
o
semaphores
D
a
a
Dispatcher
objects may also provide
F
events
An event acts much like a condition variable

Linux Synchronization

m
o

Linux:

c
.
rs

Prior to kernel Version 2.6, disables interrupts

to implement short critical sections
Version 2.6 and later, fully preemptive

e
e
in

g
n

E
O

o
Linux provides:
D
a
a
semaphores
F
spin locks