Chapter 5Concurrency: Mutual Exclusion and Synchronization

Chapter 5Concurrency: Mutual Exclusion and Synchronization

Operating Systems: Internals and Design Principles, 6/E William Stallings Chapter 5 Concurrency: Mutual Exclusion and

Synchronization Patricia Roy Manatee Community College, Venice, FL 2008, Prentice Hall Concurrency Problem: A Simple Example

char chin, chout; void echo() { chin = getchar(); chout = chin; putchar(chout); }

Concurrency Problem: A Simple Example Process P1 Process P2 . .

chin = getchar(); . . chin = getchar(); chout = chin; chout = chin; putchar(chout);

. . putchar(chout); . . Multiprogramming Concerns

Output of process must be independent of the speed of execution of other concurrent processes Competition among Processes for Resources Mutual Exclusion

Critical sections Deadlock Starvation Key Terms

Race Condition Example Process P1 Process P2 . . chin = getchar(); .

. chin = getchar(); chout = chin; chout = chin; putchar(chout); . .

putchar(chout); . . Requirements for Mutual Exclusion Only one process at a time is allowed in

the critical section for a resource A process that halts in its noncritical section must do so without interfering with other processes No deadlock or starvation Requirements for Mutual

Exclusion A process must not be delayed access to a critical section when there is no other process using it No assumptions are made about relative process speeds or number of processors A process remains inside its critical section

for a finite time only Mutual Exclusion Approaches Software approach Appendix A Hardware support, using special-purpose

machine instructions Support within OS or a programming language Semaphore, Monitors, Message Passing Mutual Exclusion: Hardware Support

Interrupt Disabling A process runs until it invokes an operating system service or until it is interrupted Disabling interrupts guarantees mutual exclusion Disadvantages:

Processor is limited in its ability to interleave programs Will not work in multiprocessor architecture Mutual Exclusion: Hardware Support Compare&Swap Instruction

int compare_and_swap (int *word, int testval, int newval) { int oldval; oldval = *word; if (oldval == testval) *word = newval; return oldval;

} Mutual Exclusion Mutual Exclusion: Hardware Support Exchange instruction

void exchange (int *register, int *memory) { int temp; temp = *memory; *memory = *register; *register = temp; }

Mutual Exclusion Mutual Exclusion MachineInstruction Advantages Applicable to any number of processes on a single processor

Processes on multiple processors? as long as processors share main memory It is simple and therefore easy to verify It can be used to support multiple critical sections; each critical section can be defined by its own variable (e.g. bolt1, bolt2, etc.)

Mutual Exclusion MachineInstruction Disadvantages Busy-waiting consumes processor time Starvation? Starvation is possible when a process leaves a critical section and more than one process is

waiting Deadlock? Semaphores Special variable called a semaphore is used for signaling

If a process is waiting for a signal, it is suspended until that signal is sent Semaphores Semaphore is a variable that has an integer value May be initialized to a nonnegative number

Wait operation decrements the semaphore value Signal operation increments semaphore value Semaphore Primitives Example of Semaphore

Mechanism Example of Semaphore Mechanism Mutual Exclusion Using Semaphores

Mutual Exclusion Using Semaphores Processes Using Semaphore Binary Semaphore Primitives

Producer/Consumer Problem One or more producers are generating data and placing these in a buffer One or more consumers are taking items out of the buffer one at time Only one producer or consumer may

access the buffer at any one time Producer cant add data into full buffer and consumer cant remove data from empty buffer Buffer

Producer producer: while (true) { /* produce item v */ b[in] = v; in++; }

Consumer consumer: while (true) { while (in <= out) /*do nothing */; w = b[out];

out++; /* consume item w */ } Incorrect Solution 32

Correct Solution Semaphores Circular Buffer

Producer with Circular Buffer producer: while (true) { /* produce item v */ while ((in + 1) % n == out) /* do nothing */; b[in] = v; in = (in + 1) % n

} Consumer with Circular Buffer consumer: while (true) { while (in == out) /* do nothing */;

w = b[out]; out = (out + 1) % n; /* consume item w */ } Semaphores

Semaphores Semaphore Implementation: Atomic Primitives Mutual Exclusion MachineInstruction vs. Semaphore

Mutual Exclusion MachineInstruction vs. Semaphore Mutual Exclusion Approaches Software approach Appendix A Hardware support, using special-purpose

machine instructions Support within OS or a programming language Semaphore, Monitors, Message Passing Monitor

