CPU 스케쥴링
CPU 스케쥴링
- CPU 스케쥴링이란 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 할당하기 위한 기법이다.
- 프로세스들의 특성에 따라 우선 순위가 부여되며, 운영체제는 우선 순위에 따라 프로세스들에게 CPU 자원을 할당한다. 이 때 우선 순위의 기준은 스케쥴링 기법 종류에 따라 다르다.
선점형 스케쥴링과 비선점형 스케쥴링
- CPU 스케쥴링 기법은 크게 선점형 스케쥴링과 비선점 스케쥴링으로 구분할 수 있다.
- 선점형 스케쥴링은 특정 프로세스가 실행 상태더라도, 다른 프로세스가 CPU 자원을 빼앗아 실행될 수 있는 스케쥴링 기법이다.
- 비선점형 스케쥴링은 특정 프로세스가 실행 상태라면, 해당 프로세스가 종료 상태 또는 대기 상태가 될 때 까지는 다른 프로세스가 CPU 자원을 빼앗을 수 없는 스케쥴링 기법이다.
CPU 스케쥴링 알고리즘
- CPU 스케쥴링 알고리즘은 CPU 스케쥴링을 구현하는 실질적인 방법을 의미한다.
선입 선처리 알고리즘(FCFS: First Come First Served Scheduling)
- 단순히 준비큐에 삽입된 순서대로 프로세스에게 CPU 자원을 할당하는 알고리즘이다.
- 다음 프로세스들이 기다리는 시간이 매우 길어질 수 있다.
- 비선점형 스케쥴링이다.
최단 작업 우선 스케쥴링(SJFS: Shortest Job First Scheduling)
- CPU 사용 시간이 가장 짧은 순으로 프로세스에게 CPU 자원을 할당하는 알고리즘이다.
- 기본적으로 비선점형 스케쥴링이며, 선점형으로도 구현될 수 있다.
- 선점형으로 구현된 최단 작업 우선 스케쥴링이 최소 잔여 시간 우선 스케쥴링이다.
라운드 로빈 스케쥴링(Round Robin Scheduling)
- 선입 선처리 스케쥴링에 타임 슬라이스의 개념이 추가된 알고리즘이다.
- 타임 슬라이스란 각 프로세스가 CPU 자원을 사용할 수 있는 정해진 시간을 의미한다.
- 즉 라운드 로빈 스케쥴링은 프로세스들이 준비큐에 삽입된 순서대로 번갈아가면서 타임 슬라이스만큼만 CPU 자원을 할당 받는 알고리즘이다.
- 선점형 스케쥴링이다.
최소 잔여 시간 우선 스케쥴링(SRTS: Shortest Remaining Time Scheduling)
- 최단 작업 우선 스케쥴링과 라운드 로빈 스케쥴링이 합쳐진 알고리즘이다. 선점형으로 구현된 최단 작업 우선 스케쥴링이라고 할 수 있다.
- 최소 잔여 시간 우선 스케쥴링은 남은 작업 시간이 가장 적은 프로세스부터 타임 슬라이스만큼 CPU 자원을 할당 받는 알고리즘이다.
- 선점형 스케쥴링이다.
우선순위 스케쥴링(Priority Scheduling)
- 우선순위 스케쥴링은 특정한 기준에 따라 프로세스들에게 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 CPU 자원을 할당하는 알고리즘이다.
- 최단 작업 우선 스케쥴링(작업 시간), 최소 잔여 시간 우선 스케쥴링(남은 작업 시간)은 우선순위 스케쥴링의 일종이라고 볼 수 있다.
- 우선순위가 낮은 프로세스는 실행 순서가 계속 뒤로 밀려서 결국 CPU 자원을 할당 받지 못하는 기아 현상이 발생할 수 있다.
- 준비큐에 오랫동안 대기한 프로세스의 우선순위를 점진적으로 높여주는 에이징 기법을 통해 기아 현상을 방지할 수 있다.
다단계 큐 스케쥴링(MQS: Multilevel Queue Scheduling)
- 다단계 큐 스케쥴링은 우선 순위 스케쥴링이 보다 발전된 알고리즘이다.
- 다단계 큐 스케쥴링은 우선순위 별로 준비큐를 여러 개 사용한다. 그리고 우선순위가 높은 준비큐의 프로세스부터 CPU 자원을 할당한다.
- 준비큐 별로 다른 타임 슬라이스를 사용하거나, 다른 스케쥴링 알고리즘을 적용함으로써 효율성을 더 높일 수 있다.
- 그러나 특정 준비큐에 삽입된 프로세스들은 큐간 이동을 할 수 없기 때문에 낮은 우선순위 준비큐에 삽입된 프로세스는 기아 현상이 발생할 수있고 에이징 기법으로도 기아 현상을 방지할 수 없다는 단점이 있다.
다단계 피드백 큐 스케쥴링(MFQS: Multilevel Feedback Queue Scheduling)
- 다단계 피드백 큐 스케쥴링은 다단계 큐 스케쥴링의 단점을 보완하기 위한 알고리즘이다.
- 다단계 피드백 큐는 프로세스들이 준비큐 간에 이동할 수 있는 알고리즘이다.
- 낮은 우선순위 준비큐에 오랫동안 대기한 프로세스들을 높은 우선순위 준비큐로 이동시키는 에이징 기법을 통해 기아 현상을 방지할 수 있다.