운영체제 - 05

강의

http://www.kocw.net/home/search/kemView.do?kemId=1226304

운영체제 - 병행 제어

1. 운영체제 동기화

1.1 race condition

• 두 개 이상의 concurrent access(동시 접근)한 스레드들이 공유된 자원에 접근하려고 할 때 동기화 메커니즘 없이 접근하려고 하는 상황
• 동기화란 프로세스 또는 스레드들이 수행되는 시점을 조절하는 것을 말함

1.2 발생원인

1.2.1 kernel 수행 중 인터럽트 발생

• 커널 모드 running 중 인터럽트가 발생하여 인터럽트 처리루틴을 수행
• 양쪽 다 커널 모드이므로 커널 주고 공간을 공유
• 해결책: 커널 수행 중에는 인터럽트 신호를 받지 않음(disable, enable 처리)

1.2.2 프로세스가 시스템콜을 하여 커널 모드로 수행 중인데 context switch가 일어나는 경우

• 두 프로세스의 주소 공간에는 데이터 공유가 없음. 프로세스는 새로 생성되어 서로 다른 동작을 하니까 당연
• 그러나 시스템 콜을 하면 커널 주소 공간의 data를 접근함. 운영체제(kernel)는 하나니까.

• 이때 다른 프로세스가 CPU의 권한을 가져가면(preempt) race condition이 발생

• 해결책: 커널 모드에서 수행 중이면 CPU를 preemt하지 않음.

1.2.3 멀티프로세서에서 공유 메모리내에 커널 데이터

• 어떤 CPU가 마지막으로 count를 저장했는가? –> race condition
• 멀티프로세서의 경우 인터럽트 enable/disable로 해결되지 않음
• 해결책 1: 한 번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법. 즉, 운영체제 전체가 lock. 그러나 이것은 오버헤드(비효율성) 문제가 발생
• 해결책 2: 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 하는 방법

2. 프로세스 동기화

• 운영체제랑 똑같이 두 프로세스 간의 race condition 문제

2.1 critical section problem

• 각 프로세스의 코드 세그먼트에는 공유 데이터를 접근하는 코드인 critical section이 존재

• 하나의 프로세스가 ciritcal section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

• 해결책 크리티컬 섹션 앞뒤로 접근할 수 있고 없고(lock/unlock)하는 코드를 삽입
• 이를 해결하기 위해 다음과 같은 충족 조건이 필요

2.2 프로그램적 해결법의 충족 조건

2.2.1 Mutual Exclusion (상호배체)

• 어떤 프로세스가 크리터컬 섹션에서 수행중이면 다른 프로세스는 들어오면 안된다.

2.2.2 Progress (진행)

• 아무도 크리티컬 섹션이 있지 않으면 크리티컬 섹션이 필요한 프로세스에게 들어가게 해줘야 한다.

2.2.3 Bounded Waiting(유한 대기)

• 프로세스가 크리티컬 섹션에 들어가려고 요청하면 그 요청이 허용될 때까지 다른 프로세스들이 크리티컬 섹션에 들어가는 횟수가 제한되어야 한다.

가정

• 모든 프로세스의 수행 속도는 0보다 크다.
• 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

2.3 소프트웨어 해결법

2.3.1 알고리즘 1

• 내 차례가 올때까지 기다리다가 차례가오면 수행 후 다음 프로세스에게 차례를 넘김

• 과잉양보: 반드시 한 번씩 교대로 들어가야 함(swap-trun). 따라서 빈번히 크리티컬 섹션을 들어가야하는 프로세스가 있는 경우.

2.3.2 알고리즘 2

• 다른 모든 프로세스의 요청(flag) 상태를 확인한다. 다른 프로세스들의 요청이 없으면 내가 크리티컬 섹션을 접근한다. 일이 끝나면 요청(flag) 을 거둔다.
• 프로세스들이 서로 양보하는 상황이 발생. while(flag[j]); 에서 서로 들어가지 않고 아무도 크리티컬 섹션을 접근하려 하지 않음.

2.3.3 알고리즘 3 (Peterson’s 알고리즘)

• 알고리즘 1,2를 합친것

• 크리티컬 섹션 해결법 3가지 모두 충족
• Busy Waiting. Spin Lock. 문제는 비효율적. 오래 걸리는 프로레스가 크리티컬 섹션을 잡고 있는 동안 다른 프로세스(or CPU)가 계속 while만 반복. 결국 자원 낭비.

2.4 하드웨어 해결법

• 하드웨어적으로 Test & modify를 atomic(자동적으로)하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결
• 즉, Test_and_Set(lock) 부분에서 a의 값을 읽어가면서 a를 동시에 lock을 걸어줌
• 그 사이 다른 프로세스가 a를 읽고 싶으나 lock이 걸려 있어서 못 읽음

