운영체제의 기초 - 11. Process Synchronization 2

Monitors : Semaphore 2

세마포어가 Synchronization 메카니즘으로써 가지고 있는 문제점

- producer와 consumer라는 Task 2개가 있음

- 각각 P()와 V()로 가드가 되어있는 session이 있음 (Critical session code로 볼 수 있음)

- code session 안에는 buffer를 사용하는 코드들이 들어가 있음

- 그러나 P()와 V() argument 값이 같아야 하는데 다름 

- 이것이 버그인지 아닌지 이해하기도 어렵고 찾아내기도 어려움

OS가 해결하는 방법

- P() ... V()라는 함수 대신에 다른 함수를 사용함

wait(), signal()  >>  세마포어를 주로 스케줄링 관점에서 바라본다는 의미

lock(), unlock()  >>  세마포어를 Critical session을 만들어 주는 Mutual Exclusion을 제공해주는 관점에서 바라본다는 의미

Mutex

- Mutual Exclusion을 구현하기 위해 사용하는 Sleeping Lock

- 동일한 Mutex를 사용할 때 mutex_lock()을 호출한 Process와 mutex_unlock()을 호출한 Process가 일치하여야 함

이제는 세마포어를 어떻게 구현해야하는지 공부해 보겠음

세마포어란?

세마포어는 integer 변수인데 synchronization에 관계한다

세마포어가 담고 있는 integer 값은 뭐냐? 

열쇠의 존재 여부. 열쇠가 있으면 1 없으면 0

실제로 구현하기 위해서는 queue가 있어야 함

- 열쇠가 없어 들어가지 못하는 프로세스들이 대기하는 공간이 필요 --> 대기 큐

세마포어는 shared resource를 관리

- 세마포어 자체도 shared 되기 때문에 interrupt disable로 가드한다

- 인터럽트 사용하지 말라면서?

- 괜찮음. int 데이터 넣고 빼는 순간만 인터럽트하니까 (매우 짧은 시간 -> 끼치는 영향 미미)

Semaphore에서 Count의 의미

0 이상인 경우: 남아있는 열쇠(공유자원)의 개수

0 이하인 경우: 카운트 절대값 = Queue에서 대기중인 Process의 개수

이것은 싱글프로세서용 세마포어임. 멀티프로세서로는 적용이 안됨

왜 그런지 살펴보겠습니다.

interrupt disable 해도 또 다른 CPU는 인터럽트가 가능하기 때문에 메모리의 공유자원에 다른 프로세스의 접근이 가능

Atomic Operation: 글로벌 리소스를 읽고, modify하고, write back하는 전체 과정을 쪼갤 수 없는 기본단위로 설정함

길목을 장악 (Bus  통제)

Bus Transaction은 2가지 타입이 있음

- Read Transaction: 메모리에 있는 값을 버스를 요구해서 버스를 장악한 다음 메모리에 controller요구해서 값을 읽어오고 버스를 release 하는 것

- Write Transaction: 버스를 request해서 grant(승인)받은 다음 메모리 controller에게 어떤 값을 줘서 메모리에 쓰고 버스를 release 하는 것

- 위 두 Transaction은 기본적으로 Atomic transaction임

우리는 read, modify, write 을 Atomic하게 만드는 것임

그래서 Read Transaction과 Write Transaction을 묶어 하나의 Transaction으로 만든다

- Bus를 request하고 grant를 받으면 글로벌변수를 load해서 수행

- 이때 버스를 release하지 않는다. 다시 write하면 그제서야 release

Multiprocessor에서 Atomic Operation을 구현하는 방법

Atomic Operation을 수행하는 동안 Bus를 장악하여 다른 Processor의 Bus Transaction을 차단

이런 operation의 가장 대표적인 것이 TAS

TAS (Test & Set): 하드웨어가 제공해주는 instruction임 

- TAS(lock_var): 파라미터인 메모리 로케이션값을 읽어들여서 1인지 0인지 판단, 무조건 1로 만든다.

TAS (Test-and-Set) Instruction

메모리 Boolean 변수를 읽어서 확인한 후 값을 1로 쓰는 작업을 Atomic하게 수행하는 명령어

while( TAS(lock_var) != 0 )    // busy waiting(CPU를 헛사용) or spin lock

          use shared resource

lock_var = 0 ;    // resource 사용이 가능

즉, Multiprocessor Synchronization을 하기 위해서는 H/W적 도움이 필요

그 H/W적 도움은 글로벌 변수(lock_var 변수)를 읽고 modify하고 write back 하는 전체 과정에 다른 프로세서가 들어오지 못하게 만드는 것. Atomic operation을 만드는 것임!!

Atomic operation 만드는 방법은 다양하지만 기본적으로 사용하는 것이 TAS.

TAS 방법은 lock_var을 가져와서 걔의 값을 체크 --> 걔의 값이 1이면 1을 리턴하는 것이고 0이면 0을 리턴  --> 그런데 1이건 0이건 무조건 1을 씀  --> 원래 lock_var에 1을 쓰는 것은 아무 의미가 없고  lock_var 값이 0일 때 1을 쓰는 것은 의미가 생김 ( lock_var을 점유한다는 의미 )

Busy Waiting (또는 Spinning)

