[OS] 7. 프로세스 동기화, 임계구역 - (1)

[이화여자대학교 반효경 교수님의 강의를 듣고 정리한 글입니다.]

운영체제

운영체제 운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각 www.kocw.net

운영체제

---

[그림과 함께 편하게 보려면 여기로]

https://adorable-aspen-d23.notion.site/OS-7-1-dfb21864877a449793d54f6d0210f8dc

[OS] 7. 프로세스 동기화, 임계구역 - (1)

1. 프로세스 동기화

1. 왜 필요할까? - Process Synchronizaion 문제

• 컴퓨터 연산을 할 때는 항상 읽어들이거나, 쓰거나 연산을 수행한다.
  • 같은 데이터를 한 프로세스가 아니라 여러 프로세스가 함께 접근하려고 한다면 어떨까?
    • A가 먼저 데이터 Z에 접근해서 read하고 write중이었는데, 아뿔싸! 모종의 interrupt가 발생해서 (timer, I/O등..) B에게 CPU제어권이 넘어갔다.
    • B도 Z에 접근해서 read하고 write 연산을 수행한다.
    • 이후 A가 다시 CPU를 가져가게 되는데, A의 context는 이전에 읽어들인 Z값이 저장되어 있다. 따라서 write는 B가 새로 바꿔놓은 Z가 아니라 옛날 Z값을 베이스로 일어난다.
  • 아니 근데, 프로세스는 별도의 주소 영역을 가져서 공유할 데이터가 없지 않나요?
    • 원래 그런데, ‘운영체제'가 끼어들게 되면 프로세스들도 공유하는 데이터가 생길 수 있다.
    • 시스템콜 등에서는 커널의 데이터를 사용하는데, 커널의 데이터는 프로세스들이 공유하는 공유변수이다.
    • 또한, 프로세스들이 Shared memory를 쓴다면 공유하는 데이터가 생길 수 있다.

2. Race Condition (경쟁 조건)

• 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황에서 발생하는 문제
• 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.

⇒ Mutual Exclusion (상호배제) 개념이 필요하다.

• 커널 내부 데이터를 접근하는 루틴들 간
  • 프로세스의 시스템 콜에 의해서 커널 모드를 수행 중인데 CPU가 다른 프로세스에 넘어가는 경우(context switching)
    • 해결 방법 ⇒ 커널 모드 중에는 CPU를 선점하지 않도록 한다. (사용자 모드에서만 선점할 수 있게끔)
  • 커널 모드 중 인터럽트가 발생하는 경우
    • 해결 방법 ⇒ 커널 고유 변수를 건드리는 동안에는 인터럽트가 발생해도 disable하여 인터럽트가 연산이 끝나고 수행될 수 있게끔 한다.
• 멀티 프로세서
  • 문제점) CPU선점이나 인터럽트를 막는 것으로 문제가 해결되지 않는다. CPU가 여러개이기 때문이다!
    • 해결 방법 → 공유 변수 자체에 lock을 걸면 어떨까? Good!

3. Process Synchronization 문제

• 공유 데이터의 동시 접근으로 인해 데이터의 불일치가 발생하는 것을 해결한다.
• ⇒ 협력 프로세스들 간의 실행 순서를 정해주면 어떨까? (일관성 유지)
• 공유 데이터 접근 문제
  • High-level Language에서 한 문장에 해당하는 instruction이,
  • Low-level 에서 기계어로서 CPU에서 실행될 때 atomic하게 한 번에 처리될 수 없기 때문에 발생하는 문제

2. Critical-Section Problem (임계구역)

• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 코드 구역
• 하나의 프로세스가 임계구역에 존재할 때, 다른 모든 프로세스는 임계구역에 들어갈 수 없어야 한다. (일관성 유지)
  • lock 이용
  • → lock이 걸리면 CPU를 뺏기더라도 B는 임계구역에 들어가지 못하고, unlock되어야 들어갈 수 있다.

1. 임계구역의 해결법 충족 조건

1. Mutual Exclusion (상호 배제)

• 한 프로세스가 임계구역에 들어가 있다면, 다른 모든 프로세스들은 임계 구역에 들어갈 수 없다.