3 Semaphores

• 앞의 방식들을 추상화시킴. 추상 자료형 이라고 불림

• P 연산은 자원을 획득하는 과정

• V 연산은 자원을 반납하는 과정

• 세마포어 5(S : Mutex라고 부름)라고 하는 것은 프로세스(예를 들어)가 자원 5개를 사용할 수 있다는 것
• 그래서 프로세스가 P연산을 통해 해당 자원 5개를 사용한다.
• 이때 다른 프로세스가 자원을 사용하고 싶은데 세마포어의 S가 0이면 사용할 수 가 없고
• 사용하던 프로세스가 자원을 2개 다 쓰면 V연산을 통해 반납하면
• 다른 프로세스가 P연산을 통해자원 2개를 사용
• 그러나 이것도 Busy Waiting 문제가 발생

3.1 Block / Wake up (Sleep Lock)

• 남아 있는 자원을 계속해서 while 할 필요가 없다.
• 한 번 확인 후 block으로 상태 변경
• 사용하고 있는 프로세스가 자원을 반납하면 block한 프로세스를 wake up
• block한 프로세스들은 세마포어 리스트에 연결되어 있음.

3.2 Block wakeup overhead vs ciritical section 정의

• block wake up도 빈번하면 오버헤드 발생(문맥 교환이 발생하니까)
• 크리티컬 섹션 길이가 길면 block wake up이 적당
• 짧으면 그냥 busy wait하게 구성하는게 적당
• 그러나 보통의 경우 block이 나음

3.3 세마포어 종류

3.3.1 카운팅 세마포어

• 도메인이 0이상인 임의의 정수 값
• 주로 자원 카운팅에 사용

3.3.2 바이너리 세마포어(=mutex)

• 0 or 1만 가지는 세마포어
• 주로 mutual exclusion (lock , unlock)에 사용

4 Deadlock and Starvation

• Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

  

• 각 프로세스가 서로의 자원을 원하는 상태를 말함. 서로 사용하고 있는 자원이 필요하기 때문에 서로 내놓지를 않음.
• Starvation : Indefinite(무기한) blocking. 프로세스가 suspend(연기)된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

5. 동기화의 전통적인 문제

5.1 Bounded-Buffer 문제(공유된 버퍼 문제). 생산자-소비자 문제

• 공유 버퍼에 lock, unlock으로 해결
• 카운팅 세마포어 사용을 하여 유한한 자원을 관리
• 바이너리 세마포어를 사용하여 각 자원의 lock을 관리

• 코드로 구현한 모습

5.2 Readers and Writer 문제

• 쓰는 사람은 문제가 되지만 읽는 사람은 데이터 변형이 아니므로 lock이여도 접근 가능

5.3 Dining - Philosophers Problem

• 젓가락(자원)은 총 5개 사람(프로세스)은 다섯 개라고 가정(젓가락은 2개를 사용하여야 밥을 먹을 수 있음(일을 수행))
• 다섯 명이 모두 왼쪽 젓가락을 잡으려고 할 때 아무도 먹지 못함 == Deadlock 발생

5.3.1 해결

• 1. 4명의 사람만 앉게 한다.
• 1. 젓가락을 두 개 모두 잡을 수 있을 때 젓가락을 가지게 한다.
• 1. 짝수 철학자는 왼쪽 젓가락부터 집도록 한다. (반대도 가능)

• 2번째 방식을 코드로 구현한 예제
• 사실은 뒤에 모니터에서의 구현을 세마포어로 변형해서 만든 코드

6. 모니터

6.1 세마포어의 문제점

• 코딩이 힘듬
• 정확성 입증이 어려움
• 자발적 협력이 필요
• 한 번의 실수가 모든 시스템에 치명적 영향

6.2 모니터란

• 동시 수행중인 프로세스 사이에서 추상적 데이터 타입의 안전한 공유를 보장하기 위한 고급 레벨 동기화 구조

• 공유데이터를 모니터 안에서 정의
• 공유데이터를 접근하기 위해선 모니터 안에서 제공하는 코드를 통해 접근
• 프로세스가 직접 lock을 걸 필요가 없고 모니터가 알아서 프로세스의 공유데이터 접근을 통제
• 모니터에서는 한번에 하나의 프로세스만이 활동. 두 프로세스의 동시접근이 기본적으로 없음
• 모니터는 프로세스가 모니터 안에 기다릴 수 있도록 condition variable(condition x, y) 사용
• condition variable은 wait과 signal 연산에 의해서 접근 가능

• x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다.

• x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다.

6.3 Bounded-Buffer 문제

• 세마포어와 유사하나 다른 점은 자원의 개수를 세지 않음

6.4 Dining - Philosophers Problem