OS - 02. Processes and Threads (1)

Race Conditions

- ProcessA와 B가 동시에 공유 메모리를 access(접근)하기 원하는 상태. 경쟁상황이 발생할 수 있고, 경쟁 결과에 따라 결과값이 변경될 수 있다.

Critical Regions

race condition을 피하기 위한 필요 조건

1. Mutual Exclusion : 상호배제, 동시에 임계구역에 들어갈 수 없도록한다.
2. Progress : 임계 영역 밖에서 실행되는 어떠한 프로세스도 다른 프로세스를 차단할 수 없다.
3. Bounded Waiting : 임계 영역에 들어가기 위해 영원히 기다리는 프로세스는 없도록 한다.

process A가 임계구역에 들어가면 B는 A가 나올때까지 기다린다.

상호배제(Mutual Exclusion)를 구현하기 위한 제안

• Disabling interrupts
• Lock variables
• Strict alternation
• peterson's solution
• The TSL instruction

Strict Alternation

process j가 임계 영역에 들어갈때까지 process i는 계속 대기 상태가 되어 실행되지 않는다. 제대로된 해결책이 아님!

Dekker's Solution

Process i는 상대방 flag를 보고 j가 TRUE면 while문에서 기다린다. FALSE이면 turn이 j인지 확인하고, j라면 자신의 flag를 FALSE로 만들고 turn이 i가 될때까지 기다린다. turn이 i이면 그때 임계구역에 들어갈 수 있다.

- flag: 들어가겠다는 표지

- turn: 실제 배정받은 turn(실행중 표시)

Peterson's Solution

Dekker와 비슷하지만 여기서 turn의 의미는 양보할 프로세스이다. Process i는 flag가 i, turn이 j일때까지 기다렸다가 임계구역에 들어간다.

Bakery Algorithm

프로세스(쓰레드)의 개수가 n개일때, 빵집처럼 번호표를 받아서 번호표가 같을 때 고유 id 순으로 임계 영역에 들어간다.

The TSL Instruction

위 빵집알고리즘은 소프트웨어적 도구인데, 이를 수행하기에는 너무 heavy함으로 하드웨어의 도움이 필요하다. 이에 TSL Register를 도입하여 하드웨어적으로 작성한다. (TSL = Test and Set Lock)

 

좌: TSL Instruction, 우: XCHG Instruction

TSL은 Lock 변수를 register로 가져와서 1로 세팅한다. 세팅 이전의 Lock값이 0인지 확인 한 후, 0이라면 return하여 임계구역에 진입하고 1이라면 다른 process가 이미 1로 세팅하여 사용중이므로 loop를 돌며 확인한다.

XCHG는 Lock변수와 Register를 exchange(swap)하여 TSL과 같은 과정을 거친다.

The Producer-Consumer Problem

• Producer-Consumer관계의 두 프로세스는 둘 다 Sleep할 수 있는 치명적인 race condition을 가질 수 있다.
• producer는 item을 만들어서 queue에 넣고, count가 N에 도달(queue가 꽉 참)하면 스스로 sleep한다. 이를 consumer가 count가 N-1이 될 때(꽉 차지 않게됨)를 확인 후 producer를 깨워주는 방식으로 동작한다.
• producer의 sleep직전에 cousumer가 실행되어 wakeup하게되면 producer는 sleep상태를 유지하게되고 이후 cousumer는 큐를 모두 소비하고 sleep하게되므로 결국 둘 다 sleep하게되는 문제가 발생한다. 이는 반대의 경우(consumer의 sleep직전에 producer가 실행되어 wakeup)도 마찬가지로 문제가 발생한다.

Semaphores

Semaphore는 Up&Down연산자를 사용하고, mutual exclusion(상호배제)와 synchronization(동기화)를 위해 사용될 수 있다.

 

down은 count를 감소시키고 만약 카운트가 0보다 작다면 (즉, sleep조건이면) down을 호출한 프로세스를 sleep시킨다.

up도 down과 마찬가지로 count를 증가시키고 만약 카운트가 0보다 같거나 작다면 sleep중인 프로세스를 wake up시켜준다.

