[운영체제 스터디] 프로세스의 특성과 CPU 스케줄링

🌟 본 게시물은 이화여자대학교 반효경 교수님 강의를 참고로 작성한 게시물 입니다. 틀린 내용은 꼬옥 지적 부탁드립니다 ! 🌟

1. CPU and I/O Bursts In Program Execution

어떤 프로그램이든 프로그램을 실행한다는 것은 CPU Burst와 I/O Burst를 반복하게 되는 것이다.

❓CPU Burst

CPU에서 instruction을 수행하는 것

❓ I/O Burst

I/O를 instruction을 수행하는 작업

💡 프로세스의 특성 분류

✔️ I/O-bound process

CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 Job
(many short CPU bursts)

✔️CPU-bound process

계산 위주의 job
(few very long CPU bursts)

💡 CPU-burst Time의 분포

✔️ 여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다.

Interactive job에게 적절한 reponse 제공 요망
CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용해야 함

2. CPU Scheduler & Dispatcher

✔️ CPU Scheduler

Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

✔️ Dispatcher

CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다
이 과정을 context switch(문맥 교환)라고 한다.

✔️ CPU 스케줄링이 필요한 경우

Running → Blocked (예: I/O 요청하는 시스템 콜)
Running → Ready (예: 할당시간만료로 timer interrupt)
Blocked → Ready (예: I/O 완료후 interrupt)
Terminate

I/O를 발생시켜 Blocked 되는 경우나 Terminate에서의 스케줄링은 강제로 빼앗지 않고 자진반납(nonpreemptive)한다. 다른 상태는 모두 강제로 빼앗기는(preemptive) 경우이다.

❓nonpreemptive = 비선점형 방식

CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않음

❓preemptive = 선점형 방식

프로세스가 CPU를 계속 사용하길 원한다고 하더라도 강제로 빼앗길 수 있음

3. Dispatcher

CPU 스케줄러가 어떤 프로레스에게 CPU를 할당해야 할지 결정하고나면 선택된 프로세스에게 실제로 CPU를 이양하는 작업이 필요하다.
이와 같이 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정 하는 운영체제의 코드를 디스패처라고 부른다.
디스패처는 현재 수행 중이던 프로세스의 문맥(context)을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 작업을 수행한다.
디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 디스패치 지연시간(dispatch Latency)이라고 하며, 디스패치 지연시간의 대부분은 문맥교환 오버헤드에 해당된다.

4. 스케줄링 알고리즘

1. 선입선출 스케줄링(FCFS)

선입선출(First-Come First-Served: FCFS) 스케줄링은 프로세스가 준비큐에 도착한 시간 순서대로 CPU를 할당하는 방식을 말한다. 이 방식에서는 CPU를 먼저 요청한 프로세스에게 CPU를 할당하고, 해당 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗기지 않는다.

1.1 선입선출 스케줄링의 단점

도착한 순서대로 CPU 작업을 처리하기 때문에 CPU Burst가 짧은 작업이어도 도착시간이 늦어지게 되면, CPU Burst가 높은 작업이 끝날 때까지 기다려야 하므로 사용량에 비해 대기시간이 길어진다는 단점이 있다. 이를 콘보이 현상 이라고 하며, 이는 FCFS 스케줄링의 대표적인 단점에 해당된다.

2. 최단작업 우선 스케줄링 (SJF)

최단작업 우선(Shortest-job First: SFJ) 스케줄링 알고리즘은 CPU 버스트가 가장 짧은 프로세스에게 CPU를 제일 먼저 할당하는 방식이다. 이와 같은 할당 방식을 통해 CPU 버스트가 짧은 프로세스가 CPU를 먼저 사용하고 준비 큐를 빠져나가게 되면 프로세스들이 준비 큐에서 기다리는 전체적인 시간이 줄어들게 된다. SJF 스케줄링 알고리즘은 평균 대기시간을 가장 짧게 하는 최적 알고리즘으로 알려져 있다.

2.1 선점방식

진행중인 작업의 남은 CPU 버스트보다 짧은 작업이 도착하면 더 짧은 작업에게 CPU를 할당하는 방식 이러한 방식을 SRTF(Shortest Remaining Time First)라고도 부른다.
프로세스들이 준비 큐에 도착하는 시간이 불규칙한 경우 선점형방식이 프로세스들의 평균 대기시간을 최소화 하는 최적의 알고리즘이 된다.
일반적인 시분할 환경에서는 중간중간에 새로운 프로세스가 도착하는 경우가 발생하므로 선점형 방식이 평균 대기시간을 가장 많이 줄일 수 있다.

2.2 비선점방식

먼저 도착한 작업의 CPU 수행이 끝나서 스스로 CPU를 내어놓을 때까지 스케줄링을 하지 않는다.
일련의 프로세스들이 준비큐에 한번에 도착하고 그 후에는 따로 도착하지 않는 환경에선 선점형방식과 같은 대기시간 결과를 나타내기도 한다.

2.1 SFJ 스케줄링의 단점

CPU 버스트가 짧은 프로세스가 계속 도착할 경우 CPU 버스트가 긴 프로세스는 영원히 CPU를 할당받지 못할 수 있다. 이를 기아 현상(starvation)이라고 한다.

3. 우선순위 스케줄링

우선순위 스케줄링(priority scheduling)이란 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식을 말한다. 이때 우선순위는 우선순위값(priority number)을 통해 표시하며 우선순위값이 작을수록 높은 우선순위를 가지는 것으로 가정한다.
우선순위 스케줄러도 비선점형방식과 선점형방식이 있는데 이는 SJF 알고리즘의 비선점형,선점형과 동일한 방식에서 CPU 버스트 시간 기준이 아닌, 우선순위 기준으로 변경된 것이다.

3.1 우선순위를 정하는 방법

CPU 버스트 시간으로 우선순위 선정
- 이러한 경우 SJF 알고리즘과 동일한 의미를 가지게 됨
시스템과 관련된 동일한 작업을 수행하는 프로세스의 우선순위를 높게 부여하는 것

3.2 우선순위 스케줄링 단점

우선순위 스케줄러 방식에서도 기아현상이 발생할 수 있다. 우선순위가 높은 프로세스가 계속 도착하는 상황에서 우선순위가 낮은 프로세스는 CPU를 얻지못한 채 계속 기다려야 할 수 있기 때문이다. 이러한 단점을 해결하기 위해 노화(aging) 기법이 존재한다.

3.3 노화기법 (aging)

노화 기법이란 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법이다.

4. 라운드로빈 스케줄링

라운드로빈 스케줄링은 시분할 시스템 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식이라 할 수 있다. 라운드로빈 스케줄링에서는 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한된다.
제한된 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다.
라운드로빈 스케줄링의 할당시간을 너무 길게 설정하면 이는 FCFS와 같은 결과를 나타나게 되고, 너무 짧게 설정할 경우엔 CPU 프로세스가 빈번하게 변경되어 문맥교환 오버헤드가 발생하게 된다. 따라서 일반적으로 할당시간은 수십 밀리초 정도의 규모로 설정하게 된다.