스케줄링 알고리즘

Chan Young Jeong·2023년 2월 7일

목록 보기

3/11

간단하게 스케줄링에 대해서 알아보면, 모든 프로세스는 CPU를 필요로 하고 모든 프로세스는 먼저 CPU를 사용하고 싶어 합니다. 운영체제가 이런한 프로세스들에게 공정하고 합리적으로 CPU 자원을 할당하는 것을 스케줄링이라고 합니다.

프로세스 우선순위

그렇다면 어떤 프로세스에게 CPU를 할당하는 것이 좋을까요?
단순히 "CPU사용하고 싶어요!"를 먼저 말할 프로세스에게 할당하는 방법이 있을 수 있습니다. 합리적으로 보이지만 이는 좋은 방법이 아닐 수도 있습니다.

그 이유는 프로세스에 따라 우선순위가 다르기 때문입니다. 우선순위가 높은 프로세스라는 것은 빨리 처리해야 하는 프로세스를 의미합니다.
우선 순위가 높은 프로세스에는 입출력 작업이 많은 프로세스가 있습니다.
그 이유는 IO BOUND PROCESS를 빨리 실행시켜 입출력 장치를 끊임없이 작동시키고, 그 다음 CPU BOUND PROCESS에 집중적을 CPU를 할당하는 것이 효율적이기 때문입니다.

따라서 프로세스의 중요도에 따라 운영체제는 프로세스마다 우선순위를 부여합니다. PCB(Process Control Block)에 저장. 따라서 우선순위가 높을 수록 더 자주, 더 빨리 실행됩니다.

CPU BOUND PROCESS : 복잡한 수학 연산, 컴파일 ,그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스. 대기 상태보다는 실행 상태에 더 많이 머무른다.
IO BOUND PROCESS : 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스. 입출력을 위한 대기 상태에 실행 상태보다 더 많이 머무른다.
CPU BURST : CPU를 이용하는 작업. 따라서 CPU BOUND PROCESS는 CPU BURST가 많은 프로세스라고 정의할 수 있다.
IO BURST : 입출력 장치를 기다리는 작업. 따라서 IO BOUND PROCESS는 IO BURST가 많은 프로세스라고 정의할 수 있다.

선점형 vs 비선점형 스케줄링

이런 상황을 가정해봅시다. 한 프로세스가 CPU를 차지하여 실행되고 있을 때 다른 급한 프로세스가 와서 CPU를 지금 당장 사용하길 요청했습니다.
이 때 택할 수 있는 방법은 두가지 입니다.
1. 지금 사용중인 프로세스로부터 CPU자원을 빼앗아 급한 프로세스에게 할당
2. 지금 사용중인 프로세스의 실행이 모두 끝날 때까지 기다림.

여기서 1번이 선점형 스케줄링, 2번이 비선점형 스케줄링에 해당합니다.

선점형이라는 것은 프로세스가 CPU를 비롯한 자원을 사용중이더라도 운영체제가 프로세스로부터 자원을 빼앗아 강제로 다른 프로세스에게 할당 할 수 있는 스케줄링 방식

비선점형이라는 것은 한 프로세스가 CPU를 사용하고 있으면 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식

1. 프로세스가 실행중 상태에서 대기중 상태로 전환 (ex. 입출력 요청)
2. 프로세스가 실행중 상태에서 준비 완료 상태로 전환 (ex. 인터럽트 발생)
3. 프로세스가 대기중 상태에서 준비 완료 상태로 전환 (ex. 입출력 완료)
4. 프로세스가 종료 

1,4에서만 스케줄링이 일어나면 비선점형 , 네가지 모든 경우에 일어나면 선점형(1,4에서는 여지 없이 스케줄링이 일어나야 하지만 , 2,3번은 여지가 존재)

대부분의 운영체제는 선점형 방식이지만 각각 장단점이 존재합니다.
선점형은 자원의 독점을 막고 프로세스들에게 골고루 자원을 배분할 수 있지만 잦은 문맥 교환 과정에서 오버헤드가 발생할 수 있습니다. 비선점형은 오버헤드는 적지만 하나의 프로세스가 자원을 사용 중이라면 급해도 기달릴 수 밖에 없습니다. 모든 프로세스가 골고루 자원을 사용할 수 없는 단점이 존재합니다.

