Portfolio

스케줄링을 알아보기 전에 프로세스의 상태부터 알아보자. 프로세스의 상태가 바뀌고 이를 알맞은 큐에 넣음으로써 스케줄링이 구현된다.

프로세스의 상태

처음 프로세스가 생성되면 new 상태인데, 특별한 경우가 아니라면 롱텀 스케줄러가 바로 허락(admitted) 바로 ready 상태가 된다. 이 ready 상태가 되면 프로세스는 ready queue에 들어가게 된다.

그리고 이제 scheduler 의해 자신의 차례가 되면 dispatcher에 의해 컨텍스트 스위칭이 진행되고 CPU를 얻어 해당 프로세스는 running 상태가 된다. 그러면 CPU에서 이런 저런 연산을 하다가 또 자신의 할당 시간이 만료가 되면 Timer에 의해 ready 상태가 된다.

schedular vs dispatcher

schedular는 CPU가 놀지 않고 항상 일을 하도록 프로세스를 선택하는 역할을 수행한다. 즉 위에서 본 ready queue에서 어떤 프로세스가 다음에 CPU로 올라가야 할지 선택한다.

dispatcher는 선택된 프로세스가 CPU에서 실제로 실행될 수 있도록 만드는 역할을 한다. 컨텍스트 스위칭, user mode → kernel mode(이 때 컨텍스트 스위칭) → user mode로 전환하는 작업을 수행한다.

CPU에서 연산을 진행하다가 I/O 작업이 필요해진다, 혹은 critical section에 들어가야 하는데 다른 프로세스 혹은 쓰레드가 critical section에 있어 기다려야 되는 상황이다, 그러면 blocked(waiting) 상태가 된다.

critical section에 들어갈 수 있는 자원을 얻게 되었거나(락, 뮤텍스, 세마포어) I/O 작업이 끝나고 결과를 받았을 때 다시 ready 상태가 된다.

이런 과정을 반복하다가 일이 다 끝나면 running 상태에서 cpu가 마무리 작업을 수행하고 terminated가 되어 프로세스가 종료된다. 이 때 마무리 작업은 다음과 같이 메모리 해제 등이 있지 않을까 싶다.

쓰레드의 상태는 거의 동일하다고 한다. 하지만 운영체제마다 쓰레드, 프로세스의 상태는 구체적으로는 다를 수 있다.

CPU 스케줄링

스케줄링이란

CPU를 효율적으로 사용하기 위해 I/O 작업 등 현재 CPU에 올라간 프로세스가 delay되어 CPU가 놀게 될 때, 이 CPU를 놀게 하지 않고 다른 프로세스를 선택해 올리는 과정.(By GeeksforGeeks)

스케줄링 선점 방식

Nonpreemptive(비선점)

CPU 주도권을 자진 반납, 양보
CPU를 가지고 있어도 별다른 작업을 할 수 없어 알아서 반납하는 방식을 말한다.
연산을 다 수행해 terminated가 될 때, 혹은 I/O 작업으로 waiting 상태가 될 때, 아니면 자발적으로 양보할 때
신사적, 협력적, 느린 응답성

Preemptive(선점)

Nonpreemptive 방식의 경우도 포함하여 현재 running 프로세스가 충분히 CPU를 다 쓰지 않았음에도 CPU를 빼앗기는, 선점 당하는 방식
운영체제가 개입하여 할당시간이 다 된 프로세스보고 양보하라는 경우(멀티 태스킹 방식에서)
혹은 waiting에서 ready로 바뀐 프로세스의 우선순위가 현재 running 상태의 프로세스보다 우선순위가 높을 경우

running 상태의 프로세스는 ready가 되고 우선순위가 높은 ready 상태의 프로세스가 running 상태가 된다. 즉 CPU를 선점, 뺏는 것.

적극적, 강제적, 빠른 응답성, 데이터 일관성 문제

데이터 일관성 문제를 해결하기 위해 락, 뮤텍스, 세마포어가 만들어짐.

스케줄링 알고리즘

FCFS, first-come first-served

먼저 도착한 순서대로 처리한다.

굉장히 CPU를 오래 쓰는 프로세스이 먼저 도착하면, 짧게 쓰는 프로세스들이 기다려야 해서 비효율적이다.

SJF, shortest-job-first, Non-Preemptive

프로세스의 다음 CPU burst time이 가장 짧은 프로세스부터 실행시킨다.
중간에 선점 당하지 않는다. 즉 더 짧은 프로세스가 도착해도 원래 작업 중인 프로세스가 끝날 때까지 내놓지 않는다.

SRTF, shortest-remaining-time-first, Preemptive(혹은 이 경우를 선점형 SJF라고 하기도 한다)

남은 CPU burst가 가장 짧은 프로세스부터 실행시킨다.
더 짧은 프로세스가 도착하면, 앞으로 남은 시간이 짧은 프로세스에게 CPU 제어권을 빼앗긴다.

SJF는 burst time이 긴 프로세스가 CPU를 얻는데에 너무 오래 걸린다는 단점이 있다.

Priority, 우선순위

우선 순위가 높은 프로세스부터 실행시키는 것이다.
Preemptive: 우선순위가 더 높은 프로세스가 들어오면 CPU를 빼앗기는 것.
Non-Preemptive : 우선순위가 더 높은 프로세스가 들어와도 일단 현재 프로세스를 완료하고 CPU를 내놓는 것.

ready queue에 1, 4 우선순위의 프로세스들이 있고, 우선순위가 7인 프로세스가 CPU에서 연산 중이다. 이 때 8인 프로세스가 ready 상태가 되면, Preemptive일 경우 8이 CPU를 얻게 된다. 반면 Non-Preemptive 일 경우는 7이 다 끝나고 나서 그 ready queue의 1, 4, 8 중 가장 우선 순위가 높은 8이 CPU를 얻게 된다.