CPU 스케줄링

프로세스 스케줄러

멀티 프로그래밍의 목적은 CPU 이용을 최대화하기 위해 항상 어떤 프로세스가 실행되고 있는 상태를 유지하는 것이 목표입니다.

목적을 달성하기 위해 사용자가 어떤 프로그램과 상호작용하고 있다면 다른 프로세스와 교체하여 항상 CPU 코어에 프로세스가 실행되고 있어야 합니다.

프로세스 스케줄러는 목표를 달성하기 위해 코어에 실행가능한 여러 프로세스 중에서 하나의 프로세스를 선택해야 합니다.

하나의 CPU 코어는 한 번에 하나의 프로세스를 실행할 수 있으며 2개 이상의 프로세스가 동시에 실행되기 위해서는 여러개의 코어가 필요합니다. 동시에 실행되는 프로세스가 코어의 개수를 넘어갈 수는 없습니다.

스케줄링 큐

프로세스가 메모리에 올라오면 준비 큐에 들어가서 준비 상태가 되어 Ready Queue로 이동하게 됩니다.

이 준비 큐는 일반적으로 링크드 리스트로 구현이 되며, 준비 상태에서는 CPU 코어에 올라가기 전까지 대기하게 되며 준비 큐의 헤더에는 첫 번째 PCB에 대한 포인터가 저장되고 각 PCB에는 준비 큐 다음 PCB를 가리키는 포인터가 저장됩니다.

I/O나 이벤트가 발생했을 때를 위한 대기 큐도 존재합니다.

프로세스에 CPU 코어가 할당되면 다 실행되어 종료되거나, 인터럽트가 발생하거나 I/O 요청의 완료와 같은 특정 이벤트가 발생할 때 까지 실행되게 됩니다.

I/O나 다른 이벤트가 발생하게 되면 해당 프로세스는 대기큐로 이동하게 됩니다.

프로세스의 스케줄링을 표현하는데는 일반적으로 큐잉 다이어그램이 사용됩니다.

원은 큐에 서비스를 제공하는 자원을 의미하고 화살표는 시스템의 프로세스 흐름을 나타냅니다.

새 프로세스는 처음에 준비 큐에 놓이고, 프로세스는 실행을 위해 선택되거나 또는 디스패치될 때까지 기다립니다.

프로세스에 CPU 코어가 할당되고, 실행상태가 되면 여러 이벤트 중에 하나가 발생할 수 있습니다.

• 프로세스가 I/O 요청을 보내고 I/O 대기 큐로 이동합니다.
• 프로세스는 새 자식 프로세스를 만든 다음 자식의 종료를 기다리는 동안 대기 큐에 놓일 수 있습니다.
• 인터럽트 또는 타임 슬라이스가 만료되어 프로세스가 코어에서 강제로 제거되어 준비 큐로 돌아갑니다.

위의 그림처럼 특정 이벤트가 발생했을 때 대기 큐에서 기다리고 있다가 처리가 완료되면 준비 큐로 돌아가게 됩니다.

프로세스는 종료될 때까지 해당 주기를 유지하며 종료 시점에 모든 큐에서 제거되고 PCB 및 리소스가 반환됩니다.

CPU 스케줄링

CPU 스케줄링은 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 역할을 합니다.

CPU 스케줄링이 중요한 이유는 다음과 같습니다.

코어가 하나인 시스템에서는 한번에 하나의 프로세스만 실행될 수 있으며, 나머지 프로세스는 CPU의 코어가 사용가능할 때까지 기다리고 있어야 합니다.

하지만 다중 프로그래밍은 CPU의 이용률을 최대화하기 위해 항상 실행중인 프로세스를 가지게 하는데 있습니다.

다중 프로그래밍의 아이디어는 비교적 간단합니다.

하나의 프로세스에서 I/O 요청이 발생했고 해당 요청이 완료될 때까지 기다린다면 CPU 코어는 그동안 놀고 있게 됩니다.

이런 대기 시간을 최대한 활용하기 위해 해당 프로세스를 대기큐에 넣고 다른 프로세스를 할당합니다.

이런 식으로 하나의 프로세스가 대기해야할 때 다른 프로세스가 CPU 사용을 양도받는 구조입니다.

