CPU 스케줄링

 

스케줄링 개요

CPU 스케줄링이란 어떤 작업에 CPU를 배정할지 결정하는 것이다. 컴퓨터 시스템 효율은 어떤 프로세스에 CPU를 먼저 배정하느냐에 따라 달라지므로 작업의 형펑성과 효율성을 결정하는 것은 중요한 일이다.

CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정한다.

 

CPU 스케줄링

고수준 스케줄링

고수준 스케줄링은 시스템 내의 전체 작업 수를 조절하는 것이다. 

작업이란 운영체제에서 다루는 단위로 1개 또는 여러개의 프로세스로 이루어진다. 

고수준 스케주링은 작업이오면 작업을 승인할지 거부할지를 결정한다.

즉 고수준 스케줄링에 따라 시스템 내에서 동시에 실행 가능한 프로세스의 총 개수가 정해진다.

 

중간 수준 스케줄링

중간 수준 스케줄링은 저수준과 고수준 사이에 일어난다.

고수준 스케줄러에 의해 프로세스를 활성화 하더라도 여러가지 사정에 의해 보류상태 즉 메모리에서 내려가 스왑영역으로 보낸다. 중간 수준 스케줄러는 중지와 활성화 상태를 이용해 메모리를 효율적으로 사용하도록 한다.

 

저수준 스케줄링

저수준 스케줄링은 어떤 프로세스에 cpu를 할당할지 대기상태를 보낼지 등을 결정하는 일이다. 

 

스케줄링 목적

공평성: 모든 프로세스가 자원을 공평하게 배정받아야하며 그 과정에서 프로세스가 배제되어선 안된다.

효율성: 시스템 자원이 유후 시간 없이 사용되도록 하고, 유후 자원을 사용하려는 프로세스에게 우선권을 준다.

안정성: 우선순위를 사용하여 프로세스가 독점하거나 파괴하지 않고 알맞은 순서로 작동하도록 해야한다.

확장성: 프로세스가 증가하더라도 시스템이 안정적으로 작동하도록 조치해야한다. 자원이 늘어나면 프로세스도 혜택

반응시간보장: 프로세스는 일정 시간안에 프로세스의 요구에 반응해야한다.

무한연기방지: 공평성과 비슷한 맥락으로 특정 프로세스의 작업이 무기한 연기되어선 안된다.

 

스케줄링 시 고려 사항

CPU 사용률: CPU 사용시간/ 전체 동작시간

처리량: 프로세스의 수/단위 시간 

대기시간: 프로세스들의 대기시간의 합/ 프로세스 수

응답시간: 프로세스 시작 후 첫번 째 반응

반환시간: 프로세스가 생성된 후 자원을 모두 반환하는데 까지 걸린 시간 (대기시간 + 실행시간)

주로 대기시간이 계산하기 쉽고 프로세스의 성능을 잘 나타내서 성능을 비교할 때 사용한다.

 

선점형 스케줄링

선점형 스케줄링은 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다.

예를들어 프로세스가 CPU를 할당받아서 작업하는 도중 입출력이 발생해 인터럽트가 발생하면 프로세스를 대기상태로 보내고 새로운 프로세스가 CPU를 할당 받는다. 선점형 스케줄링은 CPU를 독점하지 않고 컨텍스트 스위칭이 발생해 CPU 집중 우선 프로세스보다는 빠른 반응이 필요한 입출력 우선 프로세스에 알맞다.

 

RR(Round Robin)

음 라운드 로빈 의미하는 바는 대충 원형을 의미한다. 한바퀴를 돈다는 의미 정도?

라운드 로빈은 FCFS처럼 먼저 들어온 프로세스를 가장 먼저 처리하되 타임슬라이스가 지나거나 인터럽트가 발생하면 다른 프로세스에게 CPU를 양보하는 방식이다. 

 

SRT(Shortest Remaining Time)

해석해보면 가장 짧은 남은 시간을 가진 프로세스를 먼저 처리하는 방식이다.

프로세스가 준비상태 큐에 쌓이면 그 중 가장 짧은 작업시간을 가진 프로세스를 먼저 실행 하는 것이다. 

RR과 SJF를 합친 방식, 프로세스의 남은 시간을 주기적으로 계산하고 컨텍스트 스위칭이 계속 발생해 계산량이 많아 효율적이진 못하다.

 

비선점형 스케줄링 

비선점형 스케줄링은 어떤 프로세스가 CPU를 할당받아 실행 중이라면 다른 프로세스가 이를 뺴앗을 수 없는 스케줄링 방식이다.

예를들어 프로세스가 CPU를 할당 받으면 프로세스를 강제로 죽이거나 프로세스 스스로 종료되거나 대기상태에 들어가기 전까지 계속 점유해서 사용한다. 이 때문에 하나의 프로세스를 빠르게 처리되겠지만 쌓인 프로세스들의 대기시간이 길어질 것이다. 

 

FCFS(First Come First Served)

곧이 곳대로 해석하면 가장 먼저 들어온 것을 가장 먼저 처리한다 즉 큐와 같은 방식인 것 이다.

모든 프로세스의 우선순위가 동등하고 들어온 순서로 처리한다.

이는 굉장히 단순하고 공평하지만 처리 시간이 긴 프로세스가 먼저 들어오면 하염없이 기다려야한다.

 

