1. Processes in multiprogramming systems

Process synchronization

multiprogramming(multi-tasking) 시스템에서 여러개의 process가 존재하고 각각 독립적으로 일한다. 하지만 독립적으로 일하기 때문에 문제가 생긴다.

• Shared data에 동시에 접근할때 : data inconsistency가 발생하므로 process synchronization mechanism으로 해결해야한다.
• 공유 자원에 동시에 접근할때도 문제가 생긴다.

먼저, Process는 두가지 특징을 가진다.

• Concurrent (병행) : 여러 프로세스들이 시스템안에 동시에 존재한다.
• Asynchronous (비동기) : 다른 프로세스들의 정보를 가지고 있지 않다.

Concurrent와 Parallelism 그만 헷갈리자

Race condition

• 여러 프로세스가 같은 변수를 같이 read/write하는 경우에 접근하는 순서에 따라 결과값이 달라지는 상태.

• Ex1) Pi, Pj 모두 1증가 시켰으니 2가 돼야 consistent하다고 할 수 있다. 각각의 프로세스의 '변수에 값 더하기'가 어떻게 이루어지는지 machine instruction level에서 살펴보자. (1)의 순서로 실행되면 아무문제 없지만, (2)의 순서로 실행된다면 race condition으로 문제가 생긴다. Pi가 CPU의 레지스터 Ri에 1을 더한 상태에서 interrupt 또는 time quantum으로 중지된다. 이때 프로세스의 정보는 PCB에 저장된다. 이 상태에서 Pj는 아직 0인 상태의 Ri에 1을 더해 Ri=1인 상태로 저장한다. 다시 Pi차례가 되고, PCB로부터 아까 저장해둔 Ri=1을 가져와 저장해서 결과값이 1이 나오게 된다.

• EX2) Linked list에 새로운 노드를 넣는 예시이다. 정상적으로 삽입하려면 4개의 포인터 조정이 필요하지만 race condition으로 마지막 포인터가 제대로 조정되지 않은 상태다.

• machine instruction 자체는 atomicity, indivisibility를 보장하기 때문에 machine instruction 중간엔 interrupt 받지 않는다.

Critical Section Problem

일단 용어들 정리

• shared data, critical data : 여러개의 프로세스가 공유하는 data
• critical section : shared data로 접근하는 코드영역
• mutual exclusion(상호배제)
  • critical section에 여러개의 프로세스가 동시에 들어가지 못하게 막는 것
  • 그렇게 하기 위해선 process synchronization mechanism이 필요하다.

• Critical Section 진입을 제어하기 위한 Mutual exclusion primitives
  • enterCS() : 프로세스가 critical section에 들어가기 전에 cs안에 프로세스가 있는지 검사한다.
  • exitCS() : 프로세스가 critical section을 빠져나가면 다른 프로세스들에게 알려준다.
  • enterCS와 exitCS로 구현한 mutual exclusion primitives가 만족시켜야할 조건들이 있다.
    • Mutual exclusion : 상호배제문제를 만족해야한다.
    • Progress : 아무도 없으면 CS에 진입해야한다.
    • Bounded waiting : starvation과 비슷한 문제가 발생하면 안된다. (무기한 지연이 안되게)

2. SW solution for ME and synchronization

shared data로 접근하는 코드영역인 critical section (CS)에 프로세스가 진입하는 것을 제어하기 위해서는 mutual exclusion primitives ( enterCS(), exitCS() )가 필요하다. 먼저 소프트웨어적으로 어떻게 이를 구현하는지 살펴보자.

Two Process Mutual Exclusion

• ME primitives version-1 Mutual exclusion 만족하지만 Progress는 만족하지 않는다.

• ME primitives version-2초기 flag가 둘다 false라고 가정하자. P0 는 flag[0] = TRUE 전에 interrupt 되고 P1은 CS 진입한 상태에서 P0이 다시 돌아온다면 그대로 CS에 들어가게 되고 mutual exclusion을 만족하지 않는다.

• ME primitives version-3 선 flag=true 후 상대방 flag 확인하는 방식. 양쪽 flag 모두 true가 되어 누구도 CS에 들어가지 못하는 경우가 있기 때문에 Progress를 만족하지 않는다.

• Dekker's algorithm최초의 solution이다.

• Peterson's algorithm

N-Process Mutual Exclusion

SW로 N개의 프로세스의 mutual exclusion을 구현하는 방법은 매우 어렵기 때문에 여기선 구경만하자.

• N-process mutual exclusion schemes
  • Dijkstra's algorithm : Indefinite postponement
  • Knuth's algorithm : No indefinite postponements, Long delay to enter CS
  • Eisenberg and McGuire's algorithm : Guarantees CS entry in finite number of trials
  • Lamport's algorithm : Mutual exclusion for distributed systems
  • Bakery algorithm
