스케줄러

스케줄러

• 한정적인 메모리를 여러 프로세스가 효율적으로 사용할 수 있도록 다음 실행 시간에 실행할 수 있는 프로세스 중에 하나를 선택하는 역할

1. Job Queue : 현재 시스템의 모든 프로세스 집합

2. Ready Queue : 현재 메모리에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합

3. Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합

스케줄러 종류

1. 장기 스케줄러 / 잡 스케줄러(Job scheduler)

-> degree of multiprogramming 제어
-> 디스크와 메모리 사이의 스케줄링 담당
-> 어떤 프로세스에 메모리를 할당하여 ready queue로 보낼지 결정하는 역할
-> new -> ready 상태로 전이 승인 ( 승인 스케줄러 )

2. 중기 스케줄러 / 스와퍼(Swapper)

-> degree of multiprogramming 제어
-> 여유 공간을 마련하기 위해 프로세스를 통째로 메모리에서 디스크로 쫓아내는 역할 ( swap in/ swap out)

3. 단기 스케줄러 / CPU 스케줄러 (CPU scheduler)

-> 메모리와 CPU 사이의 스케줄링 담당
-> 어떤 프로세스를 ready -> run ning 상태로 전환 시킬지 결정하는 역할

활성 상태 프로세스 상태

CPU 스케줄링

정의 : 작업을 처리하기 위해서 프로세스들에게 CPU를 할당하기 위한 정책 계획

방법에 따라

비선점 VS 선점

비선점 : 프로세스 종료 또는 입출력 등의 이벤트가 있을 때까지 실행 보장 ( 이미 할당된 CPU를 뺏을 수 없다 )
(+) 모든 프로세스에 공정, 응답 시간 예측 가능
(-) 프로세스 자체가 짧게 걸리더라도 긴 작업의 종료를 기다려야 할 수 있다.
종류 : FCFS(FIFO), SJF, 우선순위, HRN, 기한부 등등
선점 : OS가 CPU의 사용권을 선점할 수 있으면 강제 회수 ()
(+) 높은 우선순위를 가진 프로세스를 빠르게 처리 가능, 빠른 응답 시간 요구 시스템에 용이
(-) 높은 우선순위를 가진 프로세스만 들어오면 Overhead 발생, 인터럽트용 타이머 clock 필요
종류 : SRT, RR, 선점 우선순위, 다단계 큐

비선점 스케줄링 종류

1. FCFS(=FIFO)

• 준비상태 큐에 도착한 순서에 따라 차례로 CPU 할당
• 먼저 도착하면 먼저 처리 ( 공평성 유지 ), 짧은 작업이 긴 작업 기다리는 경우 가능

2. SJF(Shotest JOb First)

• 실행시간이 가장 짧은 프로세스에 먼저 CPU를 할당하는 기법
• 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘

3. HRN(Highest Responseratio Next)

• 실행시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위해 대기 시간과 서비스 시간이용
• 우선순위 계산 공식 = (대기시간 + 서비스시간) / 서비스시간

4. 기한부(Deadline)

• 프로세스에 일정 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법
• 시스템은 프로세스에게 할당할 정확한 시간을 추정해야 함
• 사용자는 시스템이 요구한 프로세스에 대한 정확한 정보를 제공해야 함

5. 우선순위(Priority)

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

6. 에이징(Aging)

• 시스템에서 특정 프로세스의 우선순위가 낮아 무한정 기다리는 경우, 기다린 시간에 비례하여 우선순위를 한단계씩 높여 가까운 시간 안에 자원을 할당하도록 하는 기법
• SJF나 우선순위 기법에서 발생가능한 무한 연기 상태, 기아 상태 예방 가능

선점 스케줄링 종류

1. 선점 우선순위

• 준비 상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법

2. SRT(Shortest Remaining Time)

• 비선점 기법 SJF 알고리즘을 선점 형태로 변경한 기법
• 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 추가된 프로세스의 실행시간을 비교해 가장 짧은 실행 시간을 요구하는 프로세스에 CPU를 할당

3. RR(Round Robin)

• 시분할 시스템(Time Sharing System)을 위해 고안된 방식, FCFS 알고리즘을 선점 형태로 변형한 기법
• FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 할당된 시간동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에 CPU를 넘기고 준비상태 큐의 가장 뒤로 배치
• 할당 시간이 크면 FCFS와 같아지고, 작으면 교환의 오버헤드가 자주 발생

4. 다단계 큐 (Multi level Queue)

• 프로세스를 특정 그룹으로 분류 가능한 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법

5. 다단계 피드백 큐

• 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법