Process Synchronization

병행제어

MultiLevel Queue란 Ready queue를 여러개로 분할하는 것을 말한다. Multi level Queue에서는 큐의 종류를 두가지로 나눈다. -> foreground / background. 큐를 나누는 기준은 사용자와 ineteract를 하는경우에 foreground 큐에 그렇지 않은 경우에 background 큐에 둔다. forground는 사용자와 interactive하기 때문에 더 많은 CPU time 을 준다. 보통 Time slice로 RR알고리즘을 사용하여 80%는 foreground, 20%는 FCFS 알고리즘으로 background에 할당하여 starvation을 방지한다.

 

Multi level feedback queue 는 기존의 multilevel queue보다 조금더 유연한 방식을 제공한다.  이전에 큐의 우선순위가 한 번 정해져있으면 고정되는 것과 다르게 큐의 우선순위가 정해지더라도 나중에 유동적으로 순위가 바뀔 수 있다. 프로세스들이 우선순위가 서로다른 큐들을 이동하는 기준으로 에이징을 적용할 수 있다.  

 

realtime scheduling을 살펴보면 Hard real time system의 task는 정해진 시간안에 반드시 끝내도록 스케쥴링 해야한다. 데드라인을 지키는 것이 매우 중요하기 때문에 offline 스케쥴링이 많다 (offline: 미리 프로세스들이 언제 도착할지 알고있음).반면 Soft real time system 은 정해진 시간에 완수하지 못하더라도 높은 priority의 작업으로 할당해야한다(동영상 스트리밍 etc), 따라서 online 스케쥴링으로 된다 (프로세스 도착 시간 미리 생각안하고 그때그때 처리).

 

Thread scheduling에는 Local Scheduling과 Global scheduling 두 가지 방법이 있다. 운영체제가 스레드의 존재 유무를 알고 있다면 커널에 의해 스케쥴링 되는 global scheduling, 운영체제가 해당 스레드의 존재유무를 모른다면 (user level thread) 라면 프로세스 내부에서 스케줄링이 결정되는 local scheduling으로 동작한다.

 

알고리즘 성능평가 방법에는 크게 3가지 방법이 있다 (Queueing models, Implementation(구현)&Measurement(성능측정), Simulation(모의 실험))

• Queueing models: Arrival rate(도착율-얼마나 빠른 빈도로 CPU를 쓰겠다고 도착하느냐)와 Service rate(처리율-단위시간당 얼마나 많은 작업을 처리하느냐) 두 가지를 이용해서 평가
• Implementation(구현)&Measurement(성능측정): 실제로 구현해서 작업 비교를 통해 성능을 측정하는 방법
• Simulation(모의 실험): 실제로 구현하는 것이 아닌 가상적으로 돌려보는 방법으로 trace(주어진 작업)를 모의프로그램으로 돌려보는 방법

---

Process Synchronization

컴퓨터가 데이터에접근하는 순서는 아래와 같다.

1. 먼저 데이터가 저장되어 있어야한다
2. 저장된 데이터 중 연산할 데이터를 읽어온다.
3. 데이터를 연산한다
4. 연산결과를 다시 데이터에 저장한다

만약 읽어가는 연산이 2개 이상 있을 경우 Race Condition의 가능성이 있다. 이때 Race condition이란 한쪽이 1을 더하는 연산, 한쪽이 1을 빼는 연산을 할 때 둘의 순서에 따라 저장값에 차이가 나는 경우를 말한다. S-box(memory address space)를 두고 여러 E-Box(CPU process)가 경쟁하는 상황을 Race Condition이라 부른다. 

 

race condition은 CPU가 한 개일때도 발생할 수 있다. 한 프로세스가 CPU를 가지고 일을 하다 운영체제에게 시스템 콜을 한다. 이렇게 운영체제 안의 데이터값을 바꾸고 있을 때 자신의 CPU할당시간이 끝나버려 다음 프로세스에게 넘어간다. 이 때 다음 프로세스도 시스템 콜을 하게되면서 그전의 프로세스가 날린 시스템 콜이 건드리는 커널의 데이터와 겹치게 되면서 경쟁상황이 발생한다. 즉 프로세스에 의해서도 경쟁상황이 발생한다.

 

