[운영체제] Chapter 6. Process Synchronization, Concurrency Control (병행 제어)

2022. 12. 28. 19:39ㆍCS/운영체제

728x90

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

Semaphores, Monitor, Bounded-Buffer Problem, Dining Philosophers Example

 

1. 세마포어의 문제점

  • 코딩하기 힘들다.
  • 정확성(correctness)의 입증이 어렵다.
  • 자발적 협력(voluntary cooperation)이 필요하다.
  • 한 번의 실수가 모든 시스템에 치명적 영향을 끼친다. 
    V(mutex);    //둘이 동시에 들어가는 문제 발생
Critical Section
P(mutex);

//V연산과 P연산의 순서가 뒤 바뀜 -> 둘이 동시에 들어가는 문제 발생
//Mutual exclusion이 깨짐
    P(mutex);
Critical Section
P(mutex);    //어느 누구도 critical section에 들어갈 수 없음

//P연산을 두 번함 -> 어느 누구도 critical section에 들어갈 수 없음
//Deadlock 발생

→ 이러한 문제를 해결하기 위해 간단한 동기화 도구를 통합하여 고급 언어 구조물을 제공하는 것이다.

 

2. Monitor, 모니터

  • 동시 수행 중인 프로세스 사이에서 Abstract Data Type(ADT: 추상화된 데이터 형)의 안전한 공유를 보장하기 위한 high-level synchronization construct(고급 언어 구조물)이다.
    • ADT: 추상적인 구조체 형태로 언어마다 모니터가 다르다. 보통 모니터 안에 데이터가 정의되고 그 데이터를 접근하는 코드가 내부에 정의되기 때문에 객체지향프로그램에서 주로 지원한다.
    • high-level synchronization construct: 프로그램 언어 차원에서 동기화 문제를 해결
    • 공유 데이터를 접근하기 위해서는 모니터라고 정의된 내부의 프로시저를 통해서만 공유 데이터를 접근할 수 있게 만들어 놓은 것
    • 세마포어는 남은 자원의 개수를 카운트할 수 있는 행위를 원자적으로 할 수 있는 연산(P연산, V연산)을 제공해 주는 것이지 실제로 동기화 문제는 프로그래머가 책임을 져야 한다. 
      • 공유 데이터에 접근하기 위해서는 프로그래머가 Lock을 걸고 풀어줘야 하지만
      • 모니터는 공유 데이터에 대한 동시 접근을 책임진다.
monitor monitor-name
{
	shared variable declarations    //모니터 내부에 공유 변수에 대한 선언
	procedure body P1(...){  //공유 변수에 접근하기 위한 프로시저들을 모니터 내부 함수로 구현
		...
	}
	procedure body P2(...){
		...
	}
	procedure body Pn(...){
		...
	}
	{
		initialization code    //초기화 코드
	}
}

  • 모니터 내부에 공유 데이터를 접근하는 프로시저를 정의하고 그 프로시저를 통해서만 공유 데이터에 접근할 수 있다.
    • 모니터 내부의 프로시저는 원천적으로 동시에 여러 개가 실행될 수 없다.
    • 모니터는 기본적으로 모니터에 대한 동시접근을 허용하지 않는다.
  • 모니터 내에서는 한 번에 하나의 프로세스만이 활동할 수 있다. → 모니터에서는 lock을 걸고 푸는 것이 원칙적으로 필요 없다. 모니터가 알아서 제어한다.
    • 프로세스 A가 모니터 안에서 고유 데이터를 접근하는 코드를 실행하고 있다 CPU를 빼앗기면
      → CPU를 할당받은 프로세스 B가 모니터에 접근하는 코드에 들어오려 하지만
      → 프로세스 A는 active 한 상태로 모니터 안에 남아있기 때문에
      → 다른 프로세스는 모니터에 있는 코드를 실행하지 못하고 모니터 밖의 큐(= entry queue)에 줄 서서 기다리게 된다.
    • 모니터 밖 큐에서 기다리는 나머지 프로세스들은 모니터 안에 active 한 프로세스의 수가 0개일 때 모니터 내부로 진입할 수 있다.
      • 모니터를 쓰고 있던 프로세스 A가 CPU를 얻어서 다 쓰고 모니터를 빠져나가던지
      • 프로세스 내부에서 조건이 충족되지 않아 모니터 안에서 실행되다 active 하지 않은 상태가 되어 잠들던지(condition variable)
        • active 하지 않은 상태의 프로세스들은 모니터 내부의 condition variable의 큐에 매달려 sleep
  • 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없다.
  • condition variable
    • 동기화 기법들은 condition이라는 구조물로 제공될 수 있다.
    • 모니터 안에서 어떤 코드를 실행하다 무언가 충족이 되지 않아 오래 걸릴 때 프로세스를 잠들게 한다.(= suspend)
      이때 어떤 조건이 충족되지 않아 잠들게 되었는지를 변수로 두는 것을 condition variable이라고 한다.
    • condition variable은 세마포어처럼 값을 가지는 변수가 아니라 프로세스를 잠들게 하고 줄 세우기 위한 변수이다.
    • condition x, y;
      • condition variable은 wait와 signal 연산에 의해서만 접근 가능하다.
      • x.wait(); 
        x라는 condition variable에 가서 줄 서 있다. x라는 조건을 만족하지 못해 잠들어 있게 됨
        x.wait()을 invoke 한 프로세스는 다른 프로세스가 x.signal()을 invoke 하기 전까지 suspend 된다.
      • x.signal(); 
        접근을 다 하고 빠져나갈 때 x라는 condition variable 조건을 기다리면서 잠들어있는 프로세스가 있다면 그중 하나를 깨우고 나간다.
        x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다. suspend 된 프로세스가 없으면 아무 일도 일어나지 않는다.
      • wait, signal 연산은 condition variable 값을 변경하는 것은 아님.

 

