1. 스케줄링
스케줄링의 대상: ready/running상태에 있는 프로세스와 스레드. (kernel process는 스케줄링의 대상이 아님)
스케줄링 queue = ready queue (blocked queue에 있는 것은 스케줄링의 대상이 아님)
스케줄링 = 프로세스를 선택하는 스케줄링 알고리즘 + context_switch(디스패처)
종류: 장/단기 스케줄링, 선점/비선점 스케줄링
2. 스케줄링 알고리즘
시스템의 형태에 따라 기준이 달라진다.
기준의 평균치 최적화와 편차의 최소화를 고려하여 공평하게 해야한다.
선점/비선점 스케줄링
선점 스케줄링: running process로부터 CPU를 뺏을 수 있다. time slice나 priority에 의해서.
ex. Round-robin, Multi-level Queue, Multi-level feedback Queue
비선점 스케줄링: CPU를 빼앗지 못함. time slice가 없고, blocked될 때 CPU를 반환한다.
ex. FCFS(FIFO), SJF, priority algorithm,
3. 비선점 스케줄링
가. FCFS 스케줄링
프로세스 도착순서대로 CPU를 배정한다.
단점: 호위 효과 문제(긴 작업을 수행 하느라 여러 개의 짧은 일이 대기하는 비효율적인 상태)
사용: 장기스케줄러, time slice를 적용하지 않는 시분할 시스템
나. SJF 스케줄링
최단시간이 걸리는 작업에 CPU를 우선적으로 배정한다.(Shortest Job First)
평균대기시간(waiting time)에 있어서 가장 효율적인 알고리즘.
단점: 모든 프로세스의 CPU요구시간을 알기가 어려움, 단기 스케줄링 단계에서 구현하기 어려움
사용: 장기스케줄링을 하는 일괄처리 시스템(작업시간의 제한을 줄 수 있다).
다. 우선순위 알고리즘 스케줄링
각 프로세스 마다 가지고 있는 우선순위를 가지고 우선순위가 가장 높은 프로세스에게 CPU를 할당
우선순위가 같은 경우 FCFS로 처리된다
SJF는 우선순위 알고리즘의 특수한 형태이다.
내부적 우선순위: 제한시간, 기억장소 요구량, 사용하는 파일 수, 평균 CPU 버스트, 입출력 시행 비율
외부적 우선순위: 사용료, 정책적인 변수
단점: 기아 발생 (에이징으로 해결할 수 있다)
4. 시분할 시스템의 선점 스케줄링
1) time slice를 소진하여 CPU를 반납하거나 높은 priority의 프로세스에게 CPU를 빼앗긴다.
2) 연산위주 프로세스(CPU bound)/입출력위주 프로세스(I/O bound)에 따라서, 평균 CPU 반환시간(CPU burst)에 따라서, 실시간 프로세스/일반 프로세스에 따라서 동적 우선순위를 가진다.
3) I/O bound process에게 더 높은 우선순위를 주고, 실시간 프로세스에게 더 높은 우선순위를 준다.
4) time slice는 너무 작으면 context_switch overhead가 커지고, 너무 크면 비선점 스케줄링(FCFS)이 될 수 있으므로 평균 CPU 반환시간보다 약간 큰 것이 좋다.
5) non-preemptible kernel의 경우 선점 스케줄링을 사용해도 커널 모드에서는 선점이 일어나지 않는다.
가. Round Robin 스케줄링
실행중인 프로세스가 time slice를 다 쓰면 ready queue의 맨 뒤로 보낸다.
time slice를 다 쓰지 않았더라도 I/O 요청을 하면 blocked되고 CPU를 반납한다.
우선순위가 같은 프로세스들끼리의 스케줄링이며 priority가 높은 프로세스는 우선된다.
시분할 시스템을 위해 고안
나. 다단계 Queue 스케줄링
우선순위마다 ready queue를 가지고 있다.
일반적으로 fixed priority를 가지며 같은 level의 queue에서는 RR이나 FCFS를 사용한다.
시스템형, 대화형, 일괄처리 등의 프로세스 성격에 따라 우선순위를 부여한다.
다. 다단계 Feedback Queue 스케줄링
fixed priority가 불공평성이 있으므로 kernel이 상황에 따라 priority를 조정한다.
time slice를 소진해서 CPU를 반납할 경우 priority를 떨어뜨린다. (CPU bound process)
CPU를 많이 사용할수록 priority가 낮아지는 특징이 있다.
너무 오랫동안 CPU를 사용하지 못한 프로세스의 priority를 올려주기도 한다.
priority가 낮을수록 CPU를 많이 사용하는 프로세스이므로 경우에 따라서 time slice를 많이 줄 수도 있다.
5. Linux의 스케줄링 정책
가. SCHED_OTHERS (일반 사용자 프로세스)
time slice 존재, dynamic priority(kernel이 resource의 효율적 이용을 위해서 임의로 바꿀 수 있다)
real_time process는 super user만이 생성할 수 있다.
나. SCHED_RR (Round Robin)
time slice 존재. fixed priority(우선순위를 바꾸는 것이 가능하기는 하나 kernel이 임의로 바꾸지는 않음)
다. SCHED_FIFO
no time slice, fixed priority
☆ 아무튼 priority가 높은 process에게 CPU를 빼앗긴다 ☆
라. 그 외 특징
Linux에서는 blocked된 시간으로 priority를 조정하지만 Unix는 blocked된 이유로 priority를 조정한다.
실시간 프로세스는 매우 높은 priority를 가지며 fixed priority를 가진다. (다단계 queue 스케줄링)
커널 모드 프로세스는 커널에서 blocked되었다가 ready가 되면 resource를 차지하고 있는 것이므로 priority를 높여준다. (빨리 resource의 사용을 끝낼 수 있도록)
사용자 모드 프로세스는 Blocked되었다가 돌아오면 그 동안 CPU를 사용하지 못했으므로더 높은 priority를 가지게 된다.
마. 예) clock interrupt 처리
clock interrupt는 slow interrupt이므로 두 단계로 나눠서 처리된다.
그러므로 do_irg()함수를 수행하면 do_timer()함수와 timer_bh()함수를 호출하게 된다.
1) do_timer()함수
clock interrupt handler의 irq handler부분으로 interrupt를 disable시키고 동작하며 진짜 해야할 중요한 일들만을 처리
jiffy값을 증가시키고 하위처리기가 수행되도록 mask를 set하고 return한다.
2) timer_bh()함수
interrupt처리는 끝났지만 softirq 부분 처리가 남았으므로 bottom half 부분을 수행.
interrupt enable상태에서 동작.
다른 interrupt나 system call보다는 우선순위가 낮으나, user process보다는 우선순위가 높다.