정리하자면 OS에서 race condition이 발생하는 경우는 크게 3가지이다. 

 

첫번째 경우를 간단한 예로 들면 커널이 CPU를 사용해 1증가시키고 있을 때 인터럽트가 들어와버려 ++가 안먹히고 --를 할 수 있다. 이를 방지하기 위해서는 커널이 cpu를 통해 작업을 하고 있을 때는 inturrpt 거는걸 금지시키는 방법이 있다. 

 

두번 째 예제의 상황은 A프로세스가 본인작업을 하다 시분할에 의해 큐 뒤로가고 B프로세스가 CPU를 점유하는 과정에서 생기는문제이다. A와 B가 공유하는 데이터를 두고 작업할 경우 A는 자기작업을 끝내지 못한 생태에서 B에게 CPU를 넘기기 때문에 공유하는 데이터에 문제가 생긴다. 이러한 경쟁상황을 방지하기 위해서는 시스템 콜을 하여 커널모드에서 수행 중일 때는 시분할에 의해 할당시간이 끝나더라도 CPU를 넘기지 않는 방법이 있다. 즉 커널 모드에서는 다른 프로세스가 CPU를 preempt(점유)하지 않고 프로세스A가 커널 모드에서 사용자모드로 돌아갈 때 다른 프로세스가 preempt 할 수 있게 한다. 

 

세번째는 멀티프로세서 환경에서 CPU 여러개가 공유하는 메모리에 접근하면서 생기는 경쟁상황이다. 이때는 lock을 걸어 해결한다. 만약 한 CPU가 메모리에 접근해서 이용하고 있으면 다른 CPU가 접근하지 못하게 락을 거는 것이다.

 

정리하면 Process Synchronization 문제는 공유 데이터(shared data)의 동시접근(concurrent access)할 때 생기는 문제로 데이터 불일치 문제(inconsistency)이다. 이를 방지하기 위해, 다시말해 일관성(consistency) 유지를 위해 협력 프로세스(Cooperating process)간의 실행 순서(orderly execution)를 정해주는 매커니즘이 필요하다. 이러한 겹쳐서 이용되는 구간(Critical section)에 하나의 프로세스가 있을 때 모든 프로세스를 막는 방법(lock)으로 문제를 보완할 수 있다.

 

프로세스간 경쟁상황을 해결하는 충족조건은 3가지이다. -> Mutual Exclusion, Progress, Bounded Waiting

• Mutual Exclusion(상호배제): 한 프로세스가 Critical Section을 이용중이면 다른 프로세스는 이용불가 
• Progress(진행): Critical Section 이용 대기자가 없으면 이용하고자 하는 프로세스에게 내준다
• Bounded Waiting(유한대기): 프로세스 대기열이 길 경우 각 프로세스 대기 시간이 유효해야 한다 (starvation이 생기지 않도록)

---

Process Synchronization 문제해결

먼저 하드웨어 측면을 보자면 하드웨어에서 데이터를 atomic하게 작업할 수 있도록 해준다면 문제를 해결할 수 있다. 즉 접근과 수정을 하나의 단위로 묶는 작업(Test and set) 으로 하드웨어에서 보완하는 것이다. 이렇게 되면 단순히 작업할 때와 하지 않을 때 락을 걸거나 풀기만 하면 된다.

 

소프트웨어적인 측면에서 가장 단순한 방법은 flag를 활용하는 방법이다. 한 프로세스가 진입하면 플래그를 true로 바꿔 다른 프로세스가 진입을 못하게하고 작업이 끝나고 나올때 다시 false로 바꿔 다른 프로세스가 접근가능하도록 둔다. 하지만 이러한 flag의 문제는 만약 프로세스가 flag = true를 넣고 시간초과로 다른 프로세스에게 넘어가면 다른 프로세스가 또 flag = true로 넣게 되면 모두가 while문 안으로 진입하지 못하는 상황이 된다.

 

피터슨 알고리즘에서는 깃발 뿐만 아니라 turn변수도 들고있게 된다. turn변수를 통해 상대방이 깃발을 true로 해놓고 만약 내차례라면 while문 안으로 진입한다.

 

