CPU Scheduling

2022. 12. 28. 11:50 복습을 위한 수정 시작

CPU 스케줄러

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

여러 개의 프로세스가 하나의 프로세서(CPU)를 효율적으로 공유하려면 적절한 스케줄링이 필요하다.

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

 

스케줄링을 위한 기초적인 개념으로는 처리율과 이용률이 있다.

처리율을 극대화하고 이용률을 극대화해야만 CPU를 열심히 일하게 만드는 것이다.

CPU가 열심히 일하는 것이 OS의 목표이다.

처리율과 이용률

먼저 1초 실행, 1초 유휴를 진행하는 프로세스 P1, P2가 있다. 각 프로세스는 60초 동안 작동한다.

 

먼저 첫 번째 상황이다.

P1 프로세스가 마쳐야만 P2 프로세스가 메모리에 적재되어 시작된다.

그러면 P1이 진행하는 60초 끝나고 P2가 시작해 총 120 초가 걸린다.

다음으로는 처리율에 대해 알아보겠다. 처리율은 단위 시간당 프로세스 처리 양이다.

비례식을 세워보면 우선 120초 동안 P1, P2 2개의 프로세스를 처리했다. 그럼 비례식은 다음과 같다.

120 : 2 = 1 : X (단위 시간은 1초라고 정한다)

X는 우리가 구하려는 프로세스 처리량이다. 그러면 X는 1/60이 나온다. 처리율은 1/60 이용률은 50%이다.

 

두 번째 상황이다.

P1이 진행하는데 P1은 1초 일하고 1초 유휴 한다. 그럼 P1이 처음으로 유휴 하는 순간부터 P2는 프로세스는 돌아간다.

그럼 P1이 쉬면 P2가 일하고 P2가 쉬면 P1이 일한다. 이러면 총 61초 뒤면 2개의 프로세스가 마무리된다.

처리율을 구하기 위한 비례식은 61 : 2 = 1: X이다. 따라서 처리율은 2/61, 이용률은 100%이다.

 

CPU 집중 프로세스는 Processor Burst라고 하며 입출력 집중 프로세스는 I/O burst라고 한다.

프로세스가 주로 맡은 역할을 고려해 스케줄링을 진행해야 한다.

프로세스의 스케줄링의 단계

• 1단계: 고수준 스케줄링
• 2단계: 중간 수준 스케줄링 (작업승인과 프로세스 배당, 사용권)
• 3단계: 저 수준 스케줄링 (준비상태의 프로세서에 프로세스 할당(Dispatch)) 

고수준 스케줄링

• 레디큐에 넣을 작업을 선택해 레디큐에 넣는 역할을 한다.
• 작업 스케줄링, 장기 스케줄링이라고도 한다.
• 고수준 스케줄링에서는 전체 시스템의 부하를 고려하여 작업을 시작할지 말지를 결정한다.
• 이 결정에 따라 시스템의 전체 프로세스 수가 결정되는데 이를 멀티프로그래밍 정도라고 한다.
• 고수준 스케줄링은 메인프레임과 같은 큰 시스템에서 규모가 큰 일괄 작업을 처리할 때 사용한다.

중간 수준 스케줄링

• 중간 수준 스케줄링은 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부화를 막는다.
• 즉 일부 프로세스를 중지 상태를 옮김으로써 나머지 프로세스가 원만하게 작동하도록 지원한다.
• 이는 프로세스의 상태 중 보류 상태에 해당하며, 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할을 한다.
• 보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화된다.
• 중간 수준 스케줄링은 시스템 부하 정도에 따라 스와핑을 진행한다. (보류와 활성화, swap out, swap in)

저수준 스케줄링

