단일 프로세서

개념

스케줄링은 시스템의 목표를 달성할 수 있도록 프로세서를 할당하는 일련의 과정이다.
프로세서의 효율성을 높이고 시스템의 작업 처리 능력을 향상시키며 작업의 응답 시간을 최소화한다.

다중 프로그래밍

• 운영체제에서 가장 중요한 개념으로 여러 작업을 동시에 처리한다.
• 여러 프로그램을 메인 메모리에 적재, 프로세서를 분할하여 시스템 효율성을 향상시킨다.
• 장점: 프로세서 이용률을 높일 수 있다. 프로세서 처리율이 증가한다.

실행 과정

• 프로세스 A, B 각각 1초씩 실행하고 1초 기다리는 것을 60회 반복한다고 가정하였을 떄
• 프로세스 A 를 모두 처리한 후 프로세스 B 를 처리하면, 작업에 4분씩 소요된다.
• 컴퓨터가 실제 작업을 처리하는 시간은 2분, 쉬는 시간은 2분이 소요된다.
• A 를 먼저 실행하고 1초 후 B 를 실행한다.

기본 요소

• 프로세스 실행
• 컴퓨터 시스템에서 발생한 다양한 프로세스는 스케줄링을 해야하는 것, 그렇지 않은 것으로 구분한다.
• 스케줄링 하지 않고 실행: 인터럽트 처리, 오류 처리, 사용자의 시스템 호출 등 사전 처리
• 스케줄링을 해야하는 것: 사용자 프로세스, 시스템 프로세스
• 프로세스의 실행은 실행(프로세서 버스트), 입출력 대기의 순환으로 구성된다.

다중 작업 (Multi Tasking)

• 다중 프로그래밍과 상관없이 여러 개의 프로세스가 동시에 실행되는 경우
• 스풀링 등의 시스템 프로세스에 의해 단일 사용자 시스템에서도 여러개의 프로세스가 동시에 실행이 가능하다.

프로세스 버스트

• 프로세서 버스트 지속시간을 측정하면 전체적인 발생시간이 빈도 곡선으로 표시된다.

단계

프로세스들을 언제, 어느 프로세서에 할당한 것인가를 결정한다.

• 1단계: 작업 스케줄링(작업 선택) -> 승인 스케줄링 / 시스템 자원을 실제 사용할 작업을 결정하는 단계 / 수행빈도로 표현하여 장기 스케줄링 / 새로운 프로세스가 생성되면 실행되고, 작업 스케줄링이 수행되면 작업은 프로세스들로 나누어진다.
• 2단계: 작업 승인과 프로세서 할당 -> 어느 프로세스에 프로세서 사용 권한을 줄 지 결정 / 시스템의 부하가 변동함에 따라 어느 프로세스를 잠정적으로 연기시킬 것인지 결정 / 시스템의 작업 승인과 작업들에 대한 프로세서 배당 사이의 완충 역할 / 수행빈도로 표현하여 중기 스케줄링으로 교체 가능의 일보로 이해 가능
• 3단계: 준비 상태의 프로세서에 프로세스 할당(디스패치) -> 디스패치에 의해 준비 상태에 있는 프로세스의 프로세서를 어느 프로세스에 할당할 지 결정

성능 평가 기준

• 사용률: 프로세서를 실행 상태로 항상 유지하여 유휴 상태가 되지 않도록 한다.
• 처리율(Throughput): 단위 시간 당 시스템이 처리하는 작업의 양, 처리율이 높을수록 시스템이 더 많은 작업을 빠르게 처리할 수 있음을 나타낸다.
• 반환 시간: 작업이 시스템에 맡겨져 메인 메모리에 들어가지까지의 시간, 준비 큐에 있는 시간을 말한다.
• 대기 시간: 작업이 실행시간이나 입출력 시간에는 실제적인 영향을 미치지 못하므로 준비 큐에서 기다리는 시간이 최소화 되도록 사용자 수를 제한한다.
• 반응 시간: 의뢰한 시간에서부터 반응이 시작되는 시간까지의 간격, 대화형 시스템에 중요한 사항으로 대화식 작업을 우선 처리, 일괄 처리 작업은 대화식 작업의 요구가 없을 때 처리한다.

스케줄링 알고리즘

• 대부분의 알고리즘은 대화식 사용자 환경과 빠른 응답시간을 구현하는데 집중되었다.
• 프로세스 스케줄러는 프로세스 스케줄링 알고리즘에 따라 프로세서를 할당, 작업을 완료한다.
• 단일 프로세서로 구성된 시스템의 스케줄링 알고리즘을 살펴본다.

