⌛CPU 스케줄링

용어

CPU 이용률(CPU Utilization)

💡 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율

CPU 이용률이 높을수록 효율(성능)이 좋다

처리율(Throughput)

💡 단위 시간 당 처리할 수 있는 프로세스의 양

값이 클수록 성능이 좋다

반환시간(Turnaround Time)

프로세스가 처음 new 상태로 들어가서 terminated 상태로 나올 때까지의 시간

짧을수록 성능이 좋다

💡 작업 종료 시간 - 도착 시간

대기시간(Waiting Time)

💡 프로세스가 준비 큐(Ready Queue)에서 대기한 시간의 총합

응답시간(Response Time)

💡 요청 후 응답이 오기 시작할 때까지의 시간

🗒️CPU 스케줄링 방식

비선점(Nonpreemptive) 스케줄링

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법

호출빈도가 낮고 문맥 교환에 의한 오버헤드가 작음

일괄처리 시스템에 적합

CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스 오랫동안 대기시킬 수 있으므 처리율이 떨어질 수 있음

FCFS(First Come First Served)

FIFO(First In First Out)라고도 하며 도착 순서에 따라 프로세스를 실행

프로세스 별 점유시간(Burst Time)의 차이가 큰 경우, 일반적으로 평균 대기시간이 최소가 아니며, 도착 순서에 따라 달라질 수 있다

소요시간이 짧은 프로세스가 먼저 실행되도록 한 경우보다 성능이 떨어진다

호송 효과(Convoy Effect)

소요시간이 긴 프로세스가 먼저 도착하여 시간을 잡아먹고 있는 부정적인 현상

SJF(Shortest Job First)

CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식

두 개 이상의 프로세스 점유 시간이 같다면 FCFS 방식으로 처리

Deadline(기한부)

프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법

HRN(Highest Response-ratio Next)

짧은 작업에 유리한 SJF의 단점을 개선한 기법, 각 작업의 우선순위로 서비스

에이징 방식을 활용함

💡 우선순위 = (대기시간 + 서비스(실행)시간) / 서비스(실행)시간

Priority(우선순위)

준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법

🌟에이징(Aging)

오랫동안 대기하는 프로세스의 우선순위를 증가시키는 방법
무한 연기 상태, 기아(Starvation) 문제를 해결할 수 있다

선점(Preemptive) 스케줄링

하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

우선순위가 높은 프로세스를 빠르게 처리할 수 있음

주로 빠른 응답시간을 요구하는 대화식 시분할 시스템에 사용

선점으로 인한 많은 오버헤드를 초래함

선점을 위해 시간 배당을 위한 인터럽트 타이머 클럭(Clock)이 필요

SRT(Shortest Remaining Time)

선점 SJF

현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행시간을 비교하여 가장 짧은 실행시간을 요구하는 프로세스에게 CPU를 할당하는 기법

준비상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가한다

RR(Round Robin)

선점 FCFS

시분할 시스템(Time Sharing System)을 위해 고안된 방식

FCFS 기법과 같이 준비 상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만, 각 프로세스는 시간 할당량(Time Slice, Quantum) 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치된다

할당되는 시간의 크기가 큰 경우 FCFS와 같아짐

할당되는 시간의 크기가 작은 경우 작은 프로세스들에게 유리함

다단계큐(MLQ, Multi level Queue)

프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법

일반적으로 프로세스 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로세스 등으로 나누어 준비 상태 큐를 상위, 중위, 하위 단계로 배치한다

프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없다

하위 단계 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면 상위 단계 프로세스에게 CPU를 할당해야 한다

다단계 피드백 큐(MFQ, Multi level Feedback Queue)

다단계큐에서 특정 그룹의 준비상태 큐에 들어갈 경우 옮길 수 없다는 한계를 개선함

큐 사이를 이동할 수 있다

마지막 단계 큐에서는 작업이 완료될 때까지 RR 스케줄링 기법을 사용한다

교착상태(Deadlock)

둘 이상의 프로세스가 서로 다른 프로세스가 차지하고 있는 자원을 요구하고 요청한 자원이 영원히 할당되지 않아 결국 해당 프로세스는 무한정으로 기다리는 현상

교착상태 조건

상호배제(Mutual Exclusion)

한 번에 하나의 프로세스만이 공유자원을 사용할 수 있는 상태

점유 및 대기(Hold and wait)

프로세스들이 현재의 자원을 점유하면서 다른 자원을 요구하는 상태

비선점(Non-preemption)

각 프로세스에 할당된 자원은 사용이 완료될 때까지 강제로 해제할 수 없는 상태

환형 대기(Circular Wait)

서로 다른 프로세스 간의 자원요구가 연속적으로 반복되는 상태

해결 방안

예방(Prevention)

교착상태의 발생조건 제거

회피(Avoidance)

교착상태의 발생조건을 제거하지 않고 적절하게 피해나감

은행가 알고리즘

안전상태(Safe State)를 유지하기 위해 서비스 제공하는 순서를 적절히 지정

• 회피 알고리즘 작성

  1. 상태 체크

     안정상태 → 모든 사람들이 다리를 통과하여 다리를 지나갈 수 있는 상태

     불안정상태 → 다리에 사람이 있는 경우

     교착상태 → 다리에 진입한 사람들의 방향이 서로 반대인 경우

  2. 알고리즘의 아이디어

     교착상태를 회피하기 위해 다리에 사람이 있는 경우에만 진입하지 않고 대기하고 있다가 다리가 완전히 비었을 경우에만 진입하도록 알고리즘 작성

     1. 다리 상태 체크
     2. 안정상태일 때만 다리 자원의 점유상태 변경
     3. 현재 조원들에게 다리에 진입하도록 허락
     4. 다리에 진입한 사람이 모두 빠져나간 후 다리 자원 반납
     5. 불안정상태인 경우 대기

발견(Detection)

교착상태의 발생을 허용하고 발생 시 원인을 찾아 해결

회복(Recovery)

교착상태에 빠진 프로세스를 재시작하거나 원래 상태로 되돌림으로써 교착상태를 해결하는 방법