2022.12.27 - [Operating System] - [운영체제] 프로세스 동기화 1 (Race Condition/경쟁 상태)
[운영체제] 프로세스 동기화 1 (Race Condition/경쟁 상태)
● 데이터의 접근 데이터는 Storage Box에 저장되어 있고 그 데이터를 가지고 Execution Box 위치에서 연산 작업을 한 후 다시 원래 위치인 Storage Box에 저장한다. 이렇게 데이터를 읽고 연산/수정 후 결
rannnneey.tistory.com
2023.01.04 - [Operating System] - [운영체제] 프로세스 동기화 2 (Critical Section, Race condition)
[운영체제] 프로세스 동기화 2 (Critical Section, Race condition)
Race condition : 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황 공유 데이터와 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다. 데이터의 최종 연산 결과는 마지막에 데이터를 다
rannnneey.tistory.com
[운영체제] 프로세스 동기화 3 (Semaphore, Block & Wake-up, DeadLock, Starvation)
2022.12.27 - [Operating System] - [운영체제] 프로세스 동기화 1 (Race Condition/경쟁 상태) [운영체제] 프로세스 동기화 1 (Race Condition/경쟁 상태) ● 데이터의 접근 데이터는 Storage Box에 저장되어 있고 그 데
rannnneey.tistory.com
Classical Problems of Synchronization
- Bounded-Buffer Problem (Producer-Consumer Problem)
- Readers and Writers Problem
- Dining-Philosophers Problem
● Bounded-Buffer Problem (Producer-Consumer Problem, 생산자 소비자 문제)
Producer와 Consumer는 하나만 있는 게 아니라 여러 개 존재한다. ProducerProducer는 공유 버퍼에다가 데이터를 하나 만들어서 Buffer로 집어넣는 역할을 한다.
주황색 buffer들이 Producer가 데이터를 집어넣은 상태이며, 흰색으로 표시된 비어있는 buffer는 Consumer가 뺐거나 애초에 Producer가 쓰지 않은 자원이다.
- 문제 1
생산자 두 개가 동시에 도착해서 비어있는 같은 위치의 자원을 보고 데이터를 집어넣게 되면 동기화 문제가 생길 수 있다.
생산자가 ① 비어있는 버퍼를 확인하고 데이터를 집어넣기 전에 ② 버퍼에 Lock을 건 다음 ③ 데이터를 넣고, ④ 비어있는 버퍼의 포인터를 하나 증가시키고 ⑤ 버퍼 Unlock을 해준다. 소비자도 같은 방식으로 똑같이 데이터가 있는 버퍼라고 생각해서 동시에 꺼내가면 문제가 생기니까 생산자와 같이 자원을 사용하고 싶으면 버퍼에 Lock을 걸어 꺼내간 후 Unlock을 해줘야 한다.
- 문제 2
공유 버퍼를 가득 차 있어서 더 이상 데이터를 넣지 못하는 상황인데, 생산자가 또 도착해서 데이터를 집어넣고 싶은 상황이다.
생산자 입장에서는 사용할 수 있는 자원이 없는 상태이다.
세마포어가 자원의 개수를 Counting 하는 목적으로 사용될 수 있다고 했다.
버퍼의 개수가 n개라고 하면 생산자가 도착해서 버퍼 n개를 가득 채우고 나면, 그다음 생산자가 도착하더라도 데이터를 집어넣을 수 있는 비어있는 버퍼가 없다.
그렇다면 언제 비어있는 버퍼에다가 넣을 수 있을까? 바로 소비자가 내용을 꺼내가야지만 버퍼에다 데이터를 넣을 수 있다.
생산자 입장에서는 비어있는 버퍼의 개수가 자원의 개수이다. 반대로 소비자 입장에서는 주황색 버퍼인 데이터가 차 있는 버퍼의 개수가 자원의 개수이다.
세마포어 변수를 세 개 두고 있다. Lock을 걸기 위한 변수 mutex, 내용이 들어있는 버퍼의 개수를 세기 위한 full, 비어있는 버퍼의 개수인 empty가 있다.
공유 버퍼의 수는 n개로 내용이 들어있는 버퍼는 하나도 없다.
생산자 프로세스의 의사코드를 확인해 보자. 아이템 x를 만든 다음 버퍼에 집어넣기 전에 P(empty)로 비어있는 버퍼가 있는지 확인한 후, 비어있는 버퍼가 있으면 버퍼 전체에 Lock을 걸고 버퍼에 데이터를 집어넣는다.
버퍼 조작이 끝났으면 Lock을 다시 풀고 V(full)로 소비자 측의 자원을 하나 증가시켜 준다. 마찬가지로 소비자는 반대 시퀀스로 진행한다.
✓ 세마포어가 해야 할 일
- 동시에 공유 데이터 접근을 막기 위해 lock, unlock 과정
- 버퍼가 가득 차거나 비었을 때 가용자원의 개수를 세는 counting의 역할
✓ Shared data : 공유 버퍼 자체가 공유 데이터
- buffer 자체 및 buffer 조작 변수 (empty/full buffer의 시작 위치)
✓ Synchronization variables : lock을 걸고 푸는 용도 & 자원의 개수를 counting 하는 용도
- Mutual exclusion → Need binary semaphore (shared data의 mutual exclusion을 위해)
- Resource count → Need integer semaphore (남은 full/empty buffer의 수 표시)
● Readers and WRiters Problem (독자 저자 문제)
이 문제에서는 공유 데이터를 DB라고 칭한다. 데이터를 읽는 프로세스와 쓰는 프로세스 두 종류가 있다.
Reader와 Writer 가 하나만 있는 상황이 아니라 여러 개 있는 상황이다.
이전 문제와 마찬가지로 공유 데이터에 동시 접근을 하면 안 되니까, Lock을 걸어 하나의 프로세스만 접근하게 하고 데이터를 다 쓰고 나오면 Unlock을 해준다.
Produce/Consumer 문제는 동작 방식이 같았지만 이 문제는 Reader랑 Writer 방식이 약간 다르다.
Write는 동시 접근하면 문제가 생길 수 있는데 Read는 동시에 접근해도 문제가 되지 않기 때문이다.
그렇기 때문에 Reader가 동시에 도착하면 같이 읽을 수 있게 하지만 Writer는 동시 접근을 못하게 막는다.
Reader가 먼저 도착해서 데이터를 읽고 있을 때 Reader가 도착하면 read를 가능하게 해 주는데, Writer가 도착하면 Writer는 기다려야 한다.
Reader끼리는 상관없이 읽기가 가능하지만 Writer는 항상 아무도 없을 때에만 독점적으로 쓰기를 할 수 있다.
DB가 공유 데이터이고 이 데이터에 접근하려면 Lock을 걸어야 한다. Lock에 해당하는 변수가 db이다.
Writer를 보면, P(db) 연산을 통해 Lock을 걸고 DB에 쓴 다음 다시 Unlock을 해준다.
Reader에서도 Lock을 걸긴 걸어야 한다. Lock울 걸지 않으면 Writer가 와서 해당 데이터를 써버릴 수 있기 때문이다.
읽으려고 Lock을 걸었으면 다른 Reader가 왔을 때에는 읽을 수 있게 해줘야 한다.
그래서 몇 명이 읽고 있는지에 대한 readcount 변수를 두고 최초의 reader가 읽으러 들어갈 때 db에 Lock을 건다.
readcount가 1인 reader가 와서 이미 Lock을 걸어줬기 때문에 최초의 Reader가 아니라면 Lock을 걸 필요가 없다.
readcount도 공유 데이터이기 때문에 여러 Reader가 동시에 증가시킬 수 있기 때문에 readcount를 바꾸기 위해서도 mutex라는 세마포어 변수로 lock을 걸어줘야 한다. readcount가 0이면 DB를 마지막으로 읽고 나가는 reader이므로 DB에 건 Lock을 풀어줘야 한다.
이 코드상으로는 Writer가 너무 오래 기다릴 수 있기 때문에 starvation의 발생 가능성이 있다.
- 한 프로세스가 DB에 write 중일 떼, 다른 프로세스는 접근 불가능
- read는 동시에 여럿이 접근 가능
✓ 해결 방안
- Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.
- Writer는 대기중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
- 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
- Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.
✓ Shared data : DB 자체
- readcount : 현재 DB에 접근 중인 Reader의 수
✓ Synchronization variables
- mutex : 공유 변수 readcount를 접근하는 코드 (Critical section)의 Mutual exclusion 보장을 위해 사용
- db : Reader 와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
● Dining Philosophers Problem (식사하는 철학자 문제)
철학자 다섯 명이 원탁에 앉아있다. 다섯 명의 철학자는 생각하는 일 & 밥 먹는 일 두 가지를 행한다. 배가 고파지면 자신의 왼쪽과 오른쪽에 있는 젓가락을 들고 밥을 먹으며, 다 먹고 나면 젓가락을 내려놓고 생각하는 일을 반복한다. 밥을 먹으려면 젓가락 두 개를 모두 잡아야 하며 젓가락이 공유 자원이다.
위 코드는 데드락의 위험이 있다. 만약 철학자 모두가 오른쪽의 젓가락을 든다고 한다면 철학자 모두가 왼쪽 젓가락은 잡지 못하고 오른쪽 젓가락만 가지고 있기 때문에 식사를 하지 못한다.
철학자가 밥을 먹을 때에만 테이블에 앉게 한다거나 젓가락을 양쪽 다 얻을 수 있는 상황에서만 젓가락을 잡을 수 있는 권한을 줌으로써 해결할 수 있다.
또는 비대칭의 방법으로, 짝수 철학자는 왼쪽 젓가락만 잡도록 하고 홀수 철학자는 오른쪽 젓가락만 잡도록 하게 한다.
✓ 앞의 solution의 문제점
- Deadlock 가능성 → 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우
✓ 해결방안
- 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 잡을 수 있게 한다
- 비대칭 (짝수나 홀수 철학자는 왼쪽 혹은 오른쪽 젓가락부터 잡도록 한다.
다섯 명의 철학자가 하는 일은 먹거나 생각하는 일을 한다고 했다. 먹기 전에는 Pickup(), 먹고 나서는 Putdown() 함수를 호출한다.
세마포어 변수 self [5]는이다.
state [5]는 생각하는 상태, 먹는 상태, 배고픈 상태로 나눈다. mutex라는 Lock은 공유 데이터의 접근을 막기 위한 변수이다.
젓가락을 잡는 함수를 호출하게 되면 자신의 상태를 변경하기 전에 다른 철학자가 상태를 변경할 수 없게끔 Lock을 먼저 걸고 배고픈 상태로 바꾼 후, test() 함수로 간다. test함수는 양쪽 철학자가 밥을 먹지 않고, 내가 배고픈 상태를 만족할 때, 젓가락을 잡을 수 있는 권한을 얻게 된다.
보통 세마포어라고 함은 자원의 개수를 1로 시작을 하는데, 이 세마포어는 0으로 시작을 한 후, test()를 진행하는 단계에서 주변 철학자들이 밥을 먹지 않고 있으면서, 배고프면 V()으로 자원을 얻어 1이 된다.
● Monitor
Semaphore는 한 번 실수하게 되면 모든 시스템에 치명적인 영향을 준다.
예를 들어 Critical section에 들어가기 전에 V 연산을 하고, 빠져나올 때 P 연산을 하면 Mutual exclusion이 깨지게 된다.
또 한 가지 경우는 P 연산 후, 빠져나올 때 P 연산을 한 번 더 수행할 경우 Deadlock에 걸린다.
세마포어와 모니터는 프로세스 동기화 문제를 프로그래머 입장에서 좀 더 쉽게 할 수 있게 제공해 주는 것이다.
세마포어를 사용하더라도 불편한 점들이 있기 때문에 모니터라는 것을 제공한다. 식사하는 철학자 문제는 모니터가 더 쉽다.
condition variable은 어떤 조건을 만족하지 않아서 오래 기다려야 할 때 그 프로세스를 잠들게 하기 위한 용도이다.
- x.wait(); x라는 condition variable에 가서 줄 서 있음.
- x.signal(); 누군가 x를 다 쓰고 빠져 나가서 혹시 잠들어 있는 프로세스가 있으면 그것들 중 하나를 깨워주는 연산.
세마포어에서는 생산자가 버퍼에 데이터를 집어넣기 위해서는 버퍼 전체에다 Lock을 걸어서 다른 생산자가 접근하지 못하게 한다.
그 후 버퍼에 데이터를 집어넣고 Lock을 풀어줬다.
Monitor에서는 생산자이든 소비자이든 들어와서 코드를 실행하는 도중에 다른 프로세스의 접근을 모니터가 막아주기 때문에 굳이 공유 버퍼에 대해 Lock을 걸거나 Lock을 푸는 코드가 필요하지 않다.
생산자인 경우에는 버퍼가 비어있다면 빈 버퍼를 기다리는 줄에 가서 sleep상태로 있게 한다.
full은 내용이 들어있는 버퍼를 기다리는 프로세스들의 줄이고, empty는 빈 버퍼를 기다리는 프로세스들을 줄 세워 놓는 condition variable이다.
condition variable은 값을 가지지 않고 자신의 큐에 프로세스를 매달아서 sleep 시키거나 큐에서 프로세스를 깨우는 역할만 한다.
● Dining Philosophers Example
