OS_3W_7,8,9
- Scheduling: Introduction
- Scheduling Metrics(평가 항목)
- Turnaround Time(반환 시간) - 도착 후 끝나는 시간
- Response Time(반응 시간) - 도착 후 처음으로 스케줄되는 시간
- Fairness(공정성)
- Scheduling
- FIFO
- SJF(Short Job First)
- STCF(Shortest Time to Completion First)
- RR(Round Robin)
- Scheduling Metrics(평가 항목)
- Multi-Level Feedback Queue
- Approximate SJF/STCF - 반환시간 줄이기
- RR - 반응시간 줄이기
- MLFQ의 문제
- Starvation > 부스트(5번)
- game the scheduler > allotment, 할당량(4번)
- Proportional Share(Fair Share)
- Lottery - 비결정적
- 티켓 - 양도, inflation, 링크드 리스트 구현
- unfairness matric
- Stride - 결정적
- pass, stride
- CFS - Linux
- Lottery - 비결정적
7 Scheduling: Introduction(1/3)
운영체제와 같은 시스템 소프트웨어에서는 메카니즘과 정책 사용
프로세스 메카니즘 예시가 switch()
switch는 old와 new의 프로세스 교체
레지스터의 내용을 pcb 내용으로 저장/복원하면서 교체함
7.1
여기서 배울 것은
__새로운 프로세스를 어떻게 결정할 것인가! = 스케줄링 정책(policy)__
워크로드 : 프로세스가 동작하는 일련의 행위
실행 중인 프로세스나 job에 대해 다음을 가정함
1. 모든 작업은 같은 시간 동안 실행됨
2. 모든 작업은 동시에 도착함
3. 작업은 일단 시작하면 최종적으로 종료될 때까지 실행된다.
4. 모든 작업은 cpu만 사용함(입출력 시행하지 않음)
5. 각 작업의 실행 시간은 사건에 알려져 있음.
비현실적이나 일단 가정함, 가정은 점차 완화해감
7.2
정책의 측정하는 기준 = 스케줄링 매트릭(평가항목)
3가지가 있음
반환시간, 반응시간, 공정성
> 반환시간은 퍼포먼스(성능) 측면에서의 평가 기준임
다른 평가 기준으로 공정성이 존재함 (ex: jain's fairness index 지표)
+ 스케줄러는 전체 시스템의 성능을 극대화하기 위해 몇몇 작업에는 실행기회를
주지 않을 수 있음 결과적으로 공정성은 악화됨
반환시간 = completion - arrival (끝난시간 - 도착시간)
## 7.3 FIFO(선입선출)
안좋은 케이스 : 긴 시간이 걸리는 작업이 앞에 올 경우, 뒤에 있는 빨리 끝날 수 있는 작업들이 오래 기다림
(convoy effect : cpu를 많이 필요로 하지 않는 프로세스들이 cpu를 오래동안 사용하는 프로세스가 끝나기를 기다리는 현상)
## 7.4 SJF(최단 작업 우선, Shorest job first)
가장 짧은 실행 시간을 가진 작업을 먼저 실행함
모든 작업이 동시에 도착한다면 SJF가 Optimal(최적)의 스케줄링 알고리즘임
그러나 2번 가정을 완화하면
__일단 시작한 작업은 멈출 수 없기 때문에__ 긴 작업이 실행 중에 짧은 작업들이 도착한다면
convoy 문제 재발
## 7.5 STCF(최단 잔여시간 우선, Shorest time-to-completion first)
가정 3을 완화함. 이제 작업은 실행 도중에 중단 가능함
앞의 sjf는 noe-preenptive 스케줄러라 실행 중인 작업 중지하고 다른 작업 실행 불가능함
PSJF(Preemptive shortest job first)라고도 함
이 스케줄러는 현재 실행 중인 작업의 잔여 실행 시간과 새로운 작업의 잔여 실행 시간을 비교해 잔여 시간이 가장 작은 작업 선택해서 스케줄함.7 Scheduling: Introduction - response time(2/3)
7.6 새로운 metric(평가기준) : 반응시간(reasponse time)
__!!! 반환 다음이 반응임!!!
!!! 반환,반응 둘다 도착시간을 뺌 반환은 끝날때, 반응은 첫실행할때__
> TIME(response = firstrun - arrival) // 첫실행 - 도착
SJF는 반환시간 면에서는 우수하나 반응시간 면에서는 좋지 않음
반대로 RR은 반응시간 면에서는 최적이나 반환시간은 좋지 않음
타이머가 주기적으로 인터럽트를 걸어서 트랩 걸리고 트랩 핸들러로 갔다가 스케줄링에 따라 스위치되는 과정임
그래서 실제로는 트랩 처리하면서 거치는 모든 과정 역시도 시간에 포함됨
RR은 fair함
7.7 Round Robin(- 타임 슬라이싱)
일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환
타임 슬라이스함
7 Scheduling: Introduction - I/O(3/3)
7.8
IO요청이 들어오면 Blocked 상태가 되고 다른 ready인 상태인 프로세스가 running이 된다.
overlap은 io요청이 들어와서 cpu가 blocked되었을 때 ready 상태였던 다른 프로세스를 실행해서 반환시간(끝내는시간)을 줄이자, 성능 향상
STCF는 PSTF, Preemptive해서 끝나지 않아도 중도스위치?가능함
전체적인 흐름을 보면 그림참고
1. 프로세스 A에서 IO요청
2. 트랩걸림, 트랩핸들러로 PC이동 커널이쥬, 시스템콜 처리
3. 시스템콜 처리하면서 A가 Blocked됨
4. 스케줄링 > 스위치 B로 함
5. B 실행하다 A에서 요청했던 IO요청이 끝나면 IO가 CPU에 인터럽트 건다
6. 트랩걸림, 트랩핸들러, 인터럽트 처리
7. 인터럽트 처리하면서 A가 Ready상태가 됨
8. 스케줄링함, 여기서는 스케줄링 정책, Policy가 STCF라서 남은 작업이 더 적은 A를 선택함
9. A가 running됨8 Scheduling: The Multi-Level Feedback Queue(1)
https://www.youtube.com/watch?v=_xYL6vM9iHk&list=PLGgVuvaPty_2I_eaJbiYggCBsKt5gU9rx
MLFQ, 멀티 레벨 피드백 큐
반환시간을 최적화하면서, 반응시간도 최소화하자 (SJF/STCF && RR)
SJF/STCF는 사실 작업의 실행시간을 알고있다는 전제가 깔리는데 현실적으로 말이 안됨
작업의 실행시간에 대한 선행 정보 없이 반환 시간을 최소화하고, 반응시간도 최소화하자
> 긴일, 짧은일을 어떻게 구분할것인가? MLFQ는 일단 실행시켜서 타임슬라이스에 따라 처리해보자
# 8.1 MLFQ 기본 규칙
룰1. 높은 우선 순위 큐 안의 작업 먼저 실행
룰2. 우선순위 같으면 RR하게, 페어하게, 타임슬라이싱해서 실행
# 8.2 우선순위 변경
룰3. 작업이 시스템에 들어오면 가장 높은 우선순위 큐에 자리함
룰4-1. 작업이 타임 슬라이스를 모두 사용하면(긴 작업) 우선순위 한단계 하락
룰4-2. 작업이 타임 슬라이스를 전부 사용하지 않고 먼저 반납, 양도하면 우선순위 유지
> 긴 작업은 우선순위 낮아지고, 짧은 작업은 우선순위 높음
## IO가 섞인 2개의 Job
작업을 하다 IO가 들어오면 해당 잡은 blocked 되면서 우선순위 큐에서 빠진다. 이 때 timeout은 아니므로 우선순위가 하락하지 않는다!!!
다른 큐에 남아있는 우선순위 작업을 실행하다가 다시 B가 running이 되면 이전의 순위큐에 다시 B가 들어옴, 우선순위에 따라 작업 반복한다.8 Scheduling The Multi Level Feedback Queue(2))
## MLFQ의 문제점
1. Starvation
2. game the scheduler
### starvation
기아 상태, 낮은 순위에 있는 작업은 굶어죽음, 실행되지 못함
룰추가,
룰5 : 일정 시간 S가 지나면 시스템의 모든 작업을 최상위 큐로 이동시킴, 부스트!
> 기아 해결
그러나 S를 얼마로 해야할지에 대한 문제는 존재, 부두 상수라고 함 알수없다는...
### 게임스케줄러
사용자가 스케줄러의 허점을 이욯해 자신에게 유리하게 동작시키기 가능,
매우 짧은 IO 요청을 실행시켜 우선순위가 유지되도록 조작
타임 슬라이스가 끝나기 전에 IO 요청을 하는 것
룰추가
룰4 : 주어진 단계에서 시간 할당량을 소진하면 우선순위 강등 (Allootment) - 타임 슬라이스가 아니라 할당량제로
+ 낮은 우선순위에 더 긴 타임슬라이스를 부여도 가능, 각 큐마다 다른 타임슬라이스 부여9 Scheduling: Proportional Share(1/4)
Proportional share, 비례배분, 공정 배분이라고도 함
목적 : 반환 시간이나 반응 시간을 최적화하는 대신 스케줄러가 각 작업에게 cpu의 일정비율을 보장하자!
lottery 스케줄링, 다음 실행될 프로세스를 랜덤으로 결정한다. 비율에 따라 티켓을 더 많이준다.
## 9.1 기본 개념 : 티켓이 지분이다.
확률을 기반으로 한 티켓의 배분
## 9.2 추첨 기법(티켓 매커니즘)
티켓 currency(화폐)의 개념 : 사용자가 티켓을 자신의 화폐 가치로 자유롭게 할당가능
시스템은 자동적으로 화폐 가치를 변환
로컬 currency를 글로벌 currency로 변환함
### 티켓 transfer(양도)
프로세스는 일시적으로 티켓을 다른 프로세스에게 넘겨주기 가능,
클라이언트와 서버 환경에서
1. 클라이언트 프로세스는 서버에게 자신을 대신해 특정 잡을 해달라고 요청
2. 잡이 빨리 완료되도록 클라이언트는 서버에게 티켓 전달
3. 서버가 요청받은 잡 처리
4. 서버는 티켓 다시 클라이언트에게 되돌려줌
### 티켓 inflation
프로세스는 일시적으로 자신이 소유한 티켓을 추가발행하거나 버리기 가능
그러나 서로 신뢰하는 프로세스 관계에서 가능!
### 9.3 구현
+ 링크드 리스트로 구현됨
+ 랜덤 숫자 x가 선택
+ 리스트를 순회하며 카운터 값을 이용해 당첨자 찾음
3. current에는 A,B,C 리스트 들어있음
4. x가 current_A의 티켓 숫자보다 큼, cnt는 100
5. 다음 current_B의 티켓 숫자도 더함, 여전히 x가 큼, cnt 150
6. 다음인 C가 당첨이다.
> 하나씩 다 도는게 아니라 리스트!단위로 보유한 티켓 숫자로 당첨 프로세스 찾음!9 Scheduling: Proportional Share(2/4)
Unfairness matric, 불공정 지표를 평가기준으로
u = 첫번째 작업 종료시간 / 두번째 작업 종료 시간
작업 길이가 짧으면 불공정 정도가 낮음
작업 길이가 길수록 1.0에 수렴함
결론
> 작업이 충분한 기간 동안 실행되어야 로터리(추첨, 랜덤) 스케줄러가 원하는 결과에 가까워짐9 Scheduling: Proportional Share(3/4)
# 9.6 왜 결정론적 방법을 사용하지 않는가?
추첨 스케줄링은 티켓을 작업에게 나누어주는 것인데 몇 개씩 할당해야 하는 문제 여전히 있음
그래서 고안된 스케줄링 방법이
# Stride 스케줄링(결정론적 공정 배분 스케줄러, Deterministic fair-share)
보폭 스케줄링은 시스템의 각 작업이 stride, 보폭을 가지고 있음
보폭은 자신이 가지고 있는 티켓 수에 반비례하는 값임
임의의 큰 값 MAX를 각자의 티켓 수로 나눈 값이 각자의 발걸음, 보폭 값임
프로세스가 실행될 때마다 패스 값이 보폭만큼 증가함 > 얼마나 CPU를 사용했는지 추적
스케줄러는 보폭과 패스값을 사용해 어느 프로세스를 실행시킬지 결정함.
의사코드
1. pass 값이 최소인 클라이언트 선택
2. 선택된 프로세스에 자원을 타임 슬라이스만큼 실행
3. 다음 패스+=보폭
> 추첨 스케줄링은 정해진 비율에 따라 확률적으로 cpu 배분
> 보폭 스케줄링은 각 스케줄링 주기마다 정확한 비율로 cpu 배분
## 그렇다면 왜 추첨 스케줄링을 써야 하는가?
보폭 스케줄링이 훨씬 정확한 비율.
그러나 추첨 스케줄링은 상태 정보가 필요없다는 강점.
만약 스케줄링 중간에 새로운 작업이 도착할 경우,
새로운 프로세스 추가해야 하는 경우들에 훨씬 강점.
(한글교재 144p)9 Scheduling: Proportional Share(4/4)
이거 일단...나중에..퀴즈
CPU 스케줄링 1
2. (100 + 110 + 110) / 3 = 106.66666 = 106.67
A,B,C
A: 100
B: 100+20 - 10
C: 100+20+10 -20
3. C,B,A 순서
A: 110
B: 30
C: 10
4. A,C,B,잔여 A
A: 120
B: 40 - 10
C: 20 - 10
160/3
MLFQ
큐우선순위 Q2 > Q1 > Q0
1. Preemption 발생하지 않는 경우
(즉 우선 순위가 높은 Job이 새로 들어와도 실행 중인 Job의 time slice를 채운다.)
0-10 : Q2 - A 타임아웃 강등(Q1)
10-20 : Q2 - A 타임아웃 강등(Q0)
20-30 : Q2 - B 20에서 진입, 타임아웃 강등(Q1)
30-40 : Q2 - C 종료
40-50 : A는 우선순위 Q0이고 B가 더 우선순위 높음, Q1 - B 실행 후 종료
---
2. Preemption이 발생하는 경우
(즉 우선 순위가 높은 Job이 새로 들어오면 실행 중인 Job을 중지하고
우선 순위가 높은 Job을 먼저 실행한다.
중지된 Job이 나중에 실행될 때 time slice는 새로 주어진다.)
0-10: A 타임아웃 강등(Q1)
10-12 : B 진입, Q2 - B 실행, A 중지
12-22 : C가 15에서 진입했으나 둘다 같은 우선순위라 B 타임아웃 강등(Q1)
22-32 : Q2 - C 실행, 종료
32-42 : A,B 둘다 같은 우선순위, Q1 - A 실행, 타임아웃 강등(Q0)
42-52 : 우선순위 높은 B 실행, 완료
CPU 스케줄링2
대화형 Job이란 IO요청이 많은 작업임?
아닌듯? 걍 긴 작업인듯?질의응답
- 게이밍은 강등시키기 부스팅은 위로 올리는 서로 반대작업임
- 할당량 > 게이밍 방지, 강등시키기 // 부스팅, starvation 방지, 위로 올리기
- 처음보는 작업은 일단 최상단에 위치, 일단 숏잡으로 취급해보고 아니면 내리겠다. 모르면 숏잡으로 디폴트 취급
- 대화형잡은 cpu를 짧게 쓰고 io요청을 반복함, 숏잡이 지속적으로 반복되는 작업
- 이런게 많이 들어오면 롱잡인 아래 단계인 잡들은 실행될 수가 없음
- 그래서 일정 주기 S마다 부스팅한다.
- 퀴즈는 잘이해해서 1트만에 풀도록, 이해해서 이유까지 설명가능하게
- 대화형잡은 숏잡이 많이 존재한다로..봐야..
- 5번규칙은 모든 작업들을 최상위로 전부 다같이 올라감
- RR은 FIFO 기반, 먼저 들어온거!
MLFQ풀이, 원노트그림참고
1. 들어오면 레디큐 들어감, 스케줄링, A가 RUNNING
2. A가 타임아웃, 인터럽트, CPU에서 A 실행되다가 타임아웃, 커널이 개입해 레디큐의 A를 강등시킴, 등록
3. 스케줄링, 레디큐의 A가 다시 제거, RUNNING
4. Q1에서 A 실행
5. t=12일때 B가 도착, 커널에 진입, 커널이 B를 ready상태로 레디큐의 최상단에 세움
(다음문제switch함수호출, save/restore 자동실행)
6. t=15일때 c가 도착, 위랑 같음
(switch함수호출)
7. A를 마저 실행, 타임아웃, 강등
8. 레디큐에서 스케줄링, b가 running
9. b가 타임아웃, 강등, c를 레디큐에서 제거하고 running으로
10. 코드끝내기 전에 return, exit == c가 끝나면 exit
11. 유저프로그램 끝나고 커널로 들어감, 커널이 뒷정리
12. 스케줄링, b 스케줄
13. b도 끝나고 exit
14. A
---
차이 진입할때 switch()
커널의 사건들도 알아야함!!!
원노트 MLFQ 퀴즈
khj