프로세스 스케줄링

자원관리

시간분할 관리

• 프로세서 자원을 시간으로 분할하여 사용(프로세스 스케줄링)

공간분할 관리

• 메모리 자원을 분할하여 사용

스케줄링

스케줄링(scheduling)

자원을 어떤 시점에 어떤 프로세스에게 할당할지 정하는 것.

• 스케줄링이 필요 없는 프로세스 : 인터럽트 처리, 오류 처리, 사용자의 시스템 호출
• 스케줄링이 필요한 프로세스 : 사용자 프로세스, 시스템 프로세스

스케줄링 목적

• 자원 할당의 공정성을 보장하기 위해
• 단위시간당 처리량을 최대화하기 위해
• 적절한 반환시간(프로세스 완료)를 보장하기 위해
• 우선순위를 부여하여 우선순위가 높은 프로세스부터 실행하도록 하기위해

스케줄링의 기준

• 시스템의 특성에 맞는 스케줄링을 선택해야함
• 프로세스 우선순위에 맞는 스케줄링을 선택해야함
• 프로세스 총 실행 시간이 짧은 스케줄링을 선택해야함
• 프로세서 버스트
  프로세스를 프로세서에서 실행 할 때를 의미한다.
• 입출력 버스트
  프로세스가 추가로 실행하려고 입출력을 기다리고 있을 때를 의미한다.
  입출력 버스트 후 다음 프로세서 버스트를 위해 준비 큐로 이동한다.
  

입출력 대기시간이 짧으면 프로세서를 오래 차지하여 프로세서 버스트가 길고, 입출력 대기시간이 길면 입출력을 하려고 오래 기다리므로 프로세서 버스트가 짧다.
즉, 입출력 중심 프로세스는 프로세서 버스트가 매우 짧고, 프로세서 중심 프로세스는 프로세서 버스트가 매우 길다.

입출력 중심 프로세스 -> 프로세서 중심 프로세스 : 짧은 지연
프로세서 중심 프로세스 -> 입출력 중심 프로세스 : 긴 지연
그렇기때문에 스케줄링을 통해 프로세서 중심 프로세스와 입출력 중심 프로세스를 적절히 혼합해야함.

스케줄링 단계

1. 작업 스케줄링: 자원을 사용할 작업을 결정하는 스케줄링
2. 작업 승인 & 프로세서 결정 스케줄링: 프로세서를 사용할 권한을 부여할 프로세스를 결정 및 할당.
3. 프로세서 할당 스케줄링: 준비 상태의 프로세스 중 프로세서를 할당할 프로세서를 결정.(디스패칭)
   

스케줄링 큐

• 준비 큐
  프로세서를 할당받으려고 기다리는 프로세스들이 대기하는 곳.
• 입출력장치 큐
  입출력장치를 사용하려고 기다리는 프로세스들이 대기하는 곳.
  
  큐는 프로세스 제어 블록을 연결 리스트로 연결하고 있다. 머리(head)와 꼬리(tail)로 구성되어 있다. 머리는 첫번째 프로세스 제어 블록을 가리키고, 꼬리는 마지막 프로세스 제어 블록을 가리킨다.
  

큐잉 도표(queueing diagram)

프로세스 스케줄링을 표현하는 방법.

스케줄러의 종류

• 장기 스케줄러 = 작업 스케줄러
  디스크에서 메모리로 작업을 가져와 처리할 순서를 결정.
  단기 스케줄러에 비해 상대적으로 드물게 수행.

• 단기 스케줄러
  메모리에 적재된 프로세스 중 프로세서를 할당하여 실행 상태가 되도록 결정.
  가장 자주 수행됨.
  그래서 실행할 프로세스를 수시로 선택함.
  디스패처가 포함됨.

  디스패처
  프로세스에 프로세서를 할당하는 역할.

• 중기 스케줄러
  프로세스를 별도의 기억장소에서 뺐다가 다시 메모리로 들어가게 할 수 있다. 이를 스왑이라고 함.
  

시분할 시스템에서 장기 스케줄러는 없고 새로운 프로세스를 메모리에 넣기만 함.

선점과 비선점 스케줄링

• 선점 스케줄링
  우선순위가 높은 프로세스들을 긴급 처리할 때 유용.
  빠른 응답 시간을 유지하는 것이 필수.
  자주 프로세스를 바꿔, 오버헤드가 커질 수 있어 효과적으로 사용하려면 메모리에 가능한 많은 프로세스가 적재되어 있어야 함.
  우선순위가 존재해야함.
• 비선점 스케줄링
  모든 프로세스들이 프로세서를 공정하게 사용함.
  응답시간을 예측하기 쉬움.
  문맥교환 자체가 줄어들기때문에 그에 따른 오버헤드가 적어짐.

알고리즘의 선택 기준

• 프로세서 사용률: 프로세서를 항상 실행 상태로 유지해야함.
• 처리율: 단위시간당 완료하는 작업 수가 많도록 해야함.
• 반환시간: 작업을 완료하는 데 걸리는 시간을 최소화 해야함.
• 대기시간: 준비 큐에서 기다리는 시간을 최소화하도록 큐 안의 프로세스 수를 제한 해야함.
• 반응시간: 작업을 요청한 후 첫번째 출력 사이의 시간으로 대화형 시스템에서 중요한 사항.
  

스케줄링 알고리즘

기본 스케줄링

