[ OS ] 06. Process Synchronization

🖥️ Background

• Process communication method
  - Message passing
  - Shared memory ➡️ confliction can occur !!
• Producer-consumer problem
  - An example of communication through shared memory

Synchronization Problem

➡️ Switching can occur during modification operations !

• Problematic situation
  - Initial value of counter is 5
  - Producer increased counter, and consumer decreased counter concurrently
  - Ideally, counter should be 5. But...

Process Synchronization

• Race condition ➡️ 특정한 순서에 따라서 결과가 달라져서 나오는것, 일종의 Bug
  • A situation, where several processes access and manipulate the same data concurrently
  • The outcome of execution depends on the particular order in which the access takes place.
• Synchronization: the coordination of occurrences to operate in unison with respect to time ➡️ prevent race condition
  Ex) ensuring only one process can access the shared data at a time

---

🖥️ The critical-section problem

• Critical section problem: designing a protocol that processes can use to cooperate
  • n processes $P_0$, ..., $P_{n-1}$ are running on a system concurrently. Each process want access a shared data
  • The code of each process is composed of
    - Critical section: a segment of code which may change shared resources (common var., file, ...)
    - Remainder section: a segment of code which doesn’t change shared resources
    - Entry section: code section to request permission to enter critical section
    - Exit section: code section to notice it leaves the critical section

Critical Section

• A process modifies shared data only in the critical section
• At a time only one process can exist in its critical section

➡️ access 한다면 그떄부터 critical section

• General structure of typical processes

• Requirements of critical-section problem

  • Mutual exclusion(상호 배타성): If a process is in its critical section, no other processes can be executing in their critical sections
    ➡️ Other processes should wait ( in entry section )

  • Progress: If no process is executing in its critical section, and some processes wish to enter their critical sections, only processes not executing in their remainder section can participate in the decision of next process to enter its critical section next. This selection cannot be postponed indefinitely(무기한 연기) ➡️ unlock 안하고 가는 것

  • Bounded waiting: There exists a bound or limit on 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 it is granted

• Kernel is an example of critical-section problem ➡️ PCB의 linked list
  • Kernel data structures such as list of open files,
• Approaches
  • Non-preemptive kernel: switching cannot occur when a
    process is executing in kernel mode
    - Free from race condition
    Ex) Windows 2000, Windows XP, early version of UNIX, Linux prior to v. 2.6.
  • Preemptive kernel: accompanied with a solution of critical- section problem ➡️ 모든 solution을 붙여놓음
    • Suitable for real-time programming
    • More responsive
      Ex) Linux v. 2.6, Solaris, IRIX

Peterson’s Solution

• A S/W solution for critical section problem
  ➔ No guarantee to work correctly on some architectures due to load/store instructions, but helps to understand the problem
  • Two processes $P_0$ and $P_1$ ➡️ or $P_i$(current) and $P_j$(other)
  • Data items
    int turn; // indicates process allowed to execute
    // in its critical section
    // initial value is 0
    boolean flag[2]; // if flag[i] is true, Pi is ready to enter
    // its critical section
    

Erroneous Algorithm 1

do {
	while (turn != i); // Extry, if not my turn waiting
		critical section
	turn = j; // Exit, give the other a turn
  		remainder section
} while (1);

• Mutual exclusion is guaranteed, but progress is not guaranteed
  ➡️ Ready to execute 체크 변수가 없다.
  Ex) P1 is trying to enter its critical section, but P0 is in its remainder section -> turn is not switched to 1

Erroneous Algorithm 2

do {
	flag[i] = true; 
  	while (flag[j]) ;
		critical section
	flag[i] = false;
		remainder section
} while (1);

➡️ flag[i] = true, while(flag[j])의 위치를 바꾸면 동시 접근

• Mutual exclusion is guaranteed, but progress is not guaranteed
  Ex) P0 and P1 enter simultaneously. Both of flag[0] and flag[1] can be true

Peterson’s Solution➡️ Satisfies the three conditions➡️ Q. compiler가 순서를 바꿀 수 있다. 문제는?

A. flag[1] = 1, turn = 0의 순서가 바뀌었을때

