CPU(Central Processing Unit; 중앙처리장치)
[ 그림1. 기본적인 컴퓨터 장치와 각 장치 사이 접근 ]
•
데이터 처리 연산, 저장, 제어 등의 프로그램 명령을 실제로 수행하는 장치
•
프로세서라고도 함
•
일반적으로 처리 속도가 다른 장치보다 빠름
•
한 번에 한가지 일(프로세스)만 수행할 수 있음
◦
주기억장치(RAM)에 적재된 프로세스 중 한 프로세스를 선택하여 실행시킴
◦
프로세스를 선택하는 과정 == CPU 스케줄링
스케줄러
•
프로세스를 스케줄링하는 장치
•
큐 종류
◦
작업 큐 (Job Queue)
▪
실행되기 위한 프로그램 집합
▪
디스크에 위치
◦
준비 큐 (Ready Queue)
▪
실행에 필요한 모든 자원을 가진채로 메모리(주기억장치)에 있으면서, CPU할당을 기다리는 프로세스 집합
◦
장치 큐 (Device Queue)
▪
IO 작업을 기다리는 프로세스 집합
▪
IO를 하기 위한 여러 장치가 있는데, 각 장치를 기다리는 큐가 존재
•
스케줄러 종류
◦
장기 스케줄러 (Job scheduler)
▪
디스크와 메모리 사이 스케줄링 담당
▪
작업 큐의 프로세스 중, 메모리와 자원들을 할당해서 준비 큐로 보낼 프로세스 결정
▪
프로세스 상태: new => ready로 변경
◦
단기 스케줄러 (CPU scheduler)
▪
메모리와 CPU사이 스케줄링 담당
▪
준비 큐에 있는 프로세스 중 어떤 것을 실행 시킬 지 결정
▪
프로세스 상태: ready => running ⇒ waiting ⇒ ready
◦
중기 스케줄러 (Memory Scheduler)
▪
메모리에 너무 많은 프로세스가 있는 경우, 프로세스를 디스크로 쫒아냄 (Swapping)
▪
실행중인 프로세스 수(degree of Multiprogramming) 제어
▪
프로세스 상태: ready => suspended
프로세스 상태와 상태 전이
•
상태 종류
◦
생성 (New)
▪
프로세스가 생성되는 중
◦
준비 (Ready)
▪
프로세스가 메모리(주기억장치)에 적재되어, 실행에 필요한 자원을 모두 얻은 채로 CPU할당을 기다림
◦
실행 (Running)
▪
프로세스가 CPU할당받아 실행 중
◦
대기 (Waiting)
▪
프로세스가 할당받은 CPU를 반납하고 이벤트(ex. IO)를 처리 중
•
IO작업은 디스크에서 일어나고, 디스크는 CPU보다 처리 속도가 느림.
⇒ 따라서 디스크 IO 작업 동안 CPU 점유하고 있어도 다음 명령어 수행 불가
⇒ CPU 낭비
•
따라서 IO작업하는 프로세스는 CPU를 반납하고 장치큐에 가서 줄을 서게 됨
◦
종료 (Terminated)
▪
프로세스 실행이 완료되어 CPU 반납
◦
중지/지연 (Suspended)
▪
외부적 이유로 수행이 정지되어, 프로세스가 메모리에서 내려가 디스크로 Swap out됨
•
상태 전이
◦
승인 (Admitted)
▪
프로세스 승인되어 준비 큐에 올라옴
▪
New → Ready
◦
스케줄러 디스패치(Scheduler Dispatch)
▪
준비 큐에 있는 준비 상태의 프로세스를 실행
▪
Ready → Running
◦
Timeout 과 Interrupt
▪
선점형 스케줄링에서 발생
▪
다른 프로세스에게 CPU를 넘겨주기 위해 실행중인 프로세스를 준비 큐로 보냄
▪
Timeout : 일정시간이 지나 다음 프로세스에게 CPU 할당
▪
Interrupt : 우선순위 높은 프로세스에게 CPU 할당
▪
Running→ Ready
◦
Sleep/Block
▪
실행중인 프로세스가 IO장치 등의 자원 요청 후, 할당받을 때까지 장치큐에 들어가 기다림
▪
Running → Waiting
◦
Wake UP
▪
이벤트에 필요한 자원이 할당되면, 프로세스가 준비상태로 전이됨
▪
Waiting → Ready
◦
Swap-out
▪
프로세스 메모리 부족 등으로 프로세스가 중단되어 디스크로 내려감
▪
Ready → Suspended
▪
Waiting → Suspended
◦
Swap-in
▪
프로세스가 다시 메모리로 적재됨
▪
Suspended → Ready
▪
Suspended → Waiting
CPU 스케줄링
•
주기억장치에 적재되어 실행을 기다리는 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정하는 것
•
좋은 스케줄링의 기준
◦
오버헤드가 적다
◦
CPU사용률이 높다
◦
기아현상이 적게 발생한다.
▪
cf. 기아현상 : 프로세스가 필요한 자원을 할당받지 못하여, 실행되지 못한 채로 자원할당을 무한정 기다리는 상태
•
시스템 종류에 따른 스케줄링 목표
◦
일괄처리 시스템 (Batch System)
▪
작업을 일괄적으로 한번에 처리하므로, 시간보다는 처리량이 중요
◦
실시간 시스템 (Real-time System)
▪
작업 요청부터 응답을 얻기까지의 시간적 제약이 존재하므로, 작업이 완료되어야 하는 기한(deadline) 맞추기가 중요
◦
대화식 시스템 (Interactive System)
▪
사용자와 컴퓨터가 대화를 하며 작업을 처리하므로, 응답시간이 빨라야 함
•
종류
◦
비선점형 스케줄링(Non-Preemptive Scheduling)
▪
할당된 CPU를 다른 프로세스가 뺏을 수 없어서, 프로세스 종료까지 실행 보장되는 방식
▪
장점
•
빨리 응답해야하는 것에 초점을 맞춘 것이 아니기 때문에, 일괄처리방식에 적합
•
응답시간 예측이 쉬움(← 한번 실행 되면 종료까지 실행보장되니깐)
▪
단점
•
중요한 작업이 대기함
▪
스케줄링 방식 종류
•
FCFS(Frist Come Frist Served)
◦
큐에 도착한 순서대로 CPU할당
◦
장점
▪
단순하다
◦
단점
▪
실행시간 긴 것이 앞으로 가면, 평균 대기시간 길어짐
•
비선점형 우선순위
◦
더 높은 우선순위의 프로세스가 준비 큐에 도착 시, 준비 큐의 Head에 넣음
◦
단점
▪
우선순위 낮은 프로세스는 거의 영원히 CPU할당 못받음
•
SJF(Shortest Job First)
◦
수행시간이 가장 짧은 작업을 먼저 수행
◦
장점
▪
FCFS보다 평균대기 시간 감소
▪
짧은 작업에 유리
◦
단점
▪
사용시간 긴 프로세스는 거의 영원히 CPU할당 못받음
•
HRN(Hightest Response-radio Next)
◦
대기시간이 길어질수록 우선순위 높아짐 (SJF 단점 보완)
◦
선점형 스케줄링(Preemptive Scheduling)
▪
OS가 CPU사용권을 가지기 때문에, 한 프로세스에게 할당된 CPU를 뺏어와 우선순위가 더 높은 프로세스에게 할당시키는 방식
▪
장점
•
우선순위 높은 프로세스를 빠르게 처리 가능
•
빠른 응답을 요구하는 대화식 시분할 시스템에서 이용
◦
cf. 대화식 시분할 시스템
▪
시분할 시스템 : 프로세서가 여러 작업을 교대로 수행함
▪
대화식 시분할 시스템 : 대화형이란 컴퓨터와 사용자가 1:1 대화하는 것처럼 보인다는 것이다. 실제로는 여러 사용자가 이용함에도, 프로세서가 다중 작업을 빠르게 교대함으로써 마치 1:1 처럼 인식 되는 것이다.
▪
단점
•
선점과정에서의 문맥교환으로 인해 발생하는 오버헤드
◦
문맥교환(Context Switch)
▪
“문맥” 이란?
•
프로세스의 상태, 프로세스 명령이 어디까지 수행되었는지, 우선순위 정보 등과 같은 프로세스 현재 상태 정보
▪
CPU를 할당받아 실행되던 프로세스의 문맥을 보관하고 CPU를 뺏은 후, 새로운 프로세스의 문맥을 주기억장치에 적재하여 CPU를 할당하는 작업
▪
오버헤드 발생 이유
•
문맥을 교환하는 동안에는 작업을 수행할 수 없기 때문
•
선점시간을 재기 위한 인터럽트용 클럭 필요
◦
클럭으로 선점시간을 재고, 시간이 초과되면 인터럽트 발생하여 CPU할당 해제
•
CPU 총 사용시간 예측이 어려움
◦
새로운 프로세스가 준비 큐에 올 때마다 스케줄링을 다시하기 때문
▪
스케줄링 방식 종류
•
SRTF (Shortest Remaining Time First)
◦
남은 작업 시간이 적을 수록 우선순위가 높음
◦
단점
▪
남은 시간이 긴 프로세스는 거의 영원히 할당 받을 수 없음
▪
해결
•
aging 기법 : 우선순위 낮은 프로세스도 오래 기다리면 우선순위 높아짐
•
선점형 우선순위 (Priority)
◦
우선순위 가장 높은 프로세스에게 CPU할당
•
라운드 로빈 (Round robin; RR)
◦
FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 시간(=할당 시간)만큼 CPU 사용
◦
할당 시간 지나면 프로세스는 선점 당하고 준비 큐의 맨 뒤로 다시 대기
◦
현대의 CPU스케줄링
◦
장점
▪
응답시간 빨라짐
•
모든 프로세스들이 할당 시간 이상을 기다리지 않음
◦
단점
▪
할당 시간이 크면 FCFS와 같고, 작으면 문맥교환이 잦아져 오버헤드 증가
•
다단계 큐(Multilevel-queue)
◦
작업 종류마다 다른 우선순위 큐들을 둠
◦
우선순위 낮은 프로세스가 실행 못되는 것을 방지하고자 큐마다 다른 할당시간 설정
◦
우선순위 높은 큐는 할당시간 작음 & 우선순위 낮은 큐는 할당시간 큼
