프로세서 스케줄링 알고리즘
프로세스 스케줄링 알고리즘
CPU 스케줄링 : 언제 어떤 프로세스에게 CPU를 할당할지 결정하는 작업
스케줄링 평가기준
시스템 입장의 성능 척도
CPU 이용률 (CPU utilization)
시간당 CPU 사용 시간 비율
전체 시간 중 CPU가 쉬지 않고 일한 시간
처리율 (Throughput)
시간당 처리한 작업의 비율
단위 시간 당 수행 완료한 프로세스의 수
프로그램 입장의 성능 척도
반환시간 (Turnaround Time)
프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데까지 걸리는 시간
ready queue 대기시간 + CPU 실행시간 + I/O 작업시간의 합
대기시간 (Waiting Time)
대기열에 들어와 CPU를 할당받기까지 기다린 시간
ready queue 대기시간의 총 합
반응시간 (Response Time)
대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간
CPU를 할당받은 최초의 순간까지 기다린 시간 한번만 측정
실행시간 (Burst Time)
프로세스 수행 = CPU burst + I/O burst
CPU burst : CPU 사용 시간
I/O burst : I/O 대기 시간
시스템 입장의 성능척도(CPU이용률, 처리율)는 늘리고, 프로그램 입장의 성능척도(반환시간, 대기시간, 반응시간)는 줄이는 것이 좋음
프로세스 스케줄링 알고리즘
공평성을 고려한 방식FCFS (First-Come-First-Service) : 선착순 방식
RR (Round-Robin): 제한시간을 두는 방식
시스템 성능과 효율성을 고려한 방식(실행시간 예측 부하의 문제가 존재)SPN (Shortest-Process-Next): 짧은 BT를 우선으로 처리하는 방식
SRTN (Shortest Remaining Time Next): 남은 시간이 짧은 것을 우선으로 처리하는 방식
HRRN (High-Response-Ratio-Next): RR이 적은 것을 우선으로 처리하는 방식
BT(실행시간) 예측 문제를 개선한 방식들MLQ (Multi-level Queue): 여러개의 레디큐를 두는 방식
MFQ (Multi-level Feedback Queue): MLQ와 동일한 방식에서 queue를 다이나믹하게 운용하는 방식
1. FCFS (First-Come-First-Service)
비선점형 스케줄링
스케줄링 기준
ready queue 도착시간
특징
선입선출(FIFO) Queue로 쉽게 관리 가능
ready queue에 먼저 도착한 프로세스 먼저 처리
Batch system(일괄처리 시스템)에 적합, interactive system(대화형 시스템) 부적합
장점
스케줄링이 단순함
효율적인 자원 사용가능
불필요한 스케줄링 오버헤드 X
단점
Convoy effect발생하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게되는 현상
긴 평군 응답시간
2. RR (Round-Robin)
선점형 스케줄링
스케줄링 기준
ready queue 도착시간
특징
자원 사용 제한시간 (time quantum/time slice) 존재
time quantum(시간 할당량)이 시스템 성능을 결정하는 핵심요소
각 프로세스가 CPU를 소유하는 시간의 한계
프로세스는 할당된 시간이 지나면 자원 반납
대화형, 시분할 시스템에 적합
Time quantum이 커질수록 FCFS 방식과 유사해짐
장점
starvation(기아)현상 발생 X응답 시간이 빠름
특정 프로세스의 자원독점 방지
단점
Contetx switch overhead 큼
Time quantum에 따른 Trade-Off
작은 Time quantum
응답성 증가
프로세스가 더 빠르게 CPU를 얻음으로 더 빠른 응답과 실행
빠른 응답성이 필요한 상황에 적합
Context Switching Overhead 증가
빈번한 프로세스 전환으로 오버헤드 증가
큰 Time quantum
응답성 감소
한 프로세스가 지나치게 오랫동안 CPU를 점유하게 됨
프로세스가 CPU 기다리는 시간 증가로 더 느린 응답과 실행
Context Switching Overhead 감소
상대적으로 긴 시간동안 CPU를 사용함으로 오버해드 감소
3. SJF (Short Job First)
SJF은 SPN과 동일한 스케줄링으로 보며, SJF에 선점형이 추가된 것이 SRTN
스케줄링 기준
실행시간(burst time)기준
특징
ready queue에 있는 프로세스의 수행 시간이 짧은 순서대로 CPU 할당
Convoy effect를 해결하기 위한 방법
주어진 프로세스에 대해 최소의 평균 대기시간 보장
선점형, 비선점형 스케줄링 두 개의 방식 존재
비선점형 SJF :
SPN선점형 SJF :
SRTN
장점
평균 대기시간 최소화
시스템 내 프로세스 수 최소화
스케줄링 부하 감소, 메모리 절약으로 시스템 효율성 향상
많은 프로세스들에게 빠른 응답 시간 제공
단점
starvation(기아)현상 발생실행시간이 긴 프로세스는 자원을 계속 할당 받지못 할 수 있음
정확한 다음 프로세스의 실행시간(
Next CPU Burst Time)을 알 수 없음각 프로세스가 얼마나 CPU를 사용할지 모르기 때문에 실행시간 예측 기법 필요
지수 평활법(과거의 CPU burst time 이용 예측) 사용
짧은 작업이 먼저 실행되기 때문에 공정하지 못함
3-1. SPN (Shortest-Process-Next)
Non-preemptive SJF
FSFS의 문제점을 개선한 방식
프로세스가 한 번 CPU를 얻으면 CPU burst time이 만료될 때까지 뺏기지 않음
작업간의 context switching 오버헤드 발생
3-2. SRTN (Shortest Remaining Time Next)
Preemptive SJF
최단 잔여시간을 우선으로 하는 스케줄링으로, SRTF(Shortest Remaining Time First)라고도 함
특징
SPN의 변형
현재 실행되고 있는 프로세스의 잔여 실행 시간보다 더 짧은 프로세스가 ready 상태가 되면 선점 됨
장점
평균 대기시간(WT)를 최소화하여 시스템의 부하를 줄여주는 등 SJF(SPN)의 장점 극대화
단점
프로세스 생성시, 총 실행 시간 예측 필요
잔여 시간을 계속 추적해야하여 오버헤드 발생
선점형으로 Context Switching overhead 발생
기아 현상 발생
4. HRRN (High-Response-Ratio-Next)
HRRN 우선순위 스케줄링 알고리즘은 비선점형/선점형 두 방식으로 나뉠 수 있음
선점형 : 우선순위가 높은 프로세스가 대기큐에 들어오면 CPU를 선점함
비선점형 : CPU에 할당된 작업이 없을 때 우선순위가 높은 순서로 CPU를 할당하고 프로세스가 완료될 때까지 프로세스 교체가 일어나지 않음
SPN의 변형
SPN+에이징 기법+비선점형 스케줄링에이징 기법은 SPN의 기아 현상을 해결하기 위한 방법
스케줄링 기준
Response ratio가 높은 프로세스 우선
Response ratio(응답률)
Response ratio = (대기시간 + 실행시간) / 실행시간
SPN의 장점 +
starvation(기아)방지여전히 실행시간 예측이 필요하다는 단점 존재
에이징 기법 시스템에서 특정 프로세스의 우선순위가 낮아 무한정 기다리는 경우를 방지하기 위한 방법. 기다린 시간에 비례해 일정 시간이 지나면 우선순위를 한 단계 높여주는 방법(대기 시간이 긴 프로세스를 배려)
5. MLQ (Multi-Level Queue)
레벨이 여러개인 ready queue
특징
작업, 우선순위 별 별도의 ready queue 가짐
최초 배정된 큐를 벗어나지 못함(시스템 변화에 적응 못함)
각각의 큐는 자신만의 스케줄링 기법 사용
큐 사이에는 우선순위 기반의 스케줄링 사용
장점
우선시간이 높은 ready queue는 응답시간이 빠름
단점
여러개의 큐 관리 등 스케줄링 오버헤드 발생
우선순위가 낮은 큐는
starvation(기아)현상 발생가능큐를 여러 개 두더라도 우선순위가 낮으면 여전히 CPU 할당을 받지 못함
6. MFQ (Multi-Level Feedback Queue)
프로세스의 큐간 이동이 허용된 MLQ
MLQ의 최초배정된 큐를 벗어나지 못해, 시스템 변화에 적용하기 힘든 단점을 극복하기 위해 나온 방법
특징
선점형 스케줄링
피드백을 통해 우선순위 조정
현재까지의 프로세서 사용 패턴 활용
동적 우선순위 가짐
시스템 환경 변화에 적응 가능
장점
프로세스에 대한 사전 정보(실행시간)없이 SJF, SRTN, HRRN 기법의 효과를 볼 수 있음
단점
설계 및 구현 복잡(여러개의 큐, 큐간의 이동)
스케줄링 오버헤드가 큼(변화하는 우선순위)
starvation(기아)현상 문제여전히 우선순위 낮은 프로세스는 CPU 할당 받지 못함
MFQ의 변형
각 ready queue마다 다른 시간 할당량 배정
프로세스의 특성에 맞는 형태로 시스템 운영 가능
입출력(I/O)위주 프로세스들은 상위 단계의 큐로 이동으로 우선 순위 높임
프로세스가 block될 때 상위의 ready queue로 진입 진행
시스템 전체의 평균 응답시간을 줄이고, 입출력 작업 분산시킴
대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
에이징(aging)기법
동시성과 병렬성
동시성 (Concurrency)
하나의 코어에서 여러 스레드가 번갈아가며 실행
여러 작업이 겹치는 기간에 실행될 수 있음을 의미
동시에 실행하는 것이 아닌, CPU가 작업마다 시간을 분할해 적절한 context switching을 통해 동시에 실행되는 것처럼 보이게 함
핵심목표
유휴시간의 최소화유휴시간 : 컴퓨가 작동가능한 상태인데 작업을 하고 있지 않은 시간
발생가능한 문제점
Race Condition
여러 프로세스가 하나의 자원에 접근해 서로의 실행결과에 영향을 주는 현상
Deadlock
여러 프로세스가 서로 상대방의 작업이 끝나기를 무한히 기다리는 현상
Starvation
특정 프로세스가 우선순위가 낮아 원하는 자원을 계속 할당받지 못하는 현상
병렬성 (Parallelism)
멀티코어에서 여러 스레드를 동시에 실행
동일한 시간에 독립적인 작업을 실행할 수 있음을 의미
동일성과 달리 여러작업을 다른 코어, 프로세스, 별도 컴퓨터등에서 동시 실행가능
예시
분산 컴퓨팅 시스템
발생가능한 문제
메모리 손상과 누수
여러 작업이 어떤 자원을 공유하고 있는지 고려해야하기 때문
참고
일괄처리 시스템(Batch System)
온라인처럼 일에 대한 요청이 발생했을 때, 즉각적으로 처리하는 것이 아닌 일정기간 또는 일정량을 모아뒀다가 한번에 처리하는 방식
대화형 시스템(Interactive System)
온라인과 같이 일에 대한 요청에 대해 즉각적으로 처리하여 응답을 받을 수 있는 시스템
시분할 시스템(Time Sharing System)
각 프로세스에 CPU에 대한 일정시간을 할당하여 주어진 시간동안 프로그램을 수행할 수 있게하는 시스템
실시간 시스템(Real-time Systen)
데이터 발생 즉시, 또는 데이터 처리 요구가 있는 즉시 처리하여 결과를 산출하는 방식
Last updated