Race if a process is ready to enter the

Race Condition: several processes
access and manipulate the same data concurrently, outcome depends on which
order each access takes place.

The Critical-Section Problem

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

Peterson’s Solution

Synchronization Hardware

Mutex Locks

Semaphores

Classic Problems of Synchronization

Monitors

Synchronization Examples

Alternative Approaches

 

Critical Section Problem

Consider system of n
processes {p0, p1,
… pn-1}. Each process has critical
section segment of code. Process may be changing common variables, updating
table, writing file, etc. When one process is 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.

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

·        
Assume
that each process executes at a nonzero speed

·        
No
assumption concerning relative speed of the n processes

Critical-Section Handling in OS

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

·        
Preemptive – allows preemption of process when
running in kernel mode

·        
Non-preemptive
– runs until exits kernel mode, blocks,
or voluntarily yields CPU

·        
Essentially
free of race conditions in kernel mode

Peterson’s Solution

It is Good algorithmic description of solving the problem. It is restricted to two process solution. The two processes
share two data items:

int turn;

Boolean flag2

Here turn indicates whose turn it is to enter
the critical section and the flag array is used to indicate if a process
is ready to enter the critical section.

·        
Provable
that the three  CS requirement are met:

        1.   Mutual exclusion is
preserved

        2.   Progress requirement is satisfied

        3.   Bounded-waiting requirement is met

Synchronization Hardware

Many systems provide hardware support for implementing
the critical section code. All solutions are based on idea of locking e.g. protecting critical
regions via locks. Uniprocessors –
could disable interrupts i.e. currently running code would execute without
preemption which is generally too inefficient on multiprocessor systems because
operating systems using this not broadly scalable. Modern machines provide
special atomic hardware instructions e.g. Atomic = non-interruptible. It either test memory word and set value
or swaps the contents of two memory words

test_and_set  Instruction

It is executed atomically, returns the original value of passed
parameter and set the new value of passed parameter to “TRUE”.

compare_and_swap Instruction

ItExecuted atomically

?         
Returns
the original value of passed parameter “value”

?         
Set  the variable “value”  the value of the passed parameter “new_value”
but only if “value” ==”expected”. That is, the swap
takes place only under this condition.

Mutex Locks

Previous solutions are complicated and generally
inaccessible to application programmers. OS designers build software tools to
solve critical section problem. Simplest is mutex lock which protect a critical
section by first acquire() a lock then release() the lock. Calls
to acquire() and release() must be atomic. But this solution
requires busy waiting. This lock therefore called a spinlock.

Semaphore

It is a synchronization tool that does not require
busy waiting. Standard
operations: wait() and signal(); these are the only operations that can access
semaphore S. It an have counting (integer value can range over an
unrestricted domain) and binary (integer value can range only between
0 and 1) semaphores

Semaphore Usage

It can solve various synchronization problems and can implement a
counting semaphore S as
a binary semaphore.

Semaphore Implementation

Must guarantee that no two processes can execute the wait() and
signal() on the same semaphore at the same time. Thus, the
implementation becomes the critical section problem where the wait and signal
code are placed in the critical section. It could now have busy waiting
in critical section implementation. But implementation code is short and little
busy waiting if critical section rarely occupied.

Semaphore Implementation with
no Busy waiting

With each semaphore there is an associated waiting
queue, each entry in a waiting queue has two data items: value (of type
integer) and pointer to next record in the list. Two operations:

l       
block – place the process invoking the
operation on the appropriate waiting queue

l       
wakeup – remove one of processes in the waiting
queue and place it in the ready queue

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

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. It is solved via priority-inheritance
protocol.

Classical Problems of Synchronization

Classical problems used to test newly-proposed synchronization
schemes

1.     
Bounded-Buffer Problem

n buffers, each can hold one item, semaphore mutex
initialized to the value 1, semaphore full initialized to the value 0
and empty initialized to the value n.

2.     
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.

Problem – allow
multiple readers to read at the same time. Only one single writer can access
the shared data at the same time.

Several
variations of how readers and writers are considered – all involve some form of
priorities.

Shared Data

l       
Data
set

l       
Semaphore
rw_mutex initialized to 1

l       
Semaphore
mutex initialized to 1

l       
Integer
read_count initialized to 0

Readers-Writers Problem Variations

First 
variation – no reader kept waiting unless
writer has permission to use shared object

Second variation – once writer is ready, it performs the write ASAP

Both
may have starvation leading to even more variations

Problem
is solved on some systems by kernel providing reader-writer locks

3.     
Dining-Philosophers Problem

Philosophers
spend their lives alternating thinking and eating

Don’t interact with
their neighbors, occasionally try to pick up 2 chopsticks (one at a time) to eat
from bowl

Need
both to eat, then release both when done

In
the case of 5 philosophers

Shared
data