하지만  while문 조건을 만족해서 들어왔는데 탈출조건이 없다면 계속해서 while문에 갇혀있을 것이다. 이러한 상황을 busy waiting이라고 하는데  busy waiting은 프로세스나 스레드가 특정 조건이 만족될 때까지 CPU를 지속적으로 사용하여 루프를 반복하는 상태를 말한다. 

---

Semaphor

세마포는 이전의 레이스컨디션 방지 방법을 소프트웨어적으로 추상화시킨 방법이다. 세마포 변수값은 정수로 정의된다.(자원을 쓰는 개수), 만약 Smeaphore mutex(세마포 변수) 가 1이면 1개가 Critical Secstion에 들어갈 수 있다. 이때 세마포 자료형의 연산은 p연산과 v연산 두가지로 이루어진다.  P연산은 자원을 획득하는 과정, V연산은 자원을 반납하는 과정이다. 예를 들어 세마포어 변수값이 1이면 P연산을 할경우 lock을 획득하는 과정이라 볼 수 있다. 자원을 다쓰고 나올때 v연산을 하게되면 lock이 풀리는 과정이라고 볼 수 있다. 이러한 p연산과 v연산 사이에 공유자원을 쓰는 작업이 수행된다. 세마포는 이러한 P연산 - CS작업 - V연산을 atomic하게 처리한다.

 

 하지만 이러한 세마포에서도 busy waiting 문제는 여전히 발생한다. 만약 누군가 들어가 있어서 뮤텍스 값이 0일 때 P연산을 하면 P연산의 While문에서 무한루프가 돌아가 CPU를 빠져나오지 못하고 while문만 돌다 할당시간이 끝나버리기 때문이다. 

 

block & wake up 방식을 통해 앞선 busy waiting 문제를 해결할 수 있다. 이전에 세마포 변수에 정수를 설정하여 0이면 잠그고 1이상이면 열었던 단순한 방식과 다르게 이 방식에서는 세마포 구조체를 만들어 관리하는 방법이다. 세마포 변수L에 의해서 프로세스들을 줄세워 기다리게 하는 방법으로 Block / Wake up 방식을 사용하면 이전에 CPU를 계속 쓰면서(p연산 while문에서 대기하면서) 대기 했던 것과 다르게 CPU 밖 큐라는 대기열에서 프로세스들이 대기하게 된다. (blokced 되면서 큐에서 sleep한다, 쓰게할 때는 wake up)

 

성능면에서 봤을 때 일반적으로 Block/WakeUp이 더 효율적이기는 하다. Busy-Wait 방식은 대기를 하는 프로세스가 CPU에서 계속 동작하고 있기 때문이다. 만약 Critical Section의 길이가 매우 짧은 경우 WakeUp도 일종의 오버헤드이기 때문에 busy-wait가 좀더 효율적일 수 있다. (하지만 busy wait문제는 여전히 존재)

 

Binary semaphore와 Counting semaphore 는 어떤 차이가 있을까? 전자는 세마포 변수값이 0 또는 1만 가지고 후자는 세마포 변수값이 0이상의 임의의 정수값을 가진다. 전자의 경우 mutual exclusion(락걸고 풀기)에 사용되고 후자의 경우 resource counting에 사용된다.

 

세마포를 사용할 때 데드락과 starvation문제가 발생할 수 있다. 서로 자원을 하나씩 차지하고 상대방 자원 세마포가 1 떨어지기를 기다리게 되면 무한으로 기다리게 되는데 이게 바로 데드락 현상이다. 이렇게 계속해서 기다리다 보니 Starvation문제도 발생한다. 

 

이러한 데드락에서 Starvation으로 이어지는 문제는 철학자의 식탁문제로도 설명할 수 있다. 탁자에 둘러앉아 식사를 하는데 한 사람이 오른쪽 젓가락을 쓰고있고 왼쪽 젓가락을 기다리고 또 옆에 사람은 왼쪽 젓가락을 기다리고 오른쪽 젓가락을 쓰고있는.. 자기 젓가락을 안내려놓고 서로의 젓가락을 기다리기만 기다리는 상황을 Dining-Philosophers Problem 이라고 한다.. 이때 젓가락은 공유데이터이고 세마포의 경우 1로 설정되었다고 볼 수 있다. 일종의 데드락 상황이라고 볼 수 있으며 이를 해결하기 위해서는 젓가락 두개 모두 집을 수 있을 때만 젓가락을 집을 수 있게하는 방법이 있다. 또다른 방법으로는 데드락을 해결하는 대표적인 방법인 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 잡도록 설계하는 방법이 있다.

 

