운영체제
9) 비례 배분 proportional share scheduling
앞에선 TAT, response time을 스케줄링의 평가 척도로 정했다. 이들과 달리 CPU 사용의 일정 비율을 보장하는 목적의 척도도 존재한다.Introduction
Proportional-share scheduling(비례 배분 스케줄링)
- fair-share(공정배분)이라고도 한다
- 각 유저는 프로세서의 몫이 할당 된다
- CPU 사용시간을 일정량 얻을 수 있게 보장한다
- 공정한 점유율보다 더 많은 자원을 가진 사용자에게 더 적은 자원을 제공하고 더 적은 자원을 가진 사용자에게 더 많은 자원을 제공하기 위해 사용량을 모니터링하는 것
- TAT나 response time 측면에서 최적은 아니다
Lottery scheduling
- 랜덤하게 다음 프로세스를 결정
Stride scheduling
- lottery 기법의 약점을 보완
기본 개념: 티켓이 지분
- 티켓
- 자원에 대한 프로세스에게 할당될 몫
- 전체 티켓과 프로세스가 소유한 티켓 개수의 비율이 몫이다
- 많은 티켓을 가질수록 많은 기회를 얻는다
Lottery scheduling
핵심
- 티켓을 무작위로 뽑는다
특징
- 확률적 공정성을 지닌다
- 각 티켓이 선택될 확률은 공정하다
- 예측되는 자원 할당량은 자신이 지닌 티켓의 양에 비례한다
- starvation을 막기위해 각 작업들은 적어도 하나의 티켓을 가진다
- 정확한 예측 분배량을 보장할 수는 없다(확률적이라서)
- 구현이 쉬움
과정
Ex
A는 75개의 티켓 => 75퍼의 cpu
B는 25개의 티켓 => 25퍼의 cpu
=> A는 (0~75) B는 (75~99)의 번호의 티켓이 나오면 cpu가 할당된다- 스케줄러는 티켓을 뽑는다 (85)
- B에게 다음 CPU 할당
- 반복
- 원하는 비율을 정확히 보장하지는 않음.
- 작업이 길어질수록 원하는 비율을 달성할 가능성 높아짐
Mechanisms 기법
Ticket Currency
- 사용자가 티켓을 자신의 화폐가치로 자유롭게 할당할 수 있도록 한다
- 지역 화페 비스무리
- 시스템은 자동적으로 화폐가치를 변환한다
Ticket Transfer
- 만약 너가 block이라 놀면 다른애한테 티켓을 줄 수 있어!
- 일시적으로 티켓을 다른 프로세스에 넘겨줄 수 있다
- 클라이언트/서버에서 유용!
클라이언트가 서버에게 자신의 티켓을 줘서 빨리 작업이 완료될 수 있게 할 수 있다 => 서버는 더 많은 CPU 시간을 얻을 수 있다, 클라이언트가 놀고있을때
- 클라이언트/서버에서 유용!
Ticket Inflation/Deflation
- 프로세스는 일시적으로 자신이 소유한 티켓의 수를 늘리거나 줄일 수 있다
- 전체 시스템의 티켓 총량은 보존
- 서로 신뢰할 수 있는 프로세스끼리 가능!
- 어떤 프로세스가 많은 CPU시간을 필요로 한다면 시스템에 알리고 혼자 티켓의 양을 늘릴 수 있다
구현
간단하다, 난수 생성과 프로세스의 집합을 표현하는 자료구조, 티켓 전체 개수만 있으면 댐
1. 티켓의 숫자를 난수로 생성
2. 리스트에서 티켓을 가진 작업을 찾는다어캐 더 효율적으로??
2. 찾는 과정을 효율적으로
HOW??리스트를 내림차순으로 정렬해 검색횟수를 최소화하자
Fairness
U: unfairness metric(불공정 지표)
- 첫번째 작업이 끝나는 시간을 두번째 작업이 끝나는 시간으로 나눈다
U = 첫번째 작업 완료 시각 / 두번째 작업 완료 시각
Ex
A: 10sec에 끝
B: 20sec에 끝
U= 10/20 = 0.5-
U가 1에 근접하면 두개의 작업이 거의 같은 시간에 끝나는 것
- U가 1이되면 스케줄러는 완벽하게 공정하게 스케줄링 한 것
runtime에 따라 unfairness는 바뀔 수 있다.
1.
A: 10sec에 끝
B: 20sec에 끝
U= 10/20 = 0.5
2. 1을 두번 반복
U= 30/40 = 0.75Dark side of lottery scheduling
강점
- 간단한 알고리즘
- 이해하기 쉽다
- dynamic operation들에게 적용이 된다
단점
- 확률적으로만 보장해줌
- 짧은 작업에 대해서는 심각한 정확도
- 응답 시간의 변동이 심함
즉 정확한 비율을 보장 못한다!
그럼 어떤 방법을 사용할까??
그리고 티켓은 어떻게 나누나??Stride scheduling(보폭 스케줄링)
Stride
-
전체 티켓 수 / 프로세스의 티켓 수
-
EX)
전체 10000티켓 A = 100 ticket B = 50 C = 250 stride A = 10000/100 = 100 B = 10000/50 = 200 A = 10000/250 = 40 -
티켓에 반비례, 선택 사이의 간격을 나타냄
Pass
- 각 프로세스의 진행률을 추적하는 가상 인덱스
- 프로세스가 실행 될 때마다 해당 프로세스의 stride 값만큼 증가시켜 얼마나 CPU를 사용했는지 추적
스케줄러는 pass 값을 보고 가장 작은 pass를 가진 프로세스를 선택
Key mechanism of stride scheduling
방법
- 가장 작은 pass를 가진 프로세스가 선택됨
- 만약 같은 pass 값을 가진 프로세스가 있다면, 랜덤하게 그것들 중 고름
- 프로세스를 실행하고 해당 프로세스 값의 pass 값을 stride 만큼 증가시킴
정확히 티켓에 비례해서 CPU 권한을 얻음
lottery와 비교해서
강점
- 보장이 잘됨
- 짧은 작업에도 좋은 정확성
- response time이 일관적임
약점
- dynamic operations이면..?
- 자원 monopoly problem(독점 문제)
- 전역 변수를 추가해야함
- 전체 티켓 수, stride, pass
Monopoly problem
만약 stride scheduling이 진행 중일때, 새로운 작업이 들어오면??다른 작업들보다 pass값이 낮은 새로 들어온 작업이 CPU를 독점한다
요약
Lottery scheduling
- 랜덤한 간단한 알고리즘
- dynamic operation에 대해 지원함
- 낮은 정확성, time 척도들의 들쑥날쑥~
Stride Scheduling
- deterministic(결정론적)
- 높은 정확도, time 척도들의 일관성
- dynamic operation들에 대해선 복잡해
한계
- 두 기법 모두 입출력을 고려 안함
- 티켓 배분에 대한 의문
Compensation Ticket
어떤 작업이 입출력만 한다고 CPU를 많이 못썼는데 어떡해.. 티켓만큼 CPU를 못 썻어... 근데 pass값 증가해서 CPU 못써 ㅠㅠCPU 사용시간을 기록해 이 후 사용시간을 보장해준다
정리