프로세스 스케줄링

기운찬곰·2020년 9월 25일

CS 운영체제

Computer Science

목록 보기

4/27

프로세스 스케줄링

1. 스케줄링이란?

프로세스가 생성되어 실행될 때 필요한 시스템의 여러자원을 해당 프로세스에게 할당하는 작업을 뜻 하며, 대기 시간은 최소화 하고 최대한 공평하게 처리하는 것을 목적으로합니다.

다중프로그래밍 시스템과 시분할 시스템을 만족시키기 위해서는 스케줄링 기법이 절대적으로 필요합니다.

다중 프로그래밍 : 메모리에 여러개의 프로세스를 올려두고 CPU이용을 최대화하기 위하여 항상 어떤 프로세스가 실행되도록 하는데 있습니다.
시분할 : 각 프로그램이 실행되는 동안 사용자가 상호작용 할 수 있도록 프로세스들 사이에서 CPU를 빈번하게 교체하는 것입니다.

2. 스케줄링 목적/평가기준

CPU 이용률(CPU utilization) : CPU를 얼마나 바쁘게 하는가. 높을수록 좋습니다.
처리율(Throughput) : 단위시간당 얼마나 많은 프로세스들이 완료되는가. 클 수록 좋습니다.
소요시간(Turnaround time) : 프로세스가 요청된 후 완료하기까지 얼마나 걸리는가. 메모리 접근 시간, 대기 큐에서의 대기 시간, CPU에서의 실행 시간, I/O 시간 등의 합으로 계산한다. 짧을수록 좋습니다.
대기시간(Waiting time) : 프로세스가 대기 큐에서 기다리는 시간의 합. 짧을수록 좋습니다.
반응시간(Response time) : 프로세스가 요청된 후 첫 번째 응답을 받기까지 걸리는 시간. 주로 상호교환 시스템(interactive system)에서 사용된다. 짧을수록 좋습니다.

3. 스케줄링 큐

프로세스가 시스템에 들어오면 job queue에 놓여집니다.

주 메모리안에 존재하며 프로세스 상태가 ready인 프로세스들은 ready queue라고 불리는 리스트 상에 유지됩니다. 이 큐는 보통 연결 리스트로 저장됩니다. ready queue의 헤더는 리스트의 첫 번째와 마지막 PCB를 가리키는 포인터를 포함합니다. 각 PCB는 ready queue에 있는 다음 프로세스를 가리키는 포인터 필드를 가집니다. (그렇다고 순서대로 실행되는 건 아닙니다. 어떤 프로세스부터 실행시킬지는 스케줄러가 결정하게 됩니다.)

device queue라고 불리는 또다른 리스트는 입출력 요청을 기다리는 waiting 상태를 가지는 프로세스들을 저장하고 있습니다.

새로운 프로세스는 처음에 ready queue에 놓입니다. 프로세스는 CPU를 할당받을 때(dispatch)까지 ready queue에서 대기합니다. 그리고 CPU가 할당되면 아래 사건들 중 하나가 발생할 수 있습니다.

프로세스가 I/O(입출력)을 요청하여 device queue에 저장
프로세스가 child process를 생성하고 그 프로세스가 종료될 때까지 기다린다. 역시 device queue에 저장
프로세스가 interrupt의 결과에 따라 강제로 CPU로부터 제거되어 ready queue에 다시 놓일 수 있다.
CPU 이용시간이 만료되어서 ready 큐로 다시 저장

프로세스가 종료될때까지 이 주기를 계속반복하게 됩니다.

4. 장기, 중기, 단기 스케줄링

프로세스는 다양한 schedule queue들 사이를 이주합니다. 프로세스를 스케줄링하기 위해서 운영체제는 이 queue들에서 프로세스들을 선택해야합니다. 선택 절차는 적절한 스케줄러에 의해 실행됩니다.

이미지 출처 : https://junsday.tistory.com/28

장기 스케줄링(Long-term scheduling) : 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐로 보내는 작업을 의미. 작업 스케줄링, 상위 스케줄링이라고도 하며, 작업 스케줄러에 의해 수행됩니다. 수행빈도가 적고 느리게 수행됩니다. 신중한 선택이 중요시 됩니다.
중기 스케줄링(Middle-term scheduling) : 어떤 프로세스들이 CPU를 할당 받을 것인지 결정하는 작업을 의미합니다. CPU를 할당받으려는 프로세스가 많을 경우 프로세스를 일시 보류시킨 후 활성화해서 일시적으로 부하를 조절합니다. 스왑 인/아웃 결정 (메모리 부족 시 swap out, 남으면 swap in) 을 합니다.
단기 스케줄링(Short-term scheduling) : 프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업을 의미합니다. CPU스케줄러, 프로세서 스케줄링, 하위 스케줄링이라고도 합니다. 프로세서 스케줄링 및 문맥 교환은 프로세서 스케줄러에 의해 수행됩니다. CPU의 최대 효율을 위해 빈번하고 빠르게 선택해야 합니다.