CPU는 중요한 컴퓨터 자원 중 하나이며, CPU 스케줄링은 CPU의 효율을 최대한 끌어올릴 수 있는 작업이기 때문에 운영체제 설계의 핵심이 됩니다.

선점 및 비선점 스케줄링

• 선점형 스케줄링
  • 프로세스가 CPU를 할당받아 실행중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식입니다.
• 비선점형 스케줄링
  • 프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식입니다.

CPU 스케줄링은 다음 상황에서 발생하게 됩니다.

1. 한 프로세스가 실행상태에서 대기 상태로 전환될 때 (I/O 요청)
2. 프로세스가 실행 상태에서 준비완료 상태로 전환될 때 (프로세스에 할당된 시간이 끝났을때)
3. 프로세스가 대기 상태에서 준비완료 상태로 전환될 때 (I/O 종료)
4. 프로세스가 종료될 때

1번과 4번의 경우 비선점(non-preemptive) 스케줄링을 사용합니다.

2번과 3번의 경우 선점(preemptive) or 비선점(non-preemptive) 스케줄링을 사용합니다.

단, 선점스케줄링이 더 CPU의 성능을 이끌어낼 수 있기 때문에 2번과 3번의 경우 선점 스케줄링이 많이 쓰입니다.

디스패처

디스패처는 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이며 다음과 같은 작업을 수행합니다.

• 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일 (컨텍스트 스위칭)
• 유저 모드로 전환하는 일 (커널모드 → 유저모드)
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

CPU 스케줄링 기준

서로 다른 CPU 스케줄링 알고리즘들은 다른 특성이 있으며 한 부류의 프로세스들을 다른 프로세스들 보다 더 선호할 수 있습니다.

특정 상황에서 어떠한 알고리즘을 선택하려면 우리는 다양한 알고리즘들의 서로 다른 특성을 반드시 고려해야 합니다.

CPU 스케줄링 알고리즘을 선택하는 기준은 다음과 같습니다.

• CPU 이용률
  • 우리는 가능한 CPU를 최대한 바쁘게 유지하기를 원합니다. 실제 시스템에서는 40%에서 90%까지의 범위를 가져야 합니다.
• 처리량
  • 단위 시간당 완료된 프로세스의 개수를 의미합니다.
• 총 처리 시간
  • 프로세스의 제출 시간과 완료 시간의 간격을 총 처리 시간이라고 하며, 준비 큐에서 대기한 시간, CPU에서 실행하는 시간 그리고 I/O시간을 합친 시간입니다.
• 대기시간
  • 준비 큐에서 대기하면서 보낸 시간의 합을 의미합니다.
• 응답 시간
  • 하나의 요청을 보낸 후 첫 번째 응답이 올 때까지의 시간입니다. 여기서 응답 시간은 응답이 시작되는데 까지 걸리는 시간이며, 응답을 완료하는데 걸리는 시간이 아닙니다.

스케줄링 알고리즘

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

가장 간단한 CPU 스케줄링 알고리즘입니다.

프로세스가 요청한 순서대로 CPU를 할당받습니다. (비선점 스케줄링)

FIFO Queue를 이용해서 구현합니다.

FCFS를 사용할 경우 프로세스의 CPU 버스트 타임(프로그램의 수행중에 연속적으로 CPU를 사용하는 구간)이 다른경우 일반적으로 최소 값이 아니며 최소 값과 상당히 다를 수 있습니다.(더 오랜시간이 걸림)

convoy effect가 발생합니다. -> 소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹고 있는 현상

 

• 최단 작업 우선 스케줄링(SJF, Shortest Job First)

가장 작은 CPU 버스트 시간을 가진 프로세스에게 우선적으로 CPU를 할당합니다.

만약 CPU 버스트 시간이 동일하다면 FCFS 방식으로 작동합니다.

SJF 알고리즘은 주어진 프로세스 집합에 대한 최소 평균 대기 시간을 제공합니다.

긴 프로세스 이전에 짧은 프로세스를 먼저 처리하면 짧은 프로세스의 대기 시간이 긴 프로세스를 기다리는 것 보다 짧아지므로 평균 대기 시간이 감소합니다.