세마포 사용에 있어 발생하는 문제는 Bounded Buffer Problem(Producer-Consumer Problem) 도 존재한다. 공유데이터를 쓰는 Buffer에서 경쟁상황이 생기는 문제이다. 공유데이터 버퍼에는 두가지 프로세스가 있다 (Producer-생산자 프로세스 와 Consumer-소비자 프로세스) 만약 Producer가 버퍼를 채우고 있을 때 다른 Producer에게 CPU를 빼앗기면 똑같은 빈 버퍼에 데이터가 중복되어 저장되어 유실되는 문제가 있습니다. 비슷한 상황이 Consumer에서도 발생한다. 이러한 Bounded Buffer Problem을 방지하기 위해 lock을 거는 방법이 있다.

 

Readers-Writer problem 도 존재한다. 주로 DB에서 발생하는 문제로 한 프로세스가 Write 중일 때 다른 프로세스가 접근하는 경우 생기는 문제이다. (read는 동시에 여럿이 해도 문제 x) 이를 해결하기 위해서는 Writer가 진입할 때는 대기 중인 Reader가 없을 때만 허용하고 Writer가 빠져나가야만 Reader의 접근을 허용한다. 이때 Writer가 일찍 도착했음에도 Reader가 계속와서 틈을 주지 않으면 Starvation 문제가 발생할 수 있다. 이러한 Starvation은 일정시간 단위로 reader의 접근을 허용하고 짤라 Writer를 들어오게 함으로써 문제를 보완할 수 있다.

 

이렇게 세마포 사용에 있어 발생하는 문제는 크게 식사하는 철학자 문제, Bounded Buffer, Readers-Writer problem 3가지가 있다.

---

Monitor

모니터는 공유데이터에 접근할 수 있는 경로를 셋팅함으로써 이전 세마포에서 발생하는 문제 (함수 내부에서 p,v로 인한 버그잡기 어려움)를 보완할 수 있다. 이렇게 경로가 미리 셋팅이 되어있으면 경로에 들어가는 프로그램이 구구절절 락을 걸고 풀고 작업을 할 필요가 없어진다. (이미 모니터 자체에 동시접근을 막아놓음). 결국 모니터는 임계 구역(critical section)과 이를 제어하는 메커니즘을 포함하는 하나의 추상 데이터 타입(Abstract Data Type)이다.

 

모니터의 장점은 개발자가 동기화 제약조건을 매번 코딩할 필요가 없다는 것이다. 이를 위해 모니터 내부에서는 조건 변수(Condition varaible)을 사용한다. 조건 변수를 통해 스레드를 기다리게 하거나 실행시킨다. 조건 변수를 바꾸기 위해서는 wait/signal 호출을 해야한다.

• wait(): 조건 변수를 사용하여 스레드를 대기 상태로 만든다. 스레드는 조건이 충족될 때까지 기다린다. 이때 모니터의 락을 해제하고 대기 큐에 들어간다. 
• signal(): 조건 변수를 사용하여 대기 중인 스레드 중 하나를 깨운다. signal()은 대기 중인 스레드가 없는 경우 아무런 효과도 없다.
  
  

만약 기존 세마포를 활용했다면 임계구역에 접근할 때 P연산, 나올 때 V연산 그리고 mutex 값 관리도 해주었어야 했다. 하지만 여기에 모니터를 활용하게 되면 조건 변수를 내장하여  wait, signal 함수로만 처리해주어 훨씬 간단하고 직관적인 코드작성이 가능하다.

 

---

https://core.ewha.ac.kr/publicview/C0101020140401134252676046?vmode=f

반효경 [운영체제] 11. CPU Scheduling 2 / Process Synchronization 1