운영체제 ch 6. Synchronization Tools

critical section (임계구역)

• 여러 프로세스들이 동시에 접근할 수 있는 부분

race condition (경쟁 상태)

• 임계구역에 여러 프로세스가 동시에 접근해 예측할 수 없는 결과가 산출되는 상태

mutual exclusion (상호 배제)

• 한 번에 한 프로세스가 접근할 수 있도록 만들어주는 기법

 

프로세스를 동시에 실행 → 공유 데이터에 대한 동시 접근으로 인해 데이터 비일관성이 발생할 수 있음

프로세스가 처리하는 순서를 지켜야 함
데이터의 일관성을 유지하려면 협력 프로세스의 정상적인 실행을 보장하는 메커니즘이 필요!

Producer, Consumer

critical section에서 race condition이 발생하는 예

동기화가 필요할 때는?

1. Buffer가 full/empty
2. same slot에 접근

• Producer가 수행할 동안 Consumer가 해당 데이터를 읽으면 안 된다! (반대도)
• Producer가 중간에 수행하다가 CPU가 Consumer로 넘어가도 Consumer에서 작업이 수행되면 안 됨
• mutual exclusion 시켜줘야 함

 

Race Condition

ex) 초기의 count = 5 일 때 수행 과정

1. S0: producer execute register1 = counter         {register1 = 5}
2. S1: producer execute register1 = register1 + 1   {register1 = 6}
3. S2: consumer execute register2 = counter        {register2 = 5} → producer의 결과값을 저장하지 않아서
4. S3: consumer execute register2 = register2 – 1  {register2 = 4}
5. S4: producer execute counter = register1         {counter = 6 }
6. S5: consumer execute counter = register2        {counter = 4}

→ 예측하지 못한 값을 가지게 된다! race condition

∵ 한 번에 한 프로세스만 수행되어야 함! 다른 프로세스한테 CPU가 할당되더라도 수행하지 못하도록 빙글빙글 돌아야 함(busy waiting)

 

Critical Section

do {
    // entry sections - cs에 들어가는 부분
    	critical section
    // exit section - cs에서 나가는 부분
    	remainder section
} while(true);

Pi process 알고리즘

do {
    while (turn == j);
    	critical section
    turn = j;
    	remainder section
} while(true);

 

Critical Section 문제의 해결책

1. Mutual Exclusion - 한 번에 한 프로세스만 critical section에 들어갈 수 있도록 만들어 주어야 함
2. Progress - critical section에서 실행 중인 프로세스가 없는데 critical section에 들어가기를 무한히 기다리는 프로세스가 존재하면 안 되고, 들어가서 수행해야 함
3. Bounded Waiting - 기다리는 프로세스가 일정한 시간이 지나면 들어갈 수 있도록 만들어 주어야 함

• 각각의 프로세스 수행이 멈추면 안 됨
• 프로세스 속도에 대한 가정이 있으면 안 됨

 

Preemptive

• 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유가능
• 하나의 프로세스가 커널에 들어갔을 때 다른 프로세스도 들어올 수 있다.

Non-preemptive

• 커널에 들어간 프로세스가 자발적으로 CPU를 내주거나, 시스템 콜을 끝내고 유저 모드로 돌아갈 때까지 다른 프로세스가 커널에 들어가지 못하게 만들어 줌
• real time application이면 속도가 느려질 수 있다. → Preemptive로 구현하고 동기화 기법을 사용해야 함

 

Peterson's Solution

• 프로그램에 의한 동기화, 소프트웨어에 의한 솔루션
  • 문제 : race condition (모든 변수에 대한 접근을 atomic으로 설정하면 해결은 가능), 수행의 overhead 발생
• 두 프로세스는 두 변수를 공유
  • int turn; → 순서 (누가 들어갈 것인지)
  • Boolean flag[2] → critical section에 들어갈 준비가 되었는지를 나타냄

Process Pi

	do { 
		flag[i] = true; // 나는 cs에 들어가고자 함
		turn = j;		// 상대방의 순서인지 체크
		while (flag[j] && turn == j);	// busy waiting
			critical section 
		flag[i] = false; 	// exit
			remainder section 
	 } while (true);

 

