04. CPU 스케줄링

 

CPU 스케줄링: 운영체제가 CPU 자원을 효율적으로 관리하기 위해 어떤 프로세스에게 CPU를 할당할지 결정하는 과정. →CPU는 한번에 하나의 프로세스(작업)만 실행 가능, 여러 프로세스가 동시에 실행되는 것처럼 보이기 위해 스케줄링이 필수적.

 

스케줄링 정책: 정해진 시간(time slice, time slot)에 프로세서를 점유할 프로세스를 선택.

 

스케줄링의 목표

• 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 함. 특정 프로세스 배제X
• 효율성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정
• 안정성: 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호.
• 확장성: 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 함.
• 반응 시간 보장: 예측하는 시간 내에 적절한 반응을 해야 함.
• 무기 연기 방지: 특정 프로세스 작업 무한 연기 방지.

스케줄링 단계

 

상위 단계 스케줄링:장기/작업/승인 스케줄링. 시스템에 부담이 되지 않도록 전체 작업 수 조절.

하위 단계 스케줄링: 단기 스케줄링. 짧은 시간에 처리, 프로레스 CPU 할당/ 대기상태 전환.

중간 단계 스케줄링: 보류-활성화 상태 전환. 활성화된 프로세스 조절→ 과부화 해소.

 

선점형 스케줄링(Preemptive Scheduling): 운영체제가 필요하다고 판단하면 실행 상태에 있는 프로세스의 작업 중단→ 다른 프로세스가 프로세서 쟁취 가능.

 

특징

• CPU 독점 불가능
• 대화형 시스템, 시분할 시스템에 적합
• 저수준 스케줄러가 사용

비선점형 스케줄링(Non-Preemptive Scheduling): 한 프로레스가 CPU를 사용하면 종료 또는 자발적으로 나올 때까지 다른 프로세스 대기.

 

장점

• 선점형 스케줄링보다 스케줄러의 작업량이 적음
• 문맥 교환에 의한 프로세서 및 시간적인 낭비 감소

단점

• 큰 프로세스가 CPU 사용 시 타 프로세스의 대기시간 증가→ 전체 시스템 처리율 감소

프로세스 우선순위: 커널프로세스>일반프로세스 → 우선순위가 높다: 더 빨리, 자주 실행.

 

특징

• 우선순위가 높은 프로세스가 CPU를 먼저, 더 오래 차지함.
• 시스템에 따라 높은 숫자가 높은 우선순위를 나타내기도, 낮은 숫자가 높은 우선순위를 나타내기도 함.
• 사용자가 프로세스의 우선순위 조절 가능→ 관리자만 우선순위 높이기 가능, 일반 계정은 낮추기만 가능.

 

CPU burst: 프로그램 실행과정에서 CPU가 코드를 집중적으로 실행하는 상황

I/O burst: I/O 장치에 의해 입출력이 이루어지는 상황

 

CPU 집중 프로세스: CPU 사용 시간이 많고 계산 중심적인 프로세스.

 

특징

• I/O 작업보다는 계산 위주로 시간 소비.
• CPU 점유 시간이 길고 입출력 작업은 적음.
• 문맥 교환이 적음.
• 처리량 위주의 작업에서 효율적임.

사용예시: 계산을 주로 하는 비디오, 이미지 압축 프로그램, 행렬 연산하는 AI 프로그램 등.

 

I/O 집중 프로세스: 입출력 작업이 많은 프로세스.

 

특징

• CPU 사용 시간은 짧고, I/O 작업을 기다리는 시간이 많음.
• CPU는 자주 쉼, I/O 완료를 기다리는 동안 대기 상태.
• 많은 수의 프로세스를 동시에 처리하기에 적합.

사용예시: 파일 다운로드 프로그램, 웹 브라우저, 동영상 스트리밍 앱 등.

 

우선 배정: I/O burst 상황에서 다른 프로세스가 CPU를 사용할 수 있기 때문에 배정 순서가 성능에 영향을 미침. 스케줄링 시 I/O 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템 효율 향상→사이클 훔치기(cycle stealing)

 

사이클 훔치기와 DMA(Direct Memory Access)

사이클 훔치기: I/O 장치가 CPU를 방해하지 않으면서 메모리에 접근하는 기술

메모리 직접 접근(DMA): CPU의 개입 없이, I/O 장치가 메모리와 직접 데이터를 주고받는 기술

 

