티스토리 뷰

컴퓨터 구조론/CPU

CPU scheduling

로또_ 2019. 10. 13. 17:31

문맥교환(Context Switching)

새로운 프로세스에게 CPU를 할당하기 위해 현재 CPU가 할당된 프로세스의 상태 정보를 저장하고, 새로운 프로세스의 상태 정보를 설정한 후 CPU를 할당하여 실행되도록 하는 작업. (Overhead가 발생하는 주요 원인)

CPU 스케줄링이란?

메모리에 있는 준비(Ready) 상태의 프로세스 중 하나를 선택해 CPU자원을 할당하는 것

CPU 스케줄링이 일어나는 시점

선점과 비선점의 차이는 기존에 CPU를 사용하던 프로세스가 계속 프로세스를 사용할 수 있는데도 불구하고 자원을 빼앗는지에 대한 여부

CPU 스케줄링 종류

비선점(Non-preemptive) 스케줄링

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이다.

프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용한다.

일괄 처리 방식의 스케줄링(공정하지만 긴급 응답을 요하는 작업에 좋지 않다.)

종류

FCFS(First Come First Service) : 준비상태 큐에 도착한 순서에 따라 CPU를 할당하는 기법. 공평성은 유지되지만 짧은 작업이 긴 작업을, 중요한 작업이 중요하지 않은 작업을 기다리게 됨
SJF(Shortest Job First) : 실행시간이 가장 짧은 프로세스에 먼저 CPU를 할당하는 기법. 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘
HRN(Highest Response ratio) : 실행 시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로 우선순위 계산 결과 값이 높은 것부터 우선순위가 부여된다. 대기 시간이 길수록 계산 결과가 높다. (대기시간 + 서비스시간 / 서비스시간)
기한부(DeadLine) : 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법
우선순위(Priority) : 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법

선점(Preemptive) 스케줄링

하나의 프로세스가 CPU를 할당받아 실행 하고 있을 때 우선순위가 높은 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

선점으로 인한 많은 오버헤드가 발생한다.

시분할 시스템에 사용하는 스케줄링이다. (긴급을 요하는 우선순위를 갖는 시분할 처리, 실시간 처리에 유용)

선점을 위해 시간 배당을 위한 인터럽트용 타이머 클럭(Clock)이 필요하다.

종류

SRT(Shortest Remaining Time) : 현재 실행 중인 프로세스의 남은 시간과 대기 큐에 프로세스의 실행시간이 가장 짧은 프로세스에게 CPU를 할당하는 기법 (비선점 기법인 SJF 알고리즘의 선점 형태로 변경한 기법)
선점 우선순위 : 준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
RR(Round Robin) : 시분할 시스템을 위해 고안된 방법으로, FCFS 알고리즘을 선점 형태로 변형한 기법. 대기 큐를 사용하여 먼저 대기한 작업이 먼저 CPU를 사용한다. CPU를 사용할 수 있는 시간(Quantum)동안 CPU를 사용한 후에 다시 대기 큐의 가장되로 배치된다. 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 시간이 작을 경우 문맥교환 및 오버헤드가 자주 발생됨
다단계 큐 : 프로세스를 특정 그룹으로 분류할 수 있는 경우 그룹에 따라 각기 다른 준비상태 큐를 사용한다.
다단계 피드백 큐 : 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법

에이징(Aging) 기법

특정 프로세스의 우선순위가 낮아 무한정 기다리게 되는 경우, 한번 양보하거나 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계식 높여 가까운 시간 안에 자원을 할당받도록 하는 기법

SJF나 우선순위 기법에서 발생할 수 있는 무한 연기 상태, 기아 상태를 예방할 수 있다.