CS3103-Lecture-5

Synchronization

Backgrouond

• Concurrent access to shared data may result in data inconsistency – race condition

• Maintianing data consistency requires mechanisms to ensure the orderly execution of coorperating processes/threads

Race Condition

• Example: two thrads access shared variable Y
  • Thread 1 : Y = Y + 1
  • Thread 2 : Y = Y * 2
    

Critical Section

• Parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access

• This protected section is the critical section or critical region
  

• A good solution of CS satisfies following conditions

  • Mutual Exclusion: If one process is executing in tis CS, then no other processes can be executing in CS
  • Progress: If no process is executing in CS and some processes wish to enter CS, then the selection of the porcesses to enter the CS next should not be postponed forever
  • Bounded Waitting: A bound must exist on the number of times that other processes are allowed to enter their CS after a process has made a request to enter its CS and before that request is granted
  • Independence: The solution should not depend on the speed or the number of processors, as well as other factors that can affect the execution of the processes. The solution should be able to handle any number of processes, and any processing speed without being affected by external factors

Mutex Lock

• A mutex lock (called mutex for short) is a mechanism providing mutual exclusion
  • Mutex ensures that only one thread has access to a critical section
  • Using operations like a lock and unlock
  • Used to protect the critical sections

Peterson’s Solution

• Two processes running on two cores: index 0 and 1

• Assume that the LOAD and STORE instructions are atomic

  • Atomic: non-interruptable

• The processes share two variable: int turn and Boolean flag[n](n=0 or 1)

  • turn indicates whose turn it is to enter CS
  • flag[n]=TRUE implies that process P0 is ready to enter(similar for flag[1])
    

• Mutual exclusive

  • If one process is in CS, the other process cannot enter CS
    • Say, P0 is in CS, then flag[0] == TRUE
    • When P1 tests while condition, turn == 0, so P1 is blocked at the while loop until P0 leaves CS and flag[0]== FALSE
  • If both porcesses try to enter the CS
    • If both of them enters, it must be flag[0]==flag[1]== TRUE
    • P0 entring CS requires turn==0;P1 enter CS requires turn==1
      • Both turn==0 and turn==1, which is impossible

• Progress

  • If only one process wants to enter CS, it can enter
    • when P0 tests the while condition, P1 does not set flag[1] = TRUE, i.e., flag[1]==FALSE, so P0 can enter CS
  • If both processes want to enter CS, one of them can enter
    • If both P0 and P1 have set the flag to be TRUE, then they continue to set turn
    • Eventually, turn is either 0 or 1, and the coresponding process can enter CS

• Bounded waitting

  • If both want to repeatedly enter CS, they will do so in turn
    • When P0 leaves CS, it sets flag[0]==FALSE, so P1 immediately can enter CS
    • If P0 set flag[0]==TRUE before P1 enters CS, P1 cannot leave the while loop
    • However, before P0 enters CS again, it has to set turn==1, so P1 still can leave the while loop and enter CS

Hardware Support for Synchronization

• Many systems porvide hardware spport for critical section code
• Uniprocessors - could disable interrupts
  • Currently running code would excute without preemption
  • Generally too inefficient: OS using this not broadly scalable
• Modern machines provide special atomic hardware instructions
  • Two widely used types:
    • Test memory word and set value
    • Swap contents of two memory words

TestAndSet Instruction

Swap Instruction

Semaphore

• Semaphore S – integer variable

• Two standard operations modfy S: wait() and signal()

  • Originally called P() and V()

• Counting semaphore - S value can be positive integers

  • Multiple copies of the shared resource

• Binary semaphore - S value can be 0 or 1;

• Must guarantee no two processes 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 critical section problem

Semaphore with Busy Waiting

• Spinlock
  • Implementation is simple
  • Little busy waiting if critical section rarely occupied
  • Not a good solution if applications spend lots of time in critical sections

Semaphore with No Busy Waiting

• Each semaphore has an associated waiting queue

  • Each entry in a waiting queue has two data items
    • value
    • pointer to next record in the list

• Two operations:

  • block - place the process invoking the operation in the appropriate waiting queue
  • wakeup - remove one of processes in the waiting queue and place it in the ready queue

Deadlock

• Deadlock – is a situation in which no process can proceed because each waits for another to release a lock
• Let S and Q be two semaphores initialized to 1
  

Classical Synchronization Problems

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem

