[혼공컴운] Ch 12~13 __ 혼공학습단 11기 5주차

한 번 늦으니 계속 늦는 magic 

다른 사람들은 공부 오만 개 한다고 늦는데.. 나는.. 

하지만 

늦었는데도 제출한다는게 뿌듯하죠? 

오늘도 정신승리 

생각보다 빨리 끝나는데 얼른 제출할걸 .... 

 

---

Ch 12 프로세스 동기화

 

12 - 1 동기화란

→ 동시다발적으로 실행되는 프로세스들은 서로 협력하며 영향을 주고받는다
이 과정에서 자원의 일관성을 보장해야 한다. (프로세스들의 동기화를 고려해야 한다)

 

(프로세스) 동기화란? : 프로세스들의 수행 시기를 맞추는 것 (사전적의미)

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

+) 실행의 문맥을 갖는 모든 대상은 동기화 대상이기에 스레드도 동기화 대상이다.

 

1. 실행 순서 제어를 위한 동기화 : read writer problem 

  Writer : Book.txt 파일에 값을 저장하는 프로세스 

  Reader : Book.txt 파일에 저장된 값을 읽어 들이는 프로세스 

  Reader와 Writer 프로세스는 무작정 아무렇게나 실행되어선 안된다. 

  실행의 순서가 있기 때문이다.

  Reader 프로세스는 ‘Book.txt 안에 값이 존재한다’는 특정 조건이 만족되어야만 실행 가능.

 

  2.  상호 배제를 위한 동기화 :Bank account problem

 

 공유가 불가능한 자원의 동시 사용을 피하기 위한 동기화

 한 번에 하나의 프로세스만 접근해야 하는 자원에 동시 접근을 피하기 위한 동기화

 

 

공유 자원과 임계 구역

공유 자원: 여러 프로세스 혹은 스레드가 공유하는 자원 

(전역 변수, 파일, 입출력장치, 보조기억장치 …)

 

임계 구역: 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역

( 앞선 예시의 ‘총합’ 변수, ‘잔액’ 변수, ….. )

 

임계 구역에 진입하고자 하면 진입한 프로세스 이외에는 대기해야 한다

공동으로 이용하는 변수, 파일, 장치 등의 자원을 공유 자원이라고 하고, 

공유 자원에는 접근하는 코드 중 동시에 실행하면 문제가 발생하는 코드 영역이 임계 구역임.

 

임계 구역에 동시에 접근하면 자원의 일관성이 깨질 수 있다

→ 이를 레이스 컨디션(race condition)이라고 한다.

 

운영 체제가 임계구역 문제를 해결하는 세 가지 원칙 

(상호 배제를 위한 동기화를 위한 세 가지 원칙)

1. 상호 배제 : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 들어올 수 없다.
2. 진행 : 임계 구역에 어떤 프로세스도 진입하지 않았다면 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
3. 유한 대기 : 한 프로세스가 임계 구역에 진입하고 싶다면 언젠가는 임계 구역에 들어올 수 있어야 한다. ( 임계 구역에 들어오기 위해 무한정 대기해서는 안 된다.)

---

12 -2 동기화 기법

동기화 기법 중 뮤텍스 락, 세마포, 모니터

 

뮤텍스 락

→ 상호 배제를 위한 동기화 도구(자물쇠 역할)

단순한 형태 

→ 전역 변수 한 개 : release 함수: 임계 구역에서의 작업이 끝나고 호출하는 함수.

→ 함수 두 개 

acquire 함수

• 프로세스가 임계 구역에 진입하기 전에 호출
• 임계 구역이 잠겨 있다면 ( 임계 구역이 열릴 때까지 (lock이 false가 될 때까지) 임계 구역을 반복적으로 확인) 
• 임계 구역이 열려 있다면 ( 임계 구역을 잠그기 (lock을 true로 바꾸기))

release 함수

• 임계 구역에서의 작업이 끝나고 호출
• 현재 잠긴 임계 구역을 열기 (lock을 false로 바꾸기)

