운영체제#6
LeeMir, 05 April 2021
2강 - Processes and Threads(이어서)
Traditional Unix Scheduling
- Multilevel Feedback Queue(priority queue)를 사용
- 매 Time Quantum마다 우선순위를 다시 계산함
- Bands
- 우선 순위
- Swapper(가장 높음)
- Block I/O device control
- File manipulation
- Character I/O device control
- User processes(가장 낮음)
- 우선 순위
BSD and SVR3 scheduling
- 기존 UNIX의 decay factor는 1/2였음
- 따라서 감소 속도가 너무 빨라 몇 번 수행 안해도 CPU Time이 전부 0이 되어버려 우선순위가 모호해짐
- BSD에서는 decay factor를
(2 * load_avg / 2 * load_avg + 1)로 사용
Linux Scheduling
- Scheduling Classes
- SCHED_FIFO
- First-In-First-Out real-time threads
- thread가 스스로 멈출 때까지 실행함
- SCHED_RR
- Round-Robin real-time threads
- SCHED_OTHER
- Other, non-real-time thread
- SCHED_FIFO
- O(1) : SCHED_OTHER Scheduling
- Active Queue와 Expired Queue가 존재
- 각 Thread는 우선순위가 높은 순서대로 Active Queue에서 실행돼 Timeslice를 모두 소비하면 Expired Queue로 이동
- 모든 Thread가 Active Queue에서 Expired Queue로 이동하면, Expired Queue가 Active Queue가 되고 Active Queue가 Expired Queue가 됨
- I/O-Bound Process에게 높은 우선순위를 주는 정책
- Task의 실행시간 대비 휴면시간 비율(sleep_avg) 유지
- Linux에서는 Thread를 Task라고 표현
- 우선순위와 Time Slice 계산식
effective prio = interactive 정도(sleep_avg로 계산) + 정적 우선순위(nice 값에 비례)새로운 Time Slice = effective prio에 비례
- Interactive Task는 Timeslice를 모두 소비한 후 Expired Queue로 가지 않고 다시 Active Queue에 넣음
- 문제점
- Nice 값이 Timeslice 절대값을 결정
- Nice = 0인 두 Task는 Timeslice 100ms를 가지며 100ms마다 문맥교환 발생
- Nice = 20인 두 Task는 Timeslice 20ms를 가지며 20ms마다 문맥교환 발생
- Nice 값의 차이가 Timeslice 차이에 비례하지 않음
- Nice 0과 1의 Timeslice는 100ms와 95ms
- Nice 18과 19의 Timeslice는 10ms와 5ms
- Timeslice와 Timertick의 정밀도 문제
- Timer Interrupt
- Interactive Task 우선 문제
- Sleep에서 깨어나면 무조건 Active Queue로 들어오는 문제
- Nice 값이 Timeslice 절대값을 결정
- Active Queue와 Expired Queue가 존재
- CFS(Complete Fair Scheduler)
- Con Kolivas가 O(1) 스케쥴러를 개선한 RSDL(Rotating Staircase Deadline Scheduler) 개발
- I/O-Bound와 CPU-Bound 프로세스 구분을 없애고 CPU 할당시간을 공평하게 분배
- Ingo Monlar가 CFS 스케쥴러 개발
- Runqueue를 없애고 RB-Tree 사용
- Jiffies와 HZ 상수를 이용하지 않고 나노초 단위로 동작
- 통계적 기법이나 휴리스틱을 이용하지 않음
- Nice 값에 비례하여 weight 할당, Task들의 weight로부터 Proportion of Processor를 계산
- 프로세서 실행 시간이 100ms일 때 nice값이 같은 task가 둘이면 Timeslice 50ms 할당, 4개이면 25ms 할당
- Nice 값 차이가 weight 차이와 비례
- Nice 0과 5의 weight는 1024와 335, 각 Task의 weight 비율은
1024 / (1024 + 335), 335 / (1024 + 335)로 약 3:1임 - Nice 5와 10의 weight 비율도 약 3:1임
- Nice 0과 5의 weight는 1024와 335, 각 Task의 weight 비율은
- Virtual Runtime : Timeslice와 Timertick의 정밀도 문제 해결
- 문맥교환 주기가 20ms, 두 Task가 45ms, 15ms씩 수행해야 하면, 실제로는 40ms, 20ms 수행함
- 이를 해결하기 위해 다음 스케쥴 주기에 각 수행시간(40ms, 20ms)에 Scale Factor(1:3)을 곱하여 Virtual Runtime을 구함
- 두 Task의 Virtual Runtime(40ms, 60ms)이 같지 않으면 뒤쳐진 Task(40ms)를 수행하여 시간을 보상
- Sleep에서 깨어난 Task의 Virtual Runtime을 현재 실행되고 있는 Task가 가진 Virtual Runtime중 가장 작은 값으로 설정
- CFS Run Queue
- RB(Red-Black) Tree 사용, Task를 Virtual Runtime 기준으로 정렬
- RB Tree에서 가장 작은 Virtual Runtime을 가진 Task(RB Tree에서 가장 왼쪽 Task) 실행
- Scheduling Latency Period
- 모든 Runnable Task가 적어도 한 번씩 실행되기 위한 Interval
- Task의 Timeslice와 Vruntime 갱신
Timeslice = (se->load.weight / cfs_rq -> load.weight) * periodVruntime += (NICE_0_LOAD / se-load.weight) * delta_exec- NICE_0_LOAD = 1024
- delta_exec = Task가 실제 CPU에서 실행된 시간
- Con Kolivas가 O(1) 스케쥴러를 개선한 RSDL(Rotating Staircase Deadline Scheduler) 개발
UNIX SVR4 Scheduling
- 160개의 Scheduling Queue가 존재하고 이를 세 Priority Class로 나눔
- Preemption points가 존재
- Preemption point에 도달하면 우선순위가 더 높은 Process가 있는지 탐색 후 있으면 그 자리에서 Scheduling을 다시함
Windows Scheduling
- 32개의 Priority가 존재
- 상위 16개는 Real Time Thread를 위한 Priority
- 하위 16개는 Valiable Thread를 위한 Priority
- Thread의 Priority를 동적으로 바꾸면서 실행
- 철학자 식사 문제
- 내가 포크를 들고 식사를 하면 내 왼쪽에 있는 사람과 오른쪽에 있는 사람은 식사를 하지 못하는 문제
- Readers and Writers 문제
- Reader는 많아도 상관 없으나 Writer는 한 명만 해야하는 문제
- 그리고 Write가 진행되는 동안 Read는 없어야 함