[OS] 운영체제 스케줄링

운영체제 스케줄링의 개념과 용어

운영체제 스케줄링이란 시스템의 목표를 달성할 수 있도록 프로세서를 할당하는 일련의 과정을 이야기 합니다. 즉 어떤 프로세스가 cpu를 사용할지를 결정하는 것입니다. 스케줄링 알고리즘은 여러가지가 있는데 이러한 알고리즘의 성능의 기준은 아래와 같습니다.

• 프로세서 사용률 : 높은게 좋음.
• 단위 시간당 처리율 : 높은게 좋음.
• 반환 시간 : 작업이 시스템에서 완전이 끝날 때까지 걸리는 시간. 짧은게 좋음.
• 대기시간 : ready 큐에서 기다렸던 시간. 짧은게 좋음.

 

아래는 운영체제 스케줄링에서 사용되는 용어들과 그에 대한 설명들 입니다.

 

PCB (processor control block)

• 특정 프로세스를 관리할 필요가 있는 정보를 포함하는 운영체제 커널의 자체 자료구조입니다.
• 해당 프로세스에 관한 모든 정보를 기록해 놓는 곳으로 프로세스는 생성될 때 고유의 PBC가 생성되며 스케줄링에 관한 프로세스의 모든 정보를 가진 데이터 베이스 입니다.

 

단기 스케줄러 (short term scheduler)

• 실행할 프로세스를 수시로 선택합니다.

 

장기 스케줄러(long term scheduler)

• 한번 수행될 때마다 프로세스가 생성됩니다.
• 시스템에 새로운 작업이 들어오는 것은 분 단위이므로, 단기 스케줄러에 비해 상대적으로 드물게 실행됩니다.
• 새로운 작업이 들어오는 것을 의미합니다.

 

중기 스케줄러(mid term scheduler / swapper)

• 교체작업이 가능합니다.

 

디스패치

• 단기 스케줄러에 의해 선택된 프로세스에게 cpu 제어권을 주는 일입니다.

 

디스패처

• 단기 스케줄러에 포함되어 있는 요소로 단기 스케줄러가 선택한 프로세스에 실질적으로 프로세스를 할당합니다.

 

비선점 스케줄링

• cpu를 강제로 뺏기지 않는 스케줄링을 뜻합니다.

 

선점 스케줄링

• cpu를 강제로 뺏길 수 잇는 스케줄링을 이야기 합니다.

 

---

스케줄러의 종류

 

1. 선입 선처리 스케줄링(FCFS, First-Come-First-Served)

비선점 방식의 스케줄링으로 선입선출(fifo) 큐로 구현되어 있습니다. 준비큐의 모든프로세서들이 실행되므로 공정하다는 장점이 있으나 장기 실행 프로세스가 실행될 경우 뒤의 작업을 모두 지연시키기 때문에 평균 지연시간이 올라간다는 단점이 있습니다.

 

프로세스	실행 시간	대기시간
P1	24	0
P2	3	24
P3	3	27

예를들어 위와 같은 프로세스들이 있을 경우 P2, P3의 작업은 각각 3초씩으로 금방 종료될 수 있는 프로세스이지만, 선입 선처리 스케줄링은 순서대로 실행하므로 P1 프로세스가 종료된 24초 후에야 P2 프로세스가 실행될 수 있습니다.

 

즉 앞에 있는 프로세스가 시간이 오래 걸리는 프로세스일 경우 전체 실행시간이 지연되게 됩니다.

 

 

2. 최소 작업 우선 스케줄링 (SJE, Short Job First)

SJE는 비선점 알고리즘으로 프로세서 수행시간이 가장 짧은 작업에 프로세서를 할당하는 스케줄링입니다. 실행 시간이 ㅉ랍은 것부터 해결하기 때문에 waiting time이 가장 짧아 효율적인 스케줄링입니다. 하지만 빠른 작업만 우선 순위로 작업을 하다보면 실행 시간이 긴 작업은 cpu 스케줄링을 받지 못하는 상황이 올 수 있습니다. 또한 cpu 내부에서는 어떤 작업이 가장 실행 시간이 짧은 작업인지 알기 쉽지 않다는 어려움이 있습니다.

 

 

3. HRN (Highest Response-Rate Next) 스케줄링

SJE 스케줄링의 약점이었던 긴 작업과 짧은 작업 간의 지나친 불평등을 어느정도 보완한 기법입니다. HRN 기법은 에이징을 사용하게 됩니다. 에이징이란 오랫동안 기다리고 있는 프로세스들의 우선순위를 기다리는 시간과 비례하여 증가시키는 것을 말합니다. 즉 cpu가 할당 될 때마다 기존에 있던 프로세스들의 우선 순위를 한 단계씩 낮춰줌으로써 실행 시간이 긴 프로세스가 cpu를 할당받지 못하는 문제점을 해결합니다.

 

우선순위 = 대기한 시간 + 서비스를 받을 시간 / 서비스를 받을 시간

 

HRN 스케줄링은 비선점 방식으로 이루어집니다. 왜냐하면 선점일 경우엔 강제로 cpu를 뺏게 되면 short term scheduler가 너무 많은 일을 해야하기 때문입니다. (운영체제가 많이 일해야함)

 

 

4. 순환 할당 (Round-Robin)

순환 할당은 선점 알고리즘으로 각각의 프로세스를 정해진 time slice에 따라 일정 시간만큼 공평하게 처리하는 알고리즘입니다. 모든 프로세스가 동일한 점유율과 time slice를 공평하게 제공되기 때문에 기아 현상이 발생하지 않지만, 성능이 time slice에 따라 영향을 많이 받기 때문에 time slice가 너무 길면 선입 선처리가 되어버리고 너무 짧으면 context switching의 부담이 크게 되니다.

 

※ Context switching이란?

CPU에서 여러 프로세스를 돌아가면서 작업을 처리하는데 이 과정을 이야기 합니다. 프로세스로 예를 들자면, 동작 중인 프로세스가 대기를 하면서 해당 프로세스의 상태(Context)를 보관하고, 대기하고 있던 다음 순서의 프로세스가 동작하면서  이전에 보관했던 프로세스의 상태를 복구하는 작업입니다. Context Switching이 자주 일어나게 되면 성능은 저하되게 됩니다.

 

 

5. 다단계 큐(Multi-Level Queue) 스케줄링

짧은 작업처리 알고리즘을 연구하다보니 나온 스케줄링 알고리즘 입니다. 다단계 큐는 커널내의 준비 큐를 여러개로 구성하여 각각 다른 스케줄링 알고리즘을 사용하는 것을 말합니다. 응답이 빠르다는 장점이 있지만, 여러 준비큐의 스케줄링 알고리즘 때문에 추가적인 오버헤드가 발생하게 됩니다. 또한 우선 순위가 낮은 큐는 무한정 대기상태가 생길 수 있는 위험 역시 존재합니다.