• Proof of mutual exclusion
  • If both Pi and Pj enter their critical section, it means
    - flag[0] = flag[1] = true
    - turn can be either 0 or 1, but turn cannot be both
• Proof of progress and bounded waiting
  • Blocking condition of Pi: flag[j] == true and turn == j
    - If Pj is not ready to enter critical section: flag[j] == false
    ➡️ $P_i$ can enter critical section
    - If Pj waiting in its while statement, turn is either i or j
    - If turn is i, $P_i$ will enter critical section
    - Otherwise, Pj will enter critical section.
    ➡️ When Pj exits critical section, $P_j$ sets flag[j] to false and $P_i$ can enter critical section because $P_j$ modifies turn to i
    - Therefore, Pi will enter critical section (Progress) and waits at most one process (Bounded waiting)
• Not guaranteed to work on modern computer architectures
  • To improve system performance, processors and/or compilers may reorder read and write operations that have no dependencies
  • For a multithreaded application with shared data, the reordering of instructions may render inconsistent or unexpected results
• Example
  • Shared variables
    boolean flag = false;
    int x = 0;
  • Thread1
  1. while(!flag);
  2. print x;
  • Thread2
  1. x = 100;
  2. flag = true;
     ➔ No dependency between line 1 and 2 ➔ can be reordered

🖥️ H/W Support for Synchronization

Memory Model

• Memory model: how a computer architecture determines what memory guarantees it will provide to an application program.
• Categories of memory models
  • Strongly ordered: a memory modification on one processor is immediately visible to all other processors ➡️ 즉시 내가 바꾼것을 남이 알 수 있다
  • Weakly ordered: modifications to memory on one processor may not be immediately visible to other processors ➡️ 즉시 바꾼것을 모를 때

Memory Barriers

• Memory barrier (or memory fences): instructions that can force any changes in memory to be propagated to all other processors
  ➡️ low level, kernel 개발자들이 사용
  • All loads and stores are completed before any subsequent load or store operations are performed
• Example
  • Thread1
    while (!flag) memory barrier();
    print x;
  • Thread2
    x = 100;
    memory barrier();
    flag = true;
    

Hardware Instructions

• Critical section problem requires lock
  • Race condition can be prevented by protecting critical
    section by lock
• H/W support makes it easier and improve efficiency

Mutual Exclusion by Lock variable

• A shared variable lock
  • Boolean lock = 0;
  • If lock is false, any process can enter its critical section
    - When a process enters its critical section, it sets lock to true
  • If lock is true, a process ($P_i$) is in its critical section
    - Other processes should wait until Pi leaves its critical section and sets lock to false
• Initially, lock = false➡️ 동시 입장 가능, Mutual exclusion X
• Note! Checking and locking must not be separated

Interrupt Disable

• In single processor system, critical section problem can be solved by simply disabling interrupt ➡️ kernel mode만, user mode X
  • Non-preemptive kernel ( switching X ➡️ synchronization 문제 X )
• Problems
  • Inefficiency in multiprocessor environment
  • In some systems, clock is updated by interrupt
• This approach is taken by non-preemptive kernels

Hardware Instructions

• If H/W provides atomic instructions, locking is easer to implement
  atomic instruction : 여러 inst. 하나로 묶음
• TestAndSet: set a variable to true and returns its previous value

boolean TestAndSet(boolean *target) { // target = lock var
  	boolean rv = *target; 
  	*target = true;
	return rv; // knocking
}

• Swap: exchanges two variables

void Swap(boolean *a, boolean *b) { // a = lock var, b = local var
	boolean temp = *a; 
  	*a = *b;
	*b = temp;
}

• Compare and swap (CAS): The operand value is set to new value only if the expression (*value== expected) is true.

int compare_and_swap(int *value, int expected, int new_value) {
	int temp = *value;
	if (*value == expected)
		*value = new_value; 
  	return temp;
}

Mutual Exclusion using TestAndSet

• Shared variable
  • boolean lock = false;
• Process $P_i$

do {
	while (TestAndSet(&lock));
  
	/* critical section */
  
	lock = false;
  
	/* remainder section */
} while(1);