2. Progress

• 아무도 임계구역에 있지 않은 상태에서 들어가고자 하는 프로세스가 있으면 임계구역에 들어가게 해주어야 한다.

3. Bounded Waiting(유한대기)

• 특정 프로세스 입장에서 임계구역으로 들어가지 못하는 기아 현상이 일어나지 않도록 해야한다.
  • 프로세스가 임계구역에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 임계 구역에 들어가는 횟수에 제한이 있어야 한다.

2. SW적 알고리즘 해결법

1. 알고리즘1 - Synchronization Variable Setting

• turn이라는 변수를 이용해서 제어한다.
  • turn이 0이면 P0차례, turn이 1이면 P1차례
  • 상대 프로세스가 turn을 바꿔준다.

//프로세스 0입장
int turn = 0;

do{
	1. while(turn!=0); //내 차례인가? - 프로세스0번은 본인차례까지 기다렸다가 임계구역 들어감
	critical section
	2. turn = 1; //너 차례야
	remainder section;
} while(1);

• 특징
  • Mutual Exclusion은 만족한다.
• 문제점
  • Progress는 만족하지 않는다.
    • P0은 빈번하게 들어가는애고, P1은 가아아아끔 들어가는 애라면 P0는 들어가고 싶지만 못들어간다.
    • 상대방이 turn을 바꿔주기 때문

2. 알고리즘2 - Flag Setting

• 프로세스마다 flag를 두어 제어한다.
  • 들어가고 싶다면 flag를 들어서 의사를 표시한다.
  • 이후 상대방이 들고있는지를 체크한다.

boolean flag[2];//process 각각 자신의 flag를 가지고 있음

do{
	1.flag[i] = true; //나 들어갈거야 알려줌
	2.while(flag[j]); //상대방이 들어가있는지 봄

	critical section

	3.flag[i] = false; //나 나왔어 알려줌
	remainder section
} while(1);

• 특징
  • Mutual Exclusion은 만족한다.
• 문제점
  • Progress는 만족하지 않는다.
    • 프로세스A가 1번과 2번 사이에 CPU를 뺏겼다라고 해보자. 깃발을 든 상태에서 B체크는 못하고 넘어간 것이다.
    • 이후 B의 차례가 왔을 때 B도 깃발 든다. 근데 A가 들고 있다.
    • 어라라 A의 차례가 되었다. 근데 B도 들고있다. 오마갓 아무도 못들어간다.

3. 알고리즘3 - Peterson’s Algorithm

• turn, flag를 모두 사용해서 제어한다.
  • 임계구역에 들어가기 전에 깃발을 들고, turn을 상대방으로 바꿔준다.
  • 이후에 상대방이 flag를 들고 있고, 상대방 turn인지를 체크한다.

do{
	flag[i] = true; //나 들어갈거야 알려줌 //flag와 turn의 순서를 바꾸면 안된다.
	turn = j; //상대방 차례임을 알려줌
	while(flag[j] && turn==j); //상대방이 깃발들고있고, 상대방 차례일때까지 기다림

	critical section

	flag[i] = false; //나 나왔어 알려줌
	remainder section
}while(1);

• 특징
  • Mutual Exclusion 만족
    • 두 프로세스가 모두 자기 임계구역을 수행하려면 flag[i] == flag[j] == true인 상태이다.
    • 그러나, 공유 변수인 turn은 i,j중 어느 하나의 값만을 가질 수 있다.
      • 따라서 둘 중 하나만이 while문을 통과한다.
  • Progress 만족
    • 프로세스 Pj가 임계구역에 들어갈 준비가 되어 있지 않은 경우
      • flag[j] == false 이므로 Pi가 임계구역에 진입한다.
    • 프로세스 Pj의 flag[j] == true인 경우
      • turn == i
        • Pi가 임계구역 진입
      • turn == j
        • Pj가 임계구역 진입
    ⇒ 어느 하나가 반드시 진입한다.
    • 만약 Pj가 진입할 경우, Pj가 임계구역을 빠져나올 때 flag[j]를 false로 지정하여 Pi가 진입하도록 만들어준다. (반대도 동일)
  • bounded waiting 만족
    • Pj가 임계구역 수행을 마치고 재빠르게 다시 진입하려고 해도 마지막에 turn=i로 바꾸기 때문에 Pi가 while에서 기다리고 있다면 i가 들어가게 됨
