KOCW - 운영체제(이화여대 반효경 교수)
4장 CPU 스케줄링

Process Synchronization(동기화)

데이터의 접근

컴퓨 연산 과정(단일 로딩)

데이터 로딩 -> 연산 -> 저장

항상 데이터를 저장하는 곳(Memory, 디스크, 해당 프로세스의 주소 공간)에서 데이터를 불러오고, 연산(CPU, 컴퓨터내부, 프로세스)을 진행한 다음 다시 저장을 하는 과정이 반복된다.

Race condition

• 위 그림처럼 한 군데의 메모리에서 데이터를 읽어가는 곳(연산하는 곳)이 여러 곳일 경우 Race Condition의 가능성이 있다.

• Race Condition(경쟁상태) : 가령 어떤 한 데이터를 두 군데에서 읽어간 다음 각각 +1, -1을 해줬다고 하자, 먼저 -1을 한 값이 저장되었다고 할 때, 후에 저장하려고 한 +1값은 반영이 안되는 현상이 발생한다.

Race condition의 발생

1. 인터럽트 vs 커널

위 그림처럼 커널에서 연산을 수행하다가 인터럽트로 인해 인터럽트 요청을 처리하는데 공교롭게도 그 인터럽트 처리 루틴에서 기존 커널에서 사용하던 데이터를 조작하는 함수가 실행될 수 있다.

이 과정에서 커널 -> 인터럽트 처리 간 문맥교환이 일어나게 되는데, 그 때의 데이터 값이 문맥에 고스란히 남아있기 때문에 인터럽트에서 다시 원래의 프로세스로 돌아오면 문맥교환 했을때의 원래 데이터가 남아있다. 따라서 인터럽트 처리는 적용이 안되는 것이다.

해결책 : 커널모드일때 인터럽트를 disable 시키고 커널모드가 끝나면 인터럽트 처리

2. 

위 프로세스에서 user mode일 경우에는 프로세스 내부 데이터로 작업을 수행하기 때문에 Race condition이 발생하지 않지만, system call을 통해 kernel에서 작업을 수행할 경우에는 Kernel의 데이터(프로세스의 입장에서는 공유데이터)를 사용하기 때문에 Race condition이 발생할 수 있다.

위 그림처럼 A 프로세스를 실행하다가 CPU 할당 시간이 종료되어 문맥교환이 일어났다고 하자. 프로세스 B에서 시스템콜을 통해 kernel mode로 돌입한 후 같은 데이터를 사용했다면, Race condition이 충분히 일어날 여지가 있다. 프로세스 A가 CPU를 돌려 받았을때, 문맥교환이 다시 일어나면서 레지스터에 저장되어있던 한 데이터의 값은 B에서 수행했던 함수가 적용되지 않고 보존되어있을 것이고, 해당 값인 상태로 다시 연산을 수행하면 문맥 교환 이전의 값에 함수가 적용되어 저장될 것이다.

해결책 : Kernel mode에서는 CPU를 preempt 하지 않고, kernel mode에서 사용자 모드로 돌아갈 때 preempt한다.

3. CPU가 여러개일 때

CPU가 여러 개 있을 경우 인터럽트를 disable 시킨다고 해결이 안됨(다른 CPU에서 인터럽트 처리루틴이 가능하고 데이터 또한 인터럽트가 아니더라도 읽어갈 수 있기 때문에)

해결책 1 : 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법

-> 하지만 이 방법은 매우 비효율적이다. 딱 봐도 CPU가 여러 개인데 하나만 사용한다? 바보같은 방법이다.

해결책 2 : 운영체제나 CPU에 lock을 거는 것이 아니라, 데이터 자체에 접근할때마다 lock/unlock을 거는 것이다.

Process Synchronization 문제

Critical-Section Problem

• n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

• 근본적으로 데이터 처리를 한 번에 수행할 수가 없어서 생기는 문제, 데이터를 읽어오고 처리하고 다시 저장하는 과정에서 다른 프로세스가 끼어들면 문제가 발생하는 것이다.

Critical-Section : 공유 데이터에 접근하는 코드