하지만 SJF 알고리즘은 구현이 굉장히 어려운데, 컴퓨터 입장에서는 프로세스의 CPU 버스트 타임의 길이가 정확히 얼마인지 알 수 있는 방법이 없기 때문입니다. (CPU 버스트 타임을 예측해야함)

SJF 알고리즘은 비선점 스케줄링을 할 수도 있고 선점 스케줄링을 할 수도 있습니다.

예측한 CPU 버스트 타임을 현재 프로세스가 넘기게 되면 다른 프로세스에게 넘기는 방식으로 할 수 있기 때문입니다. (SRTF 스케줄링)

 

• 라운드 로빈 스케줄링(RR, Round-Robin)

선점형 스케줄링으로, FCFS 알고리즘 처럼 동작하지만 프로세스마다 실행시간을 부여해 해당 시간만큼만 실행하고 다른 프로세스한테 넘겨줍니다.

프로세스의 실행시간은 짧은 시간을 부여해야합니다. (10 ~ 100 ms) 단, 너무 짧은 시간이 주어지면 계속해서 짧은시간에 context switch가 계속해서 이뤄지면서 오히려 안좋아집니다.

Ready Queue는 Circular Queue로 구현되며 프로세스가 시간을 다 쓰면 OS가 인터럽트를 걸어서 현재 프로세스가 가장 뒤로 가는 방식입니다.

 

• 우선순위 스케줄링 (Priority-based)

프로세스가 Ready Queue에 도착하면 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 CPU를 할당하는 방식입니다.

만약 우선순위가 같다면 FCFS 방식으로 작동합니다.

SJF 알고리즘도 일종의 우선순위 스케줄링 방식입니다. (프로세스의 CPU 버스트 타임기준으로 실행)

선점형과 비선점형 스케줄링이 모두 가능합니다.

높은 우선순위의 프로세스가 계속오면 낮은 우선순위의 프로세스는 무한 대기해 기아 현상이 올 수 있습니다.

기아 문제는 aging으로 해결할 수 있습니다. 예를들어, 대기시간이 늘어날 수록 우선순위를 증가시키면 됩니다.

 

• 다단계 큐 스케줄링 (MLQ, Multi Level Queue)

각 큐는 절대적인 우선순위를 가지며 우선순위가 높은 큐가 모두 비어있기 전까지는 낮은 우선순위의 큐에 있는 프로세스는 실행이 불가능합니다.

우선순위가 낮은 큐의 프로세스는 starvation 현상이 일어날 수 있습니다.

 

• MLFQ(Multi-Level Feedback Queue) 다단계 피드백 큐 스케줄링

MLQ에서 계속해서 프로세스를 선점하지 못하는 프로세스에 대해 큐를 이동 시켜주는 방식을 사용합니다. 즉, 다단계 큐 방식에서 오래 대기한 프로세스가 높은 레벨의 대기 큐로 이동합니다.

또는 프로세스 버스트 시간이 짧은 프로세스에 높은 우선순위를 주어 일찍 종료시키거나 시간이 너무 오래걸리면 낮은 우선순위로 변경시킵니다.

정리

• 멀티 프로그래밍의 목적은 CPU가 항상 어떤 프로세스가 실행되는 상태를 유지하는 것입니다.
• 프로세스 스케줄러는 실행가능한 여러 프로세스 중에서 하나의 프로세스를 선택하여 CPU에게 해당 프로세스를 실행시키도록 합니다.
• 프로세스가 메모리에 올라오면 진행과정에 따라 생성, 준비, 실행, 대기, 종료 상태를 가지게 됩니다.
• CPU 스케줄링은 프로세스의 생명주기를 관리하며, 스케줄링을 통해 CPU의 효율을 최대한 끌어올릴 수 있습니다.
• CPU 스케줄링에는 선점 및 비선점 스케줄링이 있으며, 프로세스가 CPU를 점유한 상태에서 종료되지 않았을 때 CPU 점유를 뺐어올 수 있는지에 따라 나뉩니다.
• 디스패처는 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈입니다.
• CPU 스케줄링은 CPU 이용률, 처리량, 총 처리 시간, 대기 시간, 응답 시간을 기준으로 스케줄링 됩니다.
• CPU 스케줄링 알고리즘은 선입 선처리 스케줄링, 최단 작업 우선 스케줄링, 라운드 로빈 스케줄링, 우선순위 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링 등이 있습니다.