21-1학기 운영체제에 대해서 배운 내용들을 상기하고 기록하기 위해 글을 쓰려고 합니다.
5장에서는 Multiprocesses를 사용할 때 중요한 Concurrency에 대해서 자세하게 알아보겠습니다!
Multiple Processes
Multiple Processes라는 용어를 쓰면서 확실히 해두어야 할 개념이 3가지가 있다.
1. Multiprogramming : process를 여러개 번갈아가며 실행
2. Multiprocessing : 여러개의 CPU를 가졌다는 의미
3. Distributed Processing : 여러개의 컴퓨터가 네트워크로 연결되어 있어, 하나의 시스템처럼 작동
이번 chapter에서 다룰 내용은 multiprogramming으로 여러개의 process를 번갈아가며 실행을 할 때 가장 중요한 점은 동시에 실행하더라도 정확하게 하기위해서 Concurrency을 고려해야 한다는 것이다.
Race Condition
process1과 process2가 있고 x=100이라는 파일이 있을 때 아래와 같은 상황을 예를 들어 보겠다.
process1에서 x라는 파일을 읽고 time out->
process2에서 x라는 파일을 읽고 time out->
process1에서 x에 100을 더하고 파일에 쓰고 time out->
process2에서 x에 200을 더하고 파일에 쓰고 time out
이런 상황이 있다면 마지막 output은 4번째 줄에 의해 300이 된다.
하지만 process1보다 process2가 먼저 실행됐다면 마지막 output은 200일 것이다.
이처럼 output이 마지막에 실행한게 어떤 process인지에 따라서 달라지는 것을 race condition이라고 한다.
Competition among Processes for Resources
- Mutual Exclusion이 지켜지지 않아서 : 위의 상황에서 p1이 x값을 더하기 전에 p2가 x값을 읽으면 안된다.
이 때, Critical section이라는 개념이 등장하는데, 프로그램의 일부 중에서 다른 프로그램과 함께 사용하면 안되는 부분을 의미한다.
여기에선 x부분을 의미한다. - Deadlock : 둘 이상의 프로세스가 자원을 점유한 상태에서 다른 프로세스의 자원을 요구하여 무한정 기다리는(blocked) 상태이다.
- Starvation : process의 우선순위가 계속 밀려서 실행을 하지 못하는 상태이다.
이번 chapter에선 Mutual Exclusion에 대해 자세하게 살펴보겠다.
Requierments for Mutual Exclusion
공유자원에 대해 오직 하나의 프로세스만 critical section에 진입할 수 있다.
또한 critical section이 아닌 부분 때문에 critical section에 다른 코드가 들어가지 못하면 안된다.
critical section이 비었는데 들어가지 못해서도 안되고 critical section에 무한정으로 있어서도 안된다.
그리고 deadlock과 starvation이 있어서도 안된다.
Support for Mutual Exclusion
Mutual exclusion을 위해 크게 3가지 방법으로 support한다.
1. hard ware
2. OS
3. Application
1. Hardware
Compare&Swap Instruction
main에서 전역변수 bolt에 0을 대입하고 n개의 process를 만들어 동시에 P라는 함수를 실행을 시킨다.
compare_and_swap이라는 함수를 통해서 bolt의 값과 0을 비교해서 0일 때, bolt값을 1로 바꾸고 원래의 bolt값을 리턴한다.
그러므로 처음 bolt값을 바꾼 process만 0을 리턴하게 되므로 while문을 빠져나와 c.s에 들어갈 수 있다.
그리고 c.s에서 나오면 다시 bolt값을 0으로 만들게 된다.
Compare&Swap Instruction은 Mutual Exclusion의 요건 중 c.s에 1개만 들어가게 하며, 나올 때 다른 process가 들어갈 수 있도록 문을 열어두는 것을 만족한다.
Exchange Instruction
main에서 전역변수 bolt에 0을 대입하고 n개의 process를 만들어 동시에 P라는 함수를 실행을 시킨다.
exchange함수를 통해서 처음 들어온 process는 keyi값이 1이고 bolt값이 0이므로 keyi값이 1이므로 bolt와 값을 바꾸고 do-while문을 빠져나와 c.s를 실행한다.
다른 process는 1과 1을 swap하므로 계속 do-while문 안에 갖혀 있다.
c.s를 지나면 bolt를 다시 0으로 만들어서 다른 process가 진입할 수 있도록 한다.
Hardware Mutual Exclusion의 장점
Exchange Instruction과 Compare&Swap Instruction은 application code가 아니라 hard ware에서 일어나는 일이다.
따라서 process 개수에 상관 없이 사용 가능하고 간단하고 입증하기 쉽다.
또한 multiple critical section을 사용 할 수 있다.
Hardware Mutual Exclusion의 단점
while문에서 반복이 되므로 Busy-waiting이 발생하므로 CPU를 많이 차지한다.
starvation이 발생할 가능성이 많고 deadlock도 발생할 수 있다.
2. Semaphore
OS차원에서도 Mutual exclusion을 support할 수 있는데 이 때, semaphore라는 구조체 변수를 이용하여 c.s를 구현한다.
semaphore는 queue와 정수로 구성되어 있다.
정수를 s라고 할 때, OS에서 관리하는 수 이므로 임의로 대입산술논리를 할 수 없고, 이 정수에 대해서 할 수 있는 것은 initialize, decrement(semWait), increment(semSignal) 이렇게 3가지이다.
semaphore를 사용하는 방법을 아래에서 더 알아보자!
Semaphore Primitives
c.s가 열려있는지, 닫혀있는지를 s.count의 값을 통해서 확인 할 수 있다.
s가 0보다 작거나 같으면 c.s의 문이 닫혀 있는 것을 의미하고 semWait을 실행하면 process를 blocked queue에 넣는다.
또한 s가 0보다 작으면 block queue에 process가 있는 것 이므로 semSignal을 실행하면 process를 ready queue로 옮긴다.
Binary Semaphore Primitives
s의 값이 0아니면 1인 구현하기 쉬운 semaphore이다.
s가 0이면 s.c가 닫혀 있는 것을 의미하므로, semWait을 했을 때 s가 1이면 열려있는 것이므로 닫고, 0이면 닫혀 있는 것이므로 process를 block queue에 넣는다.
semSignal을 실행하면 queue가 비었으면 c.s를 열고, 아니라면 queue에 있는 process를 ready queue로 옮긴다.
Strong/Weak Semaphore
semaphore은 2종류가 있는데 하나는 Strong semaphore로 FIFO방식을 사용하고 이 글에서는 이거라고 가정하고 쓸 것이다.
그리고 Weak semaphore인데 FIFO가 아니라 사용자가 원하는 순서로 queue에서 지워지는 방식이다.
Mutual Exclusion Using Semaphore
실제 사용할 때는 semWait후 c.s가 있고 그리고 semSignal을 하여 다른 process가 semWait을 할 수 있도록 한다.
Producer/Comsumer Problem
Buffer
I/O buffer에 input data가 들어오고 CPU가 이 데이터를 가져가게 되는데 CPU가 데이터를 가져가는 속도가 input data가 들어오는 속도보다 더 빠르다.
그러므로 CPU가 가져갈 data가 없는 상황이 발생할 수 있다.
I/O buffer에서 print해서 data가 나가는 속도보다 CPU가 output data를 가져오는 속도가 훨씬 빠르다.
그러므로 I/O buffer에 data가 꽉찬다.
이 상황을 producer, consumer에 빗대어 buffer에 producer은 in에 data를 쓸 것이고, consumer은 out에 있는 data를 가져갈 것이다.
Functions in a Buffer
producer에서는 다음 칸이 out이 아니라면 데이터를 쓴다.
consumer에서는 가져가려는 칸이 in이 아니라면 데이터를 가져간다.
Buffer using Semaphores
semaphore를 이용하여 function을 구현한 것이다.
s ⇒ n개의 프로세스가 동시작업해도 rece condition이 안생기는 기준이다.
n⇒ buffer의 데이터의 개수로 초기값은 0이다.
e⇒ 버퍼의 남은 자리로 초기값은 버퍼의 크기이다.
producer function은 produce를 통해 data를 생성하고, semWait(e)에서 버퍼에 남은 자리가 있는지 확인한다.
그리고 semWait(s)에서 c.s에 들어갈 수 있는지 확인하고 데이터를 버퍼에 넣는 c.s 작업을 하고 semSignal작업을 한다.
consumer function은 semWait(n)을 통해서 버퍼에 데이터가 있는지 확인한다.
있다면 semWait(s)를 통해서 c.s에 들어갈 수 있는지 확인하고 데이터를 가져가는 c.s 작업을 하고 semSignal작업을 한다.
그리고 take를 통해 가져온 데이터를 사용한다.
3. Monitors
Application차원에서도 Mutual exclusion을 support할 수 있는데 이 때 사용하는 것이 Monitor이다.
Monitor란 프로그램의 한부분이며 queue(정확히는 모니터 밖에)와 함수의 집합을 가지고 있다.
모니터 안에는 한 process만 들어갈 수 있으며, 들어가는 방법은 모니터 안에 있는 함수를 호출하면 된다.
또한 모니터안에서만 사용할 수 있는 로컬데이터와 컨디션변수가 있다.
Structure
monitor에서 사용할 수 있는 명령어는 2가지로 하나는 Cwait(Cn)으로 모니터 내의 함수를 실행하다가 Cwait(Cn)이라는 function을 만나면 무조건 이 process를 Cn이라는 queue로 보낸다.
Csignal(Cn)은 Cn이라는 queue의 process의 block을 무조건 풀어준다.
이 때, 실행중이던 process는 urgent queue에 들어가게 된다.
Buffer Solution Using Monitor
위는 모니터 밖에서 모니터 내부로 들어올 수 있는 함수들이다.
여기서 사용하는 전역변수 count는 버퍼 안 데이터의 수로 monitor 자체가 c.s이므로 count도 c.s로 관리된다.
데이터를 넣기 위해서 append 함수를 실행하면 count가 N일 경우 버퍼가 다 차 있으므로 process는 notfull이라는 queue로 들어가 block된다.
버퍼가 다 차지 않은 경우, 데이터를 넣은 후, 변수가 없으므로 조건 없이 notempty의 queue에 있는 process의 block을 풀어준다.
데이터를 읽기 위해 take 함수를 실행하면 버퍼에 데이터가 없다면 process를 notempty queue에 block시킨다.
버퍼에 데이터가 있다면 데이터를 읽고 notfull queue에 있는 process의 block을 풀어준다.
Readers/Writers Problem
semaphore를 이용하여 Readers/Writers Problem도 해결할 수 있다.
Reader은 data를 읽기만 하므로 동시에 읽어도 되지만 Writer은 data를 읽고 수정도 하므로 c.s에서 data를 다뤄야한다.
monitor를 이용한 solution이 많지만 reader가 우선순위를 갖는 solution을 살펴보자!
Readers have Priority
x는 readercount를 위한 semaphore이고 wsem는 c.s를 위한 semaphore이다.