특정 조건의 만족 여부를 루프를 돌면서 반복해서 확인하는 기법

- 이 문제는 굉장히 나쁜 문제임. 대표적으로 스마트폰의 락업 문제가 이 spinning 문제 임

Lock Holder Preemption 문제

내가 Lock을 잡기 위해서 spinning을 하는데 Lock을 풀어주는 프로세스가 쫓겨나는 것

총 정리

- Synchronization을 제공하기 위해서 OS 차원의 메카니즘은 세마포어인데

- 세마포어를 구현하려면 H/W적인 도움이 필요하다

- singleprocessor일 경우 interrupt disable / enable 이고

- multiprocessor일 경우 TAS 같은 Atomic operation이다.

- TAS Instruction를 이용해서 루프를 만들면 spin lock을 구성할 수 있고

- spin lock은 굉장히 성능에 나쁜 영향을 줄 수 있다.

주의!

spin lock을 잘 사용하지 않으면 시스템에 굉장히 부정적인 영향을 줌!!!

disableinterrupt에 TAS spin lock을 추가 한다

- 멀티프로세서에서도 보호가 되는 세마포어 변수를 구현할 수 있다

Monitors

synchronization 메커니즘 인데 세마포어를 사용함

왜 monitor가 등작했는가? 세마포어가 Unstructured Programming Construct 기 때문에

P()나 V()를 빼먹어서 발생하는 Race Condition을 최대한 피해보기 위해서 등장함

monitor

- abstraction 데이터 타입의 구조에 기반해서 구현이 됨

   abstraction 데이터 타입이란 자바나 C++의 클래스를 의미함

   클래스에는 두가지 멤버가 있음 (데이터 멤버, 메쏘드 멤버)

- Synchronization과 Schedulint의 필요 때문에 몇가지 operate를 더 추가함

   이것이 monitor임

키는 큐가 shared Variable 이기 때문에 Synchronization이 필요함

wait와 signal을 사용하는 예

- 이 모니터에서 사용되는 shared variable은? busy

- 두 가지 메쏘드가 사용됨 ( acquire( ), release( ) )

   acquire( ): busy의 값을 읽어 그 값이 True면 자기가 wait한다는 것이고 누군가 자기를 깨우면 busy를 True로 만들고 자기 할일을 하겠다

   release( ): busy를 false로 만들고 자기 때문에 기다리고 있는 프로세스가 있으면 그것을 깨우겠다는 내용

Monitor의 Condition 변수

어떤 조건이 충족되기를 기다리고 있는 Process들의 Waiting Queue

- waiting queue에 대해서 기다리는 것이 그 Condition 변수 Not wait operator

   깨어나는 것이 그 Condition 변수 Not signal임

- 즉, Condition 변수는 Waiting Queue라고 생각하면 됨

- waiting queue가 있으면 부수적으로 wait reason이 다 있음

- 그 waiting queue에는 wait와 signal이라고 하는 operator가 정의되어 있음

용어 정리

세마포어는 integer 변수

Condition 변수는 waiting queue

Monitor 내부의 공유 변수들을 따로 보호하지 않는 이유

Monitor는 한번에 하나의 Process만 내부의 Method를 수행할 수 있도록 허용하기 때문

Hoare Style Monitor (Signal-and-Urgent-Wait Monitor)

Wait Queue에서 깨어난 Process가 바로 Monitor 내부로 진입하는 방식의 Monitor

Brinch-Hansen Style Monitor

Wait Queue에 Signal을 보낸 Process가 수행을 계속하는 방식의 Monitor

총 정리

- Monitor라는 것은 기본적으로 큰 방에 들어가는 것

- 혼자 들어가는 것이기 때문에 monitor 안에서 정의된 shared 변수는 더이상 Synchronization을 고민하지 않고 사용해도 됨

- 이것이 모니터의 가장 큰 장점

- 그 대신 모니터 안에서 어떤 조건 때문에 더 수행할 수 없는 조건을 대비해서 Condition 변수라는 개념을 만들었고

- 그 안에 wait와 signal 라는 operator를 만들었다

- wait와 signal operator는 어떻게 구현하는 가에 따라 2가지 경우가 있다.

monitor는 OS메커니즘 보다는 프로그래밍 메커니즘임

- monitor가 동작을 하려면 뭘로 변환이 되어야 하나? 세마포어

- 누가 monitor프로그램을 세마포어로 바꾸나? 컴파일러

- 컴파일러가 어떻게 monitor를 세마포어로 바꾸는지 보겠습니다.

monitor를 구현하기 위한 3가지

- monitor 진입점/진출첨 (monitor안에 있는 함수들의 시작/끝포인트)

- wait와 signal 구현 (세마포어 프로그램)

- 시스템에 존재하는 세마포어의 개수 (shared resource 개수)

- 지금 예시는 공유자원 세는 것은 어렵고 대신 queue가 몇 개 있는지 파악한다

- monitor Q, Signaler Q, Condition 변수 Q

Signaler Queue

Hoare Style Monitor에서 Signal을 보낸 Process가 Monitor 밖에서 대기하기 위한 Queue

---

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=659

출처 - http://snui.snu.ac.kr/ocw/index.php?mode=view&id=660