선점 스케줄링

• 현재 실행 중인 프로세스를 인터럽터 할 수 있거나 준비 상태로 이동시킬 수 있는 스케줄링, 하나의 프로세스가 장시간 동안 프로세서를 독점하는 것을 방지, 우선순위가 높은 프로세스들이 긴급한 처리를 요청할 때 유용하다. 선점을 효과적으로 하기위해 메인 메모리에 많은 프로세스들이 저장되어 있어야 하므로 많은 오버헤드를 초래한다. 설계 시 우선순위 개념을 반드시 고려하여 의미있게 배당해야 한다.

비선점 스케줄링

• 한 프로세스가 자원 선택 시, 다른 프로세스에 할당된 자원을 빼앗을 수 없는 스케줄링, 모든 프로세스를 공정하게 관리하여 실행시간 짧은 작업들을 기다리게 하는 경우가 있다. 우선순위가 높은 작업들이 중간에 입력되어도 대기 중인 작업들은 영향을 받지 않아 응답 시간 예측이 쉽다.

F C F S(First-Come, First-Served) 스케줄링

• 프로세스들이 도착한 순서대로 CPU 에 할당받는 방식
• 비선점형 스케줄링의 일종으로 먼저 도착한 프로세스가 종료될 때까지 다음 프로세스는 대기한다.
• FIFO(First-In, First-Out) Queue 로 구현한다.
• 일괄처리 시스템에서는 효율적이나, 대화식 시스템에서는 사용자의 빠른 응답 요구에 적합하지 않다.
• 새로운 작업이 시스템에 들어오면 프로세서의 PCB 는 준비 Queue 의 마지막에 연결한다.
• 차례가 되면 준비 Queue 의 앞부분에 있는 프로세스는 프로세서를 할당 받고 준비 Queue 에서 삭제된다.
• 성능이 좋지 않은 경우가 많으며 평균 대기시간이 긴 경우가 있다. (Convoy Effect)

SJF(Shortest Job First) 스케줄링

• 프로세서 버스트 시간이 가장 짧은 작업에 프로세서를 할당
• 선점, 비선점형 두 가지 방식이 있으며 선점형은 S R T F(Shortest Remaining Time First) 라고 한다.

Priority 스케줄링

• 준비 Queue 에 도착한 프로세스와 현재 실행중인 프로세스의 우선순위 비교
• 우선순위가 낮은 프로세스는 무한히 대기하는 기아현상이 발생할 수 있다. (Starvation)
• 우선순위가 같은 프로세스는 입장, 처리순으로 스케줄링 된다.

RR(Round Robin) 스케줄링

• 시분할 시스템을 위해 특별히 설계
• 규정 시간량(Time Quantum), 시간 할당량(Time Slice) 일정한 시간 동안 CPU 를 할당받고, 시간이 끝나면 다음 프로세스로 넘어가는 방식
• 준비 Queue 는 FIFO Queue
• 프로세서 스케줄러는 준비 Queue 의 앞부분에 있는 프로세스에 프로세서를 할당(Dispatch)
• 타임 퀀텀의 사이즈가 작으면 문맥 전환이 자주 발생하고, 너무 크면 F C F S 처럼 작동할 수 있다.

Multilevel Queue 스케줄링

• 각 작업들은 서로 다른 묶음으로 분류할 수 있을 때 사용
• 프로세스들이 우선순위에 따라 여러 개의 큐로 나뉘어 관리되는 방식
• 각 큐는 서로 다른 스케줄링 알고리즘을 사용할 수 있다.

Multilevel Feedback Queue 스케줄링

• 작업이 시스템에 들어가면 한 Queue 에서만 고정
• 다단계 큐 스케줄링의 개선된 방식 프로세스가 실행중에 다른 큐로 이동할 수 있다.
• CPU 사용 패턴에 따라 상위, 하위 Queue 로 이동 된다.

Multiprocessor 스케줄링

• 여러 개의 CPU 또는 코어가 있는 시스템에서 각 CPU 에 어떤 프로세스를 어떻게 할당할지를 결정하는 방식

HRN(Highest Response-Rate Next) 스케줄링

• 한슨 개발
• SJF 기법의 약점이었던 긴 작업과 짧은 작업 간의 지나친 불평등을 어느 정도 보완한 기법
• 비선점 스케줄링 기법으로 각 작업의 우선순위는 작업이 서비스 받을 시간 뿐만 아니라 서비스를 기다린 시간 등 두 가지의 함수로 나타낸다.
• 한 작업이 프로세서를 차지하면 작업이 종료될 때까지 실행된다.