[CS study] Operating System (4)

hjboom·2025년 4월 4일

Synchronization examples

Bounded-buffer problem

shared memory에 접근하는 프로세스를 두 가지로 구분
- 데이터를 적는 프로세스 - producer
- 데이터를 소비하는 프로세스 consumer
producer가 적을 때 consumer가 데이터를 소비하면 안됨
- Binary semaphore로 해결가능
하지만, buffer의 사이즈가 유한하기 때문에 consumer가 빠르게 데이터를 소비해주지 않으면 더 이상 데이터를 적을 공간이 없어 producer는 일을 하면 안됨 / consumer도 동일. writer가 빠르게 데이터를 적어주지 않으면 데이터를 소비할 수 없어 일을 하면 안됨
- empty buffer의 수, full buffer의 수, critical section에 대한 mutex 이렇게 3개의 변수로 컨트롤 하면 됨
- 그래서 이 문제는 buffer에 대한 mutual exclusion 뿐만아니라 buffer 상태에 대한 변수들도 동기화 해주어야 함

// Shared data
semaphore full = 0, empty = n, mutex = 1;
// Producer
do {
	P(empty);
	P(mutex);
	
	/* produce data in buffer */
	
	V(mutex);
	V(full);
} while(1);

// Consumer
do {
	P(full);
	P(mutex);
	
	/* read data in buffer */
	
	V(mutex);
	V(empty);
} while(1);

Readers-Writers problem

producer-consumer problem과 비슷한데, 이번엔 reader가 데이터를 읽고 남겨두는 상황
그러므로 reader가 동시에 여러개 접근해도 상관 없는 상황
두 가지 방식이 있음
- reader가 없을 때만 writer가 작성할 수 있게 함
- writer가 오면 reader를 그만 받고 reader가 다 빠져나가면 writer가 작성
첫번째 방식은 starvation의 문제가 있을 수 있지만, 처리율은 높음
이진 semaphore 변수인 db와 mutex를 선언
- db는 저장되어 있는 critical section에 접근할 때 이를 mutual exclusion 해주기 위한 변수
- mutex는 reader들이 readcount 변수에 접근하는 것을 mutual exclusion 해줌

// Shared data
semaphore db = 1, mutex = 1;
int readcount = 0;

// Writer
do {
	P(db);
	
	/* write data in db */
	
	V(db);
} while(1);

// Consumer
do {
	P(mutex);
	readcount++;
	if (readcount == 1) P(db) // 첫번째 reader가 들어가면서 lock을 잡음
	V(mutex);
	
	/* read data in db */
	
	P(mutex);
	readcount--;
	if (readcount == 0) V(db) // 마지막 reader가 나가면서 lock을 해제
	V(mutex);
} while(1);

Dining-Philosophers Problem

철학자 다섯 명을 원형 테이블에 앉혀 놓고 젓가락으로 밥을 먹게한다.
- 젓가락은 철학자 사이에 하나씩 놓여 총 다섯개가 있다
- 자신의 양쪽에 놓여있는 젓가락을 모두 확보할 수 있을 때 철학자는 밥을 먹고, 밥을 다 먹으면 내려놓음
모든 젓가락을 공유 자원이라고 생각하고 접근했을 때, 모든 젓가락을 semaphore로 보호하면 된다
- 하지만 모든 철학자들이 왼쪽 젓가락을 동시에 들면 밥을 먹을 수 없다
- Deadlock
해결 방법
- 무조건 양쪽 젓가락을 동시에 들게 만든다
- 홀수자리 철학자는 왼쪽, 짝수자리 철학자는 오른쪽, 이런식으로 드는 순서를 정해준다
- 다섯명을 다 앉히지 않는다

Semaphore의 단점

코딩이 어려움
코딩을 제대로 했더라고 하더라도, 올바르게 구축했는 지 알기 어려움
큰 프로그램을 짤 때 개발자끼리 합의가 쉽지 않음
잘못 사용하면 전체 시스템에 마비

Monitor

