❗
본 게시물의 내용은 양희재 교수님의 '운영체제' 수업을 참고하여 작성하였습니다.
출처 및 강의 자료는 게시글 하단에 기재된 링크를 통해 확인하세요.
1. 운영체제 관리
운영체제 관리에서 프로세스 관리는 매우 중요한 부분이다.
프로세스 관리는 크게 'CPU 스케줄링'과 '프로세스 동기화' 2가지를 생각해볼 수 있다.
그 중 프로세스 동기화(Process Synchronization)에 대해 알아보려고 한다.
2. 프로세스 동기화
공통된 자원에 접근하고 사용하고자 하다보니 프로세스들 간에 영향을 미치며, 이에 따라 프로세스 동기화의 중요성이 높아진다.
-
프로세스 간의 통신의 예: 전자우편, 파일 전송
-
프로세스간 자원 공유의 예
-
메모리 상의 자료들
-
데이터 베이스
-
온라인 수강 신청
-
BankAccount Problem
은행 계좌 문제를 통해 프로세스 동기화 문제를 이해해볼 수 있다.
-
조건
-
부모는 은행 계좌에 입금(deposit)
-
자녀는 은행 계좌에서 출금(withdraw)
-
입금과 출금은 독립적으로 발생
-
부모와 자녀가 동일한 빈도로 입금 및 출금을 진행한다면 이론적으로 은행계좌의 금액은 0이 되어야한다.
그러나 실제 코드를 이용해 확인해보면 다른 결과 값을 확인해볼 수 있는데, 이는 공통 변수(common variable)에 대한 동시 업데이트(concurrent update) 로 인한 것으로 생각해볼 수 있다.
이 문제는 임계 구역 문제로 한번에 한 쓰레드만 업데이트하도록 하는 것으로 해결할 수 있다.
3. Cirtical Section
임계구역은 멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역이다.
시간이 지나면 임계구역은 종료된다.
따라서 다른 프로세스가 임계구역에 접근하기 위해 해당 시간 만큼 대기해야한다.
-
쓰레드가 임계구역에 접근하는 순서
-
요청
-
필요시 대기
-
임계구역 처리
-
빠져나감
-
임계 구역 해결 조건
임계 구역 문제는 3가지 조건 충족 시 해결할 수 있다.
-
Mutual exclusion(상호 배타)
- 오직 한 쓰레드만 진입
-
Progress(진행)
-
진입 결정은 유한 시간 내
-
어느 프로세스가 들어갈 것인지 선택
-
-
Bounded Waiting(유한 대기)
-
어느 쓰레드라도 유한 시간 내
-
한 번 들어갔다 나온 프로세스는 다음에 들어갈 때 제한
-
4. 동기화 도구
프로세스 및 쓰레드 동기화에서 해결해야 할 이슈
→ 임계 구역 문제 해결, 프로세스 실행 순서 제어
-
동기화 도구(Synchronization Tools)
-
Semaphores
-
Monitors
-
Misc.
-
5. Semaphores
세마포는 동기화 문제 해결을 위한 소프트웨어 도구이다.
정수형 변수+두 개의 동작 (P, V)구조를 가진다.
-
Proberen(test, P):
acquire() -
Verhogen(increment, V):
release()
// acquire: 프로세스 및 스레드 블락(큐에 추가, 잠듦)
void acquire() {
value--;
if(value < 0) {
add this process/thread to list;
block;
}
}
// release: 블락된 프로세스 및 스레드 진행(큐에서 제거, 깨어남)
void release() {
value++;
if(value <= 0) {
remove a process P from list;
wakeup;
}
}
(1) Mutual exclusion
세마포의 일반적인 사용(1): 상호 배타 목적
-
초기값 지정:
sem.value = 1; -
구조
| sem.acquire(); |
|---|
| critical-section |
| sem.release(); |
(2) Ordering
세마포의 일반적인 사용(2): 프로세스 실행 순서 제어
-
초기값 지정:
sem.value = 0; -
구조
| Process 1 | Process 2 |
|---|---|
| sem.acquire(); | |
| Statement 1 | Statement 2 |
| sem.release(); |
6. 전통적 동기화 예제
-
Producer and Consumer Problem
-
생산자-소비자 문제
-
유한 버퍼 문제(Bounded Buffer Problem)
-
-
Readers-Writers Problem
-
공유 데이터베이스 접근
-
-
Dining Philosopher Problem
- 식사하는 철학자 문제
Producer-Consumer Problem
-
생산자-소비자 문제
-
생산자가 데이터를 생산하면 소비자가 소비
-
예:
컴파일러-어셈블러,파일 서버-클라이언트,웹 서버-웹 클라이언트
-
-
Bounded Buffer
-
생산된 데이터는 버퍼에 저장
-
현실 시스템에서 버퍼 크기는 유한함
-
문제: 생산자는 버퍼가 가득 차면 더이상 넣을 수 없고, 소비자는 버퍼가 비면 소비할 수 없음
-
-
문제: 해당 문제가 발생하는 이유는 임계구역(공통 변수 업데이트 구간)에 대한 동시 진입으로 볼 수 있다.
-
해결 방법
-
상호 배타: 임계 구역에 대한 동시 접근 방지
-
세마포를 사용한 상호 배타 (mutual exclusion)
-
-
Busy-wait
-
생산자는 버퍼가 가득 차면 기다려야하고, 소비자는 버퍼가 비면 기다려야한다 → CPU를 비효율적으로 사용
-
세마포를 사용하여 busy-wait를 회피할 수 있음
-
// 생산자: empty.acquire() - of permit=BUF_SIZE
// 소비자: full.acquire() - of permit=0
// 생산자
empty.acquire();
PRODUCE;
full.realese();
// 소비자
full.acquire();
PRODUCE;
empty.realese();Readers-Writers Problem
공통 데이터 베이스에서 Reader는 데이터를 읽고 수정하지 못하며, writer는 데이터를 읽고 수정이 가능하다.
- 한 번에 한 개의 프로세스만 접근 가능한데(상호배타), 이는 비효율적이다.
- 효율성 제고: reader가 들어가면 내용이 바뀌지 않기 때문에 reader-reader 접근을 허용해야한다.
-
변종
-
The first R/W problem (readers-preference)
-
The second R/W problem (writers-preference)
-
The Third R/W problem
-
Dining Philosopher Problem
식사하는 철학자 문제는 5명의 철학자와 5개의 젓가락이 있고 철학자는 생각-식사 행위를 반복한다.
식사를 하기 위해서는 2개의 젓가락이 필요하다.
왼쪽 젓가락을 얻은 후 오른쪽 젓가락을 얻고자 한다고 가정한다.
이 때 발생할 수 있는 문제는 무엇일까?
만약 모든 철학자가 모두 식사를 하고자 하고, 왼쪽 젓가락을 잡는다면 모든 철학자가 식사를 할 수 없다.
즉, 교착 상태(deadlock)가 발생한다.
이와 같이 동기화를 하다보면 교착 상태가 발생할 수 있다.
7. 교착 상태(Deadlocks)
프로세스는 실행을 위해 여러 자원이 필요하다.
만약 어떠한 자원은 가지고 다른 자원을 가지지 못했을 때 대기 상태가 되는데, 다른 프로세스 역시 다른 자원을 가지려고 대기할 때 교착상태가 발생할 가능성이 있다.
필요 조건(Necessary Conditions)
필요 조건이 모두 만족되어야 교착 상태가 일어날수도 있다 (무조건 발생 X)
-
Mutual exclusion (상호 배타)
-
Hold and wait (보유 및 대기)
-
No Preemption (비선점) → 강제로 빼앗을 수 없는 것
-
Circular wait (환형 대기) → 대기 상태가 사이클을 이룬다.
자원(Resources)
-
동일 형식 자원이 여러개 있을 수 있음
-
요청(request) - 사용(use) - 반납(release)순서 -
자원 할당도(Resource Allocation Graph)
-
자원과 프로세스의 할당 관계, 대기 상황을 나타냄
-
지원은 사각형, 프로세스는 원, 할당은 화살표로 나타낸다.
-