다른 코드가 공유 데이터를 사용중이면 Critical-Section이 진행되기 전에 다른 코드를 걸어서 공유 데이터에 접근을 못하게 막는 것(lock)이 필요하다. 마찬가지로 데이터 사용이 끝나면 또 다른 코드를 걸어서 접근 금지를 해제(unlock)시켜야한다.

Algorithm 1

Synchronization variable

• Turn = 0일 경우 P0를 수행중이기 때문에 critical section에 들어가고, 아닐 경우에는 계속 대기를 한다. 위 알고리즘은 critical section을 수행한 다음 turn = 1을 통해 다른 프로세스에게 턴을 넘겨준다.

• 동작 여부? : 두 프로세스 0과 1이 동시에 critical section에 들어가지는 않는다.

• 문제점 : 동시에 들어가는 문제는 해결, but 과잉양보 문제 발생(상대방이 turn을 내 turn으로 바꿔주어야 들어갈 수 있음, 각 프로세스의 특성 고려 X)

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

Critical-Section Problem을 해결하기 위해 알고리즘에게 필요한 조건 세 가지

1. Mutual Exclusion(상호 배제) : 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.

2. Progress(진행) : 아무도 critical section에 있지 않은 경우 들어가고자 하는 프로세스가 있으면 무조건 들어가게 해준다

3. Bounded Waiting(유한대기) : Starvation 방지, 특정 프로세스가 자원(공유 데이터)를 영원히 사용 못하는 경우 방지(A, B, C가 있는데 A,B만 계속 들어가는 경우)

Algorithm 2(flag)

• 프로세스마다 각자의 깃발이 있는데, critical section에 들어가고 싶을 경우 깃발을 들게 된다. 그 후 다른 깃발이 모두 내려졌을 때 critical section에 진입, 마지막엔 자신의 깃발을 내리면서 퇴장

• 문제점 : 깃발만 들고 눈치싸움(과잉 양보 문제 발생 가능, 위 조건에서 2번 위배)

