OS 면접 스터디 3주차 - CPU 스케줄링

CPU 스케줄링

• 운영체제에서 프로세스들이 CPU를 사용할 수 있도록 하는 순서를 결정하는 과정입니다. 즉, 언제 어떤 프로세스에 CPU를 할당할 지 결정하는 작업
• 응답 시간, 대기 시간, 소요 시간은 짧게, 이용률, 처리량은 높게, 모든 프로세스가 CPU를 사용할 수 있도록 하는 것이 목표

성능 척도

• CPU utilization (이용률)
• Throughput (처리량): 단위 시간당 완료한 프로세스 양
• Turnaround time (소요시간, 반환시간): 대기 큐에 들어와서 프로세스가 모두 완료될 때까지 걸린 총 시간 (프로세스 종료 시간 - 프로세스 도착 시간)
• Waiting time (대기시간): 대기 큐에서 CPU를 할당받기 위해 기다린 시간 총합
• Response time (응답시간): CPU를 얻으러 와서 최초로 CPU를 얻기까지 걸린 시간

 

기아 상태 (Starvation)

특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태

자원을 할당받는 데 높은 우선순위를 가진 프로세스가 계속해서 자원을 획득하여 낮은 우선순위를 가진 프로세스가 계속 대기하는 경우에 발생

교착 상태 vs 기아 상태

• 기아 상태는 특정 프로세스가 자원을 할당받지 못해 장기간 대기하게 되는 상황이고, 주로 자원 스케줄링의 불공평성에서 비롯됩니다.
• 교착 상태는 여러 프로세스가 서로의 자원을 기다리며 대기하는 상황으로, 순환 대기가 발생할 때 시스템이 멈추는 상태입니다.

기아 상태 해결 방법

우선순위 증가 (Aging)

프로세스가 자원을 기다린 시간에 비례하여 그 프로세스의 우선순위를 점진적으로 높이는 방법입니다. 시간이 지남에 따라 낮은 우선순위를 가진 프로세스도 결국 높은 우선순위를 가지게 되어 자원을 할당받을 가능성이 높아집니다.

 

CPU 스케줄러 종류 

스케줄러: 어떤 프로세스에게 자원을 할당할지를 결정하는 운영체제 커널의 모듈

장기 스케줄러 (Long-Term Scheduler)

• 작업 스케줄러 (Job Scheduler)
• 시스템에 있는 작업(Job) 중에서 어떤 작업을 메모리로 로드하여 실행할 것인지를 결정
• 작업을 메모리에 올려서 ready queue에 넣고, 동시에 실행되는 프로세스 수를 조절 (Degree of Multiprogramming) 하는 역할
• 현대의 인터랙티브 시스템에서는 거의 사용되지 않으며, 대부분의 스케줄링이 중단기 스케줄러에 의해 이루어짐

중기 스케줄러 (Medium-Term Scheduler)

• 현재 실행 중이거나 준비 상태에 있는 프로세스를 중지(Suspend)하거나 다시 준비 상태로 전환하는 역할
• 시스템의 메모리 사용량을 관리하고, 메모리 확보가 필요할 때 프로세스 일부를 중단시키고 그 내용을 디스크의 스왑 영역에 저장하는 Swap out을 하고, 메모리가 남으면 다시 Swap in
• 동시에 실행되는 프로세스 수를 조절하는 역할 (degree of Multiprogramming)

단기 스케줄러 (Short-Term Scheduler)

• CPU 스케줄러
• 준비 큐에 있는 프로세스 중에서 미리 정한 스케줄링 알고리즘에 따라 어떤 프로세스가 CPU를 사용할지를 결정
• 빈번하게 호출되고 수행속도가 빠름

스케줄링 알고리즘

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

선점형 스케줄링:

어떤 프로세스가 CPU를 할당 받아 실행 중이더라도 강제로 중단시키고 다른 프로세스에 CPU를 할당할 수 있는 방식

처리 시간이 매우 긴 프로세스의 CPU 독점을 막을 수 있지만 잦은 Context Switching으로 인한 오버헤드가 클 수 있음

비선점형 스케줄링:

어떤 프로세스가 CPU를 점유하고 있을 때 강제로 프로세스를 중지할 수 없는 방식

중요하거나 짧은 프로세스도 긴 응답시간과 대기시간이 발생할 수 있음

비선점형 스케줄링

선입선출 스케줄링 (FCFS)

• First Come First Served
• 프로세스가 레디큐에 도착한 순서대로 CPU를 할당

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

• Shortest Job First
• 실행 시간이 가장 짧은 프로세스를 먼저 실행
• 우선순위가 낮으면 영원히 실행이 안 되는 Starvation 문제 발생 가능
• 평균 대기시간을 최소화할 수 있음

우선순위 스케줄링 (Priority)

• 각각의 프로세스에 우선순위 넘버가 있는 알고리즘
• SJF의 Starvation 문제를 해결하기 위해 오래 기다린 작업의 우선순위를 높이는 Aging을 사용

선점형 스케줄링

최소 잔류 시간 우선 스케줄링(SRTF)

• 실행 시간이 가장 짧은 프로세스를 먼저 실행 (SJF와 동일)
• 실행되고 있는 프로세스의 남은 시간보다 더 빨리 끝날 수 있는 짧은 프로세스가 들어오면 현재 실행되는 프로세스를 중단하고 짧은 프로세스를 실행

라운드 로빈 스케줄링 (RR)

• 각 프로세스는 동일한 할당 시간을 가짐
• 할당 시간이 지나면 프로세스는 선점(preemptive) 당하고 ready queue의 제일 뒤로 감

멀티 레벨 큐 스케줄링 (Multi-level Queue)

• 프로세스들을 여러 개의 큐로 나누어 각각의 큐에 다른 스케줄링 알고리즘을 적용
• 프로세스들은 특정 기준(우선순위, 프로세스 타입, 필요 자원 등)에 따라 여러 큐로 분류됩니다. 예를 들어, 시스템 프로세스, 대화형 사용자 프로세스, 배치 작업 등이 각각 다른 큐에 배치될 수 있음
• 한 번 큐에 들어간 프로세스는 그 큐를 벗어나지 않음
• 각 큐는 서로 다른 우선순위를 가짐. 예를 들어, 시스템 큐는 사용자 프로세스 큐보다 높은 우선순위를 가질 수 있으며, 이 경우 시스템 큐가 비어 있을 때만 사용자 프로세스 큐에서 프로세스를 선택합니다.
• 높은 우선순위 큐는 RR, 낮은 우선순위 큐는 FCFS 사용 가능

멀티 레벨 피드백 큐 스케줄링 (Multi-level Feedback Queue)

• 프로세스의 우선순위를 동적으로 변경하며, 여러 개의 큐를 사용하여 각각 다른 스케줄링 알고리즘을 적용
• 멀티 레벨 큐와 같이 프로세스들을 특정 기준에 따라 여러 큐로 분류하고, 큐 간에 우선순위를 둠
• 멀티 레벨 큐와의 차이점: 프로세스를 다른 큐로 이동 가능