• 저수준 스케줄링은 준비 큐에서 PCB를 선택해 CPU 사용 권리를 부여한다. (1. 프로세스 선정, 2. 대기 또는 타임아웃, fork, 인터럽트, 자원 요청, 입출력 대기)
• 디스패쳐와 프로세서 사이에 문맥교환기가 존재한다.
• 즉 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일이다.
• 준비 상태에 있는 프로세스 중 하나를 골라 실행 상태로 보내고, 실행 상태에 있는 프로세스를 대기 상태로 보내며, 대기 상태으 ㅣ프로세스를 준비 상태로 보내는 것을 예로 들 수 있다.
• 저수준 스케줄링은 아주 짧은 시간에 일어나므로 단기 스케줄링이라고도 한다.

스케줄링의 목적

• 공평성: 모든 프로세스에게 공평하게 자원을 할당받아야 하며, 자원 할당 과정에서 특정 프로세스가 배제되어서는 안 됨.
• 효율성: 시스템자원이 유휴시간없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 함.
• 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 함.
• 확장성: 프로세스가 증가하거나 시스템자원이 늘어나도 안정적으로 작동하도록 조치해야 하며 시스템에 반영되게 해야 함.
• 응답 시간 보장: 응답이 없는 경우에 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템이 적절한 시간 안에 프로세스의 요구에 응답(=반응)해야 함.
• 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안 됨 (No Starvation, No Deadlock)

스케줄링 큐들은 Linked List 형태이며 큐에는 프로세스가 아닌 PCB가 줄을 선다. 스케줄링에는 크게 ready 큐와 device 큐가 있다.

링크드 리스트에 계속 PCB를 붙여나가며 붙인다면 null 포인터를 마지막 PCB 뒤에 붙이며 링크드 리스트를 바탕으로 유연하게 PCB를 다룬다.

선점형 스케줄링과 비선점형 스케줄링

• 비선점 스케줄링은 실행 중인 프로세스를 중간에 중단시키지 않고 종료될때까지 기다린 후, 다음 프로세스를 실행시킨다.
• 선점 스케줄링은 CPU가 실행중인 프로세스를 중간에 중단 후 새 작업을 시작한다.

다중 큐

준비 상태의 다중 큐

• 프로세스는 저마다 중요도가 다르며 프로세스의 중요도는 PCB에 표시된다.
• CPU 스케줄러는 모든 PCB를 뒤져서 가장 높은 우선순위의 프로세스에 CPU를 할당한다.
• 그러나 매번 프로세스 제어 블록을 검색하는 것은 번거로운 일이다.
• 이런 상황일 때 우선순위에 따라 여러 개의 큐를 만들면 굉장히 편리하다.

프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 레디큐의 마지막(tail) 부분으로 삽입된다.

CPU 스케줄러는 우선순위가 가장 높은 큐의 맨 앞에 있는 프로세스에게 CPU를 할당한다.

 

준비 큐를 몇 개로 나눌지, 여러 개의 준비 큐에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정하는 일은 스케줄링 알고리즘에 따라 달라진다.

프로세스의 우선순위를 배정하는 방식에는 고정 우선순위 방식과 변동 우선순위 방식이 있다.

 

• 고정 우선순위 방식: 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식이다. 구현은 쉽지만 효율성이 떨어진다.
• 변동 우선순위 방식: 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식이다. 구현은 어렵지만 효율성은 높다.

대기 상태의 다중 큐

대기 상태에서도 다중 큐를 사용한다. 대기 상태는 입출력이 완료되기를 기다리는 프로세스가 모여있는 곳이다.

시스템 내에는 다양한 종류의 입출력 장치가 있기 때문에 대기 상태의 프로세스를 한곳에 모아놓으면 관리하기가 불편하다.

같은 장치의 입출력을 기다리는 PCB은 동일한 입출력 큐에 모여있다.

예를 들어 하드디스크의 입출력을 기다리는 PCB는 모두 HDD 큐이 유입된다.

하드디스크에서 완료 인터럽트가 도착하면 HDD 큐에 있는 PCB를 검색하여 이 PCB의 상태를 준비 상태로 바꾸고 HDD 큐에서 제거 한 후 준비 큐로 이동한다.

 

준비 상태의 다중 큐와 대기 상태의 다중 큐는 차이가 있다.

