PROCESS SYNCHRONIZATION Dsatm

Operating Systems Module 2
Process Synchronization
Basics:
 Cooperative process that can affect or be affected by other processes.
 All running asynchronously and sharing the data
 A bounded buffer could be used to share the data
 Allow at most BUFFER_SIZE-1 items in buffer
 Add an integer variable counter initialized to 0.
Producer process code

while (true) {
/* produce an item in next produced */
while (counter == BUFFER_SIZE) ;

/* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
Consumer process code
while (true) {
while (counter == 0)
; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
/* consume the item in next consumed */
}
 Both process work correct separately, they may not function

correctly when executed concurrently
 counter++ could be implemented as

register1 = counter
register1 = register1 + 1
counter = register1
 counter-- could be implemented as

register2 = counter
register2 = register2 - 1
counter = register2
 Consider this execution interleaving with “count = 5” initially:

S0: producer execute register1 = counter {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = counter {register2 = 5}
S3: consumer execute register2 = register2 – 1 {register2 = 4}
S4: producer execute counter = register1 {counter = 6 }
S5: consumer execute counter = register2 {counter = 4}
Race condition: where several process access and manipulate the same
data concurrently and the outcome of execution depends on the
particular order in which access takes place.
Critical section problem

 Consider system of n processes {p0, p1, … pn-1}
 Each process has critical section segment of code
o Process may be changing common variables, updating table,
writing file, etc
o When one process in critical section, no other may be in its critical
section
 Critical section problem is to design protocol to solve this

 Each process must ask permission to enter critical section in entry
section, may follow critical section with exit section, then remainder
section
General structure of process Pi
Solution to Critical-Section Problem

1. Mutual Exclusion - If process Pi is executing in its critical section, 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
Two approaches depending on if kernel is preemptive or non- preemptive

1. Preemptive – allows preemption of process when running in kernel
mode
2. Non-preemptive – runs until exits kernel mode, blocks, or voluntarily
yields CPU
Peterson’s Solution
 It is a software solution to the critical section problem

 Two process solution
 The two processes share two variables:
int turn;
Boolean flag[2]
The variable turn indicates whose turn it is to enter the critical section
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
do {
flag[i] = true;
turn = j;
while (flag[j] && turn = = j);
critical section
flag[i] = false;
remainder section
} while (true);
For p0
flag[0] = true;
turn = 1;
while (flag[1] && turn = = 1);
critical section
flag[0] = false;
For p1
flag[1] = true;
turn = 0;
while (flag[0] && turn = = 0);
critical section
flag[1] = false;
Synchronization Hardware
 Many systems provide hardware support for implementing the critical
section code.
 All solutions below based on idea of locking
 Protecting critical regions via locks
test_and_set Instruction
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv:
}
1. Executed atomically
2. Returns the original value of passed parameter
3. Set the new value of passed parameter to “TRUE”.
 Shared Boolean variable lock, initialized to FALSE
Solution:
do {
while (test_and_set(&lock));
/* critical section */
lock = false;
/* remainder section */
} while (true);
 Swap Instruction
void Swap (boolean *a, boolean *b)
{
boolean temp = *a;
*a = *b;
*b = temp:
}
 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 );
// critical section
lock = FALSE;
// remainder section
} while ( TRUE);
Semaphore
 Synchronization tool that provides more sophisticated ways (than Mutex
locks) for process to synchronize their activities.
 Semaphore S – integer variable
 Can only be accessed via two indivisible (atomic) operations
o wait() and signal()
 Originally called P() and V()
Definition of the wait() operation
wait(S) {
while (S <= 0)
; // busy wait
S--;
}
Definition of the signal() operation
signal(S) {
S++;
}

PROCESS SYNCHRONIZATION Dsatm

Uploaded by

Copyright:

Available Formats

PROCESS SYNCHRONIZATION Dsatm

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

PROCESS SYNCHRONIZATION Dsatm

Uploaded by

Copyright:

Available Formats

Operating Systems Module 2

 Cooperative process that can affect or be affected by other processes.

 All running asynchronously and sharing the data

 A bounded buffer could be used to share the data

 Allow at most BUFFER_SIZE-1 items in buffer

 Add an integer variable counter initialized to 0.

Producer process code

while (counter == BUFFER_SIZE) ;

Consumer process code

 Both process work correct separately, they may not function

 counter++ could be implemented as

 counter-- could be implemented as

 Consider this execution interleaving with “count = 5” initially:

Critical section problem

 Critical section problem is to design protocol to solve this

Solution to Critical-Section Problem

Two approaches depending on if kernel is preemptive or non- preemptive

 It is a software solution to the critical section problem

 Shared Boolean variable lock initialized to FALSE; Each process has a

You might also like