[운영체제] CPU 스케줄링

[스케쥴링]

*스케쥴링이 필요한 이유?

OS의 정의를 컴퓨터의 성능을 높이고 사용자에게 편의성을 제공하는 목적을 가지고 컴퓨터 하드웨어 관리하는 프로그램이라고 정의할 수 있다. 따라서 OS는 실행 대기중인 프로세스들에게 자원 배정을 적절히 하여 시스템의 성능을 끌어올릴 수 있어야한다.

*스케쥴링을 고민해줘야하는 상태 변화에는 어떤 것들이 있을까?

• running -> waiting
• running -> ready
• waiting -> ready
• terminate

*스케쥴링의 여러방식

• FCFS(FIFO) : 먼저 들어온 순서대로 실행
• SJF :실행시간이 가장 짧은것 부터 실행시키는 방식이다. 대기 시간이 짧다는 장점이 있다.
• SRTF: 선점형 SJF방식이라 생각하면 좋다.

• Round Robin :각 프로세스에서 정해진 시간만큼 할당하고 할당된 시간안에 종료되지 않으면 ready queue에 들어간다. 이때 할당 시간량이 중요한데 너무 적으면 context switching이 자주 일어나고 너무 길면 FCFS와 다를바가 없다.

-> 보통 시간단위는 10~100ms

• MLQ : ready Queue를 여러개의 queue로 분류하고 각각 다른 스케쥴링 알고리즘을 가지는 방식이다. 쉽게 말해 프로세스를 그룹화 하는 것이다.

하지만 이러한 스케줄링은 만능이 아니며 당연히 문제가 발생할 수 있다. 특정 프로세스가 우선순위가 낮아서 우선순위가 높은 프로세스에 계속 밀려 무기한 차단될 때 발생하는 것을 Starvation이라 한다.

 

[Starvation]

이는 스케줄링과 관련이 있는데 SJF,SRTF,MLQ등의 스케줄링 알고리즘에서 발생할 수 있다.

• SJF : 실행시간이 긴 실행파일의 경우에 대해 starvation이 일어날 수 있다.
• SRTF :실행시간이 긴 실행파일의 경우에 대해 starvation이 일어날 수 있다.
• MLQ : 높은 우선순위가 계속해서 들어오게 될경우 아래 큐에 있는 실행파일은 실행될 수 없을 수 있다.

이러한 starvation을 해결하기 위해 우선순위가 낮아 대기시간이 긴 실행파일에 대해 우선순위를 주기적으로 올려주는 Aging 기법이 존재한다.

 

[Aging 기법을 적용한 스케줄링 알고리즘]

• HRN : SJF방식은 실행시간이 긴 프로세스는 뒤로 계속 밀리는 불리함이 있다. 그래서 Aging기법을 통해 보완한 스케쥴링 방식이다.

-> 우선순위 = (대기시간 + 실행시간) / 실행시간

• MLFQ : 기존 MLQ방식은 특정 프로세스가 큐에 고정되는 방식이었다. 반면 MLFQ는 큐와 큐 사이에 프로세스가 이동하는 걸 허용한다. 또한 RR와 같이 Time Quantum(타임 퀀텀)을 가지는 여러 queue가 존재하며 우선순위가 높은 순으로 이 퀀텀을 지나며 실행한다.

만약 해당 퀀텀내에 실행을 모두 마치지 못하면 아래 우선순위 큐로 내려간다. 이런식으로 우선순위를 변경하며 실행되는 스케줄링 방식이다.

 

TODO : 스케줄링시 고려사항, 스케줄링 알고리즘 

https://yabmoons.tistory.com/655