다음 요구사항이 충족됨

1. Mutual exclusion
   • Pi가 들어갈 때는 either flag[j] = false or turn = i
2. Progress
3. Bounded-waiting

---

Sychronization Hardware

• LOAD, STORE이 atomic하게 되어야만 한다!
  • 중간에 interrupt가 발생해 CPU가 다른 프로세스에 할당되면 안 됨 (race condition)
  • 해결 방법 : interrupt disable을 시키고, critical section을 수행하고 interrupt enable을 시킨다.
    
    • critical section의 코드가 짧아야 하고, error가 발생하면 안 됨. 안정적으로 수행 보장해야 함
    • 한계 : 서로 다른 CPU에서 수행되는 두 개의 프로세스에 대해서는 critical section에 들어갈 수 있다! (SMP)
      
      • 다른 머신의 CPU에서는 disable 되지 않은 상태로, enable 상태이기 때문에 동기화가 수행되지 않음
• 값을 바꾸는 부분에 Locking이 필요하다.

 

Lock을 사용한 critical-section 문제 해결

do { 
	acquire lock 
		critical section 
	release lock 
		remainder section 
} while (TRUE);

 

test_and_set Instruction

boolean test_and_set (boolean *target)	// 하드웨어로 구현되어 있는 것 atomic
{
	boolean rv = *target;
	*target = TRUE;
	return rv:
}

모든 변수에 대한 접근이 atomically하게 이루어짐 - 중간에 경쟁 상태 x

// Shared Boolean variable lock, initialized to FALSE
do {          
	while (test_and_set(&lock)) ; 
		/* critical section */ 
	lock = false; 
		/* remainder section */ 
} while (true);

 

Bounded-waiting Mutual Exclusion with test_and_set

do { 
	waiting[i] = true;
    key = true;
    while (waiting[i] && key)	// critical section에 관심 있고, 누군가가 들어가 있지 않다면
		key = test_and_set(&lock);	// True면 누군가가 들어가 있고, False면 없음
	waiting[i] = false; 
    
	/* critical section */ 
    
	j = (i + 1) % n; 
	while ((j != i) && !waiting[j])		// 기다리고 있지 않은 프로세스 skip
		j = (j + 1) % n; 
	if (j == i) 
		lock = false; 			// 자신은 critical section에 빠져나옴
	else 
		waiting[j] = false; 	// 다음 번에 들어갈 프로세스 선택
        
	/* remainder section */ 
} while (true);

waiting time을 예측할 수 있는 방식으로 구현되어 있다 → bounded-waiting

 

compare_and_swap Instruction

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

모든 변수에 대한 접근이 atomically하게 이루어짐 - 중간에 경쟁 상태 x

test_and_set과의 차이 : 변수의 값을 바꿔줄 필요가 없으면 동작하지 않음!

// Shared integer  “lock”  initialized to 0; 
do {
	while (compare_and_swap(&lock, 0, 1) != 0); 
		/* critical section */ 
	lock = 0; 
		/* remainder section */ 
} while (true);

 

하드웨어로 구현했을 때의 문제

• busy waiting
• 하드웨어는 유저가 프로그램하기 어려움
  • 소프트웨어로 구현하면서 속도 올릴 수 있는 방법이 보다 효율적!

 

Mutex Locks

• 소프트웨어 방식
• 이전 솔루션은 복잡하고, 일반적으로 사용자가 접근하기 어려움
• 먼저 lock을 acquire()하고, 이후 lock을 release()하여 critical section을 보호함
• acquire(), release()는 atomic하게 수행됨
  • 일반적으로 하드웨어 atomic instruction을 통해 구현됨
• busy waiting의 문제가 있다.
• spinlock이라고도 함

acquire() { 
	while (!available); /* busy wait */ 
    available = false;
} 

release() { 
	available = true; 
}

do { 
	acquire lock
		critical section
    release lock 
		remainder section 
} while (true);

 

---

Semaphore

