프로세스 스케줄링

 

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보다는 우선순위가 높다.