다중 프로그래밍 시스템
- 여러 개의 프로세스 존재
- 프로세스들은 서로 독립적으로 동작
- 공유 자원 또는 데이터가 있을 때, 문제 발생
동기화
- 프로세스들이 서로 동작을 맞추는 것
- 프로세스들이 서로 정보를 공유하는 것
용어 표현
- Shared data(공유 데이터) : 여러 프로세스들이 공유하는 데이터
- Critical section(임계 영역) : 공유 데이터를 접근하는 코드 영역
- Mutual exclusion(상호 배제) : 둘 이상의 프로세스가 동시에 임계 영역에 진입을 막는 것
Critical section에서의 문제
과정
1. 공유 데이터를 Register에 저장
2. 저장된 데이터에 1 더하기
3. 저장된 값을 공유 데이터에 저장
- 문제 : 일관된 답을 주지 않음
상호 배제 구현을 통한 문제 해결 시도
- 구현
* enterCS() : 다른 프로세스가 임계 영역 안에 있는지 검사
* exitCS() : 임계 영역을 벗어나면 시스템에게 알림
- 조건
* 상호 배제 : 임계 영역에 프로세스가 있으면, 다른 프로세스 진입 금지
* Progress(진행) : 임계 영역 안에 있는 프로세스만 다른 프로세스의 임계 영역 진입을 막음
* Bounded waiting(한정대기) : 프로세스의 임계 영역 진입은 유한시간 내에 허용
1. Version 1
- 문제 : Progress 조건 위배
* P1이 임계 영역에 진입 하지 않을 경우, P2는 진입 못함
* 같은 프로세스는 두 번 연속 임계 영역 진입 불가능
2. Version 2
- 문제 : 상호 배제 조건 위배
* P1 실행 도중에 선점되어 멈추면 P2가 임계 영역에 진입 -> P1가 다시 CPU 할당 받아 임계 영역 진입
3. Version 3
- 문제 : 진행, 유한 대기 조건 위배
* P1이 Flag[1]을 true로 만들고 선점됨 -> P2가 Flag[2]를 true로 만들고 대기 -> P1가 돌아왔는데, Flag[2]가 true라서 대기 -> P1과 P2 무한 대기
상호 배제 해결을 위한 SW 솔루션
1. 두 개의 프로세스에 대한 상호 배제 알고리즘
- Dekker's Algorithm
- Peterson's Algorithm
* Dekker's Algorith보다 간단하게 구현
2. N개의 프로세스에 대한 상호배제 알고리즘
- Dijkstra's Algorithm
* 문제
+ 속도가 느림 : in-CS가 빈번하면, repeat ~ until 부분을 많이 돌아야 함
+ 구현이 복잡
+ busy waiting : repeat ~ until 하면서 대기, 1단계에서 while(turn != i) do 하면서 대기
상호 배제를 해결하기 위한 HW 솔루션
1. 두 개의 프로세스에 대한 상호 배제 알고리즘
- TestAndSet(TAS) Instruction (기계어) 사용
* 실행 중 interrupt을 받지 않기 때문에 Test와 Set을 한 번에 수행
- 문제 : 3개 이상의 프로세스인 경우, bounded waiting 조건 위배
* 상황 : P1은 임계 영역. P2와 P3가 대기하다가 P3가 임계 영역에 진입. P4가 와서 P2와 진입하다가 P4가 진입하고 P2는 다시 대기. 이렇게 하나의 프로세스가 무한 대기를 할 수도 있음
2. N 개의 프로세스에 대한 상호 배제 알고리즘
- 장점
* 구현이 간단
- 단점
* busy waiting
상호 배제를 해결하기 위한 OS 솔루션
1. Spinlock
- 정수 변수
- 초기화 연산, P() 연산, V() 연산으로만 접근 가능
- OS가 원자성을 보장하기 때문에 P()와 V() 실행 중에 선점 당하지 않음
- 문제
* 멀티 프로세서 시스템에서만 사용 가능 : Pi가 임계 영역에서 실행 중이다가 멈춰서 CPU를 반환 -> Pj가 CPU를 할당 받아서 P() 실행하면서 대기 -> Pi는 다시 CPU를 할당 받을 수 없음(원자성으로 선점 불가능) -> active = 0인 상태 -> Pj는 무한대기, Pi는 CPU 못 받음 -> 따라서 CPU가 여러 개 있는 시스템에서만 사용 가능
* busy waiting
2. Semaphore
- 음이 아닌 정수형 변수(S)
- 초기화 연산, P() 연산, V() 연산으로만 접근 가능
- 임의의 S 변수 하나에 ready queue 하나가 할당됨
- Binary semaphore
* S가 0rhk 1 두 종류의 값만 갖는 경우
* 상호배제나 프로세스 동기화의 목적으로 사용
- Counting semaphore
* S가 0이상의 정수 값을 가질 수 있는 경우
* Producer-Consumer 문제 등을 해결하기 위해 사용
- 연산
* 초기화 연산 : S 변수에 초기 값을 부여하는 연산
* P() 연산, V() 연산
* P() 연산 설명
+ S를 물건의 개수라고 가정
+ if(S>0) : S가 있는지 확인
+ then S <- S - 1 : 물건 한 개를 가져가고 임계 영역으로 진입
+ else wait on the queue Qs : S에 할당된 ready queue에서 대기
+ Spinklock는? S가 없으면 while을 계속 도는 busy waiting 현상 발생, semaphore는 queue에 넣어서 프로세스를 block 상태로 대기
* V() 연산 설명
+ 임계 영역에서 일을 끝냈으면 실행
+ if(waiting processes on Qs) : ready queue에 기다리는 프로세스 있는지 확인
+ then wake up one of them : 기다리는 프로세스 중에 하나 깨우기
+ else S <- S + 1 : 물건 되돌려 놓음
- 특징 : OS가 원자성을 보장
- where to use
* Windows의 MSDN
* Unix/Linux의 system V
- Semaphore로 해결 가능한 동기화 문제
* 상호 배제 문제
* 프로세스 동기화 문제
* producer-consumer 문제
* reader-writer 문제
1) 상호 배제 문제
- P()와 V()로 해결
2) 프로세스 동기화
- 프로세스들의 실행 순서 맞추기
- 상황 : 프로세스 Pi는 프로세스 Pj가 Lj 지점을 통과할 때까지 Li 지점에서 대기해야 함
- 해결 경우 1 : Pj가 sync에서 1을 가져옴 => 그래서 sync = 0 상태 => Pj는 처리 중이고 Pi는 대기 => Pj가 끝나고 V()를 통해서 sync = 1이 됨, 동시에 V()가 ready queue에 있던 Pi를 깨움 => Pi은 sync으로부터 1을 가져오고 sync = 0이 됨 => Pi 작업 진행
- 해결 경우 2 : Pi이 먼저 도착, 하지만 Pj가 먼저 sync를 가져가서 Pi는 ready queue에서 대기 => Pj가 오고 작업 완료 후, Pi를 깨우고 sync에게 1 반환 => Pi는 sync에서 1 가져오고 작업 수행
3) Producer-Consumer 문제
- 생산자 프로세스 : 메시지를 생성하는 프로세스 그룹
- 소비자 프로세스 : 메시지를 전달받는 프로세스 그룹
- 설명 : Producer process는 물건을 생산해서 shared memory buffer에 쌓고, Consumer process는 shared memory buffer에 저장된 데이터를 가져가서 소비
- 문제 상황
* Producer process가 buffer에 쌓는 중에 Consumer process가 가져가면 안됨
* A Producer process가 buffer에 넣을 때, B Producer process가 넣으면 안됨
- 해결 방법 : with single buffer
* single buffer로 물건을 놓을 때 가져 갈 수 없고, 물건을 가져갈 때 물건을 놓을 수 없는 한 번에 한 번 접근만 가능하게 하는 방법
- 변수
* consumed : 소비되었으면 1
* produced : 생산되었으면 1
* buffer : semaphore(앞에서 S 같은 변수)
- 과정
* Producer : Producer Pi가 buffer에 넣으려고 함 => P(consumed)로 소비되었는지 확인 => 소비되어 있으면, consumed = 0으로 바꾸고, produced = 1로 바꿈
* Consumer : Consumer Cj가 소비하려고 함 => P(produced)로 생산되었는지 확인 => 생산되어 있으면, produced = 0으로 바꾸고, consumed=1로 바꿈, 만약에 생산되어 있지 않으면, queue에서 대기 => Producer Pi의 V()가 끝나면 queue에 대기하고 있던 프로세스 깨워서 작업 시작
- 해결 방법 : with N-buffers
- 변수
* nrfull : 채워진 buffer 수
*nrempty : 비워진 buffer 수
* mutexP : Producer 상호 배제를 위한 변수
* mutexC : Consumer 상호 배제를 위한 변수
* in, out : buffer에서 가져가고 가져오는 위치를 표시하는 변수
- 과정
* Producer : P(mutexP)로 critical section이 비었는지 확인 => P(nrempty)로 buffers에 빈 곳이 있는지 확인 => 공간이 없으면 대기, 공간이 있으면 Buffer[in]에 물건 M 놓기 => in <- (in + 1) mod N으로 포인터 위치 변경 => V(nrfull)로 buffers에 물건 놓았다고 갱신 => V(mutexP)로 critical section 벗어났다고 신호
* Consumer : P(mutexC)로 critical secction이 비었는지 확인 => P(nrfull)로 buffers에 물건이 있는지 확인 => 물건이 없으면 대기, 있으면 buffers[out]에서 물건 꺼내기 => out <- (out + 1) mod N으로 포인터 위치 변경 => V(nrempty)로 buffers에서 물건 뺏다고 갱신 => V(mutexC)로 critical section 벗어났다고 신호
4) Reader-Writer 문제
- Reader : 데이터에 대해 읽기 연산만 수행
- Writer : 데이터에 대해 쓰기(갱신) 연산만 수행
- 데이터 무결성 보장 필요
* Reader들은 데이터에 동시 접근 가능
* Writer와 Reader 사이에는 상호 배제, Writer와 Writer 상이에는 상호 배제
- 해결 방법 : Reader 또는 Writer에게 우선권 부여
- 해결 방법 : Reader preference solution
* 1단계 : 읽기 전 준비
+ P()와 V() 사이는 critical section
+ if(nreaders = 0) then : 읽는 작업이 없으면, 지금부터 쓸 예정이니 P(wmutex)로 writer 작업 중지
+ nreaders <- nreaders + 1 : 읽는 작업 추가
* Perform read operations : 읽는 작업 실행, 여러 개의 읽은 작업 가능
* 2단계 : 읽는 작업 완료 후 정리
+ P()와 V() 사이는 critical section
+ nreaders <- nreaders - 1 : 다 읽었느니 작업 개수 감소
+ if(nreaders = 0) then : 읽는 작업이 자신이 마지막이면, V(wmutex)로 writer 작업 중지 해제
- 장점
* no busy waiting : queue라는 대기실이 있어서 프로세스는 block 상태로 대기
* starvation problem : semaphore queue에 대한 wake-up 순서는 비결정적이기 때문에 queue에 대기하는 프로세스 중에 어떤 프로세스는 무한히 안 깨울 수도 있음 => Eventcounter / Sequencer로 해결
3. Sequencer / Eventcount
- 은행에서 번호표를 뽑아 일 처리하는 과정과 유사
- Sequencer
* 발생 사건들의 순서를 기록 (번호표 출력기)
* 정수형 변수, 생성 시 0으로 초기화, 감소하지 않음
* ticket() 연산으로만 접근 가능
* ticket()
+ 증가되어 온 sequencer 값을 반환하고 +1 해줌 (번호표 출력되듯이 반환)
- Eventcount
* 작업 중인 사건의 발생 횟수를 기록 (번호 호출판)
* 정수형 변수, 생성시 0으로 초기화, 감소하지 않음
* read(E), await(E, v), advance(E) 연산으로만 접근 가능
* read(E)
+ 현재 번호가 몇 번인지 확인하는 함수로, 현재 eventcount 값 반환
* await(E, v)
+ E = 현재 작업 번호, v = 내 번호
+ if(E < v)이면, 아직 내 차례가 오지 않았으므로 큐에 프로세스 넣고 대기 그리고 CPU scheduler에게 깨워 달라고 호출
* advance(E)
+ 은행원이 현재 번호에 + 1 시키고 기다리는 사람 부름
+ E <- E + 1, E 차례를 기다리던 프로세스를 깨움
- 상호 배제 문제 해결
- Producer-Consumer 문제 해결
* Producer Pi 설명
+ t <- ticket(Pticket) : 번호표 뽑기
+ await(In, t) : 현재 작업 번호 In에 나의 번호 t가 도달할 때까지 대기
+ await(Out, t-N+1) : 빈 공간이 있는지 확인
[공간 >= 1 -> 공간 = N-t+Out -> Out >= t-N+1 -> Out < t-N+1 : 빈 공간 없음]
+ Buffer[t mod N] <- M : mod 연산으로 t 자리에 M 넣기
+ advance(In) : 작업이 끝났으니 In <- In + 1 해주고, In 기다리는 프로세스를 깨움
* Consumer Pi 설명
+ u <- ticket(Uticket) : 번호표 뽑기
+ await(Out, t) : 현재 작업 번호 Out에 나의 번호 u가 도달할 때까지 대기
+ await(In, u+1) : 물건 있는지 확인
[물건 >= 1 -> In - u >= 1 -> In >= 1 + u -> In < 1 +u : 물건이 없음]
+ M <- Buffer[u mod N] : mod 연산으로 u 자리에서 물건 가져오기
+ advance(Out) : 작업이 끝났으니 Out <- Out + 1 해주고, Out 기다리는 프로세스를 깨움
- 장점
* No busy waiting
* No starvation : FIFO scheduling for queue
* semaphore 보다 더 low-level control이 가능 : 순서를 control 가능하기 때문에 더 세부적임
상호 배제를 해결하기 위한 Language 솔루션
SW, HW, OS 해결 방법과 차이
- 위 3가지 방법들은 low-level mechanisms
- 따라서, Flexible 하지만, 사용하기 어려움.
High-level mechanism 해결 방법
- Monitor
- Path expressions
- Serializers
- Critical region, conditional critical region
- 특징
* Language-level constructs
* Object-oriented concept과 유사
* 사용이 쉬움
1. Monitor
- 마치, 한 번에 한 명만 들어올 수 있는 책방. Critical data는 빌리는 책. Critical section은 대출과 반납을 위한 연산
- Monitor에서 일어나느 과정을 Language가 보장
- 구조
* entry queue : monitor 내의 procedure 수 만큼 존재
* mutual exclusion : monitor 내에는 항상 하나의 프로세스만 진입 가능
* Information hiding : critical data는 monitor 내의 프로세스만 접근 가능
* condition queue : monitor 내의 특정 이벤트를 기다리는 프로세스가 기다리는 대기실
* signal queue : signal() 명령을 실행한 프로세스가 임시로 대기하는 대기실
- 과정
* 초기 상태
+ Pj 요청 전 상태
+ monitor 안에 프로세스 없음
+ R_Available : 자원 있는지 확인 변수
* 상태 1
+ Pj가 자원 요청
* 상태 2
+ 자원 R은 Pj에게 할당
+ Pi와 Pl은 자원이 없어서 condition queue 대기실에서 대기
* 상태 3
+ Pj는 자원을 사용하고 반환하기 위해서 대기
* 상태 4
+ Pj가 자원을 반환
* 상태 5
+ Pj는 signal queue에 들어가서 R_Free.signal() 호출에 의해 condition queue에서 Pi를 깨움
+ Pi는 자원 요청
* 상태 6
+ Pi에게 자원 R 할당
+ Pj가 monitor 안으로 돌아와서 남은 작업 수행하고 나감
1) Producer-Consumer 문제 해결
- 설명
* Entry queue for fillBuf() : buffer에 넣는 procedure. Producer가 사용
* Entry queue for emptyBuf() : buffer에서 빼는 procedure. Consumer가 이용
* bufHasData : 데이터가 없을 때 대기하는 장소. Consumer가 이용
* bufhasSpace : 공간이 없을 때 대기하는 장소. Producer가 이용
* signaler queue : 대기하는 깨워주는 신호 대기하는 장소
* in : 넣은 위치
* out : 뺄 위치
* validBufs : buffer에 물건 개수
2) Reader-Writer 문제 해결
- Reader/Writer 프로세스들 간의 데이터 무결성 보장 기법
- Writer 프로세스에 의한 데이터 접근 시에만 상호 배제 및 동기화 필요
- 하는 방법 (한 번 해보기)
* 변수 2개
+ 현재 읽기 작업을 진행하고 있는 Reader 프로세스의 수
+ 현재 Writer 프로세스가 쓰기 작업을 진행 중인지 표시
* 조건 큐 2개
+ Reader/Writer 프로세스가 대기해야 할 경우에 사용
* 프로시저 4개
+ Reader/Writer 프로세스가 읽기/쓰기 작업을 원할 경우에 호출
+ Reader/Writer 프로세스가 읽기/쓰기 작업을 마쳤을 경우에 호출
* 정답 : 22:07
https://www.youtube.com/watch?v=AnYN-kbCbRI&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=18
3) Dining philosopher 문제 해결
- 철학자(프로세스) : 생각하는 일, 스파게티 먹는 일 반복
- 공유 자원 : 스파게티, 포크
- 조건 : 스파게티를 먹기 위해서는 좌우 포크 2개 모두 필요
- 과정
* numForks : 자신이 사용가능한 포크 개수 (즉, 좌우에 1개씩 있으면 2)
- 장점
* 사용이 쉬움
* Deadlock 등 error 발생 가능성 낮음
- 단점
* 지원하는 언어에서만 사용 가능
* 언어를 기계어로 컴파일 해줘야 하기 때문에 컴파일러가 OS를 이해하고 있어야 함
본 내용은 한국기술교육대학교 김덕수 교수님의 유튜브 강의를 듣고 정리한 내용입니다.
'Software Courses > Operating System' 카테고리의 다른 글
| [Deadlock] Deadlock Solutions (0) | 2020.12.06 |
|---|---|
| [Deadlock] Deadlock and Resources types (0) | 2020.12.04 |
| Process Scheduling (0) | 2020.12.01 |
| Thread 관리 (0) | 2020.11.30 |
| Process 관리 (0) | 2020.11.30 |