3. Bounded-Buffer Problem with Monitor

  • 세마포어) 버퍼에 데이터를 집어넣기 위해서는 버퍼 전체에 lock을 걸어 다른 생산자와 소비자가 접근을 못하게 한 다음 데이터를 집어넣고, 버퍼에서 데이터를 꺼내가기 위해서도 버퍼 전체에 lock을 걸어서 데이터를 꺼내 갔었다.
  • 모니터) 생산자던 소비자던 코드를 실행하는 도중에 다른 프로세스의 접근을 모니터가 막아주기 때문에 공유 버퍼에 lock을 걸고 푸는 작업이 필요 없다.
monitor bounded_buffer{
	int buffer[N];    //공유 버퍼가 모니터 안에 정의
	condition full, empty;  //full, empty를 기다리는 프로세스를 줄세워 놓는 condition variable
	//condition variable은 값을 가지지 않고 자신의 큐에 프로세스를 매달아서 sleep 시키거나 
      	                                   //큐에서 프로세스를 깨우는 역할만 함
	
	//공유 버퍼에 자원을 만들어서 집어 넣어주는 코드
	void produce(int x){
		if there is no empty buffer    //빈 버퍼가 없으면
			empty.wait();          //빈 버퍼를 기다리는 줄에 가서 잠들게함
		add x to an empty buffer       //빈 버퍼가 생김
		full.signal();                 //생산자가 내용을 만들어 넣음 - 잠들어 있는 소비자를 꺠워줌
	}
	
	//공유 버퍼에서 데이터를 꺼내가는 코드
	void consumer(int *x){
		if there is no full buffer    //데이터가 있는 버퍼가 없으면
			full.wait();          //데이터가 있는 버퍼를 기다리는 줄에 가서 잠들게함
		remove an item from buffer and store it to *x  //버퍼에서 데이터를 꺼내감
		empty.signal();               //빈 버퍼가 생김 - 잠들어 있는 생산자를 깨워줌
	}
}
  • 생산자가 버퍼에 데이터를 넣으려고 할 때 빈 버퍼가 없다면 empty(빈 버퍼를 기다리는 줄)에 가서 suspend 하고, 소비자가 버퍼에서 데이터를 꺼내가면서 empty에서 suspend 된 프로세스를 invoke 한다.
  • 소비자가 버퍼에서 데이터를 가져가려고 할 때 데이터가 있는 버퍼가 없다면 full(데이터가 있는 버퍼를 기다리는 줄)에 가서 suspend 하고, 생산자가 버퍼에 데이터를 넣으면서 full에서 suspend 된 프로세스를 invoke 한다.

 

4. 식사하는 철학자 문제 with Monitor