• Dijkstra's algorithm
  

3. HW solution for ME and synchronization

Mutual exclusion을 해결하기 위해 hardware차원에서 구현하는 방법이다.

Hardware support

SW를 통한 Mutual Exclusion 해결책은 느리고, ME primitives를 실행하는 도중에 preemption이 발생할 수도 있다는 점이다. 실제로 앞서 살펴본 여러가지 버전의 ME primitives들의 문제점은 enterCS 도중에 interrupt가 들어와서 발생하는 문제였다.

• Uniprocessor System (CPU가 하나)면 cs 진입시 interrupt를 받지 않으면 되니까 문제가 간단하게 해결도니다.
• Multiprocessor System면 자신 제외 모든 cpu를 disable하는 것은 쉽지 않다.

Hardware support for ME를 위해, Special machine instruction을 둔다.

• TS (Test and Set) instruction
• Swap instruction
• Fetch and add
• Compare and swap
• Etc..

TS() instruction

• Atomic(indivisible) operation
  target에 true 넣기 + target에 있던 값 return
  두 가지 일이 machine instruction으로 구현됐기 때문에 한 번에(Atomic)하게 이루어진다.

• Mutual exclusion with TS() instruction -1
  매우 간단하지만, bounded-waiting을 만족하지 않는다.

• Mutual exclusion with TS() instruction -2
  bounded-waiting을 만족하는 예시이다. 참고만 하자.

SWAP() instruction

• Atomic(indivisible) operation
  a와 b를 말 그대로 swap한다.

• Mutual exclusion with swap() instruction
  lock의 값을 빼내서 false면 CS에 진입한다는 원리인데 그 빼내는 과정을 swap으로 구현했다. 첫번째 TS 예시와 마찬가지로 매우 간단하지만 bounded-waiting을 만족하지 않는다.

Intermediate Summary

중간 정리를 해보면, mutual exclusion algorithm은 Busy waiting(enter CS에서 CS에 들어간 후 sleep한 다른 프로세스를 기다리고만 있는 경우), Inefficiency의 문제가 있다.
이 문제를 해결하는 방법은 busy waiting을 하지 않는 것이다. busy waiting을 하는 상태라면 asleep 해버리면 된다. 이를 위한 두가지 방법 Semaphore, Sequencer/eventcount(ticket lock)이 있다.

4. Semaphore

프로세스가 CS 진입을 시도하다가 진입할 수 없는 상황이 됐을 때는 Busy waiting이 아닌 asleep하는 방법을 알아보자.

Semaphore

• 정의
  • Integer variable
  • P(), V(), initialization operation만 접근할 수 있다.
  • S라는 semaphore 변수가 하나 생기면 asleep 상태에 I/O queue Qs가 생긴다. CS 진입하지 못하는 프로세스들이 asleep 상태가 될텐데 이때 Qs로 들어가는 용도다.
    
• Operations
  • Initialization operation : semaphore 변수 값을 초기화해준다.
  • P(), V() operation : indivisible operation
    • P() : wait() -> asleep 상태로 갈 때 사용
    • V() : signal() -> 난 나왔으니 다른 Process 들어가도 된다는 신호
      P()는 semaphore = 0이면 Qs에 넣고, 0이 아니면 S값을 1 감소시킨다.
      V()는 Qs에 Process가 있으면 랜덤으로 하나 wakeup하고, 없으면 S값 1 증가시킨다.
• Semaphore의 종류
  • Binary Semaphore
    • 0 또는 1의 값만 가진다.
    • ME 또는 process synchronization에 사용된다.
  • Counting semaphore
    • nonnegative integer values
    • producer-consumer problems를 해결하는데 사용된다.
• Semaphore로 해결가능한 문제들
  • Mutual exclusion problem
  • Process synchronization problem
  • Producer-consumer problem
  • Reader-writer problem
  • Dining philosopher problem
    하나씩 살펴보자.

1. Mutual exclusion problem

2. Process synchronization
조건 : Pj가 Lj를 실행한 후에 Pi가 Li를 실행해야한다. 만약 Pj가 Lj 윗부분을 실행중인데 Pi가 Li에 다다르면 Pi는 sleep해야한다.
Pi와 Pj는 asynchronize하고 independent하기 때문에 서로의 상태를 알 수 없다.
-> 동기화가 필요하므로 다음과 같이 Pi에 P(), Pj에 V()를 넣어 구현한다.

