OS 5. Process Synchronization

skh951225·2023년 2월 25일

KOCW 운영체제

목록 보기

5/10

Race Condition

Data 를 공유하는 연산장치가 여럿 있는 경우 Race condition의 가능성이 있다.
1. Multiprocessor system (CPU)
2. Shared memory를 사용하는 프로세서들
3. 커널 내부 데이터를 접근하는 루틴들 간

OS 에서 Race condition

Kernel mode 수행 중 인터럽트 발생 시

Kernel의 중요한 데이터를 접근할때 interrupt를 불가능하게 설정해둠
Process가 system call을 하여 kernel mode로 수행중인데 context switch가 일어나는 경우

Kernel mode에서 수행 중일 때는 CPU를 preempt하지 않고(빼앗기지 않게하고) kernel mode에서 사용자 모드로 돌아갈 때 preempt (빼앗김)
Multiprocessor 에서 shared memory 내의 kernel data

(1) 한번에 하나의 cpu만 커널에 들어갈 수 있게 하는 방법, 커널 전체에 lock을 거는 방법 -> 굉장히 비효율적
(2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법

process synchronization 문제

Shared data 의 concurrent access(동시 접근) 은 데이터의 inconsistency를 발생시킬 수 있다. consistency를 유지하기 위해서는 cooperating process 간의 orderly execution을 정해주는 메커니즘이 필요하다. Race condition을 막기 위해서는 concurrent process 가 synchronize 되어야 한다.

The Critical-Section Problem

Critical section은 공유 데이터를 접근하는 코드를 뜻한다. 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

Critical-section problem 의 해결을 위한 충족조건

Mutual exclusion
프로세스 P 가 critical section 부분을 수행 중이면 다른 모든 프로세스는 critical section에 들어가면 안된다.
Progress
Critical section을 수행중인 프로세스가 없을때 critical section에 들어가고자 하는 프로세스가 있다면 critical section에 들어가게 해줘야한다.
Bounded waiting
프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야한다.(starvation이 일어나면 안된다.)

*가정
1. 모든 프로세스의 수행 속도는 0보다 크다.
2. 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

Critical section problem 의 해결

프로세스들의 수행의 synchronize를 위해 프로세스들 간에 공유하는 synchronization variable 을 두어 critical section의 접을 통제할 수 있다.
Critical section 앞 뒤에 entry section, exit section을 두어 각 프로세스의 critical section 수행 여부를 synchronization variable에 표시하여 해결할 수 있다.

Algorithm 1

초기 상태가 turn=0 라고 가정하면 process 1 은 process 0 가 수행되어 turn 을 1 로 바꿔주지 않으면 평생 수행할 수 없다. 한번에 하나의 process만 critical section을 수행해야한다는 mutual exclusion은 만족하지만 critical section을 수행중인 프로세스가 없는 상황에서 process 1이 접근하지 못하므로 progress는 만족하지 못한다. 극단적으로 생각해 보면 P1은 자주 시행되어야 하고 P0는 한번만 수행된다고 한다면 P0가 수행되기 전까지는 P1의 수행이 안된다는 것은 큰 문제를 일으킬 수 있다.
Algorithm 2

Flag 라는 변수는 process 가 Critical section에 들어가고자 하는 의중을 나타낸 것이다. 만약 특정 프로세스가 수행하던 도중 flag[i]=true;를 수행하고 바로 인터럽트가 걸려 다른 프로세스에게 cpu제어권이 넘어가는 경우 두 프로세스는 영원히 critical section에 접근할 수 없다. 이 경우도 mutual exclusion은 만족하지만 progress를 만족하지 않는다.
Algorithm 3 (Peterson’s Algorithm)

Algorithm 1 과 2 를 합한 것이다. 3개의 충족조건을 모두 만족한다. 하지만 critical section을 다른 프로세스가 접근하고 있다고 의심되는 상황(while 문의 무한 루프를 도는 상황)이 생기면 cpu를 낭비하게 된다. 이를 busy-waiting(=spin lock)이라고한다. 또 다른 한계는 세 개 이상의 프로세스에는 적용될 수 없다는 것이 있다.
하드웨어 적인 접근

결국에는 이렇게 긴 코드를 사용해야하는 것은 고급언어의 수행단위와 cpu의 수행단위보다 커서 읽고 쓰는 것 이 동시에 일어날 수 없기 때문이다. 하드웨어적으로 test & modify 를 atomic 하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결할 수 있다.

Semaphores

Semaphore 는 추상 자료형이며 아래와 같은 특성이 있다.
1. Integer variable
2. 아래의 P,S 연산은 atomic 연산에 의해서만 접근 가능
Semaphore의 종류는 2개이다.
Counting semaphore는 자원의 개수가 여러개 있어서 여분이 있으면 가져다 쓰면 되는 상황, 주로 resource counting에 사용된다.
Binary semadphore는 0 또는 1 값만 가질 수 있는 semaphore로, 주로 mutual exclusion(lock/unlock) 에 사용된다.

Busy-wait 가 일어나는 방식

<semaphore를 구현한 한 가지 예이다. 구현은 OS, programming 언어에 따라 다를 수 있다.>

P 연산 : 자원이 있으면 자원을 가져감
V 연산 : 자원을 반납함

Block & wakeup 방식(=sleep lock)

Queue 를 두어 block 된 프로세스를 저장

Block : 커널은 block을 호출한 프로세스를 suspend 시키고 이 프로세스의 pcb를 semaphore에 대한 wait queue에 넣음
Wakeup(P) : block 된 프로세스 P를 wait queue 에서 꺼내 ready queue 로 옮김

<semaphore를 구현한 한 가지 예이다. 구현은 OS, programming 언어에 따라 다를 수 있다.>

P 연산 : 자원을 가져가려고 시도하고 만약 자원이 없었다면 해당 process를 blocke
V 연산 : 자원을 반납하고 wait queue에 대기중인 프로세스가 있다면 wakeup 시킴

busy-wait vs block&wakeup

싱글 코어에서는 busy-wait 방식이 전혀 이점이 없기 때문에 멀티 코어 환경을 가정할때 일반적으로 block&wake up 이 더 좋다. Critical section 의 길이가 길면 busy-wait 오버헤드가 크기 때문에 block&wake up 방식이 더 적당하고 반대의 경우 block&wake up 방식의 overhead가 더 커질 수 있다.

Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

위와 같은 예에서 P0가 S를 얻고 P1에게 cpu를 내어주게되면 P0는 Q를 얻기 전에는 S를 내어놓지 못하고 P1은 S를 얻기전에는 Q를 내어놓지 못하게 되어 결국 무한히 기다리게 된다. 이 경우 P0와 P1 의 자원을 얻는 순서를 같게 해주면 해결할 수 있다.
Deadlock 또한 일종의 Starvation이라고 볼 수 있고 위 상황을 indefinite blocking이라고 한다.

Classical problems of synchronization

Bounded buffer problem(producer-consumer problem)

Bounded buffer problem 은 말 그대로 임시로 데이터를 저장하는 buffer의 크기가 유한한데 producer, consumer 들이 동시접근을 하게되어 발생하는 문제를 말한다.

Producer 는 buffer에 데이터를 저장하는 역할을 하고 consumer는 데이터를 빼내어 쓰는 역할을 한다. Producer 가 정보를 저장하기 위해서는 empty buffer 가 존재해야한다. Empty buffer 에 정보를 쓰게 되면 full buffer 가 된다. 반대로 consumer가 데이터를 소비하기 위해서는 full buffer를 필요로 하게되고 full buffer의 데이터를 소비하면 empty buffer 가 된다. 즉, producer 입장에서 자원은 empty buffer 이고 산출물은 full buffer, 반면에 consumer 입장에서 자원은 full buffer 이고 산출물은 empty buffer 이다. 이러한 특성으로 인해 producer와 consumer의 동작은 동일한 흐름으로 실행되고 다만 차이가 있다면 자원과 산출물이 반대라는 점이다.

이 문제에서 shared data 는 buffer 자체, buffer 조작 변수(empty/full buffer의 위치) 이다. Synchronization variables 는 프로세스(producer / consumer)가 buffer 전체에 대한 접근을 mutual exclusive 하게 하기위해 binary semaphore를 쓰고 full/empty buffer의 수를 표시하기위해 counting semaphore를 쓴다.

초기에 buffer가 모두 비어 있고 데이터를 저장할 수 있는 단위가 n개 라고 하면 full = 0, empty = n 으로 둘 수 있다. 그리고 buffer에 대한 접근은 mutual exclusive 해야하므로 mutex = 1 이라고 하자. 위 그림은 3개의 semaphore 를 활용하여 producer, consumer의 synchronization 을 구현한 pseudo code의 예시이다.
++(개인적인 생각) mutex 를 관리하는 함수가 full, empty 를 관리하는 함수에 의해 둘러 싸이게 되는데 둘의 순서가 바뀌면, 즉 mutex가 둘러싸는 형태가 되면 문제가 발생할 수도 있다. 만약 여유 자원이 없는 프로세스가 buffer의 lock을 얻게되면 해당 자원을 다른 프로세스가 내어놓기 전까지 실행될 수 없다. 하지만 다른 프로세스가 자원을 내어놓기 위해선 buffer의 lock을 얻어야 하므로 Deadlock 현상이 발생한다.

Readers and writers problem

Readers-Writers problem 은 주로 DB에서 발생하는 문제이다. DB 를 읽거나 쓰는 프로세스는 동시 접근이 제한되어야 하나 여러 프로세스가 read를 동시에 하는 것은 허용된다.

위의 그림은 pseudo code의 예시를 나타낸 것이다. 이 문제에서 shared data는 DB 자체, 현재 DB를 읽고 있는 프로세스의 수를 count 하는 readcount 이다. Synchronization variables 로는 semaphore 변수 mutex, db 를 두는데, db는 db에 대한 접근 권한에 대한 것이고 mutex는 readcount에 대한 접근 권한에 대한것이다. 둘다 binary semaphore로 쓰면 적절하다. Writer 에서의 synchronization 문제는 일반적인 mutex방식을 통해 해결하였다. Reader 프로세스가 조금 다른데 아이디어는 간단하다. Readcount 가 1일때, 즉 읽으려고하는 프로세스가 한 개일때만 db에 대한 lock을 요구한다. 이때 writer가 이미 db를 사용하고 있다면 reader는 mutex를 내놓지 않게되고 readcount에 대한 다른 프로세스의 접근을 막는다. 반면에 db를 아무 프로세스도 사용하지 않고 있다면 db에 대한 lock 을 얻게된다. db에 대한 lock 을 내놓기 전에 다른 reader 프로세스가 db에 접근하려고 할때는 lock을 요구하지 않게되고 lock의 반납은 마지막 reader가 책임지고 하게된다. 즉, 다수의 reader가 db에 접속하는 경우 최초로 접근하는 reader만 db에 대한 lock을 요구하게되고 반납은 마지막 reader가 db에서 빠져나올때 수행된다.
++ 다수의 reader가 db를 점거하게 되면 writer가 db의 접근 권한을 얻지 못하는 starvation 문제가 일어날 수 있다.

Dining-Philosophers problem

Dining-Philosophers problem은 5명의 철학자가 원탁에 앉아 식사와 생각을 반복하는 상황에서 시작한다. 식사에 필요한 젓가락을 인접한 2명의 철학자와 각각 한개의 젓가락을 공유하며 철학자는 양쪽의 젓가락을 모두 소유해야 식사를 할 수 있다.

위의 그림은 pseudo code의 예시를 나타낸 것이다. 5명의 철학자가 왼쪽에 있는 젓가락을 하나씩 쥐거나 오른쪽에 있는 젓가락 하나씩 쥐게 되면 다른 사람이 젓가락을 놓지 않으면 식사를 마칠 수 없고 식사를 마칠 수 없게되면 결국 젓가락을 내어놓지 못하는 Deadlock 문제가 발생한다.

위 상황의 해결 방안은 여러가지가 있다. 4명의 철학자만이 테이블에 앉게 하거나, 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 잡을 수 있게 하거나, 한 철학자를 시작으로 시계방향을 돌면서 젓가락의 우선순위를 번갈아가면서(왼쪽,오른쪽,왼쪽,오른쪽….) 주는 방법도 있다. 아래의 그림은 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 잡을 수 있게 하여 Deadlock을 해결한 pseudo code이다.

보통 일반적으로 semaphore의 p연산은 자원을 얻는 것 v연산은 자원을 내어 놓는 것인데, 여기서는 실행의 순서를 조절하는 것에 사용되었다. test 함수는 해당 철학자가 식사를 할 의향이 있고 두 개의 젓가락을 쥘 수 있다면 두 개의 젓가락을 쥐게 하는 함수이다. Pickup 함수는 철학자가 식사 의향을 밝히고 test를 거쳐 식사준비 완료여부에 따라 식사 권한을 부여하는 함수이다. Putdown 함수는 철학자가 식사를 마치고 인접한 두 철학자에 대해 test를 진행하는 함수이다.

semaphore의 문제점 -> monitor의 등장

코딩하기 힘들다.
정확성을 입증하기 어렵다.
자발적 협력이 필요하다.
한번의 실수가 모든 시스템에 치명적인 영향을 줄 수 있다.

Monitor : 프로그래밍 언어 차원에서 synchronization 문제를 해결하는 high level synchronization construct이다. 객체지향 언어가 개체를 중심으로 operation이 정의되는 것 처럼 monitor 라는 것은 shared data에 접근하기위해선 monitor 내부의 procedure를 통해서만 접근 할 수 있게 만들어 놓은것이다. 또한 monitor 내의 procedure는 동시에 여러개 실행 될 수 없어서 여러 process의 동시 접근을 허용하지 않기 때문에 semaphore와 달리 lock을 걸 필요가 없다.(자동으로 해주니까)

Condition variable : semaphore에서 block 된 프로세스를 관리하는 queue 처럼 moniter는 condition variable 이 존재하며 이 condition variable은 wait, signal 연산을 통해서 접근이 가능하다. Condition variable x 에 대해 x.wait() 는 기능면에서 block 과 동일하며 x.signal() 은 wake up 과 유사하지만 대기중인 프로세스가 없을때도 사용가능하며 그 땐 아무일도 일어나지 않는다.(x.signal() 은 기능면에서 semaphore의 V 연산과 유사하다.)