[운영체제] 1. 스케줄링(Scheduling)

스케줄링(Scheduling)

① 스케줄링이란?

1. 스케줄링은 프로세스가 생성되어 실행될 때 필요한 시스템의 여러자원을 해당 프로세스에게 할당하는 작업을 의미함.
2. 프로세스가 생성되어 완료될 때까지 프로세스는 여러 종류의 스케줄링 과정을 거치게 됨.
3. 스케줄링의 종류에는 장기 스케줄링, 중기 스케줄링, 단기 스케줄링이 있음.

※ 프로세스(Process): 일반적으로 CPU에서 처리되는 사용자 프로그램과 시스템 프로그램과 같이 실행중인 프로그램을 의미함. 작업 또는 태스크(Task)라고도 부름.

 

② 스케줄링의 종류

1) 장기 스케줄링
 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐(Ready Queue)로 보내는 작업. 작업 스케줄링, 상위 스케줄링이라고도 하며, 작업 스케줄러(Job Scheduler)에 의해 수행됨.

2) 중기 스케줄링
 어떤 프로세스들이 CPU를 할당 받을 것인지 결정하는 작업. CPU를 할당 받으려는 프로세스가 많을 경우 프로세스를 일시 보류시킨 후 활성화해서 일시적으로 부하를 조절함.

3) 단기 스케줄링
 프로세스가 실행되기 위해서 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업을 의미함. 프로세서 스케줄링, 하위 스케줄링이라고도 하며, 프로세서 스케줄링 및 문맥 교환은 프로세서 스케줄러에 의해 수행됨.

※ 프로세스를 스케줄링 하기 위한 Queue
1) Job Queue: 현재 시스템 내에 있는 모든 프로세스의 집합. 
+ Job Scheduler에 의해 유지되는 자료 구조이자 Secondary Storage(보조 저장 장치)에 형성되어 있는 Queue.
2) Ready Queue: 메모리 내에 있으면서 CPU에 의해 실행되기를 기다리는 프로세스의 집합.
+ 메모리에 로드(Load)되어 있는 프로세스들이 쌓여있는 Queue.
3) Device Queue : Device Controller 내에 있으면서 Device I/O 작업을 대기하고 있는 프로세스의 집합.

※ 프로세서(Processor): 하드웨어 측면에서 프로그램을 수행하는 장치. ex) 중앙 처리 장치(CPU) - 명령어를 해석하는 컴퓨터의 한 부분.

※ 문맥 교환(Context Switching): 하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 이전의 프로세스의 상태(문맥)를 PCB(Process Control Block)에 보관하고 새로운 프로세스의 상태를 적재하는 작업.

 

③ 스케줄링의 목적

스케줄링은 CPU나 자원을 효율적으로 사용하기 위한 정책으로 다음과 같은 목적을 가지고 있음.

1. 공정성: 모든 프로세스에 공정하게 할당함.
2. 처리율(량) 증가: 단위 시간 당 프로세스를 처리하는 비율(양)을 증가시킴.
3. CPU 이용률 증가: 프로세스 실행 과정에서 주 기억장치를 액세스한다든지, 입출력 명령 실행 등의 원인에 의해 발생할 수 있는 CPU의 낭비 시간을 줄이고, CPU가 순수하게 프로세스를 실행하는데 사용되는 시간 비율을 증가시킴.
4. 우선순위 제도 : 우선순위가 높은 프로세스를 먼저 실행함.
5. 오버헤드 최소화 : 오버헤드를 최소화함.
6. 응답시간 최소화 : 작업을 지시하고 반응하기 시작하는 시간을 최소화함.
7. 반환시간 최소화 : 프로세스를 제출한 시간부터 실행이 완료될 때까지 걸리는 시간을 최소화함.
8. 대기시간 최소화 : 프로세스가 준비상태 큐에서 대기하는 시간을 최소화함.
9. 균형있는 자원의 사용 : 메모리, 입출력장치 등의 자원을 균형있게 사용함.
10. 무한 연기 회피 : 자원을 사용하기 위해 무한정 연기되는 상태를 회피함.

※ 오버헤드(Overhead): 어떤 작업을 하기 위해 소요되는 간접적인 시간, 메모리 등을 말함.

 