• Ex_
  • lock = 0
  • $P_1$ ➡️ Critical section
  • lock = 1
  • $P_2$ ➡️ Try in critical section
  • $P_2$ ➡️ Waiting
  • $P_1$ ➡️ Exit
  • lock = 0
  • $P_2$ ➡️ Citical section
  • lock = 1

Mutual Exclusion using Swap

• Shared variable
  • boolean lock = false;
• Process $P_i$

do {
	key = true; // local var
	while (key == true)
		Swap(&lock, &key);
  
	/* critical section */
  
	lock = false;
  
	/* remainder section */ 
} while(1);

• Ex_
  • lock = 0
  • $key_1$ = 1
  • $P_1$ ➡️ Try in critical section
  • lock = 1, $key_1$ = 0
  • $P_1$ ➡️ Critical section
  • $P_2$ ➡️ Try in critical section
  • $key_2$ = 1, Waiting
  • $P_1$ ➡️ Exit, lock = 0
  • $key_2$ = 0, lock = 1
  • $P_2$ ➡️ Critical section

Mutual Exclusion using CAS

• Shared variable
  • boolean lock = false;
• Process $P_i$

while (true) {
	while(compare_and_swap(&lock, 0, 1) != 0); 
  
  	/* critical section */
  
	lock = 0;
  
	/* remainder section */
}

• Ex_
  • lock = 0
  • $P_1$ ➡️ Try in critical section
  • lock = 1
  • $P_1$ ➡️ Critical section
  • $P_2$ ➡️ Try in critical section
  • $P_2$ ➡️ Waiting
  • $P_1$ ➡️ Exit
  • lock = 0
  • $P_2$ ➡️ Critical section

Bounded Waiting Mutual Exclusion

• Bounded waiting for n processes
  • Some processes want to enter their critical sections
    Ex) $P_0$,$P_1$,$P_3$,$P_5$
  • One of them, (ex: $P_1$) is in its critical section➡️ 굵은 선 : want to shared resource, 가는 선 : x
• Idea: Whenever a process leaves its critical section, it designates the next process to enter the critical section
  • The next process: The first waiting process in right direction

• Shared variables
  • boolean lock;
    - For mutual exclusion
  • boolean waiting[n];
    - if waiting[i] is true, it means $P_i$ wants to enter critical section, but it didn’t enter yet

• Algorithm

while(TRUE){ 
	waiting[i] = TRUE;
	key = TRUE; // local var. 
  	while(waiting[i] && key)
		key = TestAndSet(&lock); 
  	waiting[i] = FALSE;
  
	/* critical section */
  
	j = (i + 1) % n;
  	// j != i : finish searching, !waiting[j] : find the next waiting P
	while(j != i && !waiting[j]) 
		j = (j + 1) % n;
  
	if(j == i)
		lock = FALSE; // 모든 P가 들어올 수 있음
	else
		waiting[j] = FALSE; // 다음순서 P, j번째만
  
	/* remainder section */
}

• Algorithm using CAS

