[운영체제] 스케줄러

반응형

스케줄러

프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업이다. CPU나 자원을 효율적으로 사용하기 위한 정책으로 오버헤드를 줄이고 CPU 사용률을 높여 기아 현상을 줄이는 것을 목표로 한다.

• Batch System: 가능하면 많은 일을 수행. 시간보다 처리량이 중요
• Interactive System: 빠른 응답 시간, 적은 대기 시간
• Real-time System: 기한(dead line) 맞추기

Terminologies

CPU가 Operation을 수행하는데 걸리는 시간을 CPU Burst라고 한다. CPU가 I/O를 기다리는데 걸리는 시간을 I/O Burst 라고 한다. 모든 프로세스는 CPU - I/O burst를 번갈아 가면서 실행

I/O에 의해 block 당하기 전의 짧은 CPU Burst를 I/O bound 라고 한다. I/O에 의해 block 당하기 전의 긴 CPU Burst 를 CPU bound 라고 한다.

Scheduling Criteria

스케쥴링 성능 평가 지표

• CPU utilization: 전체 시간 중에서 CPU가 일을 한 시간의 비율
• Throughput: 단위 시간당 완료된 프로세스 개수
• Turnaround time: 어떤 특정 프로세스가 실행되는데 걸리는 시간
• Response time: 요청이 submit된 후 첫번째 응답까지 걸리는 시간 (time sharing 환경에서)
• Deadline: 마감 시간, process 마다 deadline을 얼마나 CPU가 충족 시키는지
• Fairness: 프로세스마다 필요한 정도에 따라 CPU proportion이 정확히 지켜지는지

스케줄러 큐

프로세스를 스케줄링하기 위한 queue에는 세가지 종류가 존재한다.

• job queue : 현재 시스템 내에 있는 모든 프로세스의 집합
• Ready queue: 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
• Device queue: I/O 작업을 대기하고 있는 프로세스의 집합

종류

크게 3가지 종류의 스케줄러가 존재한다.

장기 스케줄러 (job scheduler)

메모리는 한정 되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(디스크)에 임시로 저장된다. 장기 스케줄링은 이 중에 어떤 프로세스를 메모리에 할당하여 ready queue로 보낼지 결정하는 역할을 한다. 즉 system에 프로그램이 들어갈지 아닐지를 결정한다.

• 프로세스에 각종 리소스를 할당
• 메모리와 디스크 사이의 스케줄링을 담당
• Multiprogramming 정도 제어
• 프로세스의 상태를 new => ready (in memory)

time sharing system에는 장기 스케줄링 없이 바로 프로그램이 메모리에 올라가 ready 상태가 된다.

중기 스케줄러 (swapper)

어떤 프로세스들이 CPU를 할당 받을 것인지 결정하는 작업을 의미한다. CPU를 할당 받을 프로세스가 많을 경우 프로세스를 suspend 시킨후 메모리에서 디스크로 swap out한다. 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러이다.

프로세스의 상태를 ready => suspend

단기 스케줄러 (CPU scheeduler)

CPU에 의해 실행될 프로세스를 결정한다.

• CPU와 메모리 사이의 스케줄링
• ready queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정
• 프로세스의 상태를 ready => running => waiting => running

Decision Mode

비선점 (Nonpreemptive)

프로세스가 한번 running state에 들어가면 작업이 종료되거나 I/O 인터럽트에 의해 block 되어 wait 상태가 되기 전까지 계속 실행된다. 즉 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 기법이다.

모든 프로세스에 대한 요구를 공정하게 처리할 수 있으며 응답시간 예측이 용이하고 일괄처리 방식에 적합하다.

하지만 중요한 작업이 중요하지 않은 작업을 기다리는 경우가 발생할 수 있다.

예) FCFS, SJF, 우선순위, HRN, 기한부

선점 (Preemtive)

현재 실쟁되고 있는 프로세스는 OS에 의해 interrupted 되거나 ready state로 옮겨질 수 있다. 이미 할당된 CPU를 우선순위가 높은 다른 프로세스가 강제로 빼앗아 사용할 수 있는 기법이다.

우선수위가 높은 프로세스를 빠르게 처리할 수 있고 주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 사용된다.

많은 오버헤드가 발생하며 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클록이 필요하다.

예) RR, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐

스케줄링 알고리즘

FCFS(First come First Served) = FIFO

특징

• 비선점형: 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 반환하지 않는다.
• 먼저 온 프로세스를 먼저 처리
• 짧은 프로세스에 더 효과적

문제점

• convoy effect : 소요시간이 긴 프로세스가 먼저 도착해 효율성을 낮추는 현상

SJF(Shortest-job-First)

특징

• CPU burst time이 가장 짧은 프로세스에게 먼저 할당
• 비선점형

문제점

• Starvation: CPU 사용이 짧은 프로세스가 계속 들어오면 CPU 사용이 긴 프로세스는 프로세스를 할당 받지 못하고 굶어 죽을 수도 있다.

SRTF(Shortest Remaning Time First)

특징

• 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
• 선형점 스케줄링: 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 burst time을 가진 프로세스가 도착하면 CPU를 뺏긴다.

문제점

• starvation
• 새로운 프로세스가 도착할 때마다 스케줄링을 다시 하기 때문에 CPU burst time을 측정할 수가 없다.

Roud-Robin

특징

• timer를 기반으로 선점한다.
• 각 프로세스는 동일한 길이의 할당 시간 (time quantum)을 갖게된다. 할당 시간이 지나면 프로세스는 선점 당하고 다시 ready queue 뒤에 들어가 줄을 선다.
• 사용 시간이 랜덤한 프로세스가 섞여 있을 경우 효과적이다.
• 프로세스의 context를 저장할 수 있기 때문에 가능하다.

장점

• Response time이 빨라진다.
• 만약 n개의 프로세스가 ready queued에 있고 q의 time quantum을 가진다면 각각의 프로세스는 q 단위로 CPU 시간의 1/n을 얻는다. 어떤 프로세스도 (n-1)/q time unit 이상 기다리지 않는다.
• 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다.

주의점

• time quantum이 너무 커지면 FCFS와 같아진다. 너무 작아지면 잦은 context switch로 오버헤드가 발생한다.

HRN (Highes-Response-Ratio-Next)

실행시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로 대기 시간과 실행 시간을 이용한다.

우선 순위 공식을 이용해 실행 시간이 짧은 프로세스나 대기 시간이 긴 프로세스에게 우선순위를 주어 CPU를 할당한다. (우선순위가 높은 것 먼저 실행)

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

비선점형이다.

장점

• starvation을 줄일 수 있다.

단점

• 예측된 서비스 타임이 측정되어야한다.