④ 프로세서 스케줄링의 기법

1) 비선점 스케줄링
1. 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법.
2. 프로세스가 CPU를 할당받으면 해당 프로세스가 완료될때까지 CPU를 사용함.
3. 프로세스 응답 시간의 예측이 용이하며, 일괄 처리 방식에 적합.
4. 중요한 작업(짧은 작업)이 중요하지 않은 작업(긴 작업)을 기다리는 경우가 발생할 수 있음.
5. 비선점 스케줄링의 종류에는 FCFS, SJF, 우선순위, HRN, 기한부 등의 알고리즘이 있음.

2) 선점 스케줄링
1. 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때, 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법.
2. 우선순위가 높은 프로세스를 빠르게 처리할 수 있음.
3. 주로 빠른 응답시간을 요구하는 대화식 시분할 시스템에 사용됨.
4. 많은 오버헤드를 초래함.
5. 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클록이 필요함.
6. 선점 스케줄링의 종류에는 라운드로빈, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 등의 알고리즘이 있습니다.

※ 인터럽트용 타이머 클록: 하나의 시스템 내에서 동작하는 장치들을 감시하기 위해 주기적인 신호를 발생하는 것으로, 하나의 프로세스가 자원을 독점하지 못하도록 방지하기 위해 사용됨.

 

⑤ 스케줄러의 종류

1) 장기스케줄러(Long-term scheduler or job scheduler)
1. 메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시로 저장됨. 이 Pool 에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 Ready Queue 로 보낼지 결정하는 역할을 함.
2. 메모리와 디스크 사이의 스케줄링을 담당.
3. 프로세스에 memory(및 각종 리소스)를 할당(admit).
4. degree of Multiprogramming 제어 (메모리에 몇 개의 프로그램이 올라갈 것인지를 제어)
5. 프로세스의 상태: new -> ready(in memory)
cf) 메모리에 프로그램이 너무 많이 올라가도, 너무 적게 올라가도 성능이 좋지 않음. 참고로 time sharing system 에서는 장기 스케줄러가 없음. 그냥 곧바로 메모리에 올라가 ready 상태가 됨.

2) 단기스케줄러(Short-term scheduler or CPU scheduler)
1. CPU 와 메모리 사이의 스케줄링을 담당.
2. Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정.
3. 프로세스에 CPU 를 할당(Scheduler Dispatch)
4. 프로세스의 상태: ready -> running -> waiting -> ready

3) 중기스케줄러(Medium-term scheduler or Swapper)
1. 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping)
2. 프로세스에게서 memory를 deallocate함. (메모리 할당을 취소함)
3. degree of Multiprogramming 제어 (메모리에 몇 개의 프로그램이 올라갈 것인지를 제어)
4. 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러.
5. 프로세스의 상태: ready -> suspended

※ Suspended(stopped) : 외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 의미함. 프로세스 전부 디스크로 swap out됨. blocked 상태는 다른 I/O 작업을 기다리는 상태이기 때문에 스스로 ready state 로 돌아갈 수 있지만 이 상태는 외부적인 이유로 suspending 되었기 때문에 스스로 돌아갈 수 없음.

 

⑥ 스케줄링 용어

1) 비선점형 스케줄링(Non-Preemptive Scheduling)
어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 실행되도록 보장함. 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 상관 없이 응답 시간을 예상할 수 있으며 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥교환에 의한 오버헤드가 적음. 일괄처리 시스템에 적합하며, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점을 가지고 있음.

2) 선점형 스케줄링(Preemptive Scheduling)
어떤 프로세스가 CPU를 할당 받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있음. 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있음. 빠른 응답 시간을 필요로 하는 대화식 시스템에 적합함. 운영체제가 프로세서 자원을 선점하고 있다가 각 프로세스의 요청이 들어왔을 때 특정 요건들을 기준으로 자원을 배분하는 방식임.

3) 정적 스케줄링(Static Scheduling)
프로세스에 부여된 우선순위가 바뀌지 않음. 고정 우선순위 스케줄링이라고도 함.

4) 동적 스케줄링(Dynamic Scheduling)
스케줄링 과정에서 프로세스의 우선순의를 변동시킴. 유동 우선순위 스케줄링이라고도 함.