[혼공학습단 13기] 5주차 : 프로세스 동기화 | 교착 상태

12-1. 동기화란

동기화, 공유 자원, 임계 구역, 상호 배제

운영체제의 프로세스 관리 서비스 중 가장 중요한 두 가지 중 하나인 동기화

 

프로세스 동기화

프로세스들 사이의 수행 시기를 맞추는 것

• 실행 순서 제어 : 프로세스를 올바른 순서대로 실행
• 상호 배제 : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기

✔️ 스레드같이 실행의 흐름을 갖는 모든 것은 동기화의 대상이다. 

 

실행 순서 제어 위한 동기화

writer프로세스와 reader 프로세스가 동시에 실행 중일 때, 아무 순서대로 실행되면 안된다.

writer ➡️ reader ; reader프로세스는 book.txt에 값이 존재한 경우에만 실행할 수 있다. 

 

상호 배제를 위한 동기화

공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘

프로세스 A, B는 잔액이라는 데이터를 동시에 사용하는데 A가 끝나기 전에 B가 잔액을 읽어버리면 안된다. 

A가 잔액에 접근했으면 중간에 끼어들면 안되고 끝날 때까지 기다려야 한다. 

📍상호 배제를 위한 동기화 - 생산자와 소비자 문제

• 생산자 : 물건을 계속 생산하는 프로세스
• 소비자 : 물건을 계속 소비하는 프로세스

생산자와 소비자는 총합 데이터 공유 시 생산자가 소비자의 작업이 끝나기 전에 총합을 수정해 이상한 결과가 나온다. 

총합 데이터를 동시에 사용하기 때문에 프로세스가 제대로 동기화되어야 한다

 

공유 자원과 임계 구역

✔️ 공유 자원 : 공동의 자원. 전역 변수, 파일, 입출력장치, 보조기억장치가 될 수 있다. 

✔️ 임계 구역 : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역 (잔액 변수, 총합 변수)

 

❓ 레이스 컨디션(race condition) : 잘못된 실행으로 여러 프로세스가 동시에 임계 구역의 코드 실행

➡️ 데이터의 일관성이 깨진다. (생산자와 소비자 문제)

컴퓨터는 고급 언어가 아니라 저급 언어를 실행한다.

고급 언어 한 줄이 저급 언어 여러 줄로 변환되니 한 줄의 고급 언어 실행 과정에서 문맥 교환이 일어날 수 있다. 

 

상호 배제를 위한 동기화 위한 3가지 원칙

1. 상호 배제(mutual exclusion) : 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다. 
2. 진행(progress) : 임계 구역에 어떤 프로세스도 진입하지 않았으면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다. 
3. 유한 대기(bounded waiting) : 프로세스가 임계 구역 진입 원하면 언젠가는 임계 구역에 들어올 수 있어야 한다. (무한대기 X)

---

12-2. 동기화 기법

뮤텍스 락, 세마포, 모니터

동기화를 위한 대표적인 도구 : 뮤텍스 락, 세마포, 모니터

 

뮤텍스 락(Mutex lock; MUTual EXclusion lock)

자물쇠 기능인 상호 배제를 위한 동기화 도구

• 프로세스들이 공유하는 전역 변수 lock : 자물쇠 역할
• acquire 함수: 임계 구역을 잠그는 역할
  • 프로세스가 임계 구역에 진입하기 전에 호출
  • lock이 False가 될 때까지 임계 구역 반복적으로 확인
  • 임계 구역이 열렸으면 잠금(lock = True)
• release 함수: 임계 구역의 잠금을 해제하는 역할
  • 임계 구역에서 작업 끝나고 호출
  • 잠긴 임계 구역 오픈(lock = False)

➡️ 바쁜 대기(busy wait) : 잠겨있는지 쉴 새 없이 반복해 확인해야 함

 

세마포(semaphore)

공유 자원이 여러 개 있는 상황에서도 적용 가능한 동기화 도구

• 전역 변수 S : 임계 구역에 진입할 수 있는 프로세스 개수(사용 가능한 공유자원의 개수)
• wait 함수 : 임계 구역이 들어갈지 말지 알려줌
• signal 함수 : 임계 구역 앞에서 기다리는 프로세스에게 가도 좋다는 신호를 줌

상호 배제를 위한 동기화

✔️ 뮤텍스 락과의 차이 : 사용할 수 있을때까지 계속해서 S 확인해야 하는 문제

1. wait()은 사용 가능한 자원이 없을 때 해당 프로세스를 대기 상태로 만들기
2. 해당 프로세스의 PCB를 세마포를 위한 대기 큐에 넣기
3. 다른 프로세스에서 signal() 호출
4. signal()는 대기 중인 프로세스를 대기 큐에서 제거 후 프로세스 상태를 준비 상태로 변경해 준비 큐로 옮긴다

프로세스 순서 제어

먼저 실행할 프로세스 뒤에 signal(), 다음 실행 프로세스 앞에 wait() 함수 붙이기

P1이 먼저 실행 시 : signal() 있으니깐 먼저 실행

P2가 먼저 실행 시 : wait() 있으니까 P1이 임계 구역 진입

❓ 매번 임계 구역 앞뒤로 wait(), signal() 명시 귀찮고, 누락되면 복잡해짐

 

모니터(monitor)

공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로) 묶어서 관리
프로세스는 인터페이스 통해서만 공유 자원에 접근

1. 공유 자원에 접근 원하는 프로세스를 큐에 삽입
2. 큐에 삽입된 순서대로 공유 자원 이용

➡️ 모니터 안에 항상 하나의 프로세스만 들어올 수 있다. 

프로세스 순서 제어