구분	사이클 훔치기	메모리 직접 접근
개념	메모리 사용 중 일부 사이클을 빌리는 방식	CPU 개입 없이 직접 메모리와 통신
관계	DMA 방식의 한 종류	더 큰 개념, 여러 방식 존재함
영향	CPU 속도에 약간 영향 있음	CPU는 거의 개입 안함, 효울적
예시	I/O 장치가 CPU 쉬는 틈에 메모리 접근	하드디스크에서 RAM으로 파일 직접 복사

 

 

전면 프로세스(foreground process): GUI의 경우 운영체제 화면에서 맨 앞에 놓인 활성화 상태의 프로세스, 현재 입력과 출력을 사용하는 프로세스. 사용자와 즉각적인 상호작용이 가능→상호작용 프로세스.

후면 프로세스(background process): 사용자와 상호작용이 없는 프로세스. 사용자 입력 없이 작동(일괄 작업 프로세스), 전면 프로세스보다 우선순위가 낮음.

 

 

다중 큐(Muti-Queue Scheduling): 운영체제에서 프로세스를 특성에 따라 여러 개의 큐로 나누어 스케줄링하는 방식. (프로세스 성격에 따라 서로 다른 큐에 넣고, 각 큐마다 고유의 스케줄링 알고리즘을 사용하는 방식)

 

1. 고정 다중 큐(fixed muti-queue): 프로세스는 처음 큐에 들어가면 다른 큐로 이동X.

 

특징

• 우선 순위에 따라 준비 큐를 여러 개 사용.
• 상단 큐의 모든 작업 완료 시 하단 큐 진행→ 아사 현상 유발

 

다단계 피드백 큐(Multi-Level Feedback Queue): 프로세스 실행 상태에 따라 다른 큐로 이동 가능.

 

특징

• 우선순위가 높은 큐에서 실행되다가 시간이 오래 걸리면 낮은 큐로 이동. →사용자 응답성과 시스템 효율성을 모두 만족시키려는 방식
• 프로세스가 실행될 때마다 프로세스의 우선순위를 낮춤
• 다단계 큐의 낮은 우선순위 프로세스의 아사 현상을 해결
• 우선순위에 따라 타임 슬라이스의 크기가 다름

CPU 스케줄링 평가 방법

 

CPU 사용률(%): 전체 시스템의 동작 시간 중 프로세스들이 CPU를 사용한 비율을 측정. → 높을수록 운영체제의 성능이 좋음.

처리량: 단위 시간당 작업을 마친 프로세스의 수. →수치가 클수록 좋은 알고리즘.

 

시간

• 대기시간: 프로세스가 생성된 후 실행되기 전까지 대기하는 시간
• 응답시간:첫 작업을 시작한 후 첫번째 출력이 나오기까지의 시간
• 실행시간: 프로세스 작업이 시작된 후 종료되기까지의 시간
• 반환시간: 대기시간을 포함하여 실행이 종료될 때까지의 시간

 

FCFS(First Come First Served): 선입선출, 큐에 도착한 순서대로 CPU를 할당→ 비선점, 우선순위 동일

 

특징

• 처리 시간이 긴 프로세스가 CPU를 차지→ 다른 프로세스들 대기, 효율성 감소
• 만약 작업 중인 프로세스가 입출력 작업을 요청→ CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율 감소

SJF(Shortest Job First): 최단 작업 우선, 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당.

 

특징

• 운영체제가 프로세스의 종류시간 예측이 어려움.
• 작업 시간이 길다는 이유로 뒤로 밀려 공평성 감소→ 아사 현상

 

HRN(Highest Response Ratio Next): 최고 응답률 우선, SJF 스케줄링에서 발생할 수 있는 아사현상 해결하기 위해 만들어진 비선점형 알고리즘.

 

특징

• 대기 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식
• 여전히 공평성이 위배되어 많이 사용X
• 프로세스의 우선순위를 결정하는 기준

라운드 로빈 방식: 한 프로세스가 할당받은 시간 동안 작업. 작업을 완료하지 못하면 준비 큐의 맨 뒤로 이동 전환하여 다시 차례를 기다림.

 

특징

• 선점형 알고리즘 중 가장 단순하고 대표적인 방식
• 프로세스들이 작업을 완료할 때까지 계속 순환
• 효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이드 설정해야 함. (큰 경우: FCFS와 동일/ 작은 경우: 문맥교환 빈번→프로세스의 CPU 점유시간을 단축시켜 성능 저하 발생)

 

SRT: 라운드 로빈+SJF, CPU 할당은 남은 작업 시간이 가장 적은 프로세스를 선택. 현재 실행중인 프로세스와 큐에 있는 프로세의 남은 시간을 주기적으로 계산함.