[ 운영체제 ] 17. Liveness / Sychronization example

Liveness

: Process가 자신의 Execution life cycle내에 일을 진행할 수 있게 보장해주는 Properties

 

이게 깨지는 이유는 다음 3가지가 있다.

 

• Deadlock
• Prioirity Inversion
• 기타 등등...

 

● Deadlock

: 두 개 이상의 프로세스가 무한정으로 특정 프로세스에 이벤트가 생기길 기다리는 것

 

 

P0과 P1가 있다고 해보자. 

P0 먼저 실행시키자.

▶S,Q가 반납될 때까지 아무것도 안 하고 기다릴게

 

P1 실행

▶ Q,S가 반납될 때까지 아무것도 안 하고 기다릴게

 

근데 둘 다 기다리는 게 끝나야 S와 Q를 반납함.

서로가 서로를 기다리는 상황

 

세마포어 키를 1로 설정해둔다.
(1개만 Critical 가능)

P0가 실행하면 S를 기다림
P1은 Q를 기다린다. 

그렇다면, P0는 P1이 signal (S)를 할 때까지 기다린다.

근데 P1은 또 signal 까지 가려면 signal(Q)를 해야한다. 

'서로가 서로를 기다리는 상황.

P0 ,P1 두 개는 절대 실행될 수 이 없다. 이를 deadlock이라고 함'

 

 

● Priority Inversion

: 높은 우선 순위의 프로세스가 낮은 우선 순위가 접근하고 있는 Kernel data를 읽거나 쓰려고 할 때

 우선순위가 높은데도 작업이 낮은 우선 순위보다 늦게 끝나는 상황

 

ex) L = Lower priority / H = Higher Priority / M = Middle

 

L이 자원 A를 사용 중

▶ H가 작업하다가 A가 필요해서 기다림

▶ 그 사이에 M 실행

▶ M끝나고 L 다 끝남 - A반납

▶ H 가 이제야 A를 사용해서 일을 끝냄

 

 

https://j-i-y-u.tistory.com/21

 

타임퀀텀 느낌인가보다.

 

 

 

---

고전적 동기화 문제

 

 

◼ The Bounded-Buffer Problem

◼ The Readers-Writers Problem

◼ The dining-philosophers problem

 

 

---

 

The Bounded-Buffer Problem

 

Buffer를 통해 정보를 주고받는 방식은 다음과 같다.

 

● Producer

 : Buffer가 다 찼다면, Consumer가 Buffer에서 item을 가져갈 때까지 기다려야한다.

   (Producer는 empty space 에 정보를 넣음 )

    = Producer에게 세마포어는 Empty 라는 것 

 

● Consumer

 : Buffer가 비었다면 , Producer가 add할 때까지 기다린다.

    = Consumer에게 세마포어는 Full(Added) 라는 것 

 

 

 

Producer는 Mutex와 empty가 필요하고

Consumer는 Mutex와 full이 필요하다.

 

 

근데 이건 하나의 producer, 하나의 consumer로 이루어져 있기 때문에 

---

 

The Readers-Writers Problem

 

Shared Data를 두고, 여러 Writer, Reader가 있다.

 

우선 Write와 Read의 특성을 생각해보자.

 

Writer = 데이터의 수정 O

Read = 데이터의 수정 X

 

● Writer

: Writer or Reader Thread가 Critical section에 있다면?

   ( = 어느 종류의 Thread ) 

 

  → 모든 Writer는 기다려야한다.

 

 

● Reader

: Critical section에 Writer가 있다면?

  → Wait

 

  Reader끼리는 있어도 그냥 들어감

 

● Writer

Writer는 rw_mutex를 얻을 때까지

= 다른 writer가 critical section에 없을 때까지 기다린다.

 

 

● Reader

Reader 는 Mutex얻을 때까지 기다린다.

= Mutex = Writer가 없는지 확인

 

 + 또 지금 Reader가 처음 들어온 Read면 rw_mutex도 얻어야 한다.

 

  rw_mutex만 가진 상태로 작업을 한다.

  mutex 는 다시 돌려줘도 됨 ( Reader만 들어올 수 있으니)

 

  다시 Mutex를 얻어서 read count를 줄이고, 

  더 이상 reader가 없다면 rw_mutex도 반납한다.

 

  그냥 read_count 관련해서 작업을 할 때만 mutex를 얻는다고 생각하면 될 것 같다. 

 

 

---

 

The dining-philosophers problem

철학자들의 식사

 

https://min-h-study-review.tistory.com/251

 

철학자들의 동그랗게 모여앉아 식사를 한다.

 

식사하는 방법은 간단하다.

 

1. 자신의 왼쪽의 식기를 든다.

2. 자신의 오른쪽 식기를 든다.

3. 식사를 한다. (Eat Rice)

4. 식기를 내려둔다.

 

이를 Process와 CPU관계로 본다면

 

- Shared Data : Bowl of rice

- Semaphore chopstick[5] 이다.

 

하지만 여기에서 Deadlock이 발생한다.

 

왼쪽 젓가락을 집고 , 오른쪽 젓가락을 집는데

i번째 철학자가 왼쪽의 젓가락을 집으면 , i+1번째 철학자도 왼쪽을 집었으므로

i번째 철학자의 오른쪽 젓가락이 없다.

 

그래서 기다리자니 서로가 서로의 젓가락을 내려둘 때까지 기다리므로 Deadlock 상황이 발생한다.

 

 

---

해결책

 

 

1. 4명만 앉을 수 있다.

2. 양쪽에 있는 식기를 들 수 있을 때만 든다.

3. 홀수 번째 철학자가 왼쪽 > 오른쪽 식기를 집거나

    짝수 번째 철학자가 오른쪽 > 왼쪽 식기를 집는다.

 

 

아래 코드는 몇 명이든 상관없이 그냥 만든 거

 

 

● pickup 함수

i번째 철학자에 대해서...

 

배고픈 상태로 만들고, test로 간다.

 

그리고 본인이 먹는 상태가 아니면

           다른 프로세스가 젓가락 반납할 때까지 기다린다.

 

● test 함수

조건 [  내 오른쪽이 먹는 상태가 아니고,

            내가 배고프고

             내 왼쪽이 먹는 상태가 아니면     ]

 

먹는다.

 

그리고 젓가락 다 썼다고 알린다.

 

이걸 Monitor로도 구현할 수 있다.

서로 Mutex를 지켜주면서 식기를 집고 내려놓으면 된다.

 

Deadlock은 해결하지만 Starvation은 여전히 생길 수 있음

 

 

---

 

Synchronization within the Kernel

 

Linux 는 2.6 버전부터 Fully Preemptive

 

 

● Atomic variables

 

 

atomic 타입으로 만들어놓으면, 중간에 Inerrupt없이 깔끔하게 실행된다.

 

 

● Mutex locks

 

 

 

 

preempt_disable() : critical section에서 무슨 작업을 하면, 그건 preempted 되지 않는다.

 

 

(출처)

한동대학교 고윤민교수님 - 운영체제