ADT(abstract data type) 형식의 monitor class를 제공하여 lock을 제공
- 진짜 class라기 보다는 class와 비슷한
- high level language로 작성됨
- 객체 내부에 private data가 저장되고 이 data를 접근할 수 있는 public method가 제공됨
monitor는 montior 안에서 동작하는 process가 단 하나라는 것을 보장
- entry queue를 활용함
  - montior 내부에 다른 프로세스가 일을 하고 있으면 entry queue에서 대기
  - montior에서 프로세스가 빠져 나가면 entry queue에서 한 프로세스가 monitor 내부 method를 호출
문제는, montior 내부에서 proces가 실행되다가 조건이 충족되지 못해서 method를 실행하다가 waiting을 해야하는 경우가 있을 수 있다.
- busy waiting을 monitor 내부에서 걸어버리면 병목현상이 발생
- 이를 위해서 condition 변수가 존재
  - condition 변수에서 wait을 통해 sleep하고 signal을 통해 깨어날 수 있음
monitor를 사용할 때 지켜야할 조건
- public method를 호출할 때, method들 끼리 순서 관계가 있을 수 있으니 이를 맞추어서 호출
- private 변수들은 반드시 public method를 통해서 접근

Monitor:Dining-Philosophers Problem

Deadlock

대기중인 스레드들이 대기하고 있는 자원을 다른 대기중인 스레드가 점유하고 있어 결코 다시는 그 상태를 변경할 수 없는 상태

deadlock 조건

deadlock은 아래의 4조건을 모두 만족하면 발생

Mutual Exclusion
- resource가 공유 불가능
No preemption
- 어떤 process가 자원을 소유하고 있으면, 자신이 스스로 해당 자원을 포기할 때까지 다른 process는 해당 자원에 접근 불가능
Hold and wait
- 어떤 process가 다른 자원을 아직 소유하지 못해 진행을 할 수 없더라도, 지금 소유하고 있는 자원은 가지고 있는 채로 기다려야함
Circular wait
- 기다리고 있는 process들이 원형대기를 이루고 있어야 함

deadlock 처리방법

Deadlock이 절대로 발생하지 않게 하는 방법
- prevention
- avoidance
Deadlock을 허용하고 detection하여 발생하면 recover
- detection
- recovery
Deadlock 무시
- 껐다 키기
- 대부분의 OS는 이를 채택
  - 그만큼 deadlock 발생활귤이 낮기 때문
  - 요즘 컴퓨터들은 자원이 풍족해서 웬만하면 자원이 부족하지 않음
  - 그리고 deadlock이 발생하지 않도록 관리하기 위해서는 컴퓨터 자원을 사용해야함
    - 이것은 효율성이 너무 낮음

prevention

Deadlock이 일어나기 위해 필수적인 조건 4가지를 배웠는데, 이 조건을 없애 deadlock이 아예 발생하지 않도록 하는 것

Mutual exclusion
- 자원을 공유할 수 없게 하자는 아이디어는 불가능
- 공유 가능 여부는 해당 자원의 특성으로 이미 결정되어 있음
- OS가 관여할 수 있는 일이 아님
Hold and wait
- 자신이 추가적인 resource를 얻을 수 없으면, 이미 확보한 자원도 가지고 있을 수 없게 하기
  - atomic 하게 자원에 접근하도록 하면 됨
  - 이러면 resource utilization이 낮아지고, starvation의 위험성이 있음
No Preemption
- 어떤 process가 resource를 확보할 수 없어 기다리게 되면, process의 강제로 자원을 뺐자
- hold and wait은 허용하는데, 다른 process가 resource가 필요하면 바로 빼았길 수 있음
  - 결과적으로 생각해보면 hold and wait과 크게 다를게 없기 때문에 문제점을 공유한다
  - 그리고 추가적으로 그럼 빼았긴 process는 재시작을 해야하는데 이것이 큰 overhead
Circular Wait
- resource 마다 번호를 정하고 번호가 낮은 resource부터 확보를 해야 다른 resource를 확보할 수 있게 하는 방식으로 circular wait을 구현할 수 있음
  - 이런식으로 구현하면 반드시 1번 프로세스부터 n번 프로세스 까지 자신이 기다리는 resource를 크기 별로 나열 했을 때, pn → p1을 기다리는 상황이 절대 생기지 않음
- 이것도 지금 확보 가능한 resource를 특정 이유때문에 점유할 수 없으므로 utilization 감소
  - system throughput 감소