📍조건 변수(condition variable)

: 특정 조건을 바탕으로 프로세스를 실행하고 일시 중단하기 위한 변수. wait, signal 연산 수행 가능

✔️ 큐 비교

• 상호배제 위한 큐 : 모니터 진입 위해 삽입되는 큐
  • 1번에 1개의 프로세스만 진입하도록
• 조건 변수에 대한 큐 : wait가 호출되어 실행이 중단된 프로세스들이 삽입되는 큐
  • 모니터에 이미 진입한 프로세스의 실행 조건이 만족될 때까지 실행 중단되어 기다리는 큐

✔️ wait() : 호출한 프로세스 상태를 대기 상태로 전환하고 일시적으로 조건 변수에 대한 대기 큐 삽입하는 연산

 

조건변수 x, y -> x.wait()로 조건 변수 x의한 대기 큐에 넣고 x.signal()통해 실행재개

각 큐마다 x.signal(), y.signal() 이런식으로 순서 조정

➡️ 복잡한 순서를 조건변수들을 통해 조정할 수 있다. (큐가 여러개)

📌 기본 숙제

뮤텍스 락과 세마포에 대한 설명으로 옳지 않은 것

: 세마포를 이용하면 반드시 바쁜 대기를 해야 합니다 ❌ 

 

---

13-1. 교착 상태란

교착 상태, 식사하는 철학자 문제, 자원 할당 그래프, 교착 상태 발생 조건

교착상태가 무엇이고 교착상태를 표현하는 자원 할당 그래프와 교착 상태의 발생 원인

교착상태(deadlock)

일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상

게임 프로세스가 자원 A 점유하고 웹 프로세스 점유하는 자원 B 기다리고, 웹 프로세스는 B 점유한 채 A 기다리는 상황 

➡️ 상대가 가진 자원을 기다리기만 하다가 실ㄹ행 못하는 상황 발생

📍해결법

1. 교착 상태가 발생했을 때의 상황 정확히 표현
2. 교착 상태가 일어나는 근본적인 이유 파악

자원 할당 그래프

어떤 프로세스가 어떤 자원 사용중이고 어떤 자원을 기다리고 있는지 표현

교착 상태가 발생한 상황 : 자원 할당 그래프가 원의 형태(항상은 아님 4가지 조건 모두 만족해야 함)

교착 상태 발생 조건

상호 배제, 점유와 대기, 비선점, 원형 대기 전부 만족 시 교착 상태 발생 가능

1. 상호 배제(mutual exclution)

한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 경우

2. 점유와 대기(hold and wait)

자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태

3. 비선점(nonpreemptive)

그 자원을 이용하는 프로세스의 작업이 끝나야 이용이 가능 
강제로 빼앗지 못하는 상황

4. 원형 대기(circular wait)

자원 할당 그래프가 원의 형태로 그려지는 경우 

---

13-2. 교착 상태 해결 방법

교착 상태 예방, 교착 상태 회피, 교착 상태 검출 후 회복

교착 상태 예방

교착 상태 발생 필요조건 중 하나라도 충족 못하게 만들면 된다. 

1. 상호 배제 없애기

= 모든 자원이 공유 가능하다 흠.. 어려움

2. 점유와 대기 없애기

 특정 프로세스에 아예 다 할당하거나 아예 할당하지 않아서 기다리는 것 못하게 하면 된다. 

❓자원의 활용률이 심각하게 낮아지고, 자원을 많이 사용하는 프로세스는 타이밍 잡기가 어려워진다. (기아 현상 발생 가능)

3. 비선점 조건 없애기

자원을 이용 중인 프로세스로부터 자원을 빼앗을 수 있다. 

❓CPU같이 선점 가능한 자원이 아니라 프린터같이 중간에 뺏으면 안되는 자원도 있다. 

4. 원형 대기 조건 없애기

모든 자원에 번호를 붙이고 오름차순으로 자원 할당

순서대로 포크 집게 하면 된다! = 원형이 아닌 바테이블에 일렬로 앉히면 됨! 

❓모든 자원에 전부 번호를 붙일 순 없고, 어떤 번호냐에 따라 자원의 활용률이 떨어질 수 있음

 

➡️ 예방 방식은 조금 어렵 따.. 

교착 상태 회피

교착 상태가 발생하지 않을 정도로만 자원 할당

➡️ 무분별한 할당으로 인해 발생하는 것이라고 생각! 

 

• 안정 상태(safe state) : 교착 상태 발생 가능성 없는 상태
• 불안전 사태(unsafe state) : 교착 상태가 발생할 수도 있는 상태
• 안전 순서열(safe sequence) : 교착 상태 없이 안전하게 프로세스들에 자원 할당할 수 있는 순서
  • 안전 순서열이 있으면 안전 상태
  • 안전 순서열이 없으면 불안전 상태

교착 상태 검출 후 회복

교착상태 인정하고 사후 조치

➡️ 프로세스들이 자원을 요구할 때마다 모두 할당하는데,  교착 상태 발생 여부를 주기적으로 검사하고, 교착 상태가 검출되면 해결한다

선점으로 회복

교착상태 해결될 때까지 몰아주기(강제로 빼앗아 몰아주기)

프로세스 강제 종료를 통한 회복

싹 다 강제종료하거나, 교착 상태 없어질 때까지 하나씩 강제 종료

• 싹 다 강제종료해버리면 작업 내역 잃을 수도 있다
• 교착 상태 없어질 때까지 하나씩 강제 종료 하다가는 오버헤드 발생할 수 있다

📌 타조 방식(ostrich algorithm)

교착 상태 아예 무시,,, 때때로 적합할 때도 있다.