운영체제 레프토 (4장 CPU 스케줄링) 200612047 b반 박상수

개요 프로세서 스케줄링은 프로세서들이 언제 어느 프로세스에 할당될 지를 결정한다. 1단계 스케줄링(작업 스케줄링)은 어느 작업이 시스템에 먼저 들어올 것인지를 결정하며 이것이 일단 허락되면 그 작업은 프로세스들로 나누어진다. 3단계 스케줄링(디스패칭)은 준비상태에 있는 프로세스들 중 어느 것에 CPU를 할당할 것인지를 결정한다. 2단계 스케줄링은 어느 프로세서에게 CPU를 사용할 권한을 줄지를 결정하며 시스템의 부하가 변화함에 따라 어느 프로세서를 잠정적으로 정지시킬지의 여부를 결정한다. 스케줄링 기법은 공정해야 하며 단위 시간당 처리량을 최대화 시켜야 하고 많은 대화식 사용자들이 적절한 시간 내에 응답을 받도록 하는 등의 여러 가지 조건을 가지면 이런 조건들은 서로 상충되는 것들도 있으므로 스케줄링은 더욱 복잡한 문제가 된다. 현재 가장 많이 사용되는 스케줄링 기법은 다단계 피드백 큐잉 네트워크 기법으로 특히 다양한 특성의 작업이 혼합되어 있는 경우에 유용하다.

스케줄링 개념 (1) 기본 요소 ① CPU 입출력 버스트 주기(CPU I/O burst cycle) ② 프로세스의 상태 · CPU는 여러 프로세스에 의해 공유되므로 프로세스 상태에 따라 스케줄링 

프로세스 제어 블록 프로세스 제어 블록(Process Control Block, 줄여서 PCB)은 특정한 프로세스를 관리할 필요가 있는 정보를 포함하는 운영 체제 커널의 자료 구조이다. 작업 제어 블록(Task Control Block, 줄여서 TCB) 또는 작업 구조라고도 한다. "PCB는 운영 체제가 프로세스를 표현한 것이다 운영체제에 따라 PCB에 포함되는 항목이 다를 수 있지만, 일반적으로는 다음과 같은 정보가 포함되어 있엉. 프로세스 식별자(Process ID) 프로세스 상태(Process State) : 생성(new), 준비(ready), 실행(running), 대기(waiting), 완료(terminated) 상태가 있다. 프로그램 계수기(Prgoram Counter) : 프로그램 계수기는 이 프로세스가 다음에 실행할 명령어의 주소를 가리킨다. CPU 레지스터 및 일반 레지스터 CPU 스케줄링 정보 : 우선 순위, 최종 실행시각, CPU 점유시간 등 메모리 관리 정보 : 해당 프로세스의 주소 공간 등 프로세스 계정 정보 : 페이지 테이블, 스케줄링 큐 포인터, 소유자, 부모 등 입출력 상태 정보 : 프로세스에 할당된 입출력장치 목록, 열린 파일 목록 등

스케줄링 큐 다단계 큐 스케줄링(Multilevel Queue Scheduling)은 커널 내의 준비 큐를 여러 개의 큐로 분리하여 큐 사이에도 우선순위를 부여하는 스케줄링 알고리즘이다. 또한, 각각의 큐에 대해 다른 스케줄링 알고리즘을 적용하기도 한다. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)은 다단계 큐 스케줄링에서 한단계 발전된 방식이다. 다단계 큐 스케줄링에서는 프로세스가 하나의 큐에 영구적으로 할당되었지만, 다단계 피드백 큐 스케줄링에서는 프로세스들이 큐를 갈아탈 수 있도록 하였다.

스케줄러 ① 장기 스케줄러 · 어떤 작업이 시스템에 들어와서 수행될지를 결정 · 다중 프로그래밍의 정도를 결정 · CPU 중심 작업과 입출력 중심작업을 혼합 선택 · 실행될 작업을 주기억 장치에 적재 · 단지 작업이 시스템을 나갈 때만 실행 ② 단기 스케줄링 · 준비상태에 있는 작업들 중에서 실행할 작업을 선택 · 실행해야 할 프로세스를 수시로 선택 ③ 중간단계 스케줄러 · 가상기억 체제나 시분할 시스템에서 사용 · 교체를 전담 - 프로세스들이 서로 CPU를 차지하려 할 때에 프로세스를 기억 장소에서 빼내어 다중 프로그래밍의 정도를 줄임 -> 시간이 지나면 그 프로세스는 다시 주기억 장치로 적재되어 나머지 부분이 실행 ④ 분배기 (디스패쳐 : dispatcher) · 단기 스케줄러에 이해 선택된 프로세스에 실제로 CPU를 할당 · 프로세스의 레지스터를 적재 · 재시작시 프로그램의 위치 지정

스케줄링 단계 1단계 스케줄링 2단계 스케줄링 3단계 스케줄링 작업 스케줄링(Job schuduling)이라고도 한다. 어느 작업부터 시스템 내의 자원들을 실제로 사용할 수 있도록 할지를 결정한다. 작업들이 시스템에 들어오는 것을 승인하는 것이기 때문에 승인 스케줄링(Admission scheduling)이라고도 한다. 2단계 스케줄링 어느 프로세스부터 CPU를 차지할 수 있게 할지를 결정한다. 프로세스들을 보류시키고 다시 활성화시키는 기법을 사용하여 시스템에 대한 단기적인 부하를 조절한다. 그렇게 함으로써 시스템을 적절히 운영할 수 있다. 작업 승인(1단계)와 CPU 배당(3단계) 사이의 완충 작용을 한다. 3단계 스케줄링 CPU가 사용가능한 경우 어느 프로세스에게 배당할지를 결정한다.

선점형 스케줄링과 비선점형 스케줄링 스케줄링 적용 시점에 따라 비선점형과 선점형의 2가지로 구분할 수 있다. 비선점형은 위의 결정 시점 중 1번과 4번의 상황에서만 수행되며, 선점형은 1번에서 4번까지 모든 상황에서 수행된다. 비선점형 스케줄링(Non-preemptive Scheduling) : 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다. 선점 방식보다 스케줄러 호출 빈도 낮고 문맥 교환에 의한 오버헤드가 적다. 일괄 처리 시스템에 적합하며, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점이 있다. 선점형 스케줄링(Preemptive Scheduling) : 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다. 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있다. 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있다. '운영체제가 프로세서 자원을 선점'하고 있다가 각 프로세스의 요청이 있을 때 특정 요건들을 기준으로 자원을 배분하는 방식이다.

스케줄링의 종류 비실시간 프로세스 스케줄링 실시간 프로세스 스케줄링 FCFS 스케줄링(First Come First Served Scheduling) SJF 스케줄링(Shortest Job First Scheduling) SRTF 스케줄링(Shortest Remaining-Time First Scheduling) RR 스케줄링(Round Robin Scheduling) HRN 스케줄링 다단계 큐 스케줄링(Multilevel Queue Scheduling) 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling) 실시간 프로세스 스케줄링 RM 스케줄링(Rate Monotonic Scheduling) EDF 스케줄링(Earliest Deadline First Scheduling)

스케줄링 평가기준 스케줄링 알고리즘은 다음과 같은 기준을 통해 평가할 수 있다. CPU 사용률(CPU Utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율. 처리량(Throughput) : CPU가 단위 시간당 처리하는 프로세스의 개수. 응답 시간(Response Time) : 대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간. 대기 시간(Waiting Time) : 프로세스가 준비 큐 내에서 대기하는 시간의 총합. 턴어라운드 시간(Turnaround Time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간.