• 문제점
  • Busy Waiting - 비효율적
    • 계속 CPU와 Memory를 쓰면서 기다린다.

3. HW적 해결법

• CPU instruction이 atomic하지 않았기 때문에 이와 같은 사단이 났었다. (중간에 CPU 뺏기는 문제)
  • 그러니까 하드웨어적으로 묶어버리자
• Test_and_set(a)
  • a라는 값을 읽어가고, a라는 값을 참으로 만드는 것을 한번에 수행하는 하드웨어 연산

boolean lock = false;

do{
	while(Test_and_Set(lock));
	critical section
	lock = false;
	remainder section
} while(1);

4. Semaphore

• 앞에서 제시한 SW 알고리즘 해결법을 매번 구현해야할까? 귀찮다.
  • ⇒ Abstract Data Type (추상화 데이터 타입)으로 세마포어라는 것을 만들었다.
  • 개발자는 그냥 이걸 가져다 쓰면 동기화 문제를 해결할 수 있다.
• 공유 자원을 획득하고 반납하는 과정을 수행해준다.

semaphore mutex //1개로 초기화

do{
	P(mutex); //공유자원 mutex개 획득, lock을 거는 과정
	critical section
	V(mutex); //공유자원 반납
	remainder section
} while(1);

• 단점
  • P연산에서 아직도 Busy-waiting 문제가 발생한다.
  ⇒ Block & WakeUp방식 등장

Block & WakeUp (=sleep lock)

• 현재 세마포어를 사용할 수 없는 프로세스는 block 시키고, wait queue에 넣는다.
• 공유 자원을 반납할 때, 반납하면서 wakeUp을 통해 잠들어 있는 프로세스를 깨워준다.

• 장점
  • CPU를 더 굴릴 수 있다.
• 단점
  • Critical Section의 길이가 매우 짧은 경우, 오히려 Context Switching의 오버헤드가 커질 수 있다.

5. Monitor

• 세마포어를 사용하더라도 문제가 발생한다.
  • 한 번의 실수가 모든 시스템에 치명적인 영향을 준다. (졸면서 코딩하면 치명적)

  //Mutual Exclusion 깨짐
  V(mutex)
  Critical Section
  P(mutex)
  
  //Deadlock
  P(mutex)
  Critical Section
  P(mutex)
  

  • 정확성 입증이 어렵다. (어디에 P연산을 사용해야 하는지, V연산을 사용해야 하는지 어려움)

Monitor

: High-level Language에서 제공하는 동기화 수단

• 세마포어에서는 Lock을 프로그래머가 직접 걸었다. 하지만 모니터에서는 안그래도 됨

• 객체 지향 프로그램의 Class 개념과 비슷하게 설계된다.
  • 한 객체에 공유하고 있는 shared variable이 존재하며, 멤버 함수를 통해 instruction을 제공하며 이 instruction을 통해 공유 변수에 대한 모든 접근을 통제한다.
    • 모니터 안에 공유 변수를 정의하고, 멤버 함수를 정의해서 그 함수를 통해서만 공유 변수에 접근이 가능하게 한다.
  • 그 처리는 entry queue를 통해 한다. - 뭔말?
• 쉽게 말하자면, 모니터라는 애가 큐를 만들어서 공유변수를 관리하는데, 알아서 프로세스 하나만 활동하게 막아준다는 얘기!
• 모니터는 한 번에 하나의 프로세스만이 활동 가능하다.
  • Condition Variable을 사용하여 통제 (세마포어와 유사)
    • 근데, 얘는 그냥 잠들게 하고 깨우기 위한 변수임
      • 세마포어처럼 값이 증가하거나 감소하는 것은 아니다.
    • x.wait(), x.signal()
    
    • 모니터 안에서는 lock을 거는 로직이 필요가 없다.
    • Condition variable = full, empty
  • 생산자-소비자 문제

• Condition variable = self