즉, 전체적으로 low resource utilization과 reduced system throughput을 발생시켜 안좋음

avoidance

Deadlock의 4가지 조건을 모두 허용하는 대신에 동작과정에서 deadlock이 발생하지 않도록 제어

safe하지 않은 상태로 가는 행위로 모두 차단하는 방식으로 작동
process가 OS에게 자원을 요청하면, 지금 당장 resource 할당이 가능하더라도 deadlock이 발생할 가능성이 있다면 자원을 나누어 주지 않음
그래서 미래에 deadlock이 발생할 지 예측할 수 있어야 함. 이를 위해 정보를 가지고 있음
- 각 process마다 resource type 별로 최대로 사용할 resource maximum을 선언하게 함

Safe State

Deadlock이 발생할 수 없는 안전한 상태

모든 process가 다 종료될 수 있는 process 종료 sequence가 존재하는지로 안전한지 판단
- n개의 process가 이미 확보한 자원과 종료된 process가 반납하는 resource양을 합하여 일을 끝낼 수 있는지 모든 경우의 수를 따져봄
- 이렇게 모든 process 가 끝날 수 있는 sequence가 있으면 safe state

safe state면 절대로 deadlock이 발생하지 않음
safe state가 아니면 deadlock이 발생할 가능성이 있음
- 왜냐면, saft state는 엄청 보수적으로 가정했기 때문
- 항상 모든 process가 resource를 max로 사용한다고 가정했음
avoidance는 최악의 상황을 가정해서 항상 안전한 길로만 가는 소심한 방법

Avoidance in Single instance of a resource type

RAG(resource allocation graph)를 그려서 직접 확인해봄

업로드중..

claim edge: 지금 사용하는 것이 아닌 사용할 예정인 데이터를 점선으로 가리킴
request edge: 실제로 resource 달라고 요청. 실선으로 가리킴
assignment edge: request를 실제로 할당하면서 화살표 방향 변경
- assignment edge는 사라지면서 edge가 아예 사라지는게 아니라 claim edge료 변경됨. 언제 또 사용될 지 모르기 때문
이 그래프를 통해 request를 assign 했을 때 cycle이 생기는 지 확인해서 cycle이 생기면 resource를 할당하지 않음

Avoidance in Multiple instance of a resource type

Banker’s Algorithm

가정
- 모든 process는 resource type별로 최대로 사용할 instance 수를 명시해야함
- 어떤 process가 resource 달라 요청했어도 받지 못하고 기다릴 수 있음 (safe state 아닐경우)
- 어떤 process가 자기가 필요로하는 모든 resource를 받았으면 일을 끝내고 유한한 시간 내에 resource를 반납해야 함
자료구조
- Available[i]
  - 각 종류별로 가용한 자원의 개수를 나타내는 vector
- Max[i,j]
  - process i가 사용하는 최대 resource j
- allocation[i,j]
  - process i가 사용하고 있는 resource j
- need[i,j]
  - process i가 추가로 필요로 하는 resource j
  - need[i,j] = Max[i,j] - allocation[i,j]
알고리즘
- work 배열과 finish 배열을 만듦
  - work 배열은 available과 동일
  - finish배열은 process i가 일을 끝냈는지 저장. 처음에 모두 false
- 자원을 나눠받을 process 하나를 선택
  - finish[i] = false 이고 Need[i] ≤ work
  - 존재하지 않으면 4단계로 이동
- process가 선택 되었으면 해당 프로세스에게 모든 자원을 줘서 일을 끝냄
  - work += availalbe → 프로세스가 끝났으니 자원 반납
  - finish = true → 끝이 났음
  - 2단계로 이동
- 4단계에 도착하면 안전하지 않음
  - 모든 finish[i] = true가 아니면 sequence가 존재하지 않는거임

detection

Deadlock이 발생하기 전까지 아무것도 안하다가, 현재 deadlock이 발생했는지 따지는 것

recovery

Deadlock에 관여된 process를 아예 죽임
- deadlock에 관여된 모든 process를 다 죽임
- 하나씩 죽여보기
  - priority, 얼마나 오래 계산했는지, resource 양 등을 기준으로 삼음
Deadlock에 관여된 process로 부터 자원을 강제로 빼았음
- Rollback
- Starvation