Chapter 7: Process Synchronization

• Why synchronization
• Primitive software approaches
• Hardware approaches
• Semaphores
• Classic Problems for Synchronization

Bacground

• Concurrent access to shared data may result in data inconsistency.
• Maintaining data consistency requires machanisms to ensure the orderly execution of cooperating processes.

Bound-buffer

• Atomic operation: means an operation that completes in its entirely without any interrupt.
• If bothe the producer and consumer attempt to update the buffer concurrently, the assembly language statements may get interleaved.
• Interleaving depends on how the producer and consumer processes are scheduled.

Race condition

• The situation where several processes access and manipulate shared data concurrently.
• The final value of the shared data depends upon which process finishes last.

To prevent race condition, concurrent processes must be synchronized.

The Critical-section problem

• The n processes compete to use some shared data.
• Each process has a code segment, called critical section, in which the shared data is accessed.
• How to ensure that when one process is executing in its critical section, no other process is allowed to execute in its critical section.
• To solve the critical-section problem
  • To design a protocol that the processes can use to cooperate.
  • Each process must behave properly:
    • Entry section
    • Critical section
    • Exit section
    • Reminder section

Solution Critical

• Mutual Execution: If process $P_i$ is executing in its critical section,then no other process can be executing in their critical sections.
• Progress: If no process is executing in its critical section and there exits some processes that wishes to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.
• Bound Waiting: A bound must exists on the number of times that other processes are allowed to enter their critical section when a process has made a request to enter its critical section and before the request is granted.

2-Processes:

Algorithm 0:

• Only 2 processes, $P_0$ and $P_1$

• General structure of process $P_i$ (other process $P_j$)

  do{
      entry section
          critical section
      exit sectiom
          reminder sectiom
  }while(1)
  

• Processes may share some common variables to synchronize their actions.

• int i = 0 or 1

• int j = 1-i

Algorithm 1:

• Shared variables:

  • int turn; // initially turn = 0
  • turn = i; // $P_i$ can enter its critical section

• Process $P_i$

  do{
      while(turn != i);
        critical section
      turn = 1-i
        reminder section
  }while(1);
  

• Satisfies mutual exclusion, but not progress requirement.

Algorithm 2:

• Shared variables:

  • boolean flag[2]; // initially flag[0] = flag[1] = false
  • flag[i] = true; // Intention :$P_i$ is ready to in his critical section

• Process $P_i$

  do{
      while(!flag[i]);
        critical section
      flag[i] = false;
        reminder section
  }while(1);
  

• Satisfies mutual exclusion, but not progress requirement.

Algorithm 3

• Combined shared variables of algorithms 1 and 2.

• Process $P_i$

  do{
      while(flag[j] && turn == i);
        critical section
      flag[i] = false;
        reminder section
  }while(1);
  

• Meets all three requirements; solves the critical-section problem for two processes.

N-processes — barkery algorithm

• Critical section for n process:

  • Before entering its critical section, a process receives a number.
  • The holder with the smallest number will enter the critical section.
  • If $P_i$ and $P_j$ receive the same number, if i < j , then $P_i$ is served first; else $P_j$ is served first.
  • The numbering scheme is always generates numbers in increasing order of enumeration.

• Notation

  • $(a, b) < (c, d)$ if $a < c$ or if $a = c and b < d$

  • $max(a_0, a_1, \dots, a_{n-1})$ is a number, k, such that $k \ge a_i$ for $i = 0, 1, 2, \dots, n-1$

  • Shared data

    boolean choosing[n];

    int number[n];

  • Data structures are initialized to false and 0 respectively.

    // 执行 P_i
    do{
        // entry section
        choosing[i] = true;
        // 找出此时所有进程的数字中数字最大的赋予number[i]
        number[i] = max(number[0],number[1],...,number[n-1]);
        choosing[i] = false;
        
        for(j=0; j < n; j++){
            // 只有当 choosing[j]为 false 时，即进程 P_j 没有正在执行 entry section 时，才会跳过等待，否则会等待choosing[j] 结束
            while(choosing[j]);
            
            //当此时有进程在等待，并且等待的进程数字均小于P_i的值时，会一直等待其他所有的数字更小的进程结束。
            while(number[j]!=0 && (number[j], j) < (number[i], i));
        }
            critical section
            number[i] = 0; // 此进程结束，其他进程不需要再等待了
            reminder section
    }while(1);
    

  • If $P_i$ is in its critical section and $P_j$ has already chosen its number[j] !=0, then

    (number[i], i) < (number[j], j)

    or number([i], i) is the smallest of {(number[0], 0), (number[1], 1),...}

  • Mutual execution. Only the process with the smallest (number[i],i) can enter its critical section.

  • Process requirement and bounded waiting. The process enter their critical section with a first-come, first-serviced business.

