Reader-Writer problem
•
Reader
◦
데이터에 대해 읽기 연산만 수행
•
Writer
◦
데이터에 대해 갱신 연산을 수행
•
데이터 무결성 보장 필요
◦
Reader들은 동시에 데이터 접근 가능
◦
Writer들(또는 reader와 write)이 동시 데이터 접근 시, 상호배제(동기화) 필요
◦
해결법
▪
reader / writer 에 대한 우선권 부여
•
reader preference solution
◦
writer가 기다릴 때, 새로운 reader가 공유 자원 접근 가능
•
writer preference solution
•
reader preference
◦
wmutex = 한명의 writer을 위한 mutex
◦
rmutex = nreader을 위한 mutex
•
한번에 여러 reader 공유자원 접근 가능
•
하나의 writer만 공유 자원 접근 가능
식사하는 철학자 문제 해결(Dining Philosophy)
•
5명의 철학자
•
철학자들은 생각하는 일, 밥 먹는 일만 반복함
•
공유 자원 : 밥, 포크
•
밥을 먹기 위해서는 좌우 포크 2개 모두 들어야 함
◦
철학자가 좌 우 포크를 둘 다 사용할 수 있는 경우에만 포크를 집을 수 있다는 제한을 사용합니다. (데드락 방지를 위해서)
◦
단, 철학자는 한 번에 한 개의 포크만 집을 수 있음
•
솔루션 → 세마포어 사용
◦
semaphore chopstick[5] = {1,1,1,1,1}
◦
wait : 철학자는 그 세마포어에 wait()연산을 실행하여 젓가락을 집으려고 시도
◦
signal : signal()연산을 수행하여 자신의 젓가락을 내려놓음
•
공유 데이터 :
◦
밥그릇(데이터 셋)
◦
1로 초기화된 세마포어 chopstick[5]
•
인접한 두 철학자가 동시에 식사하지 않음을 보장
⇒ 그러나 모두가 동시에 자신의 왼쪽 젓가락을 잡는다면?
(deadlock) 발생
◦
해결안1)
최대 4명의 철학자들만이 테이블에 동시에 앉을 수 있도록 함
◦
해결안2)
한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 허용
◦
해결안3)
비대칭 해결안 사용.
홀수 번호의 철학자는 왼쪽 젓가락부터, 짝수 번호의 철학자는 짝수 젓가락부터
▪
이웃하는 철학자는 공유하는 젓가락을 얻기 위한 시도 전에 이미 필요한 다른 젓가락을 획득
•
모니터 예시
초기값으로 3가지 state를 가진다
→ Think, Hungry, Eat
→ 처음에는 think로 초기화
self
◦
Hungry 상태일 때 모니터에 들어와서 자신을 대기 상태 큐로 이동시킬 condition variable
pickup
◦
젓가락 집는 것
◦
현재 상태를 think → hungry
◦
test 함수 실행
◦
자기 자신이 eat 상태가 아니면 self 조건 변수를 wait 호출해서 waiting queue에 넣는다
putdown
◦
젓가락 내려 놓기
◦
다 먹었으니 다시 자신의 state를 eat → think 로 변환
◦
각각 인접한 좌우 철학자의 식사 여부를 test한다
▪
만약 내가 식사 완료했고 주변이 hungry라면 주변의 state를 eat으로 바꾸고 signal해주어 주변의 condition variable 프로세스를 readyqueue에서 꺼내준다.
test
◦
인접한 두 철학자가 동시에 식사하지 않음을 보장
◦
자기 자신이 hungry라면
◦
hungry → eat으로 상태 전이
◦
self 조건 변수에 signal을 보내서 ready queue에서 꺼냄
⇒ deadlock은 발생하지 않지만 다른 철학자의 상태 전이를 기다리다가 starvation이 발생할 수 있음
자원 할당 문제
Producer-Consumer Problem
Reader-Writer Problem
•
reader/writer 프로세스들간의 데이터 무결성 보장 기법
•
writer 프로세스에 의한 데이터 접근 시에만 상호 배제 및 동기화 필요함
•
모니터 구성
◦
변수 2개
▪
현재 읽기 작업을 진행하고 있는 reader 프로세스의 수
▪
현재 writer 프로세스가 쓰기 작업을 진행 중인지 표시
◦
조건 큐 2개
▪
reader/writer프로세스가 대기해야 할 경우에 사용
◦
프로시져 4개
▪
reader(writer) 프로세스가 읽기(쓰기) 작업을 원할 경우에 호출, 읽기(쓰기) 작업을 마쳤을 때 호출
OS 스케쥴링
UNIX System
•
Interactive system
◦
Priority-based scheduling, preemptive scheduling
•
Priority
◦
Kernel priority
▪
커널 모드에 있는 프로세스
▪
interruptible/uninterruptible priority
◦
User priority
▪
사용자 모드에 있는 프로세스
•
Clock handler
◦
주기적으로 인터럽트 발생
◦
모든 프로세스들의 우선순위 조정
•
스케줄링 기법
◦
높은 우선 순위 우선
▪
프로세서 사용량에 따라 우선순위가 주기적으로 변함
◦
MFQ 스케줄링 기법
•
우선순위 조정
◦
프로세서 사용 반영 (decay computation)
◦
우선순위 조정
Window System
•
Thread scheduling
•
Priority-based, Preemptive scheduling
•
32-level priority scheme
◦
Variable class: 1-15
◦
Real-time class: 16-32
•
MLQ scheduling
◦
각각의 우선순위 마다 큐(queue)를 가짐
◦
스케줄러(scheduler)는 높은 우선순위 큐부터 순차적으로 방문하며, 실행할 준비가 된 스레드를 찾음
•
스케줄링 기법
◦
스레드가 자신의 time quantum을 다 소비하고 나올때
→ 우선순위 하향 조정 (variable class의 경우)
◦
Wake-up 시 → 우선순위 상향 조정 (variable class의 경우)
▪
상향 정도는 스레드가 대기 중이었단 작업에 종속적
•
예)
키보드/마우스 I/O → 크게 상향
디스크 I/O → 약간 상향
Atomic Integer
AtomicInteger 란 원자성을 보장하는 Interger를 의미한다.
멀티 쓰레드 환경에서 동기화 문제를 별도의 synchronized 키워드 없이 해결하기 위해서 고안된 방법이다.
synchronized은 특정 Thread가 해당 블락 전체를 lock 하기 때문에 다른 Thread는 아무작업을 못하고 기다리는 상황이 되어 낭비가 심하다.
그래서 NonBlocking하면서 동기화 문제를 해결하기 위한 방법이 Atomic이다.
Atomic Interger 동작의 핵심 원리는 바로 CAS알고리즘(Compare and Swap)에 있다.
현재 쓰레드에 저장된 값과 메인 메모리에 저장된 값을 비교하여 일치하는 경우 새로운 값으로 교체하고, 일치 하지 않는 다면 실패하고 재시도를 한다.
Q. 다수 개의 변수가 관련되어 있다면 atomic integer보다는 monitor이나 semaphore 같은 방법이 더 낫지 않습니까?
atomic 변수 자체가 적은 수의 변수 때문에 block 하기 싫어서 만든 개념인 것으로 이해했습니다…