CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 한다.
전에 언급했지만 , 한번에 여러개의 프로세스들이 동시 다발적으로 상태가 변하고 하기 때문에,
이때 대기하는 줄을 큐라고 하였다.
그럼 , CPU는 어떻게 프로세스들을 순차적으로 대기시키고 수행하는 걸까??
이때 사용되는 알고리즘을 CPU Scheduling라고 한다.
먼저 , 선점과 비선점에 대해 간단히 알고 적고 넘어가자.
선점(Preemptive)
프로세스가 실행 중 일때 , 인터럽트 혹은 cpu점유시간 같은 특정 상황이 아니더라도 ,
다른 프로세스에서 해당 CPU를 강제로 점유할 수 있는 것을 의미한다.
비선점(Non-preemptive)
프로세스가 인터럽트 혹은 cpu점유 시간 초과 등의 특정 상황이 발생한 경우에만 CPU를 점유할 수 있는 것을 의미한다.
스케줄링 알고리즘은 여러가지가 있다.
그럼 이중에 어떤것이 효율적인지 판단할 수 있는 기준이 필요한데 그 기준으로는
- CPU Utilization(이용률) → CPU가 얼마나 사용되는지.
- Throughput(처리율) → 단위 시간 당 처리하는 작업 량.
- Turnaround time(반환 시간) → 프로세스의 모든 작업을 수행하는데 걸린 시간이다.
- Waiting time(대기 시간) → CPU를 점유하기 위해서 ready queue에서 기다린 시간을 말한다.(다른 큐에서 대기한 시간은 제외한다고 한다.)
- Response time(응답 시간) →일반적으로 대화형 시스템에서 입력에 대한 반응 시간을 말한다.
가 있다.
CPU Scheduling Algorithms
1) First-Come, First-Served(FCFS)
먼저 온 프로세스가 먼저 CPU를 점유하는 방식으로 비 선점 방식 이다.
비 선점 이므로 , 가장 먼저 온 프로세스의 처리 시간이 길수록 , 뒤에 있는 프로세스들은 먼저 들어간 프로세스가 끝날 때까지 기달 려야 하므로 대기 시간이 그만큼 길어질 수 있다 .
2) Shortest-Job-First(SJF)
작업 시간이 가장 짧은 프로세스가 먼저 수행되는 것을 말하며 , 선점 비 선점 둘 다 가능하다.
하지만 , 프로세스는 실행되어봐야 얼마나 걸릴지 알기 위해서는 실제로 수행되어 측정 되어져야 하며, 이마저도 실제 수행되면서 많은 변수가 존재할 수 있으므로 비현실 적이다.
(물론 아예 불가능한 것은 아니다.)
3) Priority
우선 순위가 높은 프로세스가 먼저 선택되는 방식으로 선점 비 선점 방식 둘 다 가능하다.
단 , 대기하는 프로세스 보다 우선 순위가 높은 프로세스가 계속 ReadyQueue에 들어오면 ,
계속 할당 받지 못하고 기다리기만 하는 현상이 발생될 수 있는데 이를 “기아” 라고 한다.
이를 방지하기 위한 기법으로 aging이 있는데 , 이는 기다리는 동안 일정 시간이 지나면 우선 순위를
조금씩 높여주는 기법이다.
4) Round-Robin(RR)
모든 프로세스가 돌아가며 스케줄 링 하는 것을 말한다. 시분할 시스템에서 주로 사용한다.
일정 시간을 정하여 프로세스마다 이 시간 동안 수행되고 다음 프로세스로 넘어간다.
단 , 이 일정 시간을 Time Quantum 이라고 하는데 , RR은 매우 Time Quantum에 의존적이며 ,
이 값이 어떻게 매겨 지느냐에 따라 성능이 좌우된다.
크기가 매우 커질수록 , 한 프로세스에서 cpu를 이용하는 시간이 커지므로 , FCFS와 유사해지고 ,
만일 또 너무 작다면 빈번한 context switching 으로 인해 overhead가 많이 발생되어 비효율 적이다.
일반적으로 10 ~ 100msec로 정한다고 한다.
5) Multilevel Queue
이름 그대로 여러개의 Queue를 두고 그 안에 독립적으로 스케줄링 방식을 두어 사용하는 방식이다.
프로세스는 기준에 따라 여러 그룹으로 나눌 수 있는데 ,
- System processes: 운영체제 커널 수준의 프로세스
- Interactive processes: 유저 수준의 대화형 프로세스
- Interactive editing processes
- Batch processes: 대화형 프로세스의 반대인 것으로 일정량을 한 번에 처리하는 프로세스(Ex, 컴파일러)
- Student processes
위와 같이 각 그룹의 성격에 가까운 프로세스를 하나의 queue에서가 아닌 여러개의 queue를 두어
각 그룹 별로 사용한다. 또한 queue마다 우선순위를 지정할 수도 있다.
단 , 딱 봐도 특정 그룹의 queue는 활발한 반면에 우선순위가 낮은 특정 queue는 거의 정적에 가까운 사태가 발생할 것 같다는 느낌이 온다.
6) Multilevel Feedback Queue
여러 개의 queue를 사용한다는 방식은 Multilevel Queue와 같다.
맨 처음에는 여러 개의 queue 중에서 하나의 queue에서 시작하다가 , 대기 시간이 오래 걸리면
다른 queue로 프로세스를 옮겨 대기 시간을 조정한다.
마찬가지로 각 queue마다 독립적으로 스케줄링 기법을 사용할 수 있으며 각 queue 별로 우선순위를 설정할 수 있다.
한가지 궁금한게 있다. 만일 한 queue에서 선택한 기법이 우선순위 기법인데 , 이 기법 특성상 나타날 문제인 기아 현상이 발생했을 때 , 같은 queue에서 우선순위를 점진적으로 높여주는 것이 아닌 ,
우선 순위가 더 높은 queue로 옮겨 처리할 수 있을까?? 싶었는데 가능하다고 한다.
*우리가 사용하는 운영체제는 여러 개의 큐를 사용하고 각 큐마다 독립적으로 운영된다고 한다.