Pi가 먼저 왔을 때, P()에 의해서 S값이 0이기 때문에 Pi는 Qs로 들어간다. 나중에 Pj가 V()를 지나가면서 Qs를 확인하고, 프로세스가 있기 때문에 Pi를 wakeup시키게된다.
Pj가 먼저 왔을 때, V()에 의해서 Qs를 확인하고 아무것도 없으니 S값을 1증가시킨다. 나중에 Pi가 V()를 실행하게되면 S값이 0이 아닌 2이기 때문에 S값을 1 감소시키게 되고, 초기 상태로 돌아가 정상적으로 작동됐음을 확인할 수 있다.

3. Producer-consumer problem
message를 생성하는 여러개의 Producer process들과,
message를 소비하는 여러개의 Consumer process들이 있다.

• Single buffer
  single buffer일 경우 consumed,produced 두 개의 semaphore 변수가 필요하다.
  

  Producer는 new message M을 만들고, buffer에 넣기 전에 P(consumed)로 버퍼가 비어있는지 확인한다. 초기에 버퍼는 비어있기 때문에 P(1)이므로 consumed값을 1감소시켜 0으로 만들고, 버퍼에 넣는다. (만약 버퍼가 비어있는 P(0)인 상태면 Pi를 Qs로 넣어버린다.) 버퍼에 M을 넣고 V(produced)를 통해 Qs를 확인하고 아무 프로세스도 없으니 produced = 1로 증가시킨다.

  Consumer가 왔을 때, 제일 먼저 P(produced)를 통해 버퍼에 가져갈 M이 있는지 확인한다. 0이면 기다려야하기 때문에 Ci를 sleep시키고, 0이 아니면 produced값을 1 감소시킨다. 지금 예시로는 버퍼에 M이 있는 produced = 1인 상태이기 때문에 성공적으로 M을 가져갈 수 있다. 가져간 후에 V(consumed)를 통해 consumed = 1로 세팅하고 끝나게 된다.

  하지만 버퍼가 하나이기 때문에 waiting이 발생할 수 있다.

• Multiple buffers
  

  차근차근 살펴보면,
  Producer는 제일 처음 P(nrempty)로 버퍼가 꽉 차있는지 본다. 꽉 차있는 상태인 nrempty 가 0이 아니기 때문에 nrempty를 하나 감소시키고 버퍼에 M을 넣고, 시계방향으로 회전하고, V(nrfull)을 통해 nrfull을 하나 증가시킨다.
  Consumer는 먼저 P(nrfull)을 통해 0이 아니면 nrfull을 하나 감소시키고 내려간다. 버퍼에서 M을 받고, 시계방향으로 회전하고, V(nrempty)를 통해 nrempty를 하나 증가시킨다.

4. Reader-writer problem
data를 읽기만 하는 Reader process, data를 업데이트 하는 Writer process가 있다.
Reader는 data에 동시에 접근할 수 있고, Writer는 한 프로세스만 접근(ME)을 해야한다.

Reader/Writer 누구에게 더 높은 우선순위를 줄지에 대한 기준으로 3가지의 해결법이 있다.

• Strong reader preference solution

• Weak reader preference solution <- 예시로 보자

• Writer preference solution
  필기가 복잡한데 하나씩 보면된다.
  Writer 프로세스들 간의 ME는 wmutex로 구현
  nreader연산을 한 번에 한 개의 프로세스만 수행하도록 하는 ME는 rmutext로 구현
  Writer와 Reader가 동시에 수행되지 못하게 하는 ME는 빨간색 필기로 wmutex로 구현

  하지만 실제 OS에는 semaphore로 해결하기보단 Reader-writer locks를 따로 두어 해결한다.

5. Dining philosopher problem
semaphore로 해결할 수 있는 마지막 문제다.. 실제 발생하는 문제는 아니고 공부를 위해 구상한 문제라고한다.
5명의 철학자들이 있고 철학자이기 때문에 생각한다. 그러다 배가 고파지면 앞에 밥을 먹고 다시 생각한다. 밥을 먹을 때 자기 자신의 양쪽에 있는 포크를 모두 사용해서 먹을 수 있다.구현을 위한 코드는 아래와 같다.pickup, putdown함수를 semaphore 변수와 V(), P() 함수를 통해서 해결할 수 있다. 기회가 된다면 실제로 구현을 해보고 포스팅해야겠다.

Semaphore-based solution의 특징

• No busy waiting : 기다리려하면 P()함수를 통해 sleep시켜버린다.

• No scheduling for wakeup : Q() 함수는 랜덤으로 wakeup시키기 때문에 스케줄링을 하지않는다. 운이 나쁘면 가장 마지막에 선택되기 때문에 starvation 문제가 발생한다.

  starvation은 계속 해결해야만 했던 문제이기 때문에 semaphore 대신 다른 방식을 사용해 동기화문제를 starvation 없이 해결할 수 있다.
  글이 너무 길어져서 2개로 나눠서 작성해야지

  뒷부분 링크 >> Process Synchronization(2)