CPU 스케줄링

CPU 스케줄링

• CPU의 자원을 프로세스에 배분하는 것
• 대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행 => 프로세스는 실행 상태와 대기상태를 반복하며 실행
• 실행(CPU사용) -> 대기(입출력 장치사용) -> 실행(CPU사용) -> 대기(입출력 장치사용) -> 실행(CPU사용) -> 대기(입출력 장치사용)
• CPU 스케줄링이 필요한 이유 : 프로세스마다 CPU를 할당받아야 하는 우선순위가 다르기때문
• 입출력 집중 프로세스와 CPU 집중 프로세스로 나뉘는데 비교적 CPU의 점유율이 적은 입출력 집중 프로세스의 우선우뤼를 높이고 CPU 집중 프로세스의 우선순위를 후순위로 지정하여 입출력 집중 프로세스의 작업을 먼저 처리하고 나머지 CPU 집중 프로세스를 처리함 => 문맥교환의 오버헤드를 줄임

스케줄링 큐

• 운영체제는 프로세스들에게 줄서서 자원을 할당받기를 기다리게함 => 자원을 할당받기를 기다리는 장소 : 스케줄링큐
• 스케줄링 큐는 자원 별로 나뉘어 생성됨
• 준비 큐 : CPU를 사용해야 하는 프로세스들이 대기하는 큐
• 대기 큐 : 입출력 장치를 사용하기를 기다리는 프로세스들이 대기하는 큐
• 큐에 적재된 순서에 상관없이 우선순위가 높은 프로세스는 우선순위가 낮은 프로세스 보다 먼저 처리됨

선점형 스케줄링

• 프로세스가 CPU를 사용하고 있어도 운영체제가 사용중인 CPU를 강제로 빼앗아 다른 프로세스에 할당 하는 방식
• 특정 프로세스가 CPU를 독점할 수 없는 방식
• 프로세스마다 정해진 시간동안 CPU를 사용하고 정해진 시간이 끝나 타이머 인터럽트가 발생하면 운영체제가 CPU를 빼앗아 다른 프로세스에 할당하는 방식은 선점형 스케줄링의 방식
• 특정 프로세스가 CPU를 독점할 수 없고, 자원을 골고루 배분할 수 있지만 그만큼 문맥교환 오버헤드가 발생함
• 자원을 빼앗을 수 있음

비선점형 스케줄링

• 프로세스가 CPU를 사용하는 동안 다른 프로세스가 끼어들어 CPU를 사용할 수 없는 스케줄링 방식
• 하나의 프로세스가 CPU를 독점해서 사용할 수 있는 방식
• 문맥교환의 횟수가 선점형 스케줄링보다 적기때문에 문맥교환에서 발생하는 오버헤드가 적음
• 모든 프로세스가 자원을 골고루 사용할 수 없다는 단점이있음
• 자원을 빼앗을 수 없음

CPU 스케줄링 알고리즘

선입 선처리 스케줄링

• 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
• 프로세스들이 cpu를 할당받기 위해 기다리느 시간이 길어짐 => 호위효과 발생

최단 작업 우선 스케줄링

• 준비큐에 삽입된 프로세스들 중 cpu의 이용시간의 길이가 가장 짧은 프로세스부터 실행하느 스케줄링 방식
• 비선점형 스케줄링 알고리즘
• cpu의 이용시간이 짧은 프로세스들 부터 처리하기 때문에 호위효과를 방지할 수 있음

라운드 로빈 스케줄링

• 선입 선처리 + 타임슬라이스
• 정해진 시간만큼 돌아가면 cpu를 할당받는 선점형 스케줄링 방식
• 프로세스가 cpu를 할당받아 작업을 처리하고 남은 작업이 있을때 다시 준비큐의 맨뒤로 돌아가서 삽입됨 => 문맥교환 발생
• 타임슬라이스의 크기가 길면 선입선처리 스케줄링과 다르지 않아서 호위효과가 발생할 수 있고, 타임슬라이스의 크기가 작으면 문맥교환에 오버헤드가 발생할 수 있음

최소 잔여 시간 우선 스케줄링

• 최단작업 우선 스케줄링 알고리즘 + 라운드 로빈 알고리즘
• 정해진 시간만큼 cpu를 사용하고, cpu를 사용할 다음 프로세스는 남아있는 작업이 가장 적은 프로세스가 선택됨

우선순위 스케줄링

• 프로세스에 우선순위를 부여하고 우선순위가 가장 높은 프로세스 부터 처리하는 스케줄링 방식 => 우선순위가 같은 프로세스들은 선입선처리 방식으로 스케줄링됨
• 우선순위가 높은 프로세스 부터 처리되기 때문에 우선순위가 낮은 프로세스는 cpu를 할당받지 못하는 기아현상 발생가능
• 기아현상을 방지하기 위해 에이징이라는 기법이있음 => 우선순위가 낮은 프로세스의 대기시간이 길어질때 마다 우선순위가 낮은 프로세스의 우선순위를 높이는 방식

다단계 큐 스케줄링

• 우선순위 스케줄링의 발전한 형태
• 준비큐를 여러개 사용하는 스케줄링 방식
• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면 다음 큐에 있는 프로세스들을 처리함 => 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 용이함
• 큐마다 프로세스를 처리하는 스케줄링 방식이 다르게 적용될수도 있고, 입출력 집중 프로세스, cpu 집중 프로세스를 나눠서 큐에 저장할 수 있음
• 프로세스들이 큐 사이를 이동할 수 없음

다단계 피드백 큐 스케줄링

• 프로세스들이 큐 사이를 이동할 수 있음
• 프로세스의 작업이 끝나지 않는 다면 우선순위 큐에 삽입되어 실행됨 => 실행이 끝날때 까지 우선순위 큐를 1개씩 내려가며 프로세스가 큐에 쌓임
• cpu를 오래사용해야 하는 cpu 집중 프로세스는 우선순위가 낮아지고, cpu를 적게 사용하는 입출력 집중 프로세스는 우선순위가 높은 큐에서 실행이 끝남
• 낮은 우선순위 큐에서 오래 기다리고 있는 프로세스가 있으면 우선순위를 높은 큐로 이동시켜 기아현상을 방지할 수 있음
• 특정 프로세스의 cpu이용 시간이 길면 낮은 우선순위 큐로 이동시키고 낮은 우선순위 큐에서 오래 기다리면 우선순위를 높혀 cpu가 프로세스를 처리할 수 있는 스케줄링 방식