[운영체제] Process Synchronization 1

목차

  1. Process Synchronization 문제

  2. Process Synchronization 문제 해결

  3. Deadlock과 Starvation 

 

Process Synchronization 문제

 

공유 데이터에 하나 이상의 주체가 가 동시에 접근하면 데이터의 불일치 문제를 발생시킬 수 있다. 이와 관련된 개념으로 Race condition이라는 것이 있다.

 

Race Condition

Race Condition

Race Condition은 여러  프로세스들이 동시에 공유 데이터에 접근하는 상황을 의미한다. 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.

 

E-box	S-box
CPU	Memory
컴퓨터 내부	디스크
프로세스	프로세스의 주소공간

 

 여러 프로세스의 시스템 콜에서의 문제

OS는 여러 프로세스의 시스템 콜에 의해 접근되므로 Process Synchronization에 관해 아래와 같은 문제가 발생할 수 있다.

 

CPU 한개

 

 

PA가 동작을 하고 시스템 콜을 해 커널에서 count를 하는 도중, 할당 시간이 지나 PB가 OS를 받아 시스템 콜을 해 count ++ 를 하고 다시 되돌려받아 PA가 count ++를 완료하는 경우이다.이러한 경우, count ++ 는 2번이지만, PA에서 는 PB에서의 증가전인 count에 한번 더하는 것이므로, 한번만 더해진 결과가 저장된다. 

이는 커널모드에서 수행중일 때에는 프로세스를 빼앗지 않는 방법을 통해 문제를 해결할 수 있다. 하지만 이는 CPU가 하나일 때에만 해결이 가능하고, CPU가 여러 개인 컴퓨터에서는  이 방법으로 해결할 수 없다.

 

CPU가 여러 개인 경우의 문제

CPU 여러개

 

 

이는 각 공유 데이터에 접근할 때마다 그 데이터에 대해 권한을 가진 특정한 CPU만 접근할 수 있도록 lock, unlock을 거는 방법을 통해 문제를 해결할 수 있다.

 

 Process Synchronization 문제 해결

 

해결법의 충족 요건

1. Mutual Exclusion (상호 배제)

프로세스 Pi가 critical section(공유 자원에 접근하는 코드) 부분을 수행 중이면, 다른 모든 프로세스들은 그 critical section에 들어가면 안된다.

 

2.Process (진행)

아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.

 

3. Bounded waiting (유한 대기)

프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

 

해결 알고리즘 1

해결 알고리즘 1

 

 

 

turn을 통해 자기 차례에만 들어갈 수 있게 코드를 짤 수 있다. 하지만 이는 Process 조건을 만족하지 못한다. 예를 들어, Process 0은 여러번 들어가고 Process 1은 한번만 들어가는 경우, 각 한번씩만 접근할 수 있다. turn을 번갈아 바꿔가는 식의 코드이기 때문이다. 

 

해결 알고리즘 2

해결 알고리즘 2

 

critical section에 들어가기 위해선 flag를 true로 바꾸고 접근하게 되는 코드이다. 접근 후 다른 flag가 true인지를 체크하고 없으면 공유 자원에 접근하게 되는 코드이다. 하지만 둘다 2행까지 수행하고 끊임 없이 양보하는 상황이 발생 가능하다. 두 개가 접근학기 위해 flag가 각각 true일 때 아직 들어가진 않았지만 while문에서 상대방의 flag 가 true이므로 끊임 없이 양보하게 된다.

 

해결 알고리즘 3

해결 알고리즘 3

 

변수를 두 개로 두어, 상대방이 접근하기 위해 flag를 들고, 상대방의 턴일 때에만 대기하도록 되어있다. 이 코드는 위의 3가지 조건을 모두 충족한다. 하지만 Busy Waiting이라는 문제가 있다. (계속 CPU와 memory를 쓰면서 기다리는 것이다.)

 

 

CPU는 하나의 instruction 단위로 수행된다. 고급 언어에서는 각각의 코드 줄이 하나의 instruction이므로, 코드 중간에 CPU를 빼앗길 수 있어, 코드가 이렇게 복잡해지는 것이다. 만약 하드웨어적으로 하나의 instruction 안에 읽기와 수정을 동시에 할 수 있도록 지원하면 이러한 문제를 간단히 해결할 수 있을 것이다.

Synchronization Hardware

 

while 문이 읽히면서 lock = true로 동시에 바꾸는 예시이다. 이를 추상화한 것이 Semaphores이다.

 

Semaphores 

semaphores

 

S 는 공유되는 자원의 중 남은 개수를 의미한다. 만약 P(S)연산 시 남은 자원이 없다면, 기다리고, 하나라도 있다면 S--;를 한뒤 하나를 가져가게 된다. 공유 자원 사용이 끝나면 V(S)연산을 통해 공유자원을 돌려놓게 된다. 하지만 이 방법을 쓰더라도, while문을 계속 돌기 때문에 busy-waiting이 발생해 비효율적이다. 이러한 문제는 semaphores를 block.wakeup로 구현함으로써 해결할 수 있다.

 

Block/Wake Up Semaphores

Semaphore

 

 

 

Block/Wakeup 방식

 

만약 자원이 없다면, 접근하려던 프로세스의 상태를 blocked 상태로 바꿔 대기하게 한다.

 

Deadlock과 Starvation 

Deadlock, Starvation

 

Deadlock

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

위의 예에서, P0는 P(S)와 P(Q)를 모두 가지고 코드를 작동하고 나서야, V(S), V(Q)를 실행해 자원을 반납한다. 하지만 P1은 P(S)를 가지고 놓지 않고, P1은 P(Q)를 가지고 각각 상대방의 것을 요구하는 상황에 놓이게 된다. 이렇게 계속 기다리는 상태를 DeadLock이라고 한다. 프로그래머는 이러한 상황을 유의해 코드를 작성해야 한다.

 

Starvation

특정 프로세스가, 무한히 기다려야 되는 상황을 의미한다.

 

 

 

 

 

 

본 포스팅은 kowc 이화여대 반효경 교수님 운영체제 강의를 바탕으로 작성하였습니다.