이번 시간에는 프로세스 동기화에 대해 공부해 보겠습니다. 다중 프로그래밍 환경에서는 여러개의 프로세스가 cpu를 차지하기 위해 경쟁하며 각 프로세스는 경우에 따라 다른 프로세스와 데이터를 공유할 수 있습니다. 이렇게 여러 프로세스가 하나의 데이터를 같이 사용하는 경우 해당 데이터에 대한 동기화 처리가 필요합니다. 그래야만 각 프로세스가 사용하는 공유 데이터에 대한 무결성이 보장되기 때문이죠.
데이터의 접근
컴퓨터 시스템에서 데이터에 접근하는 패턴은 위와 같습니다. 먼저 데이터가 저장되어 있는 곳에서 데이터를 읽어와 cpu에서 연산을 한 후 다시 데이터를 가져온 곳에 저장합니다.
보통 데이터를 읽기만 하는 경우는 문제가 되지 않습니다. 여러 프로세스가 단지 읽기만 하기 때문에 데이터가 변경되는 경우가 없죠. 하지만 대부분의 경우 데이터를 조작하기 때문에 문제가 발생합니다. A프로세스가 데이터를 조작하는데, 도중에 B 프로세스가 같은 데이터를 조작하게 되면 데이터의 일관성이 깨지기 때문이죠. 이러한 이유 때문에 데이터를 조작하는 프로세스간의 동기화를 맞춰주어여 합니다.
Race Condition
Race Condition이란 두 개 이상의 프로세스가 공통 자원을 병행적으로 읽거나 쓸 때 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어 졌는지에 따라 그 실행 결과가 달라지는 상황을 의미합니다. 쉽게 말하면 하나의 자원을 두고 여러 프로세스들이 경쟁하는 상태를 말합니다.
보통 프로세스는 자신의 주소공간에 접근하는 경우는 문제가 되지 않지만 system call로 운영체제가 kernel 코드에 접근하는 경우는 문제가 발생할 수 있습니다. 하지만 멀티 프로세서 환경의 경우 프로세스의 메모리 공간을 공유하기 때문에 문제가 발생할 수 있습니다.
Race Condition이 발생하게 되면 모든 프로세스에 원하는 결과가 발생하는 것을 보장할 수 없으므로 이러한 상황은 반드시 피해야 합니다.
os에서 race condition은 언제 발생하는가 ?
1. kernel 수행 중 인터럽트 발생 시
운영체제가 kernel mode에서 kernel 내부의 count+1 연산을 수행 중 cpu로 count값은 load한 상태에서 인터럽트가 걸리게 됩니다. 그리고 인터럽트 핸들러는 kernel의 count 값은 -1하고 원래 위치로 돌아오는데, 이때 count값은 인터럽트 핸들러 전의 count값이 저장되기 때문에 실제로는 count+1한 값만 반영되게 됩니다.
> kernel mode에서 작업을 하는 경우 도중에 인터럽트가 걸려도 무시하고 작업이 끝나면 인터럽터를 처리합니다.
2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
A프로세스가 system call을 호출하여 kernel의 count+1연산을 수행하는 도중 cpu시간이 끝나 B프로세스에게 cpu를 이양합니다. B프로세스 역시 system call을 호출하여 kernel의 count+1연산을 수행하고 A프로세스에게 cpu를 이양합니다. 이때 A프로세스의 context에서의 count는 B프로세스가 count+1한 결과가 반영되지 않기 때문에 실제적으로 count+2가 되어야 하지만 count+1한 결과만 반영되기 됩니다.
> 어떤 프로세스가 kernel mode에 있는 경우 cpu시간이 끝나도 cpu를 빼앗지 않고 작업이 끝나 user mode인 경우에 cpu를 빼앗습니다.
3. Multiprocessor에서 shared memory 내의 kernel data
1,2의 경우 cpu가 하나이지만 multiprocessor 환경의 경우 cpu가 여러개 이기 때문에 인터럽트를 막는다고 해결되지 않습니다. 이런 경우는 공유 데이터에 대해 lock/unlock을 해주어야 합니다.
> 데이터에 대한 접근을 제한하는 것이죠. 또한 이런 문제는 kernel 영역에 대한 접근때문에 발생하기 때문에 매 순간 하나의 cpu만 kernel에 접근하도록 해주는 방법도 있습니다.
Critical Section
Critical Section은 임계영역이라고 하며 n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드가 존재하는데 이를 Critical Section이라고 합니다.
하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 합니다.
Critical Section문제를 해결하기 위한 충족 조건
1. Mutual Exclusion
상호배제, 프로세스A가 임계영역에 들어가 있으면 다른 모든 프로세스들은 임계영역에 들어가면 안됩니다.
2. Progress
진행, 아무도 임계영역에 있지 않은 상태에서 임계영역에 들어가고자 하는 프로세스가 있으면 임계영역에 들어가게 해주어여 합니다.
3. Bounded Waiting
유한 대기, 프로세스가 임계영역에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 임계영역에 들어가는 횟수에 한계가 있어야 합니다(기아 방지)
Critical Section문제를 해결하기 위한 알고리즘
먼저 이러한 알고리즘이 필요한 이유는 임계영역의 코드가 기계어로 바뀌면 한줄씩 실행되기 때문입니다. 그렇기 때문에 한 줄, 한 줄 실행다가 그 사이에 인터럽트가 발생하게 되면 다른 프로세스로 cpu가 이양 되기 때문에 문제가 생기는 것입니다. 만약 이러한 명령어를 단 1줄로 표현할 수 있다면 아주 간단하게 critical section문제를 해결할 수 있습니다.
1. Algorithm 1
turn 변수는 자신의 차례인지를 나타내기 위한 변수로 turn 0은 P0의 차례, turn 1은 P1의 차례가 됩니다. 처음 turn이 0으로 초기화 되어있다면 먼저 P0이 임계영역에 들어가 일을 수행하고 나오면서 turn을 1로 세팅합니다. 그러면 다음에 P1이 임계영역에 들어가 일을 수행하고다 다시 turn 0으로 만들고....이런 과정을 반복합니다.
> 하지만 위의 코드는 상호배제 조건을 만족하지만 진행조건을 만족하지 않습니다. 아무도 임계영역에 들어가 있는 프로세스가 없지만 임계영역에 들어가지 못하게 됩니다. 코드를 자세히 보면 프로세스가 무조건 교대로 동작하게 되어 있습니다. P0이 임계영역에 들어갈 필요가 없어 들어가지 않으면 P1은 절대 임계영역에 들어가지 못하게 됩니다. turn을 바꾸지 않기 때문입니다.
2. Algorithm 2
여기에서는 flag[]를 사용하는데, 여기에 자신이 임계영역에 들어가고 싶다라고 표시를 합니다. 그리고 while문에서 다른 프로세스가 임계영역에 들어가 있는지 검사하고 만약 들어가 있다면 계속 대기하며 그렇지 않은 경우 임계영역에 들어가게 됩니다. 작업을 마치면 임계영역을 나오면서 자신의 flag값을 false로 만들어놓습니다.
> 하지만 만약 flag[i]=true를 하고 바로 cpu를 다른 프로세스에게 뺏기면 해당 프로세스도 flag에 체크를 하는데, 이렇게 되면 두 프로세스 모두 flag에 체크만 하고 실제로 임계영역에 들어간 프로세스는 없게 됩니다. 들어간 프로세스가 없다 보니 자신의 flag를 false로 못하기 때문에 영원히 서로 양보하는 상황이 발생하게 됩니다.
3. Algorithm 3(Peterson's Algorithm)
피터슨 알고리즘은 turn과 flag를 모두 사용한 방법입니다.
프로세스가 임계영역에 들어가기 전에 flag에 자신이 임계영역에 들어가고 싶다고 체크를 합니다. 그리고 turn을 상대방으로 바꾸고 상대방이 현재 임계영역에 들어가고 싶어하고 상대방 턴인지 검사를 합니다. 그렇지 않은 경우 내가 임계영역에 들어가고 나올때 나의 flag를 false로 만듭니다.
> 하지만 이 알고리즘도 문제가 있는데 자신의 턴이 아니여서 임계영역에 들어갈 수 없지만 cpu를 할당받은 동안 계속 while문 조건을 검색하면서 cpu를 낭비하게 됩니다. 이를 busy waiting(=spin lock)이라고 합니다.
Synchronization Hardware
대부분 데이터를 읽고/쓰는 명령어를 나누어져 있기 때문에 여러 문제가 발생합니다. 명령어 사이에 다른 인터럽트가 들어와 도중에 공유 데이터를 조작할 수도 있으며 이로 인해 각 프로세스 context의 데이터값이 달라져 원하는 결과를 얻을 수 없습니다.
이런 문제는 하드웨어 적으로 해결할 수 있으며 Test_and_set()은 읽고/쓰는 작업을 동시에 수행할 수 있습니다.
Test_and_set(a)는 a라는 값을 읽고 a값을 1로 세팅하는 과정을 한번의 명령어로 처리합니다.
만약 a=0이고 Test_and_set(a)을 하면 한번에 a=1로 바뀌며 a=1이라면 그대로 a=1이 됩니다. 다음 사진을 보면 이해하는데 도움이 될 것입니다.
프로세스가 임계영역에 들어가기 전에 Test_and_set(lock)을 검사하는데 lock=false여서 임계영역에 들어갑니다. 들어갈 때 lock은 Test_and_Set에 의해 true가 됩니다. 때문에 다른 프로세스는 while()에서 대기하게 됩니다. 임계영역을 나올 때 lock=false가 되어 다른 프로세스가 임계영역에 들어오게 됩니다.
Semaphore
semaphore는 추상 자료형 입니다. 여기서 추상 자료형이란 "기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열한 것을 추상 자료형" 이라고 합니다. 전자레인지 시작버튼을 누르면 전자레인지에서 sw/hw 적으로 어떻게 동작하는지는 모르지만 어쩃든 전자레인지가 동작하게 됩니다. 이렇게 추상 자료형은 내부적으로 어떻게 구현되었기 보다는 기능과 사용방법을 정의한 것입니다.
이런 관점에서 semaphore를 이해해 봅시다.
semaphore는 여러 프로세스가 하나의 공유자원에 접근하는 것을 제어하는 역할을 합니다. semaphore는 정수값을 가지며 이 정수값에 P(S)와 V(S), 2가지 연산을 할 수 있습니다.
1. P(S) : semaphore를 획득(=공유자원에 대한 접근권한을 얻음)
P(S)연산은 공유자원에 대한 접근권한을 얻는 연산으로, semaphore값이 5라면 P(S)연산을 하면 semaphore값은 4가 됩니다. 이는 공유자원에 대한 접근권한을 얻었을음 의미합니다. 만약 P(S) 연산을 하기 전에 semaphore <= 0인 경우라면 획득할 수 있는 semaphore가 없기 때문에 다른 프로세스가 semaphore를 반납하기 전까지 기다립니다. 이때 기다리면서 while()에서 대기를 하면서 cpu를 잡아 먹습니다(busy waiting = spin lock)
2. V(S) : semaphore를 반납(공유자원을 사용하고 접근권한을 반납)
V(S)연산은 공유자원에 대해 접근하여 연산을 하다 다 사용하고 접근권한을 반납하는 연산입니다. 이때 권한을 반납하면서 V(S)
연산을 수행하면서 semaphore값은 하나 증가 시킵니다.
semaphore는 2가지의 타입이 있습니다.
1. counting semaphore
도메인이 0 이상인 임의의 정수값으로 주로 자원에 접근할 수 있는 프로세스의 수를 제어(resource counting)하는데 사용합니다.
2. binary semaphore(=mutex)
0또는 1 값만 가질 수 있는 semaphore로 주로 mutual exclusion(lock / unlcok)에 사용합니다.
semaphore를 Block / WakeUp으로 구현
semaphore의 P(S)연산의 경우, 만약 공유자원에 대한 접근을 얻지 못하면 해당 프로세스는 while()에서 semaphore를 얻을 때까지 계속 유한대기를 하기 때문에 cpu를 낭비하게 됩니다. 해당 프로세스가 cpu를 받아도 그냥 while()에서 대기할 뿐이죠. 이런 현상을 busy waiting(spin lock)이라고 합니다.
이런 방법말고 해당 프로세스를 blocked시키고 다른 프로세스가 semaphore를 내놓을 때 그때다시 깨워주는 방법(cpu ready queue에 삽입)이 더 효율적입니다.
block/wakeup방식으로 semaphore를 구현할 때 P()연산과 V()연산은 다음과 같습니다.
1. P(S)
P(S)연산의 경우 semaphore를 하나 가져가기 때문에 S.value를 하나 빼줍니다. 만약 음수인 경우 해당 프로세스를 semaphore를 기다리는 wait queue에 넣고 block()시킵니다. 이렇게 되면 해당 프로세스가 cpu를 받을 일이 없게 되어 busy waiting이 해결됩니다.
2. V(S)
자원을 반납할 때는 S.value를 하나 증가 시킵니다. 근데 만약 하나 증가시켰는데도 그 값이 0 이하라는 것은 내가 semaphore를 내놓기를 기다리고 있는 프로세스가 있다는 의미입니다(block되어 있음). 그렇기 때문에 wait queue에 잠들어 있는 프로세스를 깨워줍니다.
Busy - wait vs Block/wakeup
Busy - waiting 는 semaphore를 기다리는 프로세스가 cpu를 받았을 때 cpu를 사용하는 시간 동안 계속 대기(while(1))하는 경우입니다.
Block/wakeup는 sempahore를 기다린느 프로세스를 cpu를 받지 못하게 아예 block시키는 방법입니다. 나중에 다른 프로세스가 semaphore를 내놓으면 block되어 있는 프로세스를 깨우는 방법이죠. 하지만 이 방법은 프로세스를 block/wakeup하는데 오버헤드가 발생합니다.
보통은 block/wakeup을 사용하는 경우가 효율적입니다. 굳이 cpu를 줘도 못쓰는 프로세스에게 cpu를 줄 필요는 없죠. 하지만 오버헤드가 존재하기 때문에 임계영역의 매우 짧은 경우는 busy - waiting해도 무방하지만 임계영역의 긴 경우는 아예 block해버리는 경우가 더 낫습니다.
동기화와 관련된 고전적인 문제
1. Producer - Consumer Problem(Bounded - Buffer Problem)
위의 사진의 buffer의 hole에 데이터를 채우는 것은 생산자(producer)이고 데이터를 가져가는 것은 소비자(consumer) 입니다. 여기서 생산자와 소비자는 여러명 이 있으며 이들 사이에는 동기화가 필요합니다. 예를 들어 생상자가 3번째 hole에 데이터를 넣었는데 또 다른 생산자가 다시 데이터를 넣으면 안됩니다. 또한 buffer가 다 채워져 있는 상태에서는 소비자가 데이터를 가져가기 전 까지는 생산자는 데이터를 넣을 수 없습니다.
> 둘 이상이 소비자/생산자가 데이터에 동시에 접근하는 것을 방지하기 위해 데이터 접근에 대한 lock/unlcok이 필요함
> 버퍼가 가득 차거나/비었을 때 소비자/생산자가 확인할 수 있도록 가용 자원을 확인할 수 있도록 counting semaphore가 필요함
full : 버퍼에 내용이 들어있는 공간의 개수
empty : 버퍼에 비어있는 공간의 개수
mutex : lock을 걸기 위한 변수
- Producer : buffer에 데이터를 넣음
먼저 P(empty)로 버퍼가 비어있는지 검사합니다. 만약 비어있지 않다면 Consumer가 소비할 때까지 기다릴 것입니다. 비어있다면 빈 버퍼를 획득하고 버퍼에 lock을 걸고(P(mutex)) 데이터를 넣습니다. 그리고 unlcok(V(mutext))을 한 후 full의 개수를 증가 시킵니다(V(full)).
- Consumer : buffer의 데이터를 가져감
먼저 내용이 들어있는 버퍼가 있다면(P(full)) 버퍼에 lock을 겁니다(P(mutex)). 이후 버퍼의 데이터를 하나 가져간 후 unlcok(V(mutex))합니다. 그리고 비어있는 버퍼의 개수를 하나 증가 시킵니다(V(empty))
2. Readers and Writers Problem
여기서는 readr/write하는 작업의 대상을 db라 생각하고 설명을 하겠습니다.
만약 한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안됩니다. 하지만 단순히 DB의 내용을 읽기만 한다면 여러 프로세스가 접근해도 되겠죠.
여기서 중요한 점(해결해야 할 부분) write는 DB를 read하는 프로세스가 하나도 없을 때 할 수 있으며, read는 여러 프로세스가 할 수 있으며 write할 때는 read할 수 없습니다.
DB : 접근하려는 공유 데이터
db : DB에 대한 semaphore 변수
readcount : DB의 데이터를 read하는 프로세스의 수
mutex : readcount에 대해 lock을 걸기위한 변수
P(mutext), V(mutex) : reactcount 접근에 대한 lock/unlock 연산
P(db), V(db) : DB 접근에 대한 lock/unlcok 연산
- Writer : DB에 데이터를 write
DB의 접근에 대한 lock을 겁니다(P(db)). 만약 누군가가 DB에 접근해 있다면 대기하겠죠. DB에 lock이 안걸려 있으면 DB에 lock을 write작업을 하고 다시 unlcok(V(db))합니다. 하지만 만약 read하는 프로세스가 계속 접근하게 되어 DB가 unlock되지 않으면 기아 현상이 발생할 수 있습니다.
- Reader : DB의 데이터를 read
writer의 경우와 마찬가지로 lock/unlcok해도 되지만 이러면 비효율적입니다. DB의 내용을 단지 읽기만 하기 때문에 여러 프로세스가 접근해도 문제가 생기지 않습니다. 때문에 내가 read인 경우라면 lock을 걸긴 하지만 write하는 프로세스가 아닌 read하는 프로세스는 접근하게 해주어여 하죠.
먼저 read하기 위해 DB에 접근하면 readcount+1 해줍니다(어쨋든 readcount도 공유변수기 때문에 readcount를 조작할 때 P(mutex), V(mutex)를 해줍니다). 근데 만약 readcount==1인 경우 즉, DB의 내용을 읽는 프로세스가 하나라면 DB에 lock(P(db))을 해줍니다. 다른 프로세스가 write하면 안되기 때문이죠. 이렇게 DB를 read하는 여러 프로세스가 내용을 읽을 수 있습니다. 하지만 만약 read 프로세스가 내용을 읽고 빠져나간 후 readcount==0인 경우, 즉 더이상 read 프로세스가 없다면 DB를 unlock(V(db))합니다. 그래야 DB에 write할 수 있기 때문이죠.
이렇게 readcount변수로 read하는 프로세스를 DB에 여러개가 접근할 수 있게 합니다.
3. Dining - Philosophers Problem
철학자들의 만찬 문제는 각 자리가 있고 자리왼쪽/오른쪽에 포크가 하나씩 있습니다. 식사를 하기 위해서는 왼쪽/오른쪽 포크를 모두 사용하여 식사를 해야 하며 철학자들이 할 수 있는 일은 식사를 하거나 생각을 하거나 둘 중 하나 입니다. 여기서 3번째 철학자가 식사를 하면 2,3번째 철학자는 식사를 하지 못하게 됩니다. 이떄 어떻게 하면 철학자들이 공평하게 식사를 할 수 있을지에 대한 문제 입니다.
먼저 위의 방법으로 문제를 풀 수 있을 것 같습니다. i 번째 철학자는 i번째와 i+1번째 포크를 집고 식사를 하고 다 먹은 후 반납하고 생각을 합니다. 이때 포크를 잡고/반납 할 때 lock/unlcok을 하는 거죠. 하지만 위의 방법은 만약 i번째 철학자가 모두 i번째 포크를 잡는다면 모두 한쪽포크만 가지고 있기 때문에 그 누구도 식사를 하지 못하게 됩니다. 이런 문제를 Deadlock이라고 합니다.
이를 해결 하기 위한 방법으로는 3가지가 있습니다.
> 4명의 철학자만이 이 테이블에 동시에 앉을 수 있도록 한다.
> 젓가락을 두 개 모두 잡을 수 있을 때에만 젓가락을 잡을 수 있게 한다
> 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락 부터 집도록 한다.
※ 이후에 monitor라는 방법으로 철학자의 만찬 문제를 좀 더 깔끔하게 해결할 수 있습니다.
Monitor
앞서 semaphore에 대해 공부하고 임계영역을 semaphore으로 해결하는 방법에 대해 배웠습니다. 하지만 semaphore를 정확하게 사용하면 문제가 되지 않지만 프로그래머의 실수로 시스템에 치명적인 영향을 끼칠 수 있습니다. 예를 들어 P(S), V(S)를 잘못 사용하는 경우 상호배제가 깨지거나 Deadlock문제가 발생할 수 있으면 이런 경우 정확성에 대한 입증이 어렵습니다.
이런 문제를 해결하기 위해 나온 것이 monitor 입니다.
monitor는 프로세스가 공유데이터에 접근하기 위해서는 monitor 내부의 어떠한 절차를 통해서만 공유 데이터에 접근할 수 있게 합니다. 위의 사진에서 프로세스가 shared data에 접근하기 위해서는 n개의 operations를 통해서만 접근할 수 있습니다.
또한 모니터의 경우 기본적으로 여러 프로세스가 모니터에 대한 동시접근을 제한합니다. 그렇기 때문에 한 순간에 하나의 프로세스만 모니터에 접근하여 공유데이터를 사용할 수 있습니다. 다른 프로세스가 접근하면 queue에서 기다리게 됩니다. 이런 이유때문에 semaphore처럼 lock/unlock을 해 줄 필요가 없습니다 모니터가 알아서 제어해주기 때문이죠.
만약 A프로세스가 모니터에 있는 도중에 cpu시간이 끝나게 되어 B프로세스가 모니터에 접근하려는 경우 A프로세스가 이미 monitor에 활성화된 상태로 존재하기 때문에 B프로세스는 monitor에 들어가지 못하고 queue에 가서 줄을 서게 됩니다.
monitor에서는 condition variable를 사용하는데 위의 사진에서 full,emtpry가 있습니다. 이것의 역할을 만약 프로세스가 monitor에서 어떤 일을 하는데 조건이 충족되지 않아서 잠시 잠들게 해야하는데 어떤 조건이 충족되지 않았느냐에 따라 그 조건에 해당하는 것을 변수로 설정할 수 있습니다.
또한 condition variable에는 2가지 연산을 할 수 있습니다.
1. wait() : 어떤 프로세스를 잠들게 해야 하는 경우 해당 condition variable에 들어가서 줄서게 됩니다.
2. signal() : 누군가가 condition variable를 사용하고 나가면 condition variable를 기다리는 프로세스를 깨웁니다.
Producer - Consumer Problem(Bounded - Buffer Problem)문제를 monitor로 해결하는 경우를 보겠습니다.
full : 내용이 들어있는 버퍼를 기다리는 프로세스를 줄세움
empty : 빈 버퍼를 기다리는 프로세스를 줄세움
- produce
만약 버퍼가 모두 차서 데이터를 넣을 빈 버퍼가 없다면 빈 버퍼를 기다리는 줄에가서 잠들게 합니다(empty.wait())
그렇지 않고 빈버퍼가 있다면 버퍼에 데이터를 넣고 내용이 들어있는 버퍼를 기다리면서 잠들어 있는 프로세스를 깨웁니다(full.signal())
- consume
만약 내용이 들어있는 버퍼가 없다면 내용이 들어 있는 버퍼를 기다리는 줄에 가서 잠들게 합니다(full.wait())
그렇지 않고 내용이 들어있는 버퍼가 있다면 버퍼로부터 아이템을 가져오고 빈 버퍼를 기다리는 프로세스를 깨웁니다(empty.signal())
'computer science > 운영체제' 카테고리의 다른 글
| [운영체제] 메모리 관리 (1) | 2020.04.27 |
|---|---|
| [운영체제] Deadlock (3) | 2020.04.27 |
| [운영체제] 시스템 구조와 프로그램 실행 (2) | 2020.04.22 |
| [운영체제] 인터럽트 (1) | 2020.02.21 |
| [운영체제] 커널 모드, 사용자 모드 (0) | 2020.02.17 |
