티스토리 뷰
Scheduling이란?
: ready queue에서 실행시킬 프로세스를 하나 선택한다. dispatch는 고른 프로세스를 CPU에 올리는 것인데 이 두개를 합쳐서 큰 의미로 scheduling이라고 한다.
Scheduling의 목적
Utilization : CPU를 최대한 일하게 한다.
Throughput(처리율) : 시간당 일의 양, 즉 효율을 최대한 높인다.
Turnaround Time : 수행 요청부터 수행 끝까지의 시간을 최소화한다.
Fairness : 각 task가 CPU의 공평한 몫을 나눠갖게 한다.
FIFO(FCFS): first in first out, first come first served
장점: 공평하다
단점: 일이 오래걸리는 사람이 먼저 시작하면 waiting time이 너무 커지고, average waiting time도 길어진다.
SJF(Shortest Job First)
- Preemptive(선점형) vs Non-preemptive(비선점형): 새로운 job이 들어왔을 때, 기존에 실행중이던 job보다 짧다면 멈추고 먼저 실행한다면 preemptive, 원래 실행중이던 job을 계속 실행한다면 non-preemptive이다.
그런데 실제로 프로세스의 수행시간을 알기가 어렵다...
예측과 실제가 꽤 많은 차이가 있었다.
그래서 이는 더이상 사용하지는 않는다.
Round Robin Scheduling
새의 종류인 robin이 새끼한테 모이를 줄 때 엄청 조금으로 나눠서, 여러바퀴 돌려서 모이를 주는 모습에서 따온 round robin!
현대의 운영체제에서 priority+ round robin을 사용하고 있다고 한다.
하지만 교체 텀을 너무 짧게 두면 교체하는데 시간이 너무 오래걸릴 수도 있다. 적절한 시간을 설정해야 한다. 이 교체하는 텀을 'time quantum' 이라고 한다. 주로 10~100ms로 잡는다고 한다.
O(N) Scheduling
O(N) Scheduling은 time-shared(시분할) interactive system을 구현하는 가장 간단한 방법이라고 한다.
'recredit' 방식을 통해서 waiting 상태에 있는 task의 interactivity를 높인다.
Priority Level
O(N) scheduling을 이해하기 위해서는 Priority Level을 알아야 한다.
Linux에서의 Priority Level은 140 level인데, real-time task는 1~100, normal task는 101~140 level을 갖는다.
101~140 level의 normal task를 -19~20의 범위로 바꿔서 nice value 라고도 부른다.
1에 가까워질수록 중요하고 140에 가까워질수록 덜중요하다.
Credit
Goodness
시행 방법
단점
must-walk queue
recrediting walks process table
scalability problem in multi-core
O(1) Scheduling
Priority Scheduling
Fair-Share Scheduling
Completely Fair Scheduler(CFS)
Virtual Runningtime, Time Slice
Enque와 Deque
Linux에서의 Scheduling
- 발전 과정
[출처]