1. 동시성 제어 (Concurrency Control)
- Context-Switch : CPU에서 running 중이던 process를 PCB에 store 하고, 다른 PCB의 register 정보(PC, IR)를 CPU에 load 해오는 상황
- Concurrency-Control : Context-Switch 를 통해서 time-sharing을 함. 즉, 동시성 = 시분할
2. Concurrent vs Parallel
- Concurrenct : 시분할
- Parallel : multicore에서 실제 동시에 병렬적으로 실행 Parallelism
- data parallelism
- task parallelism
3. 동기(synchronous) vs 비동기(asynchronous) / blocking vs non-blocking
- Synchronous VS Asynchronous
- 두 가지 이상의 대상(메서드, 작업, 처리 등)과 이를 처리하는 시간으로 구분한다.
- Synchronous
- 호출된 함수의 리턴하는 시간과 결과를 반환하는 시간이 일치하는 경우
- 함수의 결과를 호출한 쪽에서 처리
- Asynchronous
- 호출된 함수의 리턴하는 시간과 결과를 반환하는 시간이 일치하지 않는 경우
- 함수의 결과를 호출한 쪽에서 처리하지 않는다.
- 호출되는 함수에게 callback을 전달해서, 호출되는 함수가 전달받은 callback을 실행
- Blocking VS Non-Blocking
- 호출되는 대상이 직접 제어할 수 없는 경우 이를 구분할 수 있다.
- Blocking: 호출된 함수가 자신의 작업을 모두 마칠 때까지 호출한 함수를 기다리게 만든다.
- Non-Blocking: 호출된 함수가 바로 리턴해서 호출한 함수에게 제어권을 준다.
4. 동기화 객체의 종류
- 스레드 동기화 방법
- 실행 순서의 동기화
- 스레드의 실행 순서를 정의하고, 이 순서에 반드시 따르도록 하는 것
- 메모리 접근에 대한 동기화
- 메모리 접근에 있어서 동시 접근을 막는 것
- 실행의 순서가 중요한 상황이 아니고, 한 순간에 하나의 스레드만 접근하면 되는 상황을 의미
- 실행 순서의 동기화
- 동기화 기법의 종류
- 유저 모드 동기화
- 커널의 힘을 빌리지 않는(커널 코드가 실행되지 않는) 동기화 기법
- 성능상 이점, 기능상의 제한
- Ex) 크리티컬 섹션 기반의 동기화, 인터락 함수 기반의 동기화
- 커널 모드 동기화
- 커널에서 제공하는 동기화 기능을 활용하는 방법
- 커널 모드로의 변경이 필요하고 이는 성능 저하로 이어짐, 다양한 기능 활용 가능
- Ex) 뮤 텍스 기반의 동기화, 세마포어 기반의 동기화, 이름있는 뮤텍스 기반의 프로세스 동기화, 이벤트 기반의 동기화
- 유저 모드 동기화
5. 동기화 관련 문제들
- busy-waiting → sleep and wakeup으로 해결
- 생산자 소비자 문제 (Producer-Consumer)
- 생산자 (producer) : 버퍼에 정보를 삽입
- 소비자 (consumer) : 버퍼에서 정보를 제거
- 버퍼가 가득 차 있다면? 생산자를 sleep --> 소비자 수행 후, wakeup
- count에 대한 접근 → Race-Condition (경쟁 조건) → wakeup signal 분실 가능
- 해결 : 세마포어 활용
- 식사하는 철학자들 문제
- 철학자는 스파게티를 먹기 위해 양옆의 포크를 동시에 들어야 한다.
- 이때, 전부 왼쪽 포크를 먼저 들면, 오른쪽 포크를 전부 못 들어 무한정 기다리게 된다.
- 즉, 제한된 수의 자원에 접근하는 문제
- 동시성 + 데드락 : 여러 프로세스가 동시에 돌아갈 때 교착 상태에 빠지는 원인
- 해결 : 동시성을 제거 - 필요한 포크가 사용 중이라면, 배고픈 철학자라도 블락된다
- 독자 저자 문제 (The Readers and Writers Problem)
- 식사하는 철학자 문제가 I/O와 같이 제한된 수의 자원에 접근하는 문제라면
- 읽는 자 쓰는 자는 데이터베이스에 접근하는 모델
- 여러 리더가 존재 가능
- Reader와 Writer의 배타적 접근
- 해결 : 뮤 텍스 세마포어
- 잠자는 이발사 문제
- 한 명의 이발사, 하나의 이발용 의자, 기다리는 손님을 위한 n개의 의자
- 손님이 없으면 이발사는 sleep
- 손님이 오면 이발사는 wakeup
- 이발 중 손님이 오면 대기용 의자에서 기다림
- 대기용 의자도 만석이면 손님은 그냥 이발소를 떠남
- ⇒ 이발사와 손님이 Race-Condition에 빠지지 않도록 하는 것
- 해결 : 뮤 텍스
- 한 번에 한 명만이 동작 상태를 바꿀 수 있게 한다.
- 이발사 : 뮤 텍스 얻어야 대기실 손님 확인 가능
- 손님 : 뮤텍스 얻어야 이발소 들어갈 수 있음, 대기실 or 의자에 앉으면 뮤텍스 반납
- 복수의 잠자는 이발사 문제 : 세마포어 필요
6. Critical Section (임계 영역)
- 멀티 스레딩에 문제점에서 나오듯, 동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역
- Race Condition을 유발하는 코드 블록
- (e.g. 공유하는 변수 사용, 동일 파일을 사용하는 등)
7. Race Condition 이란?
- 공유 자원에 대해 여러 프로세스/스레드가 동시에 접근을 시도하는 상황
- 즉, 하나의 자원을 두고 경쟁하는 것
- 타이밍에 따라서 결과가 다를 수 있어, 자료의 일관성을 해치는 결과가 나타남
- ex) 은행에서 출금하는 스레드 사이에서 발생하는 경우 balance가 덜 줄어듦 → 심각한 문제
8. Race Condition이 발생하는 경우
- Shared resource에 access 했는데 동기화를 하지 않으면 발생
- 커널 작업을 수행하는 중에 인터럽트 발생
- 문제점 : 커널 모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
- 해결법 : 커널 모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.
- 프로세스가 'System Call'을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때
- 문제점 : 프로세스 1이 커널 모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우 ( 프로세스2가 작업에 반영되지 않음 )
- 해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함
- 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
- 문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
- 해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법
9. Thread-safe 의미, 구현
- 의미
- 멀티스레드 환경에서 여러 스레드가 동시에 하나의 객체 및 변수(공유 자원)에 접근할 때, 의도한 대로 동작하는 것
- 구현
- 결국 동기화
- 2개의 critical region이 mutual exclusive 하게 수행되도록 막아서, 2개의 thread를 synchronize 하면 Race-condition을 없앨 수 있다.
10. Critical Section Problem (임계 영역 문제)를해결하기 위한 조건
- 상호 배제 (Mutual Exclusion) : 한 프로세스가 임계 구역에 들어가 있으면 다른 프로세스 들어갈 수 없다.
- 진행 (Progress) : 임계구역에 들어간 프로세스 없다면 어느 프로세스가 들어갈지 적절히 선택
- 한정 대기 (Bounded Waiting) : 기아 방지를 위해 한 번 들어갔다 나온 프로세스는 다음에 들어갈 때 제한을 준다. - no Starvation
(+) CPU의 속도 등에 대한 어떠한 가정도 하면 안 된다
11. Mutex (Mutual Exclusive), 상호 배제
- Mutual exclusive 하게 수행하도록 하여 synchronize 하는 것
- 그러므로 Race Condition을 없앤다.
- 화장실이 하나뿐인 식당, 열쇠 1개
- 여러 프로세스/스레드가 공유된 자원에 접근하는 것을 막는 것
- 여러 프로세스가 공유 자원 사용하려 할 때 번갈아 가며 사용하도록 함
- 임계 구역 내에서 인터럽트, 교착상태, 무한반복 발생하지 않도록 해야 함
- 키가 1개인 세마포어라고 볼 수 있다. (이진 세마포어)
- 구현 방법
- 2개 프로세스 기준 : 데커 알고리즘, 피터슨 알고리즘
- 여러 개 프로세스 기준 : Lamport의 빵집 알고리즘
12. Critical Section Problem 해결 방법 4가지
- Lock
- Semaphore
- Monitor
- Message
13. Lock
- 자원을 사용하는 동안 들어오지 못하도록 잠구는 것
- 하나의 자원에 여러 스레드가 동시에 접근하는 것을 조율해준다.
1) 기본형
- 동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section에 진입하는 프로세스는 Lock을 획득하고 Critical Section 을 빠져나올 때, Lock 을 방출함으로써 동시에 접근이 되지 않도록 한다.
while (lock == 1);
lock = 1;
Critical_region();
lock = 0;- 한계 : lock 이 0 일 때 두 스레드가 동시에 진입하면 문제!
2) Spin Lock
- busy waiting을 사용한 lock
- 장점 : lock이 해제될 때 context-switching 이 없어서, 오버헤드 없이 critical section 접근 가능
- 단점 : 어떤 스레드가 락을 오래 소유하면, CPU 낭비
- 한계 : Progress를 만족하지 않음 - 010101 번갈아서 들어와야 함 / 000 이면 실행 안됨
- 언제 사용? 멀티-스레드에서 critical section 이 아주 작거나, 빠른 처리 가능할 때
while(True) {
while (turn != 0);
Critical_region();
turn = 1;
Noncritical_region();
}
while(True) {
while (turn != 1);
Critical_region();
turn = 0;
Noncritical_region();
}
3) Peterson's Solution
- 소프트웨어적으로 이 방법을 쓰면 해결 가능하지만, 오버헤드가 크다
4) TSL (Test and Set Lock) instruction
- 하드웨어적으로 제공되는 명령어로 atomic 하게 실행된다.
# 하드웨어에서 이런 명령어를 제공
bool Test_and_Set(bool *flag) {
bool old = *flag;
*flag = True;
return old;
}
lock = false;
repeat
while Test_and_Set(lock) do no-op;
Critical Section
lock = false;
Remainder Section
until false- 문제
- Spin Lock 이기 때문에 CPU를 계속 써야 함 (Lock 값 계속 체크해야 함)
14. Sleep and Wakeup
- busy-waiting 해결 → 임계 구역 진입이 허용되지 않을 때, CPU 시간을 낭비하는 대신 블록 하는 프로세스 간 통신 고려
- sleep : 호출자를 block → 다른 프로세스가 깨울 때 (wakeup)까지 보류
- wakeup
- 발생 문제 : 생산자 - 소비자 문제 (한정된 버퍼 문제)
- 생산자 (producer) : 버퍼에 정보를 삽입
- 소비자 (consumer) : 버퍼에서 정보를 제거
- 버퍼가 가득 차 있다면? 생산자를 sleep --> 소비자 수행 후, wakeup
15. Semaphore
- 화장실이 여러 개 있는 레스토랑, 열쇠 = 칸 개수만
- 현재 공유자원에 접근할 수 있는 프로세스/스레드 수를 나타내는 값을 두어 상호 배제
- Lock시 특정 수만큼의 카운트를 더하고
- Unlock시 빼주는 형식으로 처리
- 이런 락을 슬립( Sleep ) 가능한 락이라고 함
- Up, Down은 atomic 하게 동작
- 생산자 소비자 문제의 근본적 해결
- 동기화해야 하는 대상이 여러 개일 때 사용
1) 카운팅 세마포어
- 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수로 초기화된다. 자원을 사용하면 세마포가 감소, 방출하면 세마포가 증가한다.
- 생산자 소비자 문제와 비교하기
- count 하나로 표현되던 부분들이 up, down을 이용하여 mutex, empty, full로 표현
#define N 100 // 버퍼 용량
int mutex = 1; // 공유 데이터를 위한 mutex
int empty = n // 빈 용량
int full = 0 // 찬 용량
void producer(void) {
int item;
while(TRUE) {
item = produce_item(); // item 생성
down(&empty); // if 꽉차지 않았으면 empty--;
down(&mutex); // mutex = 0 으로 해서, lock 처리
insert_item(item); // 버퍼에 추가
up(&mutex); // mutex = 1 으로 해서, unlock 처리
up(&full);
}
}
void consumer(void) {
int item;
while(TRUE) {
down(&full);
down(&mutex);
item = remove_item(); //
up(&mutex);
up(&empty);
consume_item(item);
}
}2) 이진 세마포어 (MUTEX)
- MUTEX라고도 부르며, 상호 배제의 (Mutual Exclusion)의 머릿글자를 따서 만들어졌다. 이름 그대로 0과 1 사이의 값만 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용한다.
16. Monitor
- 동기화를 구현하기 위한 특수 프로그램 기법
- 특정 공유 자원을 프로세스에게 할당하는 데 필요한 데이터와 이 데이터를 처리하는 프로시저로 구성
- 자료 추상화, 정보 은폐 개념을 기초, 병행성 구조
- 상호 배제가 low-level 단에서 지원됨
- → "단 하나의 프로세스만 한 순간에 모니터에서 활동할 수 있다."
- 생산자-소비자 문제 해결
- 조건 변수 wait, signal 도입
- sleep, wakeup과 달리 모니터에서는 자동적으로 상호 배제가 됨→ 문맥교환 될 걱정하지않고 연산 완료 가능
- → wait, signal은 상호배제가 아님
17. Message Passing
- send / receive ; 시스템 호출 일종
- acknowledgement 분실 문제 -> 메시지 구별 필요
- 인증 --> 프로세스의 유일성 보장
- 생산자 - 소비자 문제
- 공유 메모리가 아닌, 메시지 전달로 해결
- 가정
- 모든 메시지는 동일한 크기
- 메시지는 운영체제에 의해 자동 버퍼링
- 방법
- 소비자는 시작할 때, N개의 빈 메시지를 생산자에게 보냄
- 생산자는 소비자에게 전달할 아이템을 생산하면, 빈 메시지 수신 → 아이템이 들어 있는 메시지 전송
'CS > 운영체제 (OS)' 카테고리의 다른 글
| 8. IPC (Inter-Process Communication) (0) | 2021.08.11 |
|---|---|
| 7. 프로세스 vs 스레드 (0) | 2021.08.11 |
| 4. 프로세스의 주소 공간 (1) | 2021.08.08 |
| 3. 인터럽트 (Interrupt) (1) | 2021.08.08 |
| 2. 커널 (Kernel) (0) | 2021.08.06 |