준비 큐는 한 번에 하나의 프로세스를 꺼내어 CPU를 할당하는 반면, 대기 큐는 여러 개의 PCB를 동시에 꺼내 준비 상태로 옮긴다.

스케줄링 알고리즘

• 선점형: FCFS Scheduling, SJF Scheduling,HRN Scheduling
• 비선점형: Round-Robin Scheduling, Multilevel Queue Scheduling, Multilevel Feedback-Queue Scheduling
• 둘다 가능: Priority Scheduling

성능 평가의 기준에는 프로세서 이용률, 처리율, 반환시간, 대기시간, 반응시간이 있는데 반환시간과 대기시간이 중요한 기준이다.

 

먼저 레디 큐가 1개일 때 스케줄링 알고리즘이다.

FCFS 스케줄링

FCFS는 First-come, First Served의 줄임말이다. 선입선처리 스케줄링 알고리즘이다.

비선점 알고리즘이고 매우 간단하다. 먼저 요청한 프로세스에게 먼저 프로세서를 할당한다.

SJF 스케줄링

SJF (Shortest Job First, 최소작업우선) 스케줄링 알고리즘이다.

프로세서 실행(Burst)시간이 가장 작은 프로세스를 우선 할당하는 기법이다. 같은 실행시간이면 FCFS순서로 할당.

일괄 처리시스템의 장기스케줄링 경우에 적합하다. 선점, 비선점이 모두 가능하다.

HRN 스케줄링

HRN (Highest Response-Rate Next) 스케줄링 알고리즘이다.

SJF 스케줄링을 보완, 비선점 스케줄링 기법이다.

가변적 우선순위 = 서비스 대기시간 + 서비스 받을 시간/ 서비스 받을 시간

시스템 응답시간 : 대기한 시간 + 서비스 받을 시간

즉 많이 기다렸다면 우선 순위가 높다. 서비스 받을 시간이 적다면 우선순위가 높다.

Round Robin 스케줄링

다음은 RR (Round Robin)스케줄링 알고리즘이다.

작은 시간량만큼 프로세스에게 차례로 할당하는 기법이다. 순환큐 TSS에 적합한 스케줄링이다.

우선순위 스케줄링

Priority Scheduling (우선순위 스케줄링)은 문제점이 존재한다. 무한정지와 기아가 발생할 수 있다.

우선순위가 높은 프로세스들이 계속 들어오면 낮은 우선 순위의 프로세스들은 무한정 기다려야한다.

이 경우에는 Aging 기법을 통해 대기 프로세스들의 우선 순위를 점진적으로 증가시켜서 문제를 해결할 수 있다.

 

다음부터는 다중 큐 상황일 때 알고리즘이다.

다단계 큐 스케줄링

Multilevel Queue Scheduling(다단계 큐 스케줄링) 알고리즘이다.

이 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다,

프로세스는 OS로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다.

라운드 로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 나뉘어 있어 프로세스가 큐에 삽입되는 것만으로 우선순위가 결정된다.

이 알고리즘도 선점형이며, 우선순위가 낮은 큐가 무한정 연기되는 문제가 발생할 수 있다.

다단계 피드백 큐 스케줄링

Multilevel Feedback-Queue Scheduling (다단계 큐 피드백 큐 스케줄링) 알고리즘이다.

다단계 큐 피드백 큐 스케줄링 알고리즘은 위 다단계 큐 스케줄링에 단점을 보완한 알고리즘이다.

Multilevel Queue Scheduling은 한 번 결정된 프로세스는 Queue를 바꿀 수 없이 신축성 있는 스케줄링이 어렵다.

다이내믹한 스케줄링 상황을 반영하여 프로세스가 Queue 간에 서로 이동하여 알고리즘의 최적을 꾀해야 한다.

이 알고리즘에서는 프로세스가 큐를 옮길 수 있으며, CPU를 사용하고 난 프로세스의 우선순위가 낮아진다.

 

2022. 12. 28. 14:50 복습을 위한 수정 마무리