• 공평성 중시 : FCFS, RR
• 효율성 중시 : SPN, SRTN, HRN
  효율성 중시 알고리즘을 사용하기 위해서는 실행시간을 예측해야하는데 이에 대한 방법의 부재와 예측하는데 부하가 생길 수 있음.
  

선입선출 스케줄링(FCFS, FIFO)

• 비선점 스케줄링
• 장점
  스케줄링의 이해와 구현이 매우 단순
  스케줄링에 대한 오버헤드가 낮음
  일괄 처리 시스템에서 매우 효율적
• 단점
  응답시간이 느림 => 대화식 시스템 부적합
  호위 효과(convoy effect) : 긴 프로세스가 진행되는 동안 짧은 프로세스들이 기다려야 하는 현상
  

라운드 로빈 스케줄링(RR)

• 선점 스케줄링
• 규정 시간량 또는 시간 할당량을 정의하여 그 시간동안만 프로세스 처리
• 시분할 시스템을 위해 설계
• 준비큐를 순환 큐로 설계
• 큐는 FIFO로 되어 있어 시간 할당량이 끝난 프로세스는 큐의 가장 뒤로 이동
• 대부분 대화식 프로세스는 시간 할당량보다 짧은 시간을 요청하므로 입출력 활용도를 극대화하고 대화식 프로세스에 빠르게 반응할 수 있음
• 시간 할당량이 작으면 문맥교환이 잦으므로 평균 반환시간이 커짐. 그러므로 시간 할당량을 충분히 크게 해줘야함.
• 모든 프로세스가 공정하게 프로세서를 할당받으므로 기아가 발생하지 않음
• 평균 대기시간이 FIFO와 SJF보다 적음
  

우선순위 스케줄링

• 선점 or 비선점 스케줄링
• 도착한 프로세스의 우선순위와 실행중인 프로세스의 우선순위를 비교하여 우선순위가 높은 프로세스를 처리
• 우선순위가 낮은 프로세스는 무한 정지 및 기아상태가 될 수 있음 -> 에이징을 통해 해결가능
• 에이징: 오래 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법
• 실시간 시스템에 사용가능

우선순위를 정하는 방법

• 내부적 우선순위
  제한시간, 기억장소 요청량, 사용 파일 수, 평균 프로세서 버스트에 대한 평균 입출력 버스트의 비율 등
• 외부적 우선순위
  프로세스의 중요성, 사용료를 많이 낸 사용자, 작업을 지원하는 부서, 정책적인 요인 등

최소작업 우선 스케줄링(SJF, SPN, Shortest Job First, Shortest Process Next)

• 선점 or 비선점 스케줄링
• 장점
  평균 대기시간 최소화
  시스템 내 프로세스 수 최소화(스케줄링 부하 감소, 메모리 절약)
  빠른 응답시간
• 단점
  매우 불공정한 작업
  기아현상 발생
  정확한 실행시간을 알 수 없음
  선점일 경우 문맥 교환 시간이 소요됨

HRN(Highest Response ratio Next) 스케줄링

• 비선점 스케줄링
• SJF과 FIFO의 단점인 기아현상 문제를 보완한 스케줄링
• 우선 순위 스케줄링의 또 다른 예
• 자원을 효율적으로 활용
• aging을 사용하여 대기사간을 고려한 기회를 제공하므로 기아가 발생하지 않음
• 오버헤드가 높을 수 있음
• 서비스 받을 시간(실행 시간)을 예측하는 기법이 필요

다단계 큐(MLQ, Multi level Queue) 스케줄링

• 선점 스케줄링
• 작업들을 서로 다른 묶음으로 분류할 수 있을 때 사용
  ex- 전면 작업/후면 작업: 전면 작업은 후면 작업에 비해 우선순위가 높음
• 준비 큐를 종류별로 여러 단계로 분할
  이런 큐는 자신만의 독자적인 스케줄링을 갖음
  또한 큐 사이는 선점 우선순위 스케줄링을 사용함
• 응답이 빠름
• 여러 준비 큐와 스케줄링 알고리즘 때문에 추가 오버헤드가 발생함
• 우선순위가 낮은 큐의 프로세스는 기아가 발생할 수 있음
  

다단계 피드백 큐(MFQ, Multi level Feedback Queue) 스케줄링

• 선점 스케줄링
• 다단계 큐 스케줄링은 작업은 한 큐에서 다른 큐로 옮기지 않는 문제가 있음
  이를 해결하기 위해 만들어진 스케줄링으로 작업이 큐 사이를 이동할 수 있음
• 요청하는 프로세서 실행 시간이 길면 작업을 낮은 단계 큐로 옮김
• 입출력 중심 작업과 전면 작업은 높은 우선순위 큐
• 프로세서 중심 프로세스는 낮은 우선순위 큐
• 높은 우선순위 큐가 완전히 비어야 낮은 우선순위 큐가 실행될 수 있기때문에 기아상태에 빠질 수 있음
  우선순위 스케줄링처럼 에이징 방법을 사용해 우선순위가 높은 큐로 이동시키는 방법으로 해결 할 수 있음
• 매우 유연하여 스케줄러를 특정 시스템에 맞게 구성할 수 있음
• 설계와 구현이 매우 복잡함
• SPN, HRN의 문제점인 실행시간을 예측을 하지 않아도 비슷한 효과를 볼 수 있음

스케줄링 알고리즘 평가

평가 기준

• 최대 응답시간이 1초라는 제약 조건에서 프로세서 이용률
• 평균 반환시간이 전체 실행 시간에 선형적으로 비례하는 처리율