• Mutex locks보다 정교하게 다익스트라에 의해 제안된 동기화 기법
• Semaphore S - 정수
• 모든 변수에 대한 변환을 atomic하게 수행
• critical section의 entry → wait() - P()
• critical section의 exit → signal() - V()

wait(S) { 
    while (S <= 0)
       ; // busy wait
    S--;
}

signal(S) { 
    S++;
}

 

Semaphore Usage

• Counting semaphore - 제한되지 않는 정수 값, 임의의 값을 가질 수 있음
• Binary semaphore - 0, 1의 정수 값 → Mutex lock과 동일
• S1이 S2보다 먼저 발생해야 하는 P1, P2 고려
  • semaphore "synch" = 0으로 초기화

P1:
   S1;
   signal(synch);
P2:
   wait(synch);
   S2;

Counting semaphore S를 Binary semaphore로 구현할 수 있다!

 

 

Semaphore Implementation

• 두 프로세스가 동일한 semaphore에서 동시에 wait(), signal()를 실행할 수 없음
• critcal section에 들어가는 것을 기다리며 busy waiting의 문제
  1. 구현 코드가 짧거나 critical section이 많지 않다면 busy waiting의 시간은 짧을 것임
  2. 하지만 애플리케이션이 critical section에 많은 시간을 사용한다면 문제가 됨
     • CPU 많은 시간을 busy waiting이 소모한다면 critical section에 들어가지 못하는 프로세스를 block 시키고 다른 프로세스에 CPU를 할당하는 방식을 고려해보자!

 

Semaphore Implementation with no Busy waiting

• 각 semaphore에는 관련된 waiting queue가 존재함 → critical section에 들어가지 못하면 waiting queue에서 대기
• waiting queue는 두 개의 데이터 항목을 가짐
  • value (정수형)
  • waiting queue에서 기다리는 프로세스들의 레코드 (다음 프로세스로의 포인터) - 일반적으로 PCB
• 두 가지 작업
  • block 
    • running → waiting
    • critical section에 들어가지 못하는 프로세스를 block해 waiting queue로 옮김
    • CPU를 다른 프로세스에 양도
  • wakeup
    • waiting → ready (→ running)
    • ready로 옮겨서 CPU를 받을 수 있도록 만들어 줌
    • critical section에 들어가 있던 프로세스가 빠져나오면 대기하고 있던 프로세스가 wakeup 되면서 CPU를 받을 수 있는 자격이 주어짐

typedef struct{ 
   int value; 
   struct process *list;	// semaphore를 기다리는 프로세스의 포인터 (linked list), waiting queue에서 기다리는 프로세스들의 리스트
   } semaphore;

 

Counting semaphore

wait(semaphore *S) { 
   S->value--; 
   if (S->value < 0) {
   	  add this process to S->list; 		// running → waiting
      block(); 
   } 
}

signal(semaphore *S) { 
   S->value++; 
   if (S->value <= 0) {					// waiting queue에 프로세스 존재
   	  remove a process P from S->list; 	// waiting queue에서 지움
      wakeup(P);	// waiting → ready (ready queue에 넣음)
   } 
}

S = 1 → 어떤 프로세스도 critical section에 없고, block 되어 있는 경우가 없을 때!

 

 

Binary Semapore

wait(semaphore *S) { 
   if (S->value == 1)
   	  S->value = 0;
   else {
   	  add this process to S->list; 		// running → waiting
      block(); 
   } 
}

signal(semaphore *S) { 
   if (IsEmpty(S->list)) 
      S->value = 1;
   else	{								// waiting queue에 프로세스 존재
   	  remove a process P from S->list; 	// waiting queue에서 지움
      wakeup(P);						// waiting → ready (ready queue에 넣음)
   } 
}

 

Deadlock and Starvation

• Deadlock
  • waiting processes 중 하나로 발생할 수 있는 이벤트를 두 개 이상의 프로세스가 무한히 기다리는 것
  • 결코 일어나지 않을 이벤트, waiting process는 CPU를 할당받고 있지 않음!
• S, Q = 1로 초기화

  P0	          P1