Bowl
of rice (data set)

Semaphore
chopstick 5 initialized to 1

Dining-Philosophers Problem Algorithm

Deadlock
handling

Allow
at most 4 philosophers to be sitting simultaneously at  the table.

Allow
a philosopher to pick up  the forks only
if both are available (picking must be done in a critical section.

 Use an asymmetric solution — an odd-numbered
philosopher picks up first the left chopstick and then the right chopstick.
Even-numbered philosopher picks up first the right chopstick and then the left
chopstick.

4.     
Problems with Semaphores

 Incorrect use of semaphore operations:

signal
(mutex)  ….  wait (mutex)

wait
(mutex)  …  wait (mutex)

Omitting
of wait (mutex) or signal (mutex) (or both)

Deadlock
and starvation are possible.

Monitors

A high-level abstraction that provides a convenient and effective
mechanism for process synchronization

Abstract data type, internal variables only
accessible by code within the procedure

Only one process may be active within the monitor at a time

But not powerful enough to model some synchronization schemes

Monitor Usage

Two operations are allowed on a condition variable:

x.wait() –  a process that invokes the
operation is suspended until x.signal()

x.signal()
– resumes one of processes (if any)
that  invoked x.wait()(If no x.wait()
on the variable, then it has no effect on the variable)

Condition Variables Choices

Options
include

Signal
and wait – P waits until
Q either leaves the monitor or it waits for another condition

Signal
and continue – Q
waits until P either leaves the monitor or it 
waits for another condition

Dining Philosophers Solution Using
Monitors

Each
philosopher invokes the operations pickup() and putdown() in the specific
sequence:

No
deadlock, but starvation is possible

Resuming Processes within a Monitor

If
several processes queued on condition x, and x.signal() executed, which should
be resumed?

FCFS
frequently not adequate

Thus
conditional-wait construct of the form x.wait(c) can be used

Where
c is priority number

Process
with lowest number (highest priority) is scheduled next

To
illustrate this new mechanism, allocate a single resource among competing processes
using priority numbers that specify the maximum time a process plans to use the
resource

Unfortunately
the monitor concept cannot guarantee the preceding access sequence will be
observed

Synchronization Examples

1.     
Windows Synchronization

Uses
interrupt masks to protect access to global resources on uniprocessor systems

Uses
spinlocks on multiprocessor systems

Spinlocking-thread
will never be preempted

Also
provides dispatcher objects user-land which may act mutexes, semaphores,
events, and timers

Events

An
event acts much like a condition variable

Timers
notify one or more thread when time expired

Dispatcher
objects either signaled-state (object available) or non-signaled
state (thread will block)

2.     
Linux Synchronization

Linux
provides:

Semaphores

atomic
integers

spinlocks

reader-writer
versions of both

On
single-cpu system, spinlocks replaced by enabling and disabling kernel
preemption

3.     
Solaris Synchronization

Implements
a variety of locks to support multitasking, multithreading (including real-time
threads), and multiprocessing

Uses
adaptive mutexes for efficiency when protecting data from short code
segments

Starts
as a standard semaphore spin-lock

If
lock held, and by a thread running on another CPU, spins

If lock
held by non-run-state thread, block and sleep waiting for signal of lock being
released

Uses
condition variables

Uses
readers-writers locks when longer sections of code need access to data

Uses
turnstiles to order the list of threads waiting to acquire either an
adaptive mutex or reader-writer lock

Turnstiles
are per-lock-holding-thread, not per-object

Priority-inheritance
per-turnstile gives the running thread the highest of the priorities of the
threads in its turnstile

4.     
Pthreads Synchronization

Pthreads
API is OS-independent

It
provides:

mutex
locks

condition
variable

Non-portable
extensions include:

read-write
locks

spinlocks

Alternative Approaches

1.      Transactional Memory

A memory
transaction is a sequence of read-write operations to memory that are performed
atomically.

2.      OpenMP

OpenMP
is a set of compiler directives and API that support parallel progamming.

3.      Functional Programming Languages

Functional
programming languages offer a different paradigm than procedural languages in that
they do not maintain state.

Variables
are treated as immutable and cannot change state once they have been assigned a
value.

There
is increasing interest in functional languages such as Erlang and Scala for
their approach in handling data races

 

 

• Each
process has critical section of code, where it is manipulating
data 
?  To solve critical section problem each
process must ask permission to enter critical section in entry
section, follow critical section with exit
section and then execute the remainder section 

 ?  Especially
difficult to solve this problem in preemptive kernels • Peterson’s
Solution: solution for two processes 
  ?  Two processes share two
variables: int turn and Boolean flag2 

??turn:?whose
turn it is to enter the?critical section ? flag: indication
of whether or not a process is ready to enter critical section 

• Modern
machines provide atomic hardware instructions: Atomic =
non-interruptible • Solution using Locks