while(true) {
	waiting[i] = true;
	key = 1;
	while (waiting[i] && key)
		key = compare_and_swap(&lock, 0, 1);
	waiting[i] = false;
  
	/* critical section */
  
	j = (i + 1) % n;
	while ((j != i) && !waiting[j])
		j = (j + 1) % n; 
  
 	if (j == i)
		lock = 0; 
  	else
		waiting[j] = false;
  
/* remainder section */

Atomic Variables

• Atomic variables: variables that provide atomic operations on basic data types such as integers and Booleans ➡️ race condition 걱정 안하게
  • Provided as “special data type + operation”
  • Can be used in to ensure mutual exclusion
  • Typically, implemented by CAS instruction

void increment(atomic int *v) { // atomic var : 임의로 변수 변경 불가능
	int temp = 0; 
  	do {
		temp = *v;
	} while (temp != compare_and_swap(v, temp, temp+1));
  	// 앞에서 다른 P가 access 했는지 check
}

• Ex_
  • v = 5
  • $temp_1$ = 0, $temp_2$ = 0
  • $temp_1$ = 5, $temp_2$ = 5
  • v = 6
  • $temp_1$ = 0, $temp_2$ = 6
  • v = 7

---

🖥️ Mutex and Semaphore

OS가 제공 High-level tool

Mutex Locks

• A synchronization tool to implement mutual exclusion
  • A Boolean variable available (1 = unlock, 0 = lock)
    • Opposite(반대) to the lock variable in the previous section
• Atomic operations on mutex locks
  • acquire() {
        while (!available);             /*busy waiting*/
        available = false;
    }
  • release() {
        available = true;
    }
• Synchronization using mutex lock→ Mutual exclusive 보장, race condition을 막을 수 있음

Semaphores

• An integer variable accessed only through two atomic operations: wait() and signal()
  • Initial value of S(사용가능한 resource cnt) is 1 or a positive integer
  • wait(S) {                 // correspond to mutex.acquire()
        while(S <= 0);   // waits for the lock
        S--;                    // holds the lock
    }
  • signal(S) {     // correspond to mutex.release()
        S++;           // releases the lock
    }
• S is similar to the number of reusable tickets to enter the critical section

Implementation of Semaphore

• Problem of previous definition of wait(): spinlock
  wait(S) {
       while(S <= 0);   // spinlocks (busy waiting) → CPU time 낭비
       S--;
  }
• Alternative implementation: block(CPU time 안받고 기다림) instead of spinlock
  • If a process invokes wait(S), put the process into a waiting queue of S and block itself

New definition of semaphore

typedef struct {
    int value;
    struct process *list;      // head of linked list for waiting queue
} semaphore;

wait(semaphore *S) {
    S->value--;
    if(S->value <(neq) 0) {
        add this process to S->list;
        block(); // CPU time 안쓰고 Sleep
    }
}

signal(semaphore *S) {
    S->value++;
    if(S->value <= 0) { // waiting process가 있는지 check
         remove a process P from S->list;
         wakeup(P); // resume
    }
}

• A critical aspect of semaphore: atomicity
  • Atomicity is often enforced by mutual exclusion
  • Single processor environment: disable interrupt → kernel mode (switch X)
  • Multiprocessor environment: spinlock = busywait
    • Disable interrupt of all processors ➔ performance degradation
    • Spinlock is much short than previous algorithms
      → semaphore의 wait, signal은 짧기 때문에 spinlock을 on, off하는게 효율적

---

Monitors

• Motivation: semaphore is still too low-level tool
• Monitor: a high-level language construct to support synchronization
  • Private data: accessible only through the methods
  • Public methods: mutual exclusion is pro vided
• Only one process can be active within the monitor at a time
  • The programmer doesn’t have to concern about synchronization

Condition Variables

• Condition: additional synchronization mechanism
  • Variable declaration → condition x, y;
  • Wait → x.wait(); // Sleep
  • Signal → x.signal(); // Release, Wakeup
    → If no process is waiting, do nothing
    
    
• Problem
  • Process P wakes up another process Q by invoking x.signal()
  • Both P and Q are executing in monitor
• Solution
  • Signal and wait: P waits until Q leaves monitor or waits
  • Signal and continue: Q waits until P leaves monitor or waits

Implementing a Monitor Using Semaphores

• Two semaphores are required:
  • semaphore mutex = 1; → mutual exclusion
  • semaphore next = 0(바로 잠들어야 하기 때문); // signaling process should wait
    // until the resumed process leaves monitor
  • int next_count = 0; → next에서 자고있는 cnt
• External procedure F
  wait(mutex);
      ...
      bodty of F;
      ...
  if(next_count > 0)
      signal(next);
  else
      signal(mutex);
• Condition variables
  • Required data
    • semaphore x_sem; // (initially, 0 → 바로 sleep)
    • int x_count = 0;
• x.wait() {
      x_count++;
      if (next_count > 0)
          signal(next); → 기다리고 있는 P를 깨움
      else
          signal(mutex); → 다른 P가 들어갈 수 있게 Unlock
      wait(x_sem);
      x_count--;
  }
• x.signal() {
      if (x_count > 0) {
          next_count++;
          signal(x_sem);
          wait(next); → x_sem을 깨우고 나(next)는 sleep
          next_count--;
      }
  }
  

---

Deadlock

HGU 전산전자공학부 김인중 교수님의 23-1 운영체제 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.