Bounded-Buffer Problem

• Multiple producers and consumers share a single buffer of size N
  • Producers write data to the buffer; must block if the buffer is full
  • Consumers read data from the buffer; must block if the buffer is empty
• A solution: use three semaphores
  • mutex(boolean, initialized to be 1):protect access to the critical sections
  • full(initialized to be 0): to count the ocuupied slots in the buffer
  • empty(initialized to be N): to count the available slots in the buffer
    

Readers-Writers Problem

• A data set is shared among a number of processes

  • Readers: only read the data set; do not perform any write
  • Writers: can both read and write

• Target:

  • Multiple readers can access at the same time.
  • Only one single writer can access at the same time(no reader access)

• A solution: two semaphores and a shared variable

  • Two boolean semaphores
    • mutex intialized to 1
    • wrt initialized to 1
  • Shared integer variable readcount initialized to 0
    

Dining-Philosophers Problem

• Five philosophers
• Two chopsticks next to each philosopher
• A philosopher sometimes thinks, sometimes eats, repeatedly
• Need two chipsticks to eat
• Hold the chopstick(s) until this time of eating finished
  
• A solution:
  • Binary semphores chopstick[5], all initialized to 1
    

Condition Variable

• There are mau cases where a thread wishes to check whether a condition is true before continuing its execution
• Example:
  • A parent thread might wish to check whether a child thread has been completed, before continue to execute
    • join
      

Parent Waiting for Child: Spin-based Approach

• Inefficient as the parent spins and wastes CPU time

• Can we put the parent to sleep until the condition we are waiting ofr comes true?

• Condition variable

  • Waiting on the condition
    • An explicit queue that threads can put themselves on when some state of execution is not as desired
  • Signaling on the condition
    • Some other thread, when it changes said state, can wake one of those waiting threads and allow them to continue.

• Declare condtion variable
  

  • Proper initialization is required

• Operation (the POSIX calls)
  

  • The wait() call takes a mutex as a parameter
    • The wait() call release the lock and put the calling thread to sleep
    • When the thread wakes up, it must re-acquire the lock

Parent waiting for Child: Using Condition Variable

Importance of the state variable done

• Imagine the case where the child runs immediately
  • The child will signal, but there is no thread asleep on the condtion.
  • When the parent runs, it will call wait and be stuck
  • No thread will ever wake it
    

Importance of the mutex

• If one does not need to hold a lock in order to signal and wait
• There is race condition
  • The parent calls thr_join()
    • The parent checks done, it will see that it is 0 and try to go to sleep
    • Just before it calls wait to go to sleep, the parent is interrupted and the child runs
  • The child cahnges the state variable done to 1 and signals
  • When the parent runs again, it sleeps forever.
    

Producer-Consumer Problem

• Suppose the buffer size is 1

• Producer

  • Produce data items
  • Wish to place data items in a buffer

• Consumer

  • Grab data items out of the buffer and consume them in some way

• Producer

  • Produce data items
  • Wish to place data items in a buffer

• Consumer

  • Grab data items out of the buffer and consume them in some way

• Producer puts an integer into the shared buffer and loops

• Consummer gets the data out of that shared buffer
  

The Put and Get Routines

• Only put data into the buffer when count is zero
  • i.e. when the buffer is empty
• Only get data from the buffer when count is one
  • i.e. when the buffer is full
    

Using Condition Variable

• A condition variable cond and associated lock mutex

• p1-p3: A producer waits for the buffer to be empty

• c1-c3: A consumer waits for the buffer to be full

• with just a single producer and a single consumer, the code works
  

Trace

Why the Solution is Broken?

• The problem arises because:
  • After the producer woke, but before ever ran, the state of the bounded buffer changed by
  • There is no guarantee that when the woken thread runs, the state will still be as desired Mesa semantics
    • Virtually every system ever built employs Mesa semantics
  • Hoare semantics provides a stronger guarantee that the woken thread will immdiately upon being woken.

Fix the Problem

• Consumer wakes up and re-checks the shared variable
  • If the buffer is empty, the consumer simply goes back to sleep.
• Is it correct now?
  

Trace

Fix the Problem

• Using two condtion variable and while
  • Producer threads wait on the condition empty, and signal fill
  • Consumer threads wait on fill and signal empty
    

Multiple Buffer Slots

• More concurrency and efficiency => Add more buffer slots
• Reduce context switches