☑️바쁜 대기 busy waiting 

→ 마치 탈의실 문이 잠겨 있는지 쉴 새 없이 반복하며 확인해 보는 것과 같다. (딱히 좋은 방식 x)

 

세마포

+) 세마포의 종류 ( 이진 세마포, 카운팅 세마포) 중 카운팅 세마포를 다룬다.

• 임계 구역 앞에서 멈춤 신호를 받으면 잠시 기다리기 
• 임계 구역 앞에서 가도 좋다는 신호를 받으면 임계 구역 진입

 단순한 형태

- 전역 변수 하나 : 임계 구역에 진입할 수 있는 프로세스의 개수 ( 사용 가능한 공유 자원의 개수)를 나타내는 전역 변수 S

- 함수 두 개

• 임계 구역에 들어가도 좋은지, 기다려야 할지를 알려주는 wait 함수
• 임계 구역 앞에서 기다리는 프로세스에 ‘이제 가도 좋다’고 신호를 주는 signal 함수

1. 만일 임계 구역에 진입할 수 있는 프로세스 개수가 0 이하라면 

2. 사용할 수 있는 자원이 있는지 반복적으로 확인하고,

3. 임계 구역에 진입할 수 있는 프로세스 개수가 하나 이상이면 S를 1 감소시키고 임계 구역 진입

 

 

+) 위도 busty waiting이라 할 수 있음. → cpu 사이클 낭비! 

+) busy waiting 해결 방법 : cpu 사이클 낭비 해결방법?? 

- 사용할 수 있는 자원이 없을 경우 대기 상태로 만듦 

  ( 해당 프로세스의 PCB를 대기 큐에 삽입 )

- 사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만듦

  ( 해당 프로세스의 PCB를 대기 큐에서 준비 큐에 삽입)

 

세마포를 활용한 실행 순서 동기화

- 세마포의 변수 S를 0으로 두고,

- 먼저 실행할 프로세스 뒤에 signal 함수,

- 다음에 실행할 프로세스 앞에 wait 함수를 붙이면 된다.

 

 

모니터

 

→ 사용자 (개발자)가 다루기에 편리한 도구 

→ 상호 배제를 위한 동기화, 실행 순서 제어를 위한 동기화 두 가지 모두 제공

 

* 상호 배제를 위한 동기화

- 인터페이스를 위한 큐

- 공유 자원에 접근하고자 하는 프로세스를 (인터페이스를 위한) 큐에 삽입

- 큐에 삽입된 순서대로 (한 번에 하나의 프로세스만) 공유 자원 이용

 

* 실행 순서 제어를 위한 동기화

- 조건 변수 (condition variable) 이용 

  → 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수

조건변수.wait( ) : 대기 상태로 변경, 조건 변수에 대한 큐에 삽입

조건변수.signal( ) : wait ( )으로 대기 상태로 접어든 조건 변수를 실행 상태로 변경. ( 준비 상태로 변경해 주는 연산 )

조건변수.wait ( )

 

조건변수.signal( )

 

+)

실행 순서 제어를 위한 동기화 (핵심)

1. 특정 프로세스가 아직 실행될 조건이 되지 않았을 때에는 wait를 통해 실행을 중단한다.

2. 특정 프로세스가 실행될 조건이 충족되었을 때에는 signal을 통해 실행을 재개한다.

 

---

Ch 13 교착 상태

 

13 - 1 교착 상태란

🍒식사하는 철학자 문제 

동그란 원탁에 5명의 철학자가 있다. 맛있는 식사가 놓여 있고 철학자 사이사이에 식사에 필요한 포크가 있다. 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이라 가정.

1. 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
3. 왼쪽과 오른쪽 포크를 모두 집어 들면 정해진 시간 동안 식사를 한다.
4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
6. 다시 1번부터 반복한다. 

→ 모든 철학자가 동시에 포크 집기 - 모두 식사 못함. 