SJF(Shortest Job First)

해석하면 가장 짧은 작업 시간을 가진 프로세스를 가장 먼저 실행하는 것이다. 

짧은 대기시간을 가진 프로세스를 우선순위를 높여 먼저 실행함으로 대기시간을 줄어드나 프로세스가 길 경우 무한 봉쇄 현상이 나타날 수 있다. 또한 프로세스의 작업시간을 정확히 예측하는것은 어렵다(상호작용하는 프로세스가 많이 때문).

각 프로세스의 뒤로 밀리는 횟수를 제한하는 방식, 이도 결국 하나의 긴 대기시간을 발생할 것이며, 횟수를 제한하는 기준을 정하는 것도 쉽지 않다.

 

HRN(Highest Response Ratio Next)

해석하면 가장 높은 응답률을 가진 프로세스를 먼저 실행하는 것이다.

높은 응답률은 어떻게 구할까? (대기시간 + CPU 작업시간)/ CPU 작업시간 으로 응답률을 구한다.

즉 CPU 작업시간이 클수록 뒤로 밀리지만 대기시간이 늘어날 수록 우선순위가 증가한다. 그래도 프로세스의 작업시간이 아주 길다면 아사현상은 발생하지 않겠지만 우선순위의 증가가 아주 느릴 것이다. 

 

우선순위스케줄링

프로세스마다 우선순위를 정해 우선순위에 따라 프로세스를 실행한다.

SJF: 작업시간이 짧을 수록 우선순위가 높다.

HRN: 응답률이 높을 수록 우선순위가 높다.

SRT: 잔여시간이 낮을수록 우선순위가 높다. 

고정우선순위 스케줄링: 우선순위가 변하지 않고 계속해서 해당 우선순위로 프로세스를 진행시킨다.

변동우선순위 스케줄링: 일정시간마다 우선순위를 재계산하고 이를 반영시켜 프로세스를 진행시킨다.

보통 우선순위는 시스템의 효율성보다는 프로세스의 중요도에 따라 정해진다.

 

다단계 큐 스케줄링(MultiLevelQueue)

해석해보면 다양한 레벨의 큐에 프로세스를 넣고 레벨큐에 의해 프로세스가 작동한다.

기본적으로 라운드 로빈 스케줄링 방식을 이용하며 고정 우선순위 스케줄링을 사용한다.

즉 프로세스가 생성되면 우선순위에 따라 큐에 들어가고 타임슬라이스가 지나거나 인터럽트에 의해 다시 준비상태로 오더라도 같은 우선순위를 유지한다. 하위 우선순위 큐는 상위 우선순위 큐가 비어있어야 실행시킬 수 있다.

 

다단계 피드백 큐 스케줄링 (MultiLevelFeedbackQueue)

해석해보면 다양한 레벨의 큐에 프로세스를 넣고 레벨큐에 의해 프로세스가 작동하되 계속해서 피드백을 받아 수정하는 스케줄링 방식이다.

프로세스가 CPU를 할당받아 진행후 다시 준비상태로 돌아오면 한단계 밑에 큐로 들어가며 각 레벨이 낮아질 수록 타임슬라이스를 높여 공정성, 효율성, 무기한연장 등을 고려해 프로세스를 실행한다.

 

 

CPU 집중 프로세스와 입출력 프로세스

CPU 집중프로세스는 주로 작업시간이 긴 프로세스이고 입출력 프로세스는 입출력이 많은 프로세스이다.

주로 입출력 프로세스의 우선순위를 높이면 입출력은 인터럽트에 의해 자주 대기상태에 들어가기 때문에 전체적인 대기시간을 줄일 수 있다. 이러한 입출력 프로세스가 cpu 집중프로세스보다 실행 상태에 먼저 들어가는 경우가 사이클 훔치기에 해당한다. 
https://codingstudytrace.tistory.com/166

컴퓨터 구조와 성능 향상

인터럽트 부분을 확인해보자.

 

프로세스 우선도

커널 프로세스 > 일반 프로세스

입출력 프로세스 > CPU 집중 프로세스(사이클 훔치기)
대화형 프로세스 > 일괄 처리 프로세스 (위와 비슷한 맥락)

전면 프로세스 > 후면 프로세스

 

 

다중 큐

준비 상태의 다중 큐

프로세스마다 중요도가 다르며 중요도는 PCB에 표시된다.

준비 상태의 큐는 우선 순위마다 큐가 존재한다. 

고정 우선순위 방식 큐는 PCB에 우선순위가 정해지면 해당 프로세스가 종료되기 전까지 우선순위가 변하지 않는다.

시스템 상황이 시시각각 변하는데 우선순위가 고정되면 진짜 중요한 프로세스를 제때 처리하지 못할수 있다.

변동 우선순위 방식은 프로세스의 우선순위가 작업 중간에 변하는 방식이다. 

대기 상태의 다중 큐

대기 상태 큐는 입출력이 발생하면 프로세스가 옮겨지는 저장 공간이다.

대기 상태 큐는 IRQ 즉 입출력 장치 마다 큐가 존재한다. 

대키 상태의 큐는 준비 상태의 큐와 달리 입출력이 동시에 끝날 경우 여러개의 인터럽트를 벡터에 보내 한번에 처리한다.