Mutual Exclusion Approaches Software approach Appendix A Hardware support, using special-purpose machine instructions Support within OS or a programming

language Semaphore, Monitors, Message Passing Message Passing Enforce mutual exclusion Exchange information

send (destination, message) receive (source, message) Synchronization The receiver cannot receive a message

until it has been sent by another process What happens to a process after it issues a send or receive primitive Sender and receiver may or may not be blocked (waiting for message) Synchronization

Blocking send, blocking receive Both sender and receiver are blocked until message is delivered Nonblocking send, blocking receive Sender continues on Receiver is blocked until the requested

message arrives Nonblocking send, nonblocking receive Neither party is required to wait Addressing Direct addressing

Send primitive includes a specific identifier of the destination process Receive primitive may/may not know ahead of time from which process a message is expected Receive primitive could use source parameter to return a value when the receive operation has been performed

Addressing Indirect addressing Messages are sent to a shared data structure consisting of queues Queues are called mailboxes One process sends a message to the mailbox

and the other process picks up the message from the mailbox Indirect Process Communication General Message Format

Mutual Exclusion Using Messages (1) Assume blocking receive primitive & nonblocking send primitive

Mutual Exclusion Using Messages (2) Producer/Consumer Messages Readers/Writers Problem

Any number of readers may simultaneously read the file Only one writer at a time may write to the file If a writer is writing to the file, no reader may read it How is this problem different from mutual

exclusion problem? Cast it to a mutual exclusion problem? Any Problem with This Solution? Readers have Priority

Writers Have Priority The following semaphores and variables are added: A semaphore rsem that inhibits all readers while there is at least one writer desiring access to the data area A variable writecount that controls the setting of

rsem A semaphore y that controls the updating of writecount A semaphore z that prevents a long queue of readers to build up on rsem Writers have Priority

Writers have Priority Writers have Priority Message Passing

Note: count is initialized to the maximum possible number of readers, e.g., 100.

Recently Viewed Presentations

  • Ohm&#x27;s law: e = R·I

    Ohm's law: e = R·I

    Ohm's Law Experiments show that for many materials, including most metals, the resistance remains constant over a wide range of applied voltages or currents This statement has become known as Ohm's Law V = I R Ohm's Law is an...
  • Taxonomy Why did we feel fruit?  What is

    Taxonomy Why did we feel fruit? What is

    The species name is always lowercase Binomial Nomenclature Bi means two Nomen means name A binomial nomenclature is a classification system using two names to identify an organism Dichotomous Key tool that allows the user to determine the identity of...
  • Where do we start?  Create the Universe  Form

    Where do we start? Create the Universe Form

    Create the Universe Form the Earth and elements move the elements into their correct positions build the atmosphere and oceans Controls on CO2 CO2 is controlled by a global scale feedback loop with a time scale of >10,000 years Consider...
  • Cover sample. Title runs here in font Times New Roman 36 pt.

    Cover sample. Title runs here in font Times New Roman 36 pt.

    We have therefore developed a lot of support and run networks to explain how this new AO will work and how you can support your students in the classroom. ... Title runs here in font Times New Roman 36 pt....
  • The Many Manifestations of A Cerebellar Timing System

    The Many Manifestations of A Cerebellar Timing System

    THE MANY MANIFESTATIONS OF A CEREBELLAR TIMING SYSTEM Author: Mark W. Geisler Last modified by: ... Spinal Reflex Pathways Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide...
  • Pengantar Ilmu Ekonomi

    Pengantar Ilmu Ekonomi

    Dosen : Drs. Octo Rianto, MM S-1 : Jurnalistik (1989, IISIP Jakarta) S-2 : Manajemen Keuangan (1998, STIE IPWI Jakarta) Kasubbag. Kemahasiswaan FIP UNJ.
  • SimpleDB Overview - Massachusetts Institute of Technology

    SimpleDB Overview - Massachusetts Institute of Technology

    SimpleDB Overview 9/21/2016 What is SimpleDB? A basic database system SQL Front-end (Provided for later labs) Heap files (Lab 1) Buffer Pool (Labs 1-6) Basic Operators (Labs 1 & 2) Scan, Filter, JOIN, Aggregate Transactions (Lab 3 or 4) Query...
  • Modeling Vegetation Dynamics with LPJ-GUESS

    Modeling Vegetation Dynamics with LPJ-GUESS

    Katie Ireland, Andy Hansen, and Ben Poulter. Modeling Vegetation Dynamics with LPJ-GUESS