각 down과 up과정은 수행중 끼어들 수 없고, 이를 아토믹하게(원자적으로) 진행한다고 한다.

producer-cousumer problem을 Semaphore로 해결한 과정

Producer과 Consumer사이에는 유한한 큐 버퍼가 존재하고, Semaphore n, mutex, e를 설정한다.

down(mutex)를 producer와 consumer가 동시에 호출해도 OS자체에서 한 프로세스만 down하도록 한다.

만약 producer가 down mutex를 하면 1에서 0으로 바꾸어 먼저 수행하고, consumer는 0에서 -1로 바꾸어 실행을 대기한다(sleep).

이후 producer가 작업을 수행하고 임계 영역을 나올 때 mutex를 up하면 -1에서 0로 바뀌고 sleep을 호출한 프로세스(consumer)를 깨워주고 consumer은 바로 semaphore을 획득하여 임계 영역에 들어가 바로 실행하게 된다.

 

Priority Inversion(우선순위 역전)

sleep과 wakeup이 수행될 때 우선순위를 기반으로한 선점 스케줄링(priority-based preemptive scheduling scheme)에서 우선순위 역전이 일어날 수 있다.

우선순위: T1 > T2 > T3

T3이 필요한 데이터를 Lock을 하여 실행중인데, T1이 깨어나서 수행 시 T3이 Lock을 한 데이터를 필요로 한다. 이 때 T1은 T3이 수행 종료되어 Lock을 반환할 때 까지 기다려야하는데, 그 사이 T2가 스케줄링되어 실행되면 T2가 T1보다 먼저 수행되며 종료하는 우선순위 역전이 생길 수 있다.

Priority Inheritance

T1의 우선순위를 T3에게 상속하여 T3 수행 중에 T2는 깨어나도 T3이 우선순위가 더 높기 때문에 T3이 수행 종료된 후 수행된다.

Mutexes

• Semaphore는 OS에 시스템 호출을 함으로써 상호배제를 구현한다. 반대로 Mutex는 OS에 부탁하지 않고 독립적으로 상호배제를 할 수 있는 방법이다.
• Mutex는 쓰레드들 간에 OS 공유없이 가능한 공유방법으로, 하나의 프로세스 내에서 TSL연산을 그대로 이용할 수 있다.
• 따라서 Mutex는 멀티 쓰레드로 구현하고 싶을 때 효율적일 수 있다.

TSL과 마찬가지로, registe는 mutex를 1로 세팅하고, 이전값이 0이었다면 return하고 1이었다면 mutex가 수행중(다른 쓰레드 스케줄중)이므로 처음부터 다시수행하며 대기한다.

Mutexes in pthreads

• 대부분의 OS는 Mutex연산을 제공하여 하나의 프로세스 안에서 멀티 쓰레드로 일을 할 때 사용하는것이 가능하다!
• 하지만 mutex는 semaphore과는 다르게 동기화(sleep-wakeup)는 해주지 못하기 때문에 condition 변수를 도입하였다.

Pthread 패키지, mutex 변수를 생성하거나(init) 삭제(destroy), lock, unlock등의 기능을 제공한다. signal, broadcast를 이용하여 쓰레드를 하나만 깨우거나 모두 깨우는 등의 작업도 가능하

쓰레드를 이용하여 producer-cousumer problem를 해결한 코드. consumer와 producer를 별도의 쓰레드로 생성하여 병렬 실행한다.

이때 만약 producer가 lock을 하고 버퍼가 MAX에 도달하면 unlock하지 않고 잠들게되어 consumer는 이를 깨워줄 수 없게 된다. 따라서 sleep직전에 unlock하도록 설계되어있고, 깨어날 때 lock을 하지 않고 깨면 안되므로 lock을 하고 깨어나도록 하는 코드도 설계되어 있다.

Monitors

• up&down연산(high level)과 lock&unlock연산(low level)은 설계시 코드가 수천줄이 넘어가면 up&down쌍을 맞추기 어렵다는 문제점이 있다.
• Monitor은 동기화를 프로그래머가 설계하는것이 아니라 컴파일러 수준에서 하도록 설계한 것이다.

