Process Synchronization(1)

Background

동기화 문제를 다루는 이유?

->공유 data로의 동시적 접근이 발생하는 경우 result inconsistency 문제가 발생할 수 있음

 

Race condition

:몇몇의 process들이 접근하여 shared data를 동식에 조작하는 상황

-> 이 경우 final value 는 마지막 실행 프로세스의 결과에 따라 달라짐

 

Race condition 문제를 방지하기 위해 concurrent processes는 synchronize 되어야 한다.

 

Race condition 문제의 예시                                                                    원래는 2가 저장되어야 하지만 결과적으로 1이 저장됨 -> Race condition

The Critical-Section Problem

n개의 process들이 shared data를 사용하기 위해 competing 하는 상황

각 process는 code segment를 갖는데 이를 critical section이라고 한다. (shared data가 접근되는 영역)

Race condition을 막기 위한 solution : 하나의 process가 실행중인 경우 다른 process는 critical section을 실행하지못하도록 막자!

 

Requirements for the Solution

3가지 요구조건

1. Mutual Exclusion

- 상호베타적으로 Critical Section을 수행할 수 있도록 해줘야 한다.

하나의 process pi 가 critical section 에서 실행중이면 다른 어떤 process도 critical section에서 수행할 수 없도록 해야한다.

 

2.Progress

-과도하게 막아서 어떤 process도 critical section에서 수행중이지 않은데도 못들어가게 막는 상황은 발생하면 안된다.

 

3. Bounded Waiting

- 다른 process가 실행중이라 기다리는 중인데 순서가 계속해서 밀려서 기다리게 되는 경우가 발생해서는 안된다.

(기다리는 시간의 bound값을 정해야 한다. -> starvation 개념과 비슷)

 

Progress, Bounded Waiting 은 Race condition을 방지하되 Throughput이 떨어져 전체적인 성능이 저하되지 않도록 하기 위한 조건

 

Initial Attemps to Solve Problem

2개의 process p1,p2가 있는 경우

entry section과 exit section을 설정

entry section : 진입 가능한 상태인지 확인 (다른 process의 상태를 확인)

exit section : 끝난 후 다른 기다리는 process에게 알림 (본인 상태를 다른 process에게 알림)

-> process 상태를 나타내는 변수가 필요

 

Algorithm 1

Shared variables : int turn, initially turn = 0

turn 이라는 변수를 사용하여 해당하는 값의 process만 critical section에 들어갈 수 있음

turn이 0이 아닌 경우 while loop 문을 돌면서 기다린 후 process가 끝나서 turn =1 이 되면 실행

 

특징 : P0이 끝나서 turn =1 이 되면 P1이 실행되어 turn =0 이 되어야지 다시 P0 실행이 가능하다.

mutual exclusion 조건을 만족하지만 progress 조건을 만족하지 못한다. -> swap-turn 문제 발생

=> solution이 될 수 없다!

 

Algorithm 2

들어가고자 하는 process를 들어가도록 만들어주자

Shared variables : boolean flag[2];

initially flag[i] = flag[j] = false;

flag 값이 true 이면 critical section에 들어간다. 이때 상대방의 flag를 먼저 check 하여 true 인 경우 양보하고 기다린 후 끝나면 들어감

 

swap turn 문제는 해결되지만 여전히 mutual exclusion 조건만 만족하고 progress 조건을 만족시키지 못한다.

->둘 다 true 인 경우 while 문에서 서로 기다리기 때문에 막혀버려서 critical section이 비었음에도 양보하며 기다리기만 하는 현상 발생

=> solution이 될 수 없다!