wait(S); 	    wait(Q);
wait(Q); 	    wait(S);
  ...		      ...
signal(S);      signal(Q);
signal(Q);      signal(S);

• Starvation - 무기한 blocking
  • 프로세스가 일시적으로 중단된 semaphore queue에서 제거될 수 없음
• Priority Inversion
  • 우선 순위가 높은 프로세스가 우선 순위가 낮은 프로세스에 의해 성능적인 영향을 받는 현상
  • 우선 순위 H > L, 둘다 리소스 R을 사용하기를 원함
    • 우선 순위가 낮은 L 프로세스가 R을 선점 →  H 프로세스는 L 프로세스가 끝나기를 기다림 → 우선 순위가 중간인 M 프로세스가 들어와 L 프로세스가 CPU가 M 프로세스에게 감 → 우선 순위 낮은 M 프로세스에 의한 성능 지연이 발생함
  • priority-inheritance protocol을 통해 해결
    • L 프로세스가 R을 선점하고 있는 동안 L 프로세스의 우선 순위를 H만큼 높여줌 → M 프로세스가 들어오더라도 CPU가 가지 않음 → Priority Inversion 문제 해결

 

Problems with Semaphores

• Semaphore operation의 잘못된 사용
  • signal (mutex)  ….  wait (mutex) → 동시에 여러 프로세스가 critical section에 들어가 no mutual exclusion
  • wait (mutex)  …  wait (mutex) → 어떤 프로세스도 들어갈 수 없게 막힘, deadlock
  • wait (mutex) or signal (mutex) (or both)의 누락
• Deadlock과 starvation이 발생 가능하다.

 

Monitors

• 프로세스 동기화를 위한 효과적인 메커니즘 제공
• 한 번에 한 프로세스만 monitor 내에서 활성화
• monitor 내에서만 함수 사용 가능 (함수 안의 변수들은 바깥에서 수정할 수 없음)
• 유저가 추가적으로 기능을 설정해야 함

monitor monitor-name
{
	// shared variable declarations
	procedure P1 (…) { …. }

	procedure Pn (…) {……}

    Initialization code (…) { … }
	}
}

 

 

Schematic view of a Monitor

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

Shared data 문제

1. Producer와 Consumer 중 Consumer가 먼저 들어왔을 경우 → 모니터 내에서 block
2. 이후 Producer가 들어오면 작업을 수행하고 Consumer을 깨워야 함
   • Producer와 깨워진 Consumer 2개가 존재하게 됨
   • mutual exclusive는 가능하지만, 모니터 안에는 한 번에 한 프로세스만 수행이 가능해 추가적인 기능이 필요함

 

 

Condition Variables

• 모니터 안에서의 조건 변수 x, y;
• x.wait() – 작업을 호출하는 프로세스는 x.signal()에 의해 깨어날 때까지 중단되어 기다림
• x.signal() – x.wait()를 호출한 프로세스들 중 하나를 시작
  • 어떤 프로세스도 x.wait()를 호출하지 않아 block 되어 있지 않으면 이벤트가 발생하지 않음
• queues associated with x, y conditions - x, y 조건에서 기다리는 프로세스들의 큐
• entry queue - 모니터 안에 들어가기를 기다리는 프로세스들

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• 공유 데이터 때문에 모니터 안에서 block 된 프로세스 여러 개 존재

 

Condition Variables Choices

• Q 들어옴 → 조건에 맞지 않아 block → P 들어와서 조건 해결 → Q를 깨움 → 1. 깨워진 Q 수행 2. 깨운 P 수행
• Q와 P 모두 병렬로 실행할 수 없음 → Q가 다시 시작되면 P는 기다려야 함
• 옵션
  • Signal and wait – P는 Q가 모니터를 빠져나올 때까지 기다림
  • Signal and continue – Q는 P가 먼저 수행하고 모니터를 빠져나올 때까지 기다림
  • 둘 다 장단점이 있고, 모니터 안에 한 번에 한 프로세스가 존재하도록 만들어줌. 언어 구현자가 결정할 수 있음
  • Concurrent Pascal compromise으로 구현된 모니터
    • P가 signal()를 실행하면 모니터에서 빠져나온 후, Q가 재개됨
  • Mesa, C#, Java를 포함한 다른 언어로 구현됨

 

 

