##본 포스팅은 운영체제 강의 '이화여자대학교 운영체제 강의 - 반효경 교수님'를 보고 정리한 내용입니다.
데이터의 접근
동기화가 필요한지, 이게 뭔지 등에 대해 알아보기 전에 데이터의 접근이 어떻게 이뤄지는지 알아야한다.
데이터를 접근할 때는,
1) 데이터가 저장되어있는 곳(메모리, 하드디스크)에 가서 데이터를 가져오고,
2) 가져온 데이터로 연산을 하는 곳(CPU, 컴퓨터 내부)에서 수행을 하고
3) 바뀐 데이터, 결과를 저장소(메모리, 하드디스크)에 저장을 한다.
하지만, 문제는 데이터를 읽어가는 곳이 여러곳일 때 발생한다.
연산 주체가 여럿이 있으면, 연산이 끝난 뒤에는 데이터가 원하는 대로 조작되지 않을 수 있다.
이렇게 공유 데이터를 여럿이 접근하려고 할 때 발생하는 문제를 'Race Condition'이라고 한다.
CPU가 하나있는 상황에서도 생길까?
생기지 않는다면 이것은 CPU가 여러개 있는 상황에서도 생기지 않다고 생각할 수도 있다.
저러한 변수는 프로세스 내부의 데이터고, 프로세스는 자신의 주소공간에 있는 데이터만 접근 가능하다.
그러므로 CPU가 여러개여도 정해진 주소공간에서만 데이터를 조작하기에 문제가 생기지 않는다.
하지만, 문제가 생기는 예는 다음과 같다.
운영체제가 끼어드는 경우에 문제가 발생한다.
A프로세스는 System call을 통해 운영체제를 불러 자신이 처리 불가한 일들을 맡긴다.
이 작업이 운영체제 내부의 데이터를 변경하는 일이라고 생각해보자.
그러면 이제 B프로세스가 CPU를 가지게 된다.
이 때 B도 운영체제를 call하고, B도 앞서 "변경 중"이던 데이터를 변경해야한다면?
즉, 운영체제 내부의 데이터는 둘 다 접근 가능하다는 것이 포인트이다.
프로세스들끼리는 데이터를 공유하지 않았는데,
운영체제 안에 있는 데이터(kernel 데이터)를 건드리는 과정에서 문제가 생긴 것이다.
OS에서 race condition이 발생하는 경우
- System Call
유저 모드말고,
커널 모드에서 코드가 수행 중일 때 커널에 있는 데이터인 '공유 데이터'를 건드릴 경우
> 해결책 : 커널 모드에서 수행 중일 때는 CPU를 넘겨주지 않고, 커널 모드에서 사용자 모드로 돌아갈 때 넘겨줌
(시간과 상관없이, 커널 모드의 경우에만 -> 불공평할 수는 있지만, 어쩔 수 없다!) - Interrupt
커널모드에서 돌아가다가(커널 코드),
인터럽트 처리(커널모드, 더 긴급한 일이기때문에 뺏아감)를 위해 운영체제 내부의 데이터를 건드리는 경우
> 해결책 : 공유 데이터를 건드리는 동안엔 interrupt를 받지 않음 - Multiprocessor에서 shared memory 내의 kernel data
CPU가 여러개 있는 경우에서도 발생
똑같이 커널 모드에 들어가서 내부 데이터를 만지는 경우
> 해결책 1 : 한번에 하나의 CPU만이 커널에 들어갈 수 있게 -> (굉장한 오버헤드 발생, 비효율적)
> 해결책 2 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다 공유 데이터 각각에 대한 lock/unlock을 하는 방법
접근 전 막고, 접근 후 풀고...하는 방법
지금까지 운영체제의 '데이터 동시 접근'에서 생기는 문제를 해결하는 방법을 알아봤다.
다음엔 공유 데이터의 동시 접근에서 발생하는 inconsistency 문제를 보자!
프로세스 Race Condition과 해결책
공유 데이터를 건드리는 중요한 공간을 Critical section이라고 한다.
이 section에서는 아래와 같이 lock을 걸고(entry section)/풀고(exit section)하는 작업이 필요하다.
0. 알고리즘이 만족해야할 조건들
- Multual Exclusion(상호 배제)
동시에 들어가면 안된다. - Progress(진행)
아무도 들어가있지 않은 상태에서, 누군가 들어가고자 한다면 통과시켜줘야한다. - Bounded Waiting(무한 대기, starvation)
대기시간은 유한해야 한다.
한 프로세스만 들어가고 계에에에속 사용하고 있다면?
A, B, C 모두 들어가고 싶은데 A와 B만 들어간다면?
1. Algorithm 1
위 코드가 P0의 코드,
밑줄 친 turn={i}의 코드에서 0과 1이 바뀐 것을 P1이라고 생각해보자.
turn이라는 Synchronization variable을 두고,
critical section에 들어가기전에, 이번엔 누구 차례인지 알아낸다.
(너 한번, 나 한번)
하지만, 이 방법은 과잉양보이다.
내 차례가 오기 전까지 계속 기다려야하는데, 만약 특정 프로세스가 '더' 빈번히 critical section에 들어가야한다면?
근데 상대방은 아예 들어가지도 않는다면?
즉, 원하지도 않는데 번갈아 들어가야한다는 것이다.
2. Algorithm 2
깃발을 두어 누가 들어가고 싶은지 보는 방법이다.
자신의 깃발(flag[i])을 올리고,
상대방의 깃발(flag[j])를 확인한 뒤에 critical section에 들어간다.
동시에 들어가는 방법은 깃발을 통해 방지한다.
하지만 '진행'에 있어서 문제가 있다.
여러 프로세스가 사용하겠다고 서로 '깃발을 들고 있는 상태'에서 CPU를 뺏긴다면?
3. Algorithm 3 (Peterson's Algorithm)
위 두가지 방법을 합친 방법이다.
모든 조건을 만족하며 해결할 수 있다.
내 깃발을 들고, 상대방 깃발이 들려있는지 && 상대방 차례면 -> 기다림!
하지만 이것도 Busy Waiting(spin lock!)이라는 문제가 있다.
while을 빠져나갈려면 상대방이 turn을 줘야하는데, while때문에 CPU를 줄 수가 없다는 문제가 있다...
Synchronization Hardware
이러한 critical section 접근 문제는 하드웨어적으로 Test & modify(set)을 atomic(쪼개지지 않고 한번에)하게 수행하면 해결할 수 있다.
하드웨어적으로 기능을 제공하지만 하면 문제는 해결된다.
Semaphores
앞의 방식을 추상화한 것을 Semaphore, Monitor 라고 한다.
- Integer variable(자원을 카운팅하는 수)
- 아래 두가지 atomic 연산에 의해서만 접근 가능하다
P 연산은 lock을 거는 과정이며, V 연산을 lock을 해제하는 연산이다.
자원을 다 사용하면, 여분이 없으니 기다리는 것이고,
상대방은 자원을 다 쓰고 나서 다시 반납을 하는 과정을 진행한다.
P와 V 사이에는 실제 critical section으로 실제 공유 자원(S와 다름)을 사용한다.
이러한 방식이 지원되면 race condition 문제를 쉽게 해결할 수 있다.
하지만, 상대방이 V연산을 하기 전에 자신은 P만 진행하기 때문에 busy-wait을 해야한다는 단점이 있다.
이를 해결하기 위해서 Block/Wakeup 방법을 사용하면 된다.
*Block/Wakeup(sleep lock)
Sepaphore를 정의하여, 큐를 사용해 대기 상태로 줄세운다.
즉, 락이 걸렸을 때 sleep을 하여 busy wait을 탈출하는 방법이다.
이제 Semaphore 연산은 아래와 같이 정의된다.
Busy-wait vs Block/wakeup
Block/wakeup overhead vs Critical section 길이
- critical section의 길이가 긴 경우 Block/wakeup이 적당
- critical section의 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
- 일반적으로는 Block/wakeup 방식이 좋음
'System > OS' 카테고리의 다른 글
| 운영체제 10] 가상 메모리 (0) | 2021.11.29 |
|---|---|
| 운영체제 6주차] 병행제어(2) (0) | 2021.10.17 |
| 운영체제 5강] CPU Scheduling (0) | 2021.10.10 |
| 운영체제 4강] (0) | 2021.10.04 |
| 운영체제 3-3~3-4] 스케줄러 (0) | 2021.09.26 |
