Unit 3
Unit 3
Unit 3
{ Int Counter=5 {
Counter++; Counter--;
} Shared Variable }
2. Progress:
• No process running outside its critical region may block other processes.
3. No starvation(Bounded wait):
• No process should have to wait forever to enter its critical region.
Proposals for achieving Mutual Exclusion
Disabling Interrupts
Lock variables
Strict Alteration
Peterson’s solution
TSL instruction
1. Disabling Interrupts
• When Interrupts are disabled, context switch won’t happen.
• Requires privileges:
• User process generally cannot disable interrupts.
• Disadvantage:
• Not suited for multicore systems
• Process has power to disable the interrupt. (If process does not turned it on?)
Process 1 Process 2
{ {
Disable Interrupts() Disable Interrupts()
Critical section Critical section
enable Interrupts() enable Interrupts()
} }
2. Lock Variables
• Shared Lock variable, initially 0.
• When a process wants to enter its critical region, it first tests the lock.
• If the lock is 0, the process sets it to 1 and enters the critical region.
• Initially turn=0.
• Violates Progress
• Busy Waiting: Continuously testing a variable until some value appears.
• Waste CPU cycle
• Spin lock:Lock that uses busy waiting.
4. Peterson’s Solution
Hardware Locks: TSL(Test and Set Lock)
• TSL instruction locks the memory bus to prohibit others from accessing
memory until it is done.
Intel x86 CPUs use XCHG instruction
Sleep and Wakeup
Why Sleep and Wakeup?
•Solution of Busy waiting(Waste CPU Cycle).
•Sleep is system call which blocks the caller, that is, be suspended until
another process wakes it up.
Producer-Consumer Problem(Bounded Buffer
Problem)
• We have a buffer of fixed size.
Context Switch
Semaphore
• Semaphore is a variable is used to solve critical section problem and
to achieve process synchronization in the multi processing
environment.
• The two most common kinds of semaphores
• Counting semaphore can take non-negative integer values
• Binary semaphore can take the value 0 & 1. only.
Semaphore
• 2 operations on Semaphores:
• P operation is also called wait, sleep or down operation
• V operation is also called signal, wake-up or up operation.
• Both operations are atomic and semaphore(s) is always initialized to one.
• A critical section is surrounded by both operations to implement
process synchronization.
• Uses of Semaphores:
• Achieve Mutual Exclusion
• Deciding order of execution
• Managing Resource
Semaphore Implementation
Void down(int *s) Void up(int *s)
{ {
while(*s<=0); *s++;
*s--; }
}
• Answer: 2
Gate Example
• A counting semaphore was initialized to 10. Then 6 P (wait)
operations and 4V (signal) operations were completed on this
semaphore. The resulting value of the semaphore is
• (a) 0 (b) 8 (c) 10 (d) 12
Ans: option(b)
Gate Example
• The following program consists of 3 concurrent processes and 3 binary
semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.
Thinking
OR
Eating
#define N 5 /* #philosophers */
First Try void philosopher(int i) /* i: from 0 to 4 */
{
while (TRUE) {
4 think( ); /* Thinking */
take fork(i); /* take right fork */
take fork((i+1) % N); /* take left fork*/
eat( ); /* Eating*/
put fork((i+1) % N); /* put left fork */
put fork(i); /* put right fork*/
4 0 0 }
3 }
3 Problems
1
2 :
1.What happens if only philosopher 0 and 2 are always
given the priority?
P1, P3 and P4 starves.
2.What happens if all philosophers pick up right forks at a
2 same time?
1
Circular Wait (Deadlock).
#define N 5 /* #philosophers */
Second Try
void philosopher(int i) /* i: from 0 to 4 */
{
while (TRUE) {
think( );
take fork(i); /*Right Fork*/
4 if(available(take fork((i+1) % N)) { /*left fork available*/
take fork((i+1) % N); /*Left Fork*/
eat();
put fork((i+1) % N);
put fork(i);
}
4 0 0 else{ put fork(i);
3 Sleep(Time); /*sleep for some time*/
}
3 }
1
2 }
Problem:
All Philosophers start at the same time , Run
simultaneously and think for the same time.
This could lead to philosophers taking fork and putting it
2 1 down continuously. Deadlock
Solution using #define N 5
semaphore mutex =1 ;
/* #philosophers */
while (TRUE) {
4 think( ); /* Thinking */
wait(mutex);
take fork(i); /* take right fork */
take fork((i+1) % N); /* take left fork*/
eat( ); /* Eating*/
put fork((i+1) % N); /* put left fork */
0 0 put fork(i); /* put right fork*/
4
signal(mutex);
3 }
3
1 }
2
Problem:
Only one philosopher can eat at a time.
2 1
Solution using Semaphore
A Philosopher can only move to EATING state if neither neighbour is eating.
• If no other process is using the monitor, the calling process may enter.
Condition variables in Monitor
• We can perform two operations on them, wait and signal.
• The former call sends a message to a given destination and the latter
one receives a message from a given source.
• When the sender and receiver are on the same machine. One of
these is performance. Copying messages from one process to another
is always slower than doing a semaphore operation or entering a
monitor.
Producer Consumer using Message Passing
#define N 100 /* number of slots void consumer(void)
in the buffer */ {
void producer(void){ int item, i;
int item; message m;
message m; /* message buffer */ for (i = 0; i < N; i++)
while (TRUE) { send(producer, &m);
item = produce item( ); while (TRUE) {
receive(consumer,&m); receive(producer,&m);
build message(&m, item); item = extract item(&m);
send(consumer,&m); send(producer,&m);
} consume item(item);
} }
Any
Questions