Monitor Implementation Using Semaphores

• 모니터 자체를 지원하는 언어가 제한 → semaphore로 모니터 구현

semaphore mutex;  // (initially  = 1), 모니터 안에서 한 번에 한 프로세스만 들어갈 수 있도록 만들어주는 semaphore
semaphore next;   // (initially  = 0), signaling processes가 대기하는 큐, 모니터 안에서 block된 것을 깨워주는 데 필요한 semaphore
int next_count = 0;		// 모니터 안에서 block된 프로세스 수

// mutex = 1;
wait(mutex);	// 모니터 들어가기 전 wait
	…			 
  body of F;
	…
if (next_count > 0)		// 모니터 안에 block된 프로세스 존재할 때 깨워주기
	signal(next)
else					// 모니터 바깥에서 순서 기다리는 프로세스 깨워주기 
	signal(mutex);

• 모니터의 바깥 부분
• 모니터를 빠져나오면서 누군가를 모니터 안에 들어갈 수 있도록 만들어줌

 

Monitor Implementation – Condition Variables

• condition variable을 x라고 가정

semaphore x_sem; // (initially  = 0) x.wait 큐
int x_count = 0;	// block된 프로세스의 수, x.wait한 프로세스 개수

모니터 안에서의 x.wait 구현 - x라는 조건하에 block → 다른 애를 깨워줘야 함

x_count++;		// x조건에서 block된 프로세스 증가, x 조건에서 나는 block
if (next_count > 0)		// 모니터 안에 block된 프로세스 존재한다면 깨워주기
	signal(next);
else					// 모니터 바깥에서 순서 기다리는 프로세스 깨워주기
	signal(mutex);
wait(x_sem);			// 한 프로세스가 signal 되고 자신은 wait (x.wait 큐로)
x_count--;				// 다른 프로세스에 의해 내가 깨어나면 block된 프로세스 감소

모니터 안에서의 x.signal 구현 - 내가 깨워줄 때 (signal and wait)

if (x_count > 0) {		// block된 프로세스 존재할 때
  next_count++;			// 자신은 block됨
  signal(x_sem);		// block된 프로세스 signal 시켜줌 (x.wait한 프로세스)
  wait(next);			// 자신은 wait, signaling processes가 기다리는 큐로 감
  next_count--;			// 다른 프로세스에 의해 signal 되면 내가 깨어나서 모니터 안에서 block된 프로세스 감소
  }

 

Resuming Processes within a Monitor

• 여러 프로세스가 x 조건에서 queue에 있고 x.signal()이 실행된 경우 어떤 프로세스를 다시 시작해야 할까?
• FCFS가 적합하지 않은 경우가 많음
• x.wait(c) 형식의 조건부 대기 구조
  • 여기서 c는 priority number
  • 가장 낮은 수(가장 높은 우선순위)의 프로세스가 다음에 예약됨

 

 

Single Resource allocation

• 프로세스의 리소스 사용 시간에 따라 priority number를 사용하여 경쟁 프로세스 간에 단일 리소스 할당
• resource를 적게 사용하는 프로세스부터 깨우자!

R.acquire(t);		// 리소스를 사용하는 시간을 보내줌
	...
access the resource;
	...
R.release;

 

 

A Monitor to Allocate Single Resource

monitor ResourceAllocator 
{ 
	boolean busy; 
	condition x; 
	void acquire(int time) { 
		if (busy) 				// busy일 때 쓰지 못 함
			x.wait(time);		// wait하면서 자신이 깨어났을 때 리소스를 얼마나 사용할 것인지 시간을 줌 	
		busy = TRUE; 
	} 
	void release() { 
		busy = FALSE; 
		x.signal(); 			// block 되어 있는 프로세스 깨워주기
	} 
initialization code() {
	 busy = FALSE; 
	}
}

---

 

 

 

 

 

참고 자료 : Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne