혼자 공부하는 컴퓨터 구조 + 운영체제를 읽고 공부한 내용입니다.CPU 스케줄링 개요
CPU 스케줄링은 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 말한다.
프로세스 우선순위
프로세스마다 우선순위가 있다.
이 우선순위가 높을 수록 빨리 처리해야 하는 프로세스이다.
입출력 작업이 많은 프로세스를 입출력 집중 프로세스,
CPU작업이 많은 프로세스를 CPU 집중 프로세스라고 한다.
두 프로세스 중 우선 순위가 높은 것은 입출력 집중 프로세스이다.
입출력 집중 프로세스를 먼저 실행 시켜 입출력 장치를 작동하는 동안 CPU 집중 프로세스를 사용하면 효울적이기 떄문이다.
이렇게 운영체제는 각각의 상황에 맞게 프로세스에게 CPU를 할당한다.
그래서 운영체제는 프로세스마다 우선순위를 부여하고 이 우선순위는 PCB에 저장이 된다.
스케줄링 큐
PCB의 우선순위가 적혀 있다고 해서 운영체제가 직접 PCB를 찾아 다니는 것은 시간이 오래 걸리고 비효율적이다.
그래서 운영체제는 프로세스들이 줄을 서서 기다리게 한다.
운영체제는 이 줄을 스케줄링 큐에 담아서 관리한다.
운영체제는 관리하는 대부분의 자원을 큐로 관리한다.
이런 큐에는 대표적으로 준비 큐와 대기 큐가 있다.
준비 큐는 CPU를 이용하기 위해서 기다리는 것이고
대기 큐는 입출력 장치를 이용하기 위해서 기다리는 것이다.
준비 큐와 대기 큐 모두 들어온 순서대로 실행을 한다.
하지만 우선순위가 높은 프로세스를 먼저 실행을 한다.
뒤늦게 들어왔더라도 우선순위가 높으면 먼저 들어온 프로세스 보다 먼저 실행이 된다.
프로세스의 상태 다이어그램에서 준비 큐와 대기 큐를 넣으면 과정이 이해하기가 쉽다.
선점형과 비선점형 스케줄링
만약 운영제체가 프로세스에 CPU를 할당해서 실행 중에 있는데 다른 프로세스가 급하게 CPU 사용을 요청한다면 2가지를 선택할 수 있다.
첫 번째는 현재 진행 중인 프로세스를 중단하고 급한 프로세스에 CPU를 할당하는 것과
두 번째는 현재 진행 중인 프로세스가 끝날 때까지 기다리게 한 다음 끝나고 나서 CPU를 할당하는 방법이다.
첫 번째의 경우는 선점형 스케줄링이라고 하는데, 프로세스가 CPU를 사용하고 있더라도 운영체제가 프로세스로부터 자원을 빼앗아 다른 프로세스에게 할당하는 스케줄링 방식이다.
두 번째의 경우는 비선점형 스케줄링이라고 하고 이미 프로세스가 자원을 사용하고 있다면, 그 프로세스가 종료되거나 대기 상태가 될 때까지 기다렸다가 자원을 할당 받는 스케줄링 방식이다.
선점형 스케줄링은 자원의 독점을 막고 골고루 분배할 수 있지만
그 만큼 문맥 교환이 자주 일어나기 때문에 그 과정에서 오버헤드가 발생할 수 있다.
비선점형 스케줄링은 문맥교환이 적게 일어나서 오버헤드 발생할 확률이 적지만 모든 프로세스가 자원을 골고루 이용하기가 힘들다.
CPU 스케줄링 알고리즘
스케줄링 알고리즘 종류
선입 선처리 알고리즘은 FCFS스케줄링이라고도 한다.
준비 큐에 삽입이 된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다.
이 알고리즘의 단점은 들어오는 순서대로 실행을 하기 때문에 만약 마지막에 들어온 프로세스처리 시간이 2초 밖게 되지 않는데
먼저 들어온 프로세스들이 17초, 10초 라면 2초를 실행하기 위해서 27초를 기다려야 하는 호위 효과라는 현상이 발생한다.
최단 작업 우선 스케줄링은 SFJ스케줄링이라고도 한다.
최단 작업 우선 스케줄링은 준비 큐에 들어온 프로세스 중 CPU이용 시간이 짧은 프로세스부터 실행하는 알고리즘이다.
라운드 로빈 스케줄링은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 붙혀진 알고리즘이다.
타임 슬라이스는 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다.
준비 큐에 삽입이 된 프로세스들은 타임 슬라이스에 맞춰서 CPU를 이용하고 프로세스가 다 끝나지 않았다면 준비 큐에 맨 뒤로 삽입이 된다.
최소 잔여 시간 우선 스케줄링은 SRT 스케줄링이라고 불리기도 한다.
최소 잔여 시간 우선 스케줄링은 최단 작업 우선 스케줄링과 라운드 로빈 알고리즘을 합친 알고리즘이다.
프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세는 남아있는 작업 시간이 짧은 프로세스가 선택이 된다.
우선순위 스케줄링은 프로세스들에게 우선순위를 부여하고 가장 높은 우선순위의 프로세스부터 실행하는 알고리즘이다.
하지만 근본적인 문제가 있는데 중간 중간 우선순위가 높은 프로세스가 들어오면 우선순위가 낮은 프로세스는 계속 뒤로 밀리게 된다.
이를 기아 현상이라고 한다.
이를 방지하기 위한 기법으로 에이징이 있다.
에이징은 오랫동안 대기한 프로세스의 우선순위를 점차 높히는 방식이다.
다단계 큐 알고리즘은 우선순위 별로 큐를 여러 개 사용하는 알고리즘이다.
우선순위가 가장 높은 큐에 들어온 프로세스부터 처리하고 다음 우선순위의 큐를 처리하는 방식이다.
큐별로 타임 슬라이드를 지정할 수 있고 큐 마다 다른 스케줄링 알고리즘을 사용할 수 있다.
다단계 피드백 큐 알고리즘은 다단계 큐에서 프로세스들이 큐 사이를 이동할 수 있는 알고리즘이다.
다단계 큐 알고리즘에서는 프로세스들이 다른 큐로 이동을 하지 못 했다.
그래서 우선순위가 높은 큐에 프로세스들이 들어오면 다음 우선순위 큐의 프로세스들이 순서가 밀리는 기아 현상이 발생한다.
만약 우선순위가 높은 큐에서 프로세스가 다 끝나지 못하면 위선순위가 낮은 큐로 들어간다.
또, 계속 낮은 우선순위의 큐에 있는 프로세스들은 에이징 기법으로 점차 높은 우선순위 큐로 이동한다.
이 알고리즘이 가장 일반적인 CPU 스케줄링 알고리즘이다.
