스케줄링
스케줄링이랑 CPU에서 어떠한 프로세스가 실행되어야 할지 결정하는 작업이다. 적절한 스케줄링을 해야만 컴퓨터 작업의 효율성이 향상되고 반환시간이 단축된다.
스케줄링을 하는데 고려해야 할 요소는 CPU 이용률 , 처리량, 반환시간,대기 시간, 응답시간이 있다. 스케줄링은 수행되고 있는 프로세스를 뺏을 수 있냐 없냐에 따라서 선점/비선점 스케줄링으로 구분된다.
비선점 스케줄링
비선점 스케줄링이란 현재 실행되고 있는 프로세스의 작업을 중단시키고 CPU의 이용을 빼앗을 수 없는 스케줄링이다. 대표적으로 FCFS, SJF, HRN, 우선순위 방식이 있다.
FCFS (First Come First Served)
도착한 순서대로 스케줄링하는 가장 간단한 스케줄링 방식이다. 구현이 매우 쉽지만 우선순위가 높아 먼저 처리해야 하는 프로세스가 생겨도 먼저 처리할 수 없는 단점을 가지고 있다. 위의 그림에서 P0,P1,P2,P3순으로 도착 했으므로 순서대로 할당한다.
SJF(Shortest Job First)
SJF는 가장 짧은 서비스 시간을 갖는 프로세스를 가장 먼저 실행하는 스케줄링이다. 위 그림에서는 서비스 시간이 가장 짧은 순서대로 p1, p0 ,p3,p2 순으로 실행되며 모든 스케줄링 중에서 평균 반환시간이 가장 짧은 스케줄링이다. 하지만 짧은 수행시간을 가지는 작업이 계속 들어올 경우 상대적으로 긴 작업이 계속 뒤로 밀려나는 기아 현상이 발생할 수 있다.
HRN(Highest Response Ratio Next)
HRN은 SJF의 기아문제를 해결하기 위한 스케줄링 방법으로 (서비스 시간 + 대기시간) / 서비스 시간으로 나눈 값을 우선순위로 결정하여 이 값이 작은 프로세스를 우선적으로 수행한다.
우선순위 ( 비선점)
프로세스의 우선순위를 기준으로 우선순위가 높은 프로세스 순으로 스케줄링하는 기법이다. 비선점이기 때문에 높은 우선순위의 프로세스가 들어와도 현재 실행하는 프로세스는 계속 실행한다.
선점 스케줄링
선점 스케줄링은 CPU의 이용을 빼앗을 수 있는 스케줄링 기법이다. 비선점과 다르게 수행되고 있는 현재 프로세스를 중단시키고 다른 프로세스를 먼저 실행할 수 있다.
RR(Roudn Robin)
라운들 로빈 방식은 시분할 방식으로 프로세스를 time slice만큼만 실행하도록 하는 방식이다. 위에서의 time slice 간격은 4로 4만큼 수행한뒤 다른 프로세스에게 cpu 이용을 넘겨주게 된다. 이 방식을 통하여 사용자는 프로세스 여러개가 동시에 수행되는 것 처럼 느낄 수 있다.
SRT(Shortest Remaining First)
SJF의 선점형 방식으로 SJF와 다른점은 더 짧은 작업이 들어왔을 경우 CPU를 빼앗을 수 있다는 점이다.
Multilevel Queue(다단계 큐)
다단계 큐는 cpu의 ready 큐를 우선순위에 따라 여러개로 나눈 것이다. 각 큐는 독립적인 스케줄링 알고리즘을 가지고 각 큐에 대해 Cpu time을 적절히 할당하여 수행한다. 대표적으로 Foreground /Background 큐가 있는데 Foreground 큐는 RR 방식, Background 큐는 FCFS 방식 으로 스케줄링하며 80: 20의 CPU 이용시간을 가지고 작업을 처리하도록 구현한다.
Multilevel Feedback Queue
다단계 피드백큐는 다단계 큐가 서로 다른 큐로 이동할 수 있는 큐의 구조이다. 위의 그림에서 quantum 즉 timeslice가 8/16인 큐와 fsfs인 큐가 존재한다. 프로세스는 처음 첫번째 큐에서 8의 큐를 할당받고 프로세스를 수행한다. 만약 다 완료하지 못하면 16인 큐로 이동하고 이마저도 완료하지 못하면 fcfs로 이동하여 순차적으로 처리하게 된다. -> 이는 aging 기법을 이용한 것으로 프로세스가 시간이 지날수록 더 많은 수행시간을 가지게 함으로써 작업을 마칠 수 있도록 한다.
실시간 스케줄링
실시간 스케줄링은 작업이 마감시한 내에 완료되도록 스케줄링하는 것이다. 이 스케줄링을 적용하는 시스템은 다음과 같은 시스템들이 있다.
- 경성 실시간 시스템 - 작업이 마감시간내에 완료되지 않으면 치명적인 시스템
- 연성 실시간 시스템 - 작업이 마감시간내에 완료되지 않아도 되지만 시간이 지날수록 손해가 점점 커지는 시스템
RM(Rate Monotonic) 알고리즘
작업의 크기와 개수가 알려진 프로세스들이 주기적으로 발생하는 환경에서 사용한다. 프로세스는 각자 독립적이고 주기적으로 수행되는 환경에서 각 프로세스의 마감시한은 각자의 주기와 같다고 가정하고 주기가 짧을수록 높은 우선순위를 받게 된다. -> 주기가 짧을수록 프로세스가 다시 발생하므로 빨리 수행해야 한다. RM은 선점 스케줄링 방식으로 높은 우선순위 작업에게 CPU를 뺴앗길 수 있다.
EDF(Earlist Deadline First) 알고리즘
EDF 알고리즘은 프로세스의 마감시한이 가까워질수록 우선순위를 높게 부여하는 선점 방식의 동적 스케줄링이다. EDF 기법은 우선순위에 의해 CPU를 뺏길 수 있다. 한 프로세스의 실행이 완료되면 마감시간이 가장 가까운 것을 찾아 스케줄링 한다. 모든 프로세스가 주기적일 필요가 없으며 주기가 있을 경우 마감시간을 주기로, 그렇지 않을 경우 마감시간을 명시적으로 알려주어야 한다.