모니터. 쓰레드가 동시에 호출해도 컴파일러는 항상 한번에 하나씩만 실행해준다.(상호배제)

 

모니터로 구현한 producer-cousumer problem.

2개의 쓰레드가 동시에 실행되는 중에 동시에 insert, remove를 부르게 되더라도 컴파일러가 알아서 동시에 실행되지않도록 구현된다.

Structure of a Monitor

1. 프로세스들은 Queue에서 기다리다 하나씩 모니터로 들어와 실행한다. 
2. 첫번째 프로세스가 실행하다 sleep하는 코드를 만나면 monitor의 waiting area로 들어가서 기다린다.
3. 그동안 모니터가 비게되면 두번째 프로세스가 들어와서 실행한다.
4. 이때 첫번째 프로세스를 wake up해주는 코드가 있다고 하면 깨워준 이후 두 프로세스는 동시에 수행될수 없으므로
5. 두번째 프로세스는 1) wake up을 시켜주고 바로 urgent Queue로 들어가 기다리고 첫번째 프로세스를 실행하거나 / 2)  wake up을 시켜주고 쭉 수행 후 종료된 다음 첫번째 프로세스를 실행할 수 있다.

• Hoare's Monitor : 1) 방법. 안멈추고 실행시 이후 코드에 따라 다른 일을 하게되면 조건이 훼손될 수 있다는 이유가 명확하다.
• Lampson&Redell's Monitor: 2) 방법. 첫번째 프로세스가 깨어나면 바로 실행(if문으로 작성)하는것이 아니라 처음 코드로 다시 돌아가서(while문으로 작성) count가 0인지 확인하는 등의 작업을 하여 조건 훼손 가능성(에러 가능성)이 없도록 구현하였다.

Lock-free Data Structure

CPU의 core수가 많아져서 공유 변수를 수정할 때 Lock이 병목현상을 일으킬 수 있게되어 성능이 떨어질 수 있다.

따라서 CPU는 Atomic한 CAS기능(Compare-and-Swap 명령어)을 제공한다.

 

Lock-free Push and Pop

push&pop 자료구조의 포인터 위치의 변경을 CAS로 구현할 수 있다.

ABA Problem

Node들이 Linked list로 연결되어있다. head를 Node A에서 B로 변경하는 Thread1을 수행하기 전에 pop을 2번, A를 push하는 Thread2가 수행되면 head가 잘못 옮겨지는 문제가 발생한다.

Synchronization(동기화)

Message Passing

send와 receive를 통해 데이터를 주고받을 수 있다. 이때 destination, source등을 위해 addressing이 필요하다.

Synchronization

Sender와 Receiver는 메세지를 전달될때까지 기다리는동안 blocking될 수도있고 안될수도있다.

• Blocking send, blocking receive : sender와 receiver가 메세지가 전달될 때 까지 모두 block된다.
• Nonblocking send, blocking receive : sender는 메세지를 보내고 꼭 기다릴 필요 없고(작업 수행) 자기일을 한다. 가장 일반적인 경우.
• Nonblocking send, nonblocking receive : sender와 receiver모두 메세지가 전달될 때 까지 block되지 않는다. 이때 메세지를 저장하는 Q가 중간과정에 별도로 존재해야한다!

Addressing

Direct Addressing

• process id로 Addressing하는 방법. Addressing시 몇번 process인지 알 수 있다. 하지만 process id는 실행될 때 마다 동작이 할당되기 때문에 프로그램 작성시 몇 번일지 예측할 수 없다.

Indirect Addressing

• mailbox(=port, Queue)를 이용하는 방법. 보통 이 방법을 많이 사용한다.
• ex) sender은 mailbox 10번에 데이터를 할당 한 후 receiver가 이를 가져간다.

Indirect Process Communication

N개의 message를 이용한 producer-cousumer problem. 메세지 자체를 주고받으므로 임계 영역은 필요하지 않다.

Barriers

모든 쓰레드가 특정 지점(Barrier)에 도달할 때까지 기다렸다가 다음단계를 진행하도록 한다.

a -> b -> c, 모든 프로세스가 Barrier에 도달하면 그 이후 프로세스가 진행된다.