스케줄링

스케줄링 목적

• 공평성: 특정 프로세스가 실행되지 않는 경우가 없도록 해야한다.
• 효율성: 자원을 효율적으로 사용해 자원이 사용되지 않는 시간이 없도록 해야 한다.
• 안정성: 우선순위의 프로세스를 먼저 처리하도록 해야한다.
• 반응 시간 보장: 프로세스가 오랜 시간 응답이 없으면 사용자는 시스템이 멈춘 것으로 보기 때문에 일정 시간 내에 응답할 수 있도록 해야한다.
• 무한 연기 방지: 특정 프로세스에 대한 처리가 무한히 연기되지 않도록 스케줄링해야 한다.

스케줄링의 단계

장기 스케줄링(잡 스케줄링, 승인 스케줄링)

준비 큐에서 어떤 프로세스를 넣을지 결정해 메모리에 올라가는 프로세스 수를 조절한다.

중기 스케줄링

메모리에 로드된 프로세스 수를 동적으로 조절한다. 메모리에 프로세스가 많이 로드되면 스왑 아웃해서 일부 프로세스를 통째로 저장한다. 여기서 스왑 아웃된 프로세스는 중단 상태가 된다.

단기 스케줄링(CPU 스케줄링)

준비 큐에 있는 대기 상태 프로세스 중 어떤 프로세스를 다음으로 실행할지 스케줄링 알고리즘으로 결정한다. 즉, 어떤 프로세스를 디스패치할 지 결정한다.

디스패치(dispatch): CPU 코어의 실행 대상을 다음 프로세스(또는 스레드)로 전환하는 작업

스왑 아웃: 메모리 공간보다 많은 프로세스가 로드 될 때 이벤트 발생을 기다리고 있는 프로세스를 통째로 저장공간(SSD)로 옮겨 저장하는 것을 의미한다.

스왑인: 스왑 아웃한 프로세스에서 이벤트 요청이 오면 해당 프로세스를 다시 메모리에 로드하는 것이다.

스와핑: 위 과정을 스와핑이라 한다.

스케줄링 알고리즘

CPU 스케줄러가 준비 큐에 있는 프로세스 중 어떤 프로세스를 실행시킬지 결정하는 데 사용한다. 즉, 실행하려는 프로세스가 여러 개 존재하는 상황에서 CPU를 누구한테 얼마나 줄까를 결정해야한다.

스케줄링 알고리즘은 스케줄링의 목적을 달성하기 위해 다음과 같은 기준으로 평가한다. 하지만 아래 내용을 모두 만족하기는 어려우므로 어떤 기준을 더 중요하게 여길지 판단해야한다.

• CPU 사용률: CPU를 놀리지 않고 사용하는지 판단
• 처리량: 단위 시간 당 실행한 프로세스 수
• 응답 시간: 프로세스에 요청이 발생했을 때 응답까지 걸리는 시간
• 반환 시간: 프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간
• 대기 시간: 프로세스가 대기 큐에서 대기하는 시간의 총합

스케줄링 알고리즘은 비선점형과 선점형으로 나뉜다.

비선점형 스케줄링

실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음을 의미한다. 특정 CPU 코어가 프로세스가 종료될 때까지 점유되며 OS가 중간에 멈추고 다른 프로세스를 실행시키지 못한다.

뜻을 보면 선점형 스케줄링이 어울린다고 생각했지만 다른 프로세스가 선점 못하기 때문에 비선점형으로 지어진 듯 하다.

FCFS 스케줄링

준비 큐에 먼저 들어온 프로세스가 우선순위를 갖는 알고리즘이다. 따라서 준비 큐에 먼저 들어온 프로세스를 먼저 실행한다.

SJF 스케줄링

실행 시간이 짧은 프로세스가 우선순위를 갖는 알고리즘이다. 준비 큐에 있는 프로세스 중 CPU를 점유하는 실행 시간이 가장 짧은 프로세스부터 실행한다.

선점형 스케줄링

스케줄러가 실행 중인 프로세스를 중단시키고 다른 프로세스를 실행할 수 있음을 의미한다.

RR 스케줄링

프로세스 간 우선순위가 없다. 모든 프로세스를 순서대로 일정 시간 동안 실행하며, 일정 시간을 초과하면 다른 프로세스를 실행한다.

SRTF 스케줄링

준비 큐에서 대기 시간이 가장 짧게 남은 프로세스를 우선 수행하는 알고리즘이다. 만약 한 프로세스가 실행 중일 때 실행 시간이 더 짧은 프로세스가 준비 큐에 들어오면 실행 시간이 더 짧은 프로세스가 CPU를 차지하게 된다.

멀티 레벨 스케줄링

준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘이다. 분리한 큐는 각각 우선순위가 있고 각자 다른 스케줄링 알고리즘을 적용할 수 있다.

여러 개의 큐는 foreground 큐와 background 큐로 나뉜다. foreground 큐에는 응답 속도가 중요한 프로세스가 들어가고, background 큐에는 응답 속도보다 성능을 더 중요시하는 프로세스가 들어간다.

예를 들면 다음과 같다.

Foreground Queue → 사용자와 직접 상호작용하며 응답 속도가 중요한 프로세스들

• 게임
• UI 앱
• 채팅

Background Queue → 오래 걸려도 되며 성능을 더 중요시 하는 프로세스들

• 백업
• 압축
• 로그 정리