Algorithm3 (Peterson's Algorithm)

Algorithm1 과 Algorithm2 의 변수를 모두 사용하여 합친 개념

(1의 경우 들어갈 생각이 없는 process에게 turn을 줘서 문제 발생, 2의 경우 둘 다 들어가려고 하는 상황에서 교통정리를 못해줘서 문제 발생)

flag,turn 두 가지 변수를 모두 사용하여 문제를 해결 (상대가 들어갈 생각이 있고 순서를 갖는다면 문제 해결)

3가지 요구조건을 모두 만족 시킴 -> solution이 될 수 있음!

 

But 문제점

1. Busy waiting (waiting 상태에서 process가 while loop를 돌면서 CPU를 잡아먹고 있음 -> 매우 비효율적)

2.entry section 부분의 코드가 길다. -> 각 process 마다 작성하는데 너무 code가 복잡해질 수 있다. 개발자 입장에서 비효율적

 

Solution to Critical-section Problem using Locks

-위의 문제를 locking system을 이용하여 해결하자.

lock을 사용하여 해당 process 가 key를 확보하면 critical section에 진입하고 끝나면 key를 반납하여 다른 process가 사용가능하도록 설계

중요한 전제 조건 : key는 반드시 단 하나의 process만 갖도록 보장되어야 한다.

Synchronization Hardware

: 특별한 Hardware 회로를 제공하여 하나의 실행이 끝까지 수행되도록 보장해줌 (Atomic Hardware)

 

Cpu가 하나인 경우 CPU Scheduling에 의해서 process를 이동하며 문제가 발생한다. -> interleaved execution 발생

P1이 LOAD 되기 전에 CPU Scheduling이 발생하지 않도록 한다면 괜찮지 않을까?

->critical section을 빠져나오면 그때 cpu를 놓을 수 있도록 하자

How? -> interrupt가 발생하는 경우 cpu scheduling이 일어남

interrupt가 발생하는 경우는 i/o device, time out 두 가지 경우가 있음. critical section에서 I/O 발생은 일어나지 않으므로 time outㄹ을 활용하자

timer device가 time quantum이 끝나서 interrupt를 발생 시킬때 cpu scheduling이 발생한다.

critical section에 들어가면 timer interrupt를 disable 시키고 끝나고 나오면서 enable 시키자! => critical section 동안 cpu를 계속 사용 가능함

 

최근에는 atomic hardware instruction을 제공한다

atomic = non -interruptible

1. Test - and - Set (TAS)

2. Swap

 

Synchronization Hardware (1. TAS)

Test and modify (= Test and Set, TAS)

-한번 실행하면 중지 없이 끝을 보장한다. (atomically)

return은 target의 원래값을 해주고 target의 값을 true로 바꿈

Mutual Exclusion with Test-and-Set

초기 lock은 false 값을 가지며 TAS에 의해 false를 return 하고 lock 은 true 값을 갖게 된다.

이 경우 lock 값이 true 이므로 새로운 process가 들어오려고 해도 while 문을 돌게 된다.

critical section이 끝나고 lock이 false 값을 가지면 새로운 프로세스가 들어올 수 있는 상태가 된다.

 

=>Peterson's Algorithm에 비해 매우 간단하다.

TAS 라는 atomic hardware가 존재하기 때문이다. (atomic 한 성질때문에 가능)

Synchronization Hardware (2.Swap)

shared data : boolean lock; (초기값 false 설정)

-swap(lock, key)를 사용하여 lock이 false 인 경우에만 critical section으로 들어갈 수 있다.

이미 실행중인 경우 lock 값이 true 가 되어 swap(true,true) 가 되며 key값이 그대로 true값을 가져 while문을 실행하게 된다.

=>결론 : atomic 한 hardware가 있다면 synchronization 문제를 해결할 수 있다.

 

Semaphores

Hardware를 사용하지 않고 Software적으로 해결할 수 있는 방법은 없을까? -> Semaphores

Semaphores : primitive한 것만 호출함으로써 동기화 문제를 해결해주는 도구

 

integer variable Semaphore S 사용

반드시 두 개의 atomic operation으로만 access 가능

1. P( ) : wait function

2. V( ) : signal function

 

S는 초기값 0을 사용하여 0보다 작은 경우 실행하지 않고 실행이 끝나 1값을 가지면 critical section 수행

 

Critical Section of n Processes

shared data : semaphore mutex (초기값 1)

 

mutex가 초기값 1을 가지고 critical section에 들어가면 0값을 가진다. 이때, 다른 프로세스가 와도 mutex값이 0이므로 while 문 실행

critical section이 끝나면 mutex는 다시 1값을 가지고 다음 프로세스가 들어가게됨

 

가능한 이유?

P, V 함수가 atomic 함수이기 때문이다. (atomic hardware와 동일하게 동작)

P, V 가  atomic한 함수가 아니라면 어떤 문제가 발생할까?

-> critical section에 두 process가 동시에 진입가능하게 될 것이다. atomic 하지 않다면 동시에 mutex 값을 1로 읽을 수 있음

 

Semaphore Implementation

Single Process인 경우 P 함수 첫부분에 interrupt disable을 설정하고 제일 마지막 부분에 interrupt able을 설정한다.

 

Single Process가 아닌 경우 Semaphore S를 Peterson Algorithm으로 감싸서 보호하여 S에 대한 동시 접근이 불가하도록 한다.

기존의 Peterson's Algorithm 과의 차이점?

->Semaphore를 사용하지 않는다면 critical section을 만날때마다 Peterson's Algorithm 구현이 필요하다.

하지만 Semaphore를 사용하여 P, V에 구현을 해두면 사용할 때마다 구현할 필요가 없다. (P, V 자체가 Peterson's Algorithm에 의해 Synchronization 되고 있다!)

 

P() 를 사용하는 경우 busy waiting 문제가 발생한다. 

critical section이 커지게 되는 경우 waiting 이 길어져 오버헤드가 커진다. 

 

Block / Wakeup Implementation

busy waiting 문제를 줄이기 위해 사용

while문을 돌면서 busy waiting을 하는 대신에 sleep을 시키고 조건이 충족되면 wakeup 해서 실행하도록 하자.

semaphore를 변수가 아닌 구조체로 정의

*L -> 포인터를 사용하여 sleep process들을 linked-list로 저장

block, wakeup 을 사용하여 관리

구조체로 정의한 semaphore

Implementation : block/wakeup version of P() & V()

초기값 1로 설정하여 S.value --를 통해 0이 되고 if문에 걸리지 않아 critical section을 수행하게 된다.

하지만 이후 들어오는 프로세스는 -값을 가져 if문에 걸려 block 된 후 linked-list에 추가된다.

critical section이 끝난 후 value값에 1을 더하고 하나를 list에서 제거 후 wakeup을 실행하여 다음 프로세스가 수행하게 된다.

이때 wakeup을 하는 경우 block 된 위치부터 실행하므로 바로 critical section으로 들어가게 된다.

 

integer semaphore -> value값을 사용하여 기다리는 프로세스의 개수를 파악 할 수 있음

binary semaphore -> 개수는 파악할 수 없고 유/무만 파악 가능

 

=>while loop 가 없어서 busy waiting 문제가 해결된다.

But! 무조건 좋은 것은 아니다. sleep, linked_list 저장, wakeup 모두 overhead를 발생시키기 때문이다

=> critical section이 짧은 경우 그냥 busy waiting을 하는 것이 더 효율적일 수 있다.

 

When the CS problem occurs in Operating System?

: 여러개의 Process 가 동시에 일하는 일이 OS에서도 일어날까? -> 발생한다!

 

3가지 경우

1.  Interrupt handler 와 kernel 사이에서 발생

2. kernel 이 system call 수행중 context switch 가 발생하는 경우

3. Multiprocessor - shared memory에서 kernel data 사용하는 경우

 

CS problem in OS (1) Interrupt handler v.s kernel

kernel process는 하나임에도 내부에서 동기화문제가 발생한다.

kernel code 실행중에 interrupt가 발생하여 interrupt handler code 실행 중 같은 kernel 변수를 사용하는 경우

-> disable/enable intrp 을 사용하여 해결

 

CS problem in OS (2) Preempt a process running in kernel?

: 프로세스간 scheduling 에 의해서 발생하는 문제

shared data가 없음에도 systemcall이 수행되는 동안 interleaved execution이 발생 할 수 있음

If you preempt CPU while in kernel mode

system call 이 발생하여 kernel code 수행 중 CPU Scheduling이 발생하여 다른 프로세스가 실행되고 이 프로세스가 kernel code 를 수행하게 되면 잘못된 결과를 도출한다.

-> System call 발생동안 CPU Scheduling이 발생하지 않도록 해서 문제를 해결하자

*UNIX의 경우 systemcall이 끝날 때까지 기다린다.

 

CS problem in OS (3) Multiprocessor

System 내에 CPU가 여러개인 경우 Interrupt disable,enable로 해결 할 수 없다.

1. Operating System 자체를 하나의 거대한 critical section으로 취급하는 방법 (간단한 방법)

CPU가 kernel 수행중이면 다른 CPU가 kernel 작업을 못하도록 한다.

-> 과도한 blocking으로 성능상의 문제가 발생한다. (CPU 개수를 늘려도 성능이 저하됨)

 

2. kernel 변수 하나하나에 대한 동기화 방법 (복잡한 방법)

-> 복잡하지만 성능면에서 문제가 발생하지 않음

 

=> 적절한 방법을 선택하는 것이 중요