6-1. 스케줄링의 이해
- Scheduling: 공유 자원을 언제 어떤 프로세스에 할당할지 결정하는 것
- 프로세서 스케줄링: 자원이 프로세서인 경우
스케줄링의 목적
- 자원 할당의 공정성 보장
- 단위 시간당 처리량 최대화
- 적절한 반환시간(turn around time) 보장
- 예측 가능성 보장
- 오버헤드 최소화
- 실행 대기 방지: aging(노화) 방법으로 언젠가 자원을 확보하게 해줄 수 있음
스케줄링 기본 요소
- 프로세서 버스트(burst): 프로세스를 프로세서에서 실행할 때
- 입출력 버스트: 프로세스가 추가로 실행하기 위한 입출력을 기다리고 있을 때
- 프로세스는 입출력 버스트 후, 다음 프로세서 버스트를 위해 ready queue(준비큐)로 이동
- 프로세서 버스트를 시작과 끝으로, 두 버스트를 교대로 진행
- 프로세서 중심 프로세스와 입출력 중심 프로세스를 잘 혼합해서 사용해야 함
스케줄링 단계
- 작업선택
- 작업 스케줄링에 따라 작업을 프로세스로 나눠 생성
- 수행 빈도가 적음 (장기 스케줄링)
- 작업 승인과 프로세서 결정
- 작업 승인(프로세서 사용 권한을 부여할 프로세스 결정)과 프로세서 할당 스케줄링
- 시스템의 오버헤드에 따라 연기할 프로세스 잠정적 결정
- 중기 스케줄링
- 프로세서 할당 스케줄링
- dispatching(준비 상태의 프로세스에 프로세서 할당)
- 단기 스케줄링
스케줄링 큐
- ready queue
- 시스템에 하나
- 프로세서를 할당받아 실행하기 위해 기다리는 프로세스가 대기
- 입출력 장치 큐
- 입출력 장치를 사용하려는 프로세스들이 대기
- 큐는 PCB를 연결 리스트로 연결한 형태
- 입출력장치 큐는 프로세스를 하나만 가질 수 있음 (공유 가능한 장치는 제외 ex 디스크)
스케줄링과 스케줄러
- 장기 스케줄러 (작업 스케줄러)
- 스케줄링에 따라 디스크에서 메모리로 작업을 가져와 처리할 순서를 결정
- 프로세스의 생성과정에서 프로세스의 준비 상태에 추가할 것 결정 + 메모리의 사용 가능 공간과 자원을 확인
- 실행할 작업을 메모리에 적재 → 단기 스케줄러(processor scheduler)가 메모리의 준비 상태인 프로세스 중 선택하여 프로세서 할당
- 중기 스케줄러
- 메모리에 부분적으로 프로세스 적재 (스왑: 프로세스를 별도의 기억 장소로 빼낼 수 있음)
- 프로세스 중단 원인 해결 시, 다시 준비 상태로 돌림
- 단기 스케줄러
- 미리 정한 스케줄링 알고리즘에 따라 실행할 프로세스를 선택
- 성공적인 작업 종료, 심각한 오류 발생 시 모든 자원 해제
- 문맥 교환: 프로세스의 레지스터를 적재
- user mode로 전환, 재시작시 사용자 프로세스가 올바른 위치를 찾을 수 있도록 함 - queueing diagram: 프로세스 스케줄링을 표현하는 방법
선점 스케줄링과 비선점 스케줄링
- 선점 스케줄링
- 독점하는 것 방지
- 우선순위가 높은 프로세스의 긴급 처리 용이
- 메모리에 프로세스가 많이 적재되어 있어야 효율적
- 비선점 스케줄링
- 모든 프로세서 공정
- 응답 시간 예측이 쉬움
스케줄링 알고리즘의 선택 기준
- 프로세서 사용률, 처리율은 최대화
- 반환시간, 대기시간, 응답시간 최소화
6-2. 스케줄링 알고리즘
- 선입선처리 스케줄링
- 비선점 방식, FIFO 큐로 구현
- 일괄 처리 시스템에서 효율적, 대화식 시스템에 적합 X
- 새로운 프로세스가 들어오면 PCB를 준비 큐 마지막에 연결
- 차례가 되면 준비 큐의 앞 부분 프로세스가 프로세서 할당 받고 준비 큐에서 삭제
- 호위 효과(convoy effect): 프로세서 중심 프로세스 하나가 프로세서 떠나기를 기다리는 현상 (불균형 상태)
- 최소작업 우선 스케줄링
- 선점 또는 비선점
- 선점형은 최소잔여 시간 우선(Shortest Remaining Time First)라고도 부름
- 실행 시간이 짧은 작업/프로세스에 할당 (시간이 같으면 선입선처리로 처리)
- 우선순위 스케줄링 (priority scheduling)
- 선점 또는 비선점
- 우선 순위가 가장 높은 프로세스에 프로세서를 할당
- 우선 순위는 내부적(제한 시간, 사용 파일 수, 기억장소 요청량…), 외부적(프로세스 중요도, 사용료, 정책….)으로 정의 구분
- 에이징: 오래 대기하는 프로세스의 우선순위를 점진적으로 증가시키는 방법 (기아와 무한 정지 해결)
- 라운드 로빈 스케줄링 (round-robin)
- 선점 방식, 시분할 시스템을 위해 설계
- 규정 시간량(time quantum) 또는 시간 할당량(time slice)를 정의
- 준비 큐를 순환 큐(circular queue)로 설계
- 실행 시간 > 규정 시간량 : OS가 인터럽트하여 프로세스를 중단, 프로세스의 레지스터를 PCB에 저장, 해당 프로세스를 준비 큐 마지막에 입력
- 최대 q시간 단위로 프로세서 시간의 1/n을 얻음 (규정 시간량 = q, 준비 큐의 프로세스 = n)
- processor sharing: 규정 시간량이 매우 작음
- 규정 시간량이 작을 수록 문맥 교환 횟수가 늘어남
- 기아 발생 X
- 다단계 큐 스케줄링 (MultiLevel Queue)
- 각 작업을 서로 다른 묶음으로 분류할 수 있을 때 사용
- 준비 상태의 큐를 종류별로 분할
- 각 큐는 독자적인 스케줄링
- 각 큐는 순서대로 절대적 우선순위
- 큐 사이 시간을 나눠 사용할 수 있음
- 다단계 피드백 큐 스케줄링 (MultiLevel Feedback Queue)
- 다단계 큐 스케줄링 + 작업이 큐 사이를 이동할 수 있음
- 프로세서 버스트의 특성에 따라 분리
- 입출력 위주의 프로세스에 우선권 부여
- 에이징 방법 활용: 오래 기다린 프로세스를 우선순위가 높은 큐로 이동 + 규정 시간량을 증가시킴
- HRN 스케줄링 (High Response-ratio Next)
- 비선점 방식
- 우선순위 스케줄링
- 우선순위 = (서비스를 받을 시간 + 대기 시간) / 서비스를 받을 시간
- 시스템 응답 시간 = 대기 시간 + 서비스를 받을 시간
- 다중 프로세서 스케줄링
- 각 프로세서에는 독자적인 큐와 스케줄링이 있음
- 하나의 시스템에 같은 종류 프로세서가 여러 개면 부하 공유가 발생 → 서로 독립된 큐 제공 → 비는 프로세서가 생김
- 공동의 준비 큐 사용, 모든 작업이 이용 가능한 프로세서 큐로 가도록 스케줄링
- 프로세스가 메모리에 적재되는 동안, 다른 프로세서에서 작업 실행 가능
- 비대칭 다중 처리 (Asymmetric MultiProcessing): 주종 구조, 주 프로세서의 오류는 시스템 마비로 이어짐
- 프로세서 스스로 스케줄링: 프로세서 2개가 같은 프로세스를 선택하면 안 됨
- 스레드 스케줄링
- 부하 공유(load sharing)
- 전역 큐에서 프로세서 유지
- 쉬고 있는 프로세스는 전역 큐에서 스레드 선택
- 중앙 큐가 병목 지점이 될 수도 있음
- 갱 스케줄링
- 스레드의 집합 : 프로세서 집합 = 1:1대응
- 단일 프로세스에 속한 스레드를 동시 스케줄링
- 전용 프로세서 할당
- 스레드를 실행 전담 프로세서에 할당하여 정의된 스케줄링 제공
- 동적 스케줄링
- 프로세스의 스레드 수를 동적으로 변경 (부하 조절 허용)
- 운영체제가 이용률을 높일 수 있도록 함
- 부하 공유(load sharing)
6-3. 스케줄링 알고리즘 평가
- 평균 대기 시간을 조사하여 평가할 수 있음
- 결정성 모형화를 주로 사용
