1. Introduction
- 컴퓨터의 자원(i/o device, memory 등)들은 유한하다. 이 유한한 자원을 여러 프로세스, 쓰레드가 순서대로 돌아가면서 사용해야하는데 여러 프로세스 혹은 쓰레드가 한개의 프로세서 혹은 여러 프로세서에 할당되어 작업되기 때문에 필연적으로 여러 프로세스가 동시에 공통된 자원을 요구하는 등의 문제들이 발생할 수 있다.
- 이런 병렬적 수행에서 발생하는 문제들을 살펴보고 어떻게 운영체제가 프로세스와 쓰레드를 관리하는지 살펴보자.
2. Race Condition
- 프로세스 혹은 쓰레드 a,b가 A라는 변수를 읽고 값을 수정한다고 해보자 이런 상황에서 a,b중 누가 먼저 실행되느냐에 따라 두 프로세스의 실행 결과가 바뀔 것이다.
- 즉 하나의 자원을 여러 쓰레드가 사용하기 위해 경쟁하고 프로세스들이 실행된 후 결과를 확정적으로 알 수 없다(non-deterministic)는 것이다.
- 이런 상황을 race condition이라고 한다.
3. Mutual Exclusion
*critial section
- 공유된 자원을 나 혼자만 사용해야만 하는 코드영역을 말한다.
- A가 종이에 그림을 그리고 있었는데 중간에 B가 수학문제를 푸는데 연습장이 필요하다며 갑자기 종이를 뺏어갔다고 생각해보자. B가 수식을 잔뜩 쓰고 종이를 돌려주었다면 A는 엉엉 울 것이다. 여기서 "그림을 그리는 중"이 critical section이 될 것이다.
- 좀 더 그럴 듯한 사례로 설명을 이어서 해보겠다.
- p1이 ra라는 자원을 받아서 critical section에 진입했다고 해보자. 그런데 이때 p2가 ra라는 자원을 요청해서 들어가고자 한다면? p1이 사용중이니까 진입을 막도록 해주어야 할 것이다.
- 이렇게 한정된 자원에 대해서 프로세스들이 one by one으로 한명씩 들어가 있음을 보장해주는 것을 mutual exclution이라고 한다.
4. Mutual Exclusion - Compare&Swap Instruction
- 하드웨어가 상호배제를 지원하는 방법이다.
- parbegin(p(1), .., p(n));은 n개의 프로세스가 동시에 돌아가도록 하는 함수이다.
- 처음 자원을 사용하는 프로세스가 없으면 bolt는 0일 것이다.
- a라는 프로세스가 자원을 점유하려고 한다. 이때 compare_and_swap에서 bolt가 0임을 확인하고 1로 바꾼다.
- a프로세스가 자원을 점유하여 critical section에 들어간다.
- 이 상태에서 b라는 프로세스가 자원을 점유하려고하면 compare_and_swap에서 bolt가 1임을 확인하고 작업을 진행하지 못하게 하여 계속 while루프에 갇혀있게 된다.
- a가 마침 critical section을 빠져나와서 자원사용을 마쳤다면 bolt를 0으로 바꿔서 다른 프로세스가 자원을 할당받을 수 있도록 한다.
- 이렇게 자원의 점유상태를 나타는 변수(bolt)를 도입해서 한명씩 자원을 점유받을 수 있도록 한다.
- 이런 방식은 구현이 간편하다는 장점이 있지만 반대로 여러 문제를 지닌다.
- 일단 자원을 기다리는동안 while문에 계속 갇혀서 프로세서의 시간을 계속 소모하게 될 것이다. 이게 무슨 말이냐면 여러 프로세스가 돌아가면서 cpu를 정해진 시간만큼 할당 받을 것인데 위의 예시에서 b의 경우는 a가 critical section을 탈출할 때까지 제공받은 cpu 시간을 while루프에서 아무것도 안하면서 소모한다는 것이다. 이런 상황을 busy-waiting이라고 한다.
5. Semaphore
- OS가 상호배제를 지원하는 방법이다.
- 자원의 점유 상태를 나타내는 변수 1개와 함수2개로 구성된다.
- 일단 프로세스는 semWait이라는 함수를 호출해서 자원을 받을 수 있는지 확인한다.
- 자원을 받았다면 critical section으로 들어가게 되고
- 다 끝나면 semSignal을 보내서 자원을 사용가능 상태로 바꿔준다.
- 초기 semaphore의 값(count)은 1이다. 이는 한 명만 자원을 점유할 수 있음을 나타낸다.
- queue는 자원을 사용하고 싶어하는 프로세스들이 block된 채로 줄서있는 곳이다.
- semWait은 자원할당 전에 자원 점유 가능 여부를 판단하기 위해 잠시 기다리라는 함수이다.
- 첫번째 프로세스가 semWait을 호출하면 count가 0이 되고 if문을 뛰어 넘고 자원을 할당 받는다.
- 이어서 두번째 프로세스가 semWait을 호출하면 count가 -1이 되어 할당이 불가능한 상태가 되고 blocked 큐로 프로세스를 이동시킨다.
- 즉 count의 절대값은 block된, queue에 있는 프로세스의 수를 나타낸다.
- 이렇게 프로세스가 block되기 때문에 자원을 기다리는 동안 cpu를 할당받지 않음으로써 processor 타임을 소모할 일이 없다. (busy waiting해결)
- semSignal은 자원을 다 썼다는 신호를 보내는 함수이다. count를 하나 증가시키고 count가 0보다 작거나 같으면 queue에서 프로세스를 꺼내온다.
- 즉 semSignal은 자원을 다 썻으니 소유권을 놓아주고 block되어있는 프로세스 하나를 깨우는 역할을 한다.
- 이제 위의 내용을 종합해서 여러 프로세스가 semaphore를 사용해서 자원을 mutual exclusive하게 사용하는 과정을 살펴보자.
- 초기 세마포어값은 1이다. A가 processor로 들어간다. semWait을 통과하여 자원을 할당받고 critical section으로 진입한다(이때 s=0). 그러나 정해진 프로세서 타임을 소모하면 A는 다시 ready queue로 들어간다. 아직 A가 자원을 다 사용하지 않았다. 즉 semSignal이 호출되지 않았다.
- B가 프로세서를 할당 받아서 semWait을 호출하여 자원을 요청한다. 그러나 세마포어 값이 -1이 되기 때문에 blocked queue로 이동한다. 즉 A가 자원을 사용중이므로 다른 프로세서의 자원 점유를 막는 것이다.
- 여기서 D는 이미 자원을 받아서 critical section을 마친 상태라고 가정한다.
- 이어서 D가 프로세서를 할당받고 semSignal을 호출한다. 이때 s값은 0이 되고 blocked queue에 있는 프로세스를 ready queue로 이동시킨다.
- 정리하면 semaphore를 활용해 프로세스간 Mutual Exclusion을 구현하고 busy waiting의 문제를 해결했다.
6. Producer-Consumer Problem
- 컴파일러가 코드를 컴파일해서 생산해 낸 것을 어셈블리 코드라고 한다. 그리고 이 어셈블리 코드를 어셈블러가 받아서 작업을 수행한다.
- 생산자는 소비자로 결과물을 넘겨줄때 buffer를 사용한다. 컴파일러가 생산중일 때는 어셈블러가 소비를 못하도록 버퍼에 대한 소유권을 얻지 못하게 해야한다.
- 이처럼 생산자가 결과를 만들어주면 소비자가 그 결과를 소비할 수 있는 관계로 프로세스간 관계를 설명한 것을 producer-consumer라고 한다. 이때 버퍼를 통해 결과물을 넘겨줄 것인데 생산자와 소비자가 동시에 버퍼를 접근할 수 없도록 버퍼에 대해서 mutual exclusion이 보장 되어야 한다.
- 이제 버퍼에 대한 소유권을 세마포어를 활용하여 어떻게 관리하는지 살펴보자.
- 단! 여기서 버퍼의 크기는 무한하다고 가정한다.
- 생산자는 produce()를 해서 결과물을 만들어낸다.
- 그리고 semWait으로 버퍼를 사용할 수 있는지 소유권을 요청한다.
- semWait을 통과하면 append()해서 버퍼에 내용을 채워 넣는다.
- semSignal(s)는 버퍼를 다 사용했으니 버퍼의 소유권을 놓겠다는 의미이고
- semSignal(n)은 버퍼에 n크기 만큼 데이터를 채웠으니까 block되어있는 소비자 하나를 ready queue로 옮기는 신호를 보내준다.
- 소비자는 먼저 semWait(n)을 통해 버퍼에서 n크기만큼 데이터를 읽어올 것인데 버퍼에 그만큼 내용이 차 있는지 물어본다. 버퍼에 데이터도 없는데 자원의 소유를 요청할 이유가 없기 때문이다.
- 만약 그게 아니라면 semWait(s)를 통해 버퍼를 다 사용했을 수도 있으니 내가 버퍼를 써도 되는지 물어본다.
- 이렇게 semWait을 통과하면 take()를 통해 버퍼 내용을 가져오고
- 버퍼를 다 사용했기 때문에 소유권을 내려 놓는다.
- 소유권을 내려 놓고 버퍼에서 받아온 내용을 소비한다.
- 이번에는 버퍼의 크기가 유한하다고 가정하고 생산자, 소비자 문제를 해결해보자.
- 생산자 입장에서는 semWait(e)를 통해 현재 버퍼에 쓸 공간이 있는지 확인한다. 쓸 공간이 없다면 버퍼의 소유권을 가질 필요가 없기 때문이다. e는 현재 사용할 수 있는 버퍼의 크기를 나타낸다.
- 만약 쓸 공간이 있다면 semWait(s)를 통해 버퍼를 소유할 수 있는지 확인한다.
- 작업을 끝내고 semSignal(s)를 통해 버퍼 자원에 대한 소유권을 내려놓고 semSignal(n)을 통해 n크기만큼 데이터를 채워 넣었으니 소비자를 block상태에서 ready큐로 이동시키라는 신호를 보낸다.
- 소비자는 버퍼에 n만큼 읽어올 수 있는지 semWait(n)을 통해 확인한다. 읽어올 내용도 없는데 버퍼의 소유권을 요청할 필요가 없기 때문이다.
- 이어서 semWait(s)로 버퍼의 소유권을 요청한다.
- 데이터를 다 받았으면 semSignal(s)로 자원의 소유권을 내려놓고 semSignal(e)를 통해 버퍼의 크기가 e만큼 비었으니 block되어있는 생산자를 ready queue로 옮기라는 신호를 보낸다.
7. atomic operation
- atomic operation은 명령어들이 더 이상 쪼개지지 않는 실행 단위를 말한다. instruction set이 반드시 하나의 묶음으로 수행됨을 보장하는 단위이다.
- semWait, semSignal함수를 실행하는 도중 중간에 interrupt가 걸리면 절대 안된다. 따라서 이 함수들은 atomic operation임이 보장되어야 한다. (반드시 한번에 수행되어야 한다.)
- 이런 atomic한 구현을 위한 첫번째 방법은 compare_and_swap을 활용하는 것이다.
- compare하는 동작과 bolt값을 swap하는 두가지 동작이 atomic한 단위로 수행되도록 하드웨어 support를 받는 방식이다.
- 두번째 방법은 semWait, semSignal이 실행될 때 interrupt를 금지시키는 것이다.
- 실행이 완료되면 interrupt를 다시 허용해 줘야한다.
'ComputerScience > Operating System' 카테고리의 다른 글
| OS - 6 Concurrency: Deadlock and Starvation (0) | 2021.07.20 |
|---|---|
| OS - 5.2 Concurrency: Mutual Exclusion and Synchronization (0) | 2021.07.14 |
| OS - 4 Threads (0) | 2021.07.07 |
| OS - 3 Process Description and Control (1) | 2021.07.06 |
| OS - 2 Operating System Overview (0) | 2021.07.06 |