→ 모두 왼쪽 포크를 집으면 모두 오른쪽을 집을 수 없음 - 모두 다른 사람이 포크 내려놓길 기다림. 

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

교착 상태 해결 방안

1. 교착 상태가 발생했을 때의 상황을 정확히 표현해 보기

2. 교착 상태가 일어나는 근본적인 이유 이해하기

🔽

 

자원 할당 그래프 

→ 위의 1번 ( 교착 상태가 발생했을 때의 상황 정확히 표현)에 대한 방법

 

교착 상태 발생 조건 파악 가능 

- 어떤 프로세스가 어떤 자원을 할당받아 사용 중인지 확인 가능

- 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능

 

첫째, 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.

둘째, 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현

셋째, 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시

넷째, 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

 

+) 식사하는 철학자 문제를 자원할당 그래프로 나타낸다면?  ➡️ 교착 상태의 그래프! 

 

 

➡️ 교착 상태가 일어난 그래프의 특징은 

      자원 할당 그래프가 원의 형태를 띠고 있다. 

 

 

 

 

 

 

 

교착 상태 발생 조건

→ 상호 배제, 점유와 대기, 비선점, 원형 대기

→ 위 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않음

→ 위 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있음

 

1. 상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

2. 점유와 대기 : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태

3. 비선점 : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태

4. 원형 대기 : 프로세스들이 원의 형태로 자원을 대기하는 상태

 

---

 

13 - 2 교착 상태 해결 방법

 

교착 상태 예방

- 애초에 교착 상태가 발생하지 않도록 하는 방법

- 교착 상태 발생 조건 (상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애버리기

 

1) 상호 배제를 없애면?

    = 모든 자원을 공유 가능하게 만든다는 말과 같음 

   → 이론적으론 교착 상태를 없앨 수 있지만, 현실적으로 모든 자원의 상호 배제를 없애기에는 어려움.

 

2) 점유와 대기를 없애면? 

→ 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분

     → 자원의 활용률을 낮출 수 있는 방식

 

3) 비선점 조건을 없애면?

- 선점이 가능한 자원 (e.g CPU)에 한해 효과적

   → 모든 자원이 선점 가능한 것은 아니다

 

4) 원형 대기 조건을 없애면? 

- 자원에 번호를 붙이고 오름차순으로 할당하면 원형 대기는 발생하지 않음

이는 마치 원형 식탁이 아닌 사각형 식탁에서 일렬로 앉아 식사하는 상황과 유사하다. 

→ 자원에 번호 붙이는 것은 어려운 작업 → 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다.

→ 교착 상태가 발생하지 않음은 보장할 수 있으나 부작용이 따르는 방식

 

 

교착 상태 회피

- 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주

- 교착 상태가 발생하지 않을 만큼 조심조심 할당하기 

- 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원 배분

→ 안전 순서열 / 안전 상태 / 불안전 상태

 

1) 안전 순서열 

: 교착 상태 없이 안전하게 프로세스들이 자원을 할당할 수 있는 순서

2) 안전 상태

: 교착 상태 없이 모든 프로세스가 자원을 할당받고 종료될 수 있는 상태 (안전순서열 0)

3) 불안전 상태

: 교착 상태가 발생할 수도 있는 상태 ( 안전 순서열이 없는 상태)

 

교착 상태 검출 후 회복

- 교착 상태의 발생을 인정하고 사후에 조치하는 방식

- 프로세스가 자원을 요구하면 일단 할당 교착 상태가 검출되면 회복

- 선점을 통한 회복, 프로세스 강제 종료를 통한 회복 

 

선점을 통한 회복

→ 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식 

 

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

→ 교착 상태에 놓인 프로세스 모두 강제 종료 ( → 작업 내역을 잃을 위험)

→ 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 ( → 오버 헤드 ) 

 

+) 교착 상태 무시 

→ 타조 알고리즘

---

 답 : 4 

 반드시 바쁜 대기를 할 필요는 없다. 대기 상태로 접어들게 할 수도 있습니다.