Process Synchronization

Definition:

• Solve CSP

Race condition & Critical Section Prblem

• Race Condition
• Critical Section Problem, CSP:
  • consider system of n processes P1 to Pn-1
  • Each process has common variables, writing files,…
  • When one process in critical section, no other may be in its critical section
  • Requirements:
    1. Mutual exclusion: if process $P_i$ is executing in its $C{S}_i$ then $P_j$ cannot execute $C{S}_j$
    2. Progress: if no process $P_i$ is executing in $C{S}_i$, then only those processes $P_j$ that are not executing in $\{REMAI{N}_j\}$ can be considered to enter $\{C{S}_j\}$ next and this selection cannot be postponed indefinitely.
    3. Bounded waiting: Once a process $P_i$ has made a request to enter $C{S}_i$ and before that request is granted, the number of times that $P_J$ accessing $C{S}_j$ should be bounded
• Solution: Each process must “ask permission” to enter entry of critical section, may follow critical section with exit section, then remainder section
  • with general structure:
    • Entry section
    • Critical section
    • Exit section
    • Remain section
  • Peterson’s solution:
    • Idea: if we have 2 processes, use 2 variables to control the access on critical sections
    • int turn: indicates whose turn is it to enter critical section (turn = i so i can enter)
    • boolean flag[2]: list of 2 booleans denoting candidate process is ready to enter (flag[i]=true means process i is waiting to enter)
    • ex: for process i

      while (true) {
          flag[i] = true;
          turn = j;
          while (flag[j] && turn == j); // wait if its j's turn and j is in critical section
          /* critical section */
          flag[i] = false // i is no longer candidate
          /* remainder section */
      }

    • Problem: only 2 processes running at the same time
      • solution Memory Barrier

Synchronization tools

• Mutex Lock
• Semaphore: similar to a traffic light
• Monitor: similar to restaurant and waiter
• Monitor vs Semaphore:

Semaphore	Monitor
It is an integer variable.	It is an abstract data type
The value of this integer variable tells about the number of shared resources that are available in the system.	It contains shared variables
When any process has access to the shared resources, it performs the ‘wait’ operation (using wait method) on the semaphore	It also contains a set of procedures that operate upon the shared variable
The number of threads is dependent on the available shared resources	Allow one thread at a time
It doesn’t have condition variables.	It has condition variables

Typical Synchronization problem

• Bounded-buffer:
  • A buffer of n slots
  • Producer must stop inserting when full and consumer must stop consuming when empty
  • Solution: use 3 semaphores:
    • mutex: Mutex Lock, binary semaphore
    • Empty: count number of slots that are currently empty, initial = n
    • Full: count number of non-empty slot, intial = 0
    • * note that empty + full != n as one slot might being written to
    • Producer:

      do {
          wait(empty) // wait until empty > 0 then empty --
          wait(mutex) // acquire lock
          /* add data to buffer*/
          signal(mutex) // release lock
          signal(full) // full++
      } while (TRUE)

    • Consumer

      do {
          wait(full) // wait full > 0
          wait(mutex)
          /* remove data */
          signal(mutex)
          signal(empty)
      } while (TRUE)

• Read-writer synchronization problem:
  • A database with many writers and many readers
    • 2 readers at same time is ok
    • 1 writer and 1 (reader or writer) is not ok
      • 1 writer and 1 reader is not ok because: reader might read half old/half new data
  • → When writer is writing, writer have exclusive access to the shared data
  • Solution: 2 semaphores and an integer
    • mutex: a Mutex Lock to lock on readcount, (init to 1)
    • wrt: a Semaphore for writer (init to 1)
    • readcount: an integer to keep track of how many processes reading the database (init to 0)
    • Writer:

      do {
          wait(wrt); // wait for
          /* writing */
          signal(wrt); // done writing
      } while (TRUE);

    • Reader:

      do {
          wait(mutex); // wait and lock lock for readcount var 
          readcount++;
          if (readcount == 1){ // if there is no other reader, if there was another reader means no writer writing cuz that would have waited for writer to be done
        	  wait(wrt); // wait for writer done writing
          }
          signal(mutex); // done modifying readcount
          /* reading */
          wait(mutex) // wait and lock for readcount
          readcount--;
          if (readcount ==0){ // if there is no read other than this, let writers write
        	  signal(wrt);
          }
          signal(mutex); // done modifying readcount
      } while (TRUE)

• Dining-philosophers problem
  • Five philosophers seated around a circular table, each with a plate of spaghetti.
  • To eat, a philosopher needs two forks: the one to their left and the one to their right.
  • If a philosopher picks up both forks, they can eat, but they can only pick up 1 at a time.
  • After eating, they put down both forks and think (wait)
  • Solution with Semaphore:
    • use array of 5 semaphore chopstick[5] (each can be 0 or 1) (init to all 1)
    • Each Philosopher

        while (TRUE) {
        	wait(chopsticks[i]);
        	wait(chopsticks[(i + 1) % N]);
        	// Eat
        	signal(chopsticks[i]);
        	signal(chopsticks[(i + 1) % N]);
        	// Think
        }

    • This can lead to deadlock as each philosopher picks up their left forks at the same time
  • Solution with Monitor

      monitor DiningPhilosophers
      {
      	enum (THINKING; HUNGRY, EATING) state [5];
      	condition self [5];
      	
      	void pickup (int i) {
      		state [i] = HUNGRY;
      		test (i) ;
      		if (state[i] != EATING) self[i].wait();
      	}
      	
      	void putdown (int i) {
      		state [i] = THINKING;
      		// test left and right neighbors
      		test ((i + 4) % 5); 
      		test ((i + 1) % 5);
      	}
      	
      	void test (int i) {
      		// if i am hungry and left and right folk are free
      		if ((state[(i + 4) % 5] != EATING) 
      			&& (state [i] == HUNGRY)
      			&& (state [(i + 1) % 5] != EATING) ) {
      			state[i] = EATING ;
      			self [i].signal () ;
      		}
      	}
      	
      	initialization_code () {
      		for (int i = 0; i < 5; i++)
      		state [i] = THINKING;
      	}
      }

    • Each philosopher invokes pickup() and putdown()

      ```c
      DiningPhilosopher.pickup(i)
      /* EAT */
      DiningPhilosopher.putdown(i)
        ```
      

    • No deadlock, but starvation is possible