Each philosopher:{
	pickup(i);  //젓가락을 잡는 행위: Enter monitor
	eat();
	putdown(i); //젓가락을 놓는 행위: Enter monitor
	think();
} while(1)
monitor dining_philosopher    //모니터 내부의 코드로 구현
{
	enum {thinking, hungry, eating} state[5];  //철학자의 현재 상태 공유 변수
	condition self[5];    //젓가락을 잡을 수 있느냐 없느냐를 판단하기 위한 공유 변수
	
	void pickup(int i){
		state[i] = hungry;       //모니터 안에서 공유 데이터에 접근하는 코드를 만듬 -> lock 필요 없음
		test(i);                 //젓가락을 잡을 수 있는지 확인
		if(state[i]!= eating)    //양쪽 젓가락을 잡을 수 없는 상태 - 잠들게 해둠
			self[i].wait();
	}

	void test(int i){
		if((state[(i+4)%5]!=eating) && (state[i]==hungry) && (state[(i+1)%5]!=eating)){
			state[i] = eating;   //내가 밥을 먹을 수 있는 상태
			self[i].signal();    //철학자 i가 잠들어 있다면 깨워주는 역할 - 양쪽 철학자가 기다리고 있을 때
	}

	void putdown(int i){
		state[i] = thinking;     //젓가락을 내려두고
		test((i+4)%5);           //왼쪽 오른쪽 철학자들이 밥을 못 먹고 기다리고 있는지 체크
		test((i+1)%5);
	}

	void init(){
		for(int i=0;i<5;i++)
			state[i]=thinking;
    }
}
  • 젓가락은 공유 데이터: 공유 데이터에 대한 접근은 모니터 안에 정의한다
    • 젓가락을 잡기 위한 코드(pickup, putdown)는 모니터 안에 있는 코드로만 실행될 수 있다.
  • 철학자의 상태(state)가 공유 변수인 이유: 5명의 철학자가 자신의 상태만 변경하거나 확인하는 것이 아니고, 주위의 철학자들이 젓가락을 잡았는지 아닌지의 상태를 확인해야 하기 때문
  • condition self 변수는: 젓가락을 잡을 수 있는 상태가 아니면 self condition variable에서 suspend
  • pickup(i): 젓가락 잡기
    • (1) 철학자의 상태를 hungry로 변경하고
    • (2) 젓가락을 잡을 수 있는지 테스트(test) 한다.
    • (5) 내 상태가 eating으로 바뀌었기 때문에 밥을 먹으면 된다.
    • (7) 권한이 없어서 밥을 먹을 수 없기 때문에 self(내 큐)에서 wait()
  • test(i): 젓가락 테스트
    • (3) 내가 젓가락을 잡을 수 있는지를 보려면 왼쪽, 오른쪽 철학자가 밥을 먹고 있는지 확인한다.
    • (4) 둘 다 안 먹고 있다면 내 상태를 eating으로 변경해 준다.
      • 첫 번째에는 젓가락을 잡으러 온 것이기 때문에 signal 연산이 필요 없지만(이때 signal 연산을 해도 문제없음)
      • 나중에 철학자가 밥을 먹고 나서 젓가락을 내려놓을 때 인접한 다른 철학자들이 밥을 못 먹고 있는지를 확인하고, 잠들어 있는 철학자가 있으면 깨워주기 위해서 signal 연산을 해준다.
    • (6) 만약, (3)에서 인접 철학자가 밥을 먹고 있어서 (4) 내 상태가 eating이 될 수 없다면 
    • (10) 인접 철학자가 밥을 먹으려고 하는지, 주위의 철학자가 젓가락을 들고 있지는 않은지를 확인하고 
    • (11) 인접 철학자의 state를 eating으로 변경하고, 잠들어 있는 왼쪽 철학자를 깨워준다.
  • putdown(i): 젓가락 내려놓기
    • (8) 밥을 다 먹은 상태이기 때문에 내 상태를 thinking으로 변경해 준다.
    • (9) 인접 철학자 둘이 밥을 못 먹고 있는 상태라면 깨워줘서 밥을 먹게 해줘야 하기 때문에 test 함수 호출 

 

[복습]

    1. 세마포어의 문제점: 한 번의 실수가 모든 시스템에 치명적인 영향을 끼친다.
    2. 모니터: 프로그램 언어 차원에서 동기화 문제를 해결
      • 모니터는 공유 데이터를 접근하기 위해서 모니터라고 정의된 내부의 프로시절르 통해서만 공유 데이터를 접근할 수 있다.
      • 모니터에서는 한 번에 하나의 프로세스만이 활동할 수 있다(= 모니터에 대한 동시접근을 허용하지 않는다). 
        → 모니터는 lock을 걸고 푸는 것이 원칙적으로 필요 없다. 모니터가 알아서 제어한다.
    3. condition variable: 프로세스를 잠들게 하고 줄 세우기 위한 변수
      1. x.wait(): x.wait()을 invoke 한 프로세스는 다른 프로세스가 x.signal()을 invoke 하기 전까지 suspend 된다.
      2. x.signal(): x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다.
    4. Bounded-Buffer Problem: 다른 프로세스의 접근을 모니터가 막아주기 때문에 공유 버퍼에 lock을 걸고 푸는 작업이 필요 없다.
    5. Dining-Philosopher Problem: 동일

 

 

 

 

이화여자대학교 반효경 교수님의 [2014년 1학기 운영체제], [2017년 1학기 운영체제] 강의 정리입니다.

  [운영체제 Operating System Concepts] 교재를 참고하였습니다. 감사합니다.

https://core.ewha.ac.kr/publicview/C0101020140411143154161543?vmode=f 

 

반효경 [운영체제] 15. Process Synchronization 4

설명이 없습니다.

core.ewha.ac.kr

 

728x90

'CS > 운영체제' 카테고리의 다른 글

[운영체제] Chapter 8. Memory Management (1)  (0) 2023.01.16
[운영체제] Chapter 7. Deadlock (1), (2)  (0) 2023.01.05
[운영체제] Chapter 6. Process Synchronization (3)  (2) 2022.12.28
[운영체제] Chapter 6. Process Synchronization (2)  (1) 2022.12.24
[운영체제] Chapter 6. Process Synchronization (1)  (0) 2022.12.23

관련글

댓글 0

티스토리툴바