Hardware

• Interrupt enabling and disabling:
  • Can be applied to Uni-process.
  • Not feasible for Multi-process.
• Special Memory instruction
  • TestAndSet
  • Swap

TestAndSet

• Test and modify the content of a word ==atomically==.

  // 将输入的值赋为 true，再返回输入的值
  boolean TestAndSet(boolean &target){
      boolean rv = target;
      target = true;
      return rv;
  }
  

• Shared data:

  boolean lock = false;

• Process $P_i$:

  do{
      // 当且仅当 lock == false,才会进入 enter section
      while(TestAndSet(lock));
        critical section
      lock = false;
        reminder section
  }while(1);
  

Swap

• Swap two variables ==atomically==.

  void Swap(boolean &a, boolean &b){
      boolean temp = a;
      a = b;
      b = temp;
  }
  

• Shared data:

  boolean lock = false;

• Process $P_i$:

  do{
      boolean key = true;
      // 检查是否锁上了，若是，等待，否则，上锁并拿走钥匙。
      while(key) swap(key,lock);
          critical section
      lock = false;
          reminder section;
  }
  

Bounded-Waiting Mutual Exclusion with TestAndSet

• Shared data:

  boolean waiting[n];

  boolean lock;

• Process $P$:

  do{
      waiting[i] = true;
      boolean key = true;
      // 若没有其他进程进入critical section, while内部执行一次后，key 变为 false, lock 变为了 true。使其它进程无法进入。若有，则等待 lock 变为 false。
      while(waiting[i]&&key) key = TestAndSet(lock);
        critical section
      j = (i+1)%n;
      //循环检查是否有 其他进程在等待进入 critical section
      while(j != i && !waiting[j]) j = (j+1)%n;
      //若没有其他进程在等在，就解锁。
      if(j == i) lock = false;
      //若有其他进程等待，告知其他进程不需要等待，使其执行
      else waiting[j] = false;
        reminder section
  }while(1);
  

Semaphores

• A semaphore can be viewed as an object which has an integer value and ==three atomically operations==:
  • A semaphore can be initialized via a nonnegative value.
  • The ==wait== operation decrements the semaphore value. If the value becomes negative, then the process executing the wait is blocked.
  • The ==signal== operation increments the semaphore value. If the value becomes non negative, then the process blocked by a wait operation is unblocked.

Critical section of N processed

• Shared data:

  semaphore mutex; //initial mutex = 1;

• Process $P_i$:

  do{
      wait(mutex);
          critical section
      signal(mutex);
          reminder section
  }while(1);
  

Implementation

• Assume two simple operations:

  • ==block==: suspends the process that invokes it.
  • ==wakeup(P)==: resumes the execusion of a blocked process P.

• defines a semaphore as a record

  typedef struct{
      int value;
      struct process *L;
  }semaphore;
  

• Semaphores operation now defined as

  ==wait(S)==

  S.value--;
  if(S.value < 0){
      add this progress to S.L;
      block;
  }
  

  ==signal(S)==

  S.value++;
  if(S.value<0){
      remove a process P from S.L;
      wakeup(P);
  }
  

  $S$ : describe the condition of the struct Semaphore

  $S = 1$ : the semaphore queue the buffer are both empty.

  $S = 0$ : the buffer(can only contain an object) is blocked, but the semaphore is enmpty

  $S = -n$ : n - the number of object waited in semaphore queue. The buffer is blocked.

• Semaphores: As a general synchronization tool

  • Only after A is executed in $P_i$, execute B in $P_j$.

    Use semaphore flag initialized to 0.

    $P_i$ $P_j$

    $\vdots$ $\vdots$

    A wait(flag)

    signal(flag) B

Deadblock starvetion

• ==Deadlock==: two or more processes are waiting indefinitely for an event that can only cause by one of the waiting process.

  $P_0$ $P_1$

  waits(S); waits(Q);

  waits(Q); waits(S);

  $\vdots$ $\vdots$

  signal(S) signal(Q);

  signal(Q) signale(S);

• ==Starvation== : indefinite blocking. A process may never be removed from the semaphores queue in which it is suspended.

Types

• Counting semaphore : integer value can range over a unrestricted domain.
• Binary semaphore : integer value can range only range between 0 and 1; can be simplifier to implement.
  • Can implements a counting semaphore S by a binary semaphore.

Binary semaphores implementing ==S== as a counting semaphore

• Data structures:

  binary-semaphores S_1, S_2;

  int C;

  $S_1$ : use as enter section

  $S_2$ : use to describe the condition of the buffer C

  C : use to describe how many space are left in buffer C

• Initialization:

  S1 = 1;

  S2 = 0;

  C = initial value of semaphore S

• ==wait== operation

  wait(S1);
  C--;
  if(C<0){signal(S1); signal(S2);}
  signal(S1)
  

• ==signal== operation

  wait(S1);
  C++;
  if(C<=0){signal(S2);}
  else signal(S1);
  

Classical problems of synchronization

• Bounded-buffer problem
• Reader-writers problem
  • Readers have priorities
• Dining-philosophers problem
  • With deadlock solution
  • Deadlock free solution

Bounded-buffer problem

shared data

// the producter produce the item

// which is consumed by the consumer.

// The number of buffers is bounded.

Semaphore

mutex = 1; // To protect the buffer pool

full = 0; // To count the number of full buffers

empty = 0; // To count the number of empty buffers.

Why do not just make one parameter to count the number of buffer?

To protect the buffer which is in the condition between full and empty?

producer process

while(1){
    ...
    produce an item in next p
    ...
    wait(empty); //wait--
    
    wait(mutex); //protect the buffer pool
    ...
    add next p to buffer;
    ...
    signal(mutex);
    
    signal(full); //full++
}

consumer process

while(1){
    wait(full); //full--
    
    wait(mutex); //protect the buffer pool
    ...;
    remove one buffer to next c;
    signal(mutex);
    
    signal(empty);//empty++
    ...
    comsume the item in next c;
    ...
}

Readers-writers problem

• Readers-writers problem

  • Readers first

    No reader will be waited unless a writed has already obtained permission to use the shared object.

  • Writers first

    Once a writer is ready, that writer performs its write opereation. (In other words, if a writer is waiting to access the object, no new readers may start reading.)

  • …

• Shared data

  • Data set
  • Semaphore ==mutex== : initialize to 1, used to ensure mutual exclusion when the variable readcount is updated.
  • Semaphore ==wrt== : initialize to 1, common in both the reader and writer, used as a mutual exclusion semaphore for the writer.
  • Integer ==readcount== : initialize to 0, keeps track of how many processes are reading the object.

• Shared data

  Semaphore

  ​ mutex = 1;

  ​ wrt = 1;

  ​ int readcount = 1;

Readers First

• Writers process

  wait(wrt);
    writing is performed
  signal(wrt);
  
    reminder section
  

• Reader process

  wait(mutex);
  readcount++;
  if(readcount==1) wait(wrt)
  signal(mutex);
    reading is performed
  wait(mutex);
  readcount--;
  if(readcount==0) signal(wrt);
  signal(mutex);
    reminder section
  

Dinging-Philosophers problem

• The scene:

  • 1 round table
  • 1 bowl of rice
  • 5 plates
  • 5 chopsticks
  • 5 chairs

• The actor: 5 philosophers

• The plot

  1. A philosopher sends his life thinking, eating, and starving.
  2. When a philosopher gets hungry, he tries to picks up two chopsticks that are closest to him. He may pick up only one chopstick at a time.
  3. When he gets both chopsticks at the same time, he eats without releasing his chopsticks.
  4. When he is finished eating, he puts down both of his chopsticks and thinks again.

• The dining-philosophers problem is concidered as a classic sychronization problem, because it is an example of a large class of concurrency-control problem.

• The dining-philosophers problem is a simple representation of the need to allocate several limited resources to many processes in a deadlock-free and starvation-free manner.

ch7_2.png

• Shared data

  • semaphore chopstick[5] = {1,1,1,1,1};

    // One chopstick can be picked by one philosopher at a time

    do{
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]);
            ...
            eat
            ...
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5]);
            ...
            think
            ...
    }while(1);
    

• ==semaphore coord = 4==

  //同一时刻只有 (n-1) 个人申请进餐，保证不会出现死循环的现象。

  //Only four philosophers can try to eat simultaneously

  Philosopher i

  wait(coord);
  wait(chopstick[i]);
  wait(chopstick[(i+1)%5]);
      ...
      eat
      ...
  wait(chopstick[i]);
  wait(chopstick[(i+1)%5])
  wait(coord);
      ...
      think
      ...
  }while(1)
  

  ​

​