Algorithm 3(Peterson's Algorithm)

• 1번 알고리즘 + 2번 알고리즘(깃발 + 턴)

• 깃발을 든 경우에 한해서 프로세스 간 turn을 정하게 된다.

• 자신이 깃발을 들고 있고, 자신의 턴일 경우 상대방의 깃발 상태에 상관 없이 critical section 진입.

• 문제점 : 동작은 하지만 비효율적인 면이 있음

  • Busy Waiting(spin lock!) : 결국 프로세스 j가 턴을 i에게 넘겨줘야 while문을 탈출할 수 있는 구조이기 때문에 턴을 넘겨받기 전까지는 계속해서 CPU와 Memory를 사용하면서 대기해야한다(CPU 낭비).

Synchronization Hardware

• 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

Test & set

Test_and_set(a) -> a의 값이 1이든 0이든 상관없이 1로 만들어주는 함수

업로드중..

• READ와 TRUE 처리를 동시에 수행하여 앞선 문제를 해결

Semaphores(Busy wait)

추상 자료형

• 정의 : 어떤 Object & Operation으로 정의된 자료형

• Semaphore S : 세마포어 변수 S는 정수로 정의, P(S) 연산과 V(S) 연산에 의해서만 접근 가능

P(S) : 자원을 획득하는 과정(lock)
V(S) : 자원을 반납하는 과정(unlock)

• 예시 - S값이 5일 경우 : P 연산 5번에 의해 현재 남아있는 자원이 0일 경우 P 연산이 들어오면 다른 연산에서 자원을 반납하기 전까지 대기

• 용도 : 공유 자원들을 카운팅하고 남아있는 자원들을 확인하기 위해서 세마포어 변수를 사용

Critical Section of n Processes

• semaphore mutex : Critical section에 들어갈 수 있는 개수가 1개

• 위와 같은 연산을 atomic하게 수행하기 위해 하드웨어의 도움이 필요하다.

Semaphores(Block / Wakeup)

• 하드웨어의 도움을 받아서 atomic하게 연산을 수행할 수 있게 되었으나 자원이 0일 경우 V(S)연산이 들어오기 전까지 계속 기다려야하기 때문에 Busy wait 문제는 해결되지 않았음.

Block / Wakeup Implementation

• Block : 남은 자원이 없을 경우 프로세스는 blocked 됨. 커널은 이 프로세스를 suspend시키고 이 프로세스의 PCB를 위 그림처럼 Semaphore의 대기 큐에 넣게 됨

• wakeup(P) : block된 프로세스 P를 Wakeup 시키고 이 프로세스의 PCB를 ready queue에 넣게 됨

• P 연산은 S에서 무조건 1을 빼게 됨. 이 때 S값이 음수일 경우 S.L(세마포어 리스트)에 추가하고 block

• V 연산은 S값을 1 추가 시키게 됨. 누군가 V 연산을 실행했을 때 S값이 0 이하일 경우 S.L에 있는 프로세스를 Wakeup하고 리스트에서 제거

Busy-wait vs Block/wakeup

• C.S의 길이가 긴 경우 Block/Wakeup이 더 좋은 알고리즘

• C.S의 길이가 매우 짧은 경우 busy-wait에 비해 Block/Wakeup의 오버헤드가 더 커질 수 있음

• 일반적인 경우 : Block/wakeup 방식이 더 좋음

• C.S의 길이가 길다 = C.S 진입 경쟁이 치열하다.

• C.S의 길이가 짧다 = C.S 경쟁이 널널하다.

Two Types of Semaphores

1. Counting semaphore(자원의 개수를 세는 방법) : S값이 0 이상인 임의의 정수값

2. Binary semaphore(=mutex) : S가 0 또는 1의 값만 가질 수 있음, 주로 lock/unlock에 사용

Deadlock and Starvation

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

• 해결책 : 자원 획득 순서를 정해주면 데드락 현상을 방지할 수 있음

Starvation : indefinite blocking

Classical Problems of Synchronization(전통적 동기화 문제)

Bounded-Buffer Problem

• 이 문제에서는 공유 버퍼를 동시에 접근할 때 문제가 발생하기 때문에 Binary Semaphore로 (Lock/Unlock) 상태를 조정하고, Full Buffer와 Empty Buffer를 카운팅하기 위해서 Counting BUffer를 사용하였다.

Producer Process

• 생산자 프로세스 도착시 : Empty Buffer가 필요하며 없을 경우 대기(Consumer Process가 Empty Buffer를 만들어줄 때까지)

• Empty Buffer가 생성 되었을 때 : 공유 데이터에 Lock을 걸고 Empty Buffer에 데이터 생성 -> Lock 해제 및 Full Buffer를 가리키는 값 1 증가(Consumer가 Full Buffer를 획득할 수 있도록)

❗ Consumer Process의 경우 반대로 생각하면 된다

코드

• 좌측이 생산자 프로세스, 우측이 소비자 프로세스

Readers-Writers Problem

• 한 프로세스가 DB에 write중일 때 다른 process가 접근하지 못하도록 해야하는 문제

• Reader process는 동시에 여럿이 해도 상관 X, 하지만 Write Process는 여럿이 하면 문제가 발생할 수 있음

• 그렇기 때문에 접근 시에 Lock을 걸면 문제를 해결할 수 는 있지만 매우 비효율적임

• 따라서 Reader는 여럿에게 허락, Write는 한 프로세스에게만 허락하는 알고리즘을 채택해야함.

Shared data

• 자체(Reader 여럿 접근 가능, Writer 한 개만 접근 가능)
• readcount (현재 DB에 접근 중인 Reader의 수) - Readcount 또한 공유데이터이기 때문에 mutex(binary semaphore)로 lock을 건다.

Synchronization variables

• mutex
• db

코드

• 코드 해석
  • P(mutex) -> readcount 1 증가(만약 증가시킨 후 readcount가 1일 경우? -> 최초로 DB에 접근했기 때문에 lock을 걸어야함.) reading이 끝나면 readcount -1, 만약 readcount가0이 되면 DB unlock
• reader가 끊임없이 도착하면 writer는 영원히 기다려야 할 수도 있기 때문에 위 코드는 starvation이 발생할 수 있음

Dining-Philosophers Problem(식사하는 철학자 문제)

다섯 명의 철학자가 식탁에 앉아서 생각, 식사를 반복한다. 그런데 각 철학자마다 배고파지는 주기가 다르다(동기화가 되어있지 않음), 또한 젓가락을 집어서 밥을 먹어야 하는데 젓가락이 한쪽씩 공유데이터로 이루어져있다. 즉 한 철학자가 밥을 먹고 있으면 양 옆의 철학자는 밥먹을 못먹게 되는 것이다.

문제

1. 모든 철학자가 굶어 죽으면 안된다

2. 한 철학자가 밥을 먹고 있는 경우에는 양 옆의 철학자가 밥을 못먹게 lock을 걸어야 한다.

• 위와 같은 경우 모든 철학자가 한쪽씩 젓가락을 집을 경우 모든 철학자가 영원히 밥을 못먹게 된다(다른 젓가락 자원이 나오는걸 영원히 기다리게 됨)

코드 1

위 코드는 왼쪽 젓가락을 들게 해서 문제를 해결하려고 하였으나, 모든 철학자가 동시에 배고플 경우(데드락)를 해결하지 못하였다.

해결 방안

1. 4명의 철학자만 테이블에 앉을 수 있도록 한다.

2. 왼쪽 젓가락을 잡았을 때 오른쪽 젓가락도 잡을 수 있는 경우에만 젓가락을 잡을 수 있게 한다.

3. 짝수 철학자 - 왼쪽 젓가락, 홀수 철학자 - 오른쪽 젓가락을 잡게 한다.

2번째 해결방안(Monitor 기반)

• pickup() : 젓가락을 드는 함수

• putdown() : 젓가락을 내리는 함수

• P(mutex) : 젓가락을 들었을때(내렸을때) 락을 거는 함수

• V(mutex) : 락을 푸는 함수

• text(i) : 양쪽 젓가락을 들 수 있는지 체크

• 위 코드는 젓가락을 내려놓을 때 양 옆 철학자의 state를 체크하고, 만약 현재 들고 있는 철학자가 내려놓으면 양쪽 다 들 수 있는지 확인하고, 만약 양쪽 다 들 수 있는 철학자면 젓가락을 들 수 있는 권한을 부여하게 된다.

Monitor

Semaphore의 문제점

• 코딩 난이도(상)
• 정학성의 입증이 어렵다
• 자발적 협력이 필요하다
• 한번의 실수가 모든 시스템에 치명적 영향

🖥 Monitor란?

공유데이터에 대한 접근을 모니터 안에서 정의된 함수를 통해서만 할 수 있게 함

• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능

• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없음

• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용

condition x, y; : condition variable은 wait와 signal 연산에 의해서만 접근 가능

• x.wait(); : 자원의 여분이 없을 경우 잠들게 하는 함수

• x.signal(); : 자원 여분이 있을 경우 큐에서 프로세스를 깨우는 함수

Bounded-Buffer Problem

semaphore 코드와의 차이점

• 공유 데이터에 대한 lock을 걸 필요가 없음

• 생산자와 소비자 프로세스는 각각 자신들이 원하는 자원이 없을 경우 wait() 함수로 잠들어 있다가 자원이 생기면 signal() 함수로 깨어나게 된다.

Dining Philosophers Problem

semaphore 코드와의 차이점

• 기존에는 모든 철학자가 한쪽 젓가락만 집을 경우 영원히 데드락에 걸리는 문제가 발생하였음.

• semaphore 코드에서는 양쪽 젓가락을 잡을 수 있을 경우에만 젓가락을 잡게 해주었는데 Monitor에서도 마찬가지다.

• 생각하는 상태, 배고픈 상태, 먹고있는 상태로 상태를 나눈다.

• 그리고 젓가락을 드는 함수, 젓가락을 내려놓는 함수, 상태를 테스트하는 함수로 나눈다.