스케줄링 알고리즘

알고리즘 선택시 사용되는 기준

CPU 사용률(CPU Utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율.
처리량(Throughput) : CPU가 단위 시간당 처리하는 프로세스의 개수.
응답 시간(Response Time) : 대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간.
대기 시간(Waiting Time) : 프로세스가 준비 큐 내에서 대기하는 시간의 총합.
반환 시간(Turnaround Time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간.

선입 선처리 스케줄링(FCFS,first come first served)

준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 방식.
먼저 온 프로세스를 먼저 처리
starvation이 없다.
프로세서가 지속적으로 프로세스를 처리하므로 처리율이 높다.
convoy effect : 소요시간이 긴 프로세스가 먼저 도착해 효율성을 낮추는 현상.

최단 작업 우선 스케줄링(SJF, shortest job first scheduling)

호위 효과를 방지하려면?단순히 생각해보면 CPU사용 시간이 긴 프로세스는 나중에 실행하고 , CPU사용 시간이 짧은 프로세르르 먼저 실행하면 되겠죠?

평균 대기시간이 가장 짧다.
비선점형으로 분류되지만 선점형으로 구현 될 수 있다. 이는 선점형 최단 작업 우선 스케줄링으로 최소 잔여 시간 우선 스케줄링을 의미합니다.
실행 시간이 긴 process는 실행 시간이 짧은 process를 기다려야 하기에 starvation이 일언난다.
실행시간을 예측하기 어렵다.

라운드 로빈 스케줄링

선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 방식. 즉 정해진 시간 동안 돌아가며 CPU를 사용하는 선점형 스케줄링 방식입니다.

타임 슬라이스 크기 중요! 너무 크면 선입 선처리 스케줄링이랑 다름 없고 너무 작으면 문맥교환이 자주 발생하여 비용이 커짐.
하드웨어 타이머가 필요합니다.
starvation이 발생하지 않습니다.

최소 잔여 시간 우선 스케줄링(SRT, shortest remaining time)

최단 작업 우선 스케줄링과 라운드 로빈을 합친 스케줄링 방식. 최단 작업 우선 스케줄링은 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘이고 라운드 로빈은 정해진 타임 슬라이스만큼 돌아가며 CPU 를 사용하는 선점형 알고리즘입니다. 따라서 최소 잔여 시간 우선 스케줄링에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되 CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택됩니다.

우선순위 스케줄링

프로세스들에게 우선순위를 부여하고 우선순위가 높은 프로세스부터 실행하는 스케줄링 알고리즘.

높은 우선순위 프로세스가 계속 오면 우선순위가 낮은 프로세스는 Starvation 현상을 겪을 수 있다. 이를 방지하기 위한 대표적인 방식이 Aging.(오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식)

다단계 큐 스케줄링(MLQ,multilevel queue)

우선순위 스케줄링에서 발전된 형태로, 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식. 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 우선순위가 높은 큐가 비어있으면 그다음 우선순위 큐에 있는 프로세스들을 처리합니다.

프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해짐
큐별로 다른 알고리즘 적용 가능
starvation이 일어난다.

다단계 피드백 큐 스케줄링(MLFQ, multilevel feedback queue)

앞서 설명한 다단계 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 없습니다. 그렇기 때문에 우선순위가 낮은 프로세스는 starvation이 일어날 수 있습니다. 이를 보완한 것이 다단계 피드백 큐 스케줄링입니다.
새로 준비 상태가 된 프로세스가 있다면 우선 순위가 가장 높은 큐에 삽입되고 타임 슬랑이스 동안 실행됩니다. 그리고 만약 주어진 타임슬라이스동안 실행이 끝나지 않는 다면 다음 우선순위 큐에 삽입되어 실행됩니다. (우선순위 낮아짐)

즉 ,CPU를 많이 사용하는 프로세스는 자연스럽게 우선순위가 낮아지고, CPU를 비교적 적게 사용하는 입출력 집중 프로세스는 우선순위가 높은 큐에서 실행이 끝납니다.

그리고 여기서도 에이징이 적용되는데,낮은 우선순위 큐에 오래 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시킵니다.