운영체제 5장

5장 CPU 스케줄링
•5.1 기본개념
•5.1.1 CPU-입출력 버스트 사이클
•프로세스 실행은 CPU실행과 입출력 대기의 사이클로 구성된다. 프로세스들은 이들 두 상태 사이를 교대로 왔다갔다 한다.
•프로세스의 실행은 CPU버스트로 시작된다. 뒤이어 입출력 버스트가 발생하고, 그 뒤를 이어 또 다른 CPU버스트가 발생하며, 또 다른 입출력 버스트가 발생하는 식으로 진행된다.
•5.1.2 CPU스케줄러
•CPU가 유휴상태가 될때마다 운영체제는 준비완료 큐에 있는 프로세스들중에서 실행될 프로세스를 선택해야한다.
•선택절차는 단기 스케줄러에 의해 실행된다.
•준비완료큐는 반드시 선입선출 (FCFS)방식의 큐가 아니여도 된다.
•5.1.3 선점 스케줄링(preemtive scheduling)
•CPU스케줄링은 다음 네가지 상황하에서 발생할 수 있다.
•- 한 프로세스가 실행상태에서 대기상태로 전환될때
•- 프로세스가 실행상태에서 준비완료 상태로 전환될때(인터럽트)
•- 프로세스가 대기상태에서 준비완료 상태로 전환될때
•- 프로세스 종료할때
•상황 1,4에서의 스케줄링 방법을 비선점(non-preemtive)또는 협조적이라고 한다. 아니면 선점이라한다.
•5.1.4 디스패처(dispatcher)
•디스패처는 CPU의 제어를 단기스케줄러가 선택한 프로세스에게 주는 모듈이며, 다음과같은 작업을 포함한다.
•- 문맥을 교환하는 일
•- 사용자모드로 전환하는 일
•- 프로그램을 다시 시작하기 위해 사용자프로그램의 적절한 위치로 이동하는 일
•디스패치 지연(dispatch latency) : 디스패처가 하나의 프로세서를 중단시키고 다른 프로세스를 실행하는데 소요되는 시간
•5.2 스케줄링 기준(scheduling criteria)
•프로세스 스케줄링 기준
•- CPU이용률(utilization) : 우리는 가능한 한 CPU를 최대한 바쁘게 유지하기를 원한다.
•- 처리량(throughput) : 단위시간당 완료된 프로세스의 개수
•- 총 처리시간(turnaround time) : 프로세스를 실행하는데 소요된 시간, 메모리에 적재되기 위한 기다리며 소비한 시간, 준비완료 큐에서 대기한 시간, CPU에서 실행하는 시간, 그리고 입출력 시간을 합한시간이다
•- 대기시간(waiting time) : 준비완료큐에서 대기하면서 보낸 시간의 합이다.
•- 응답시간(response time) : 하나의 요구를 제출하고 첫번째 응답이 나올 때까지의 시간
•5.3 스케줄링 알고리즘 (FCFS)
•평균 대기시간이 길어질 수 있다.
•호위효과 (convoy effect) : 모든 다른프로세스가 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것
•비선점형
•5.3.2 최단 작업 우선 스케줄링(shortest job first scheduling)
•*
•5.3.3 우선순위 스케줄링(priority scheduling)
•CPU는 가장 높은 우선순위를 가진 프로세스에게 할당된다.
•CPU버스트가 클수록 우선순위는 낮다.
•문제는 무기한 봉쇄(indefinite blocking) 또는 기아상태(starvation)이다.
•노화 : 오랜시간 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
•5.3.4 라운드 로빈 스케줄링
•시분할 시스템에 적합하다.
•시간 조각은 일반적으로 10에서 100밀리초 동안이다.
•원형큐로 동작한다.
•5.3.5 다단계 큐 스케줄링(multilevel queue scheduling)
•포그라운드(대화형), 백그라운드(일괄처리)
•준비완료 큐가 여러개 존재
•각 큐는 다음과 같은 우선순위를 가진다
•- 시스템 프로세스
•- 대화형 프로세스
•- 대화형 편집 프로세스
•- 일괄처리 프로세스
•- 학생 프로세스
•5.3.6 다단계 피드백 큐 스케줄링
•프로세스가 큐 사이를 이동하는것을 허용한다.
•다음 매개변수에 의해 정의된다.
•- 큐의 개수
•- 각 큐를 위한 스케줄링 알고리즘
•- 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
•- 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
•- 프로세스가 서비스를 필요로 할때 프로세스가 들어갈 큐를 결정하는 방법
•5.4 스레드 스케줄링
•커널 수준 스레드가 스케줄링 대상
•5.5 다중처리기 스케줄링(multiple processor scheduling)
•부하공유(load sharing) 가능
•5.5.1 다중처리기 스케줄링에 대한 접근방법
•주 서버(master server)라는 하나의 처리기가 모든 스케줄링 결정과 입출력 처리 그리고 다른 시스템의 활동을 처리하게 하는 것(비대칭 다중처리)
•대칭 다중처리(symmetric multi processing,SMP) : 각 처리기가 독자적으로 스케줄링한다.
•5.5.2 처리기 친화성(processor affinity)
•캐시를 무효화하고 다시 채우는 작업은 비용이 많이 들기 때문에 대부분의 SMP시스템은 한처리기에서 다른 처리기로의 이주를 피하고 대신 같은 처리기에서 프로세스를 실행하려 하는것
•약한 친화성(soft affinity)->보장못함, 강한 친화성(hard affinity)
•5.5.3 부하균등화(load balancing)
•각 처리기가 자신만의 큐를 갖고 있어야한다.
•push 이주 : 특정 태스크가 주기적으로 각 처리기의 부하를 검사하고 만일 불균등 상태로 밝혀지면 과부하인 처리기에서 쉬고있거나 덜 바쁜 처리기로 프로세스를 이동시킴
•pull 이주 : 쉬고 있는 처리기가 바쁜 처리기를 기다리고 있는 프로세스를 자기쪽으로 가져올때 일어난다.
•5.5.4 다중코어 프로세서
•메모리 멈춤(memory stall) : 캐시미스등의 여러원인으로 발생
•크게 나눔(coarse-grained) 다중 스레딩 : 스레드가 메모리 멈춤과 같은 긴 지연시간을 가진 사건이 발생할 때까지 한 처리기에 실행됨
•잘게나눔(fine-grained) 다중 스레딩 : 명령의 주기의 경계에서와 같이 좀더 세밀한 정밀도를 가진 시점에서 스레드 교환이 일어난다.
•5.5.5 가상화와 스케줄링
•5.6 운영체제 사례들
•5.7 알고리즘 평가
•5.7.1 결정론적 모델링(deterministic modeling)
•5.7.2 큐잉 모델
•큐잉 네트워크 분석(queueing network analysis) : 도차귤과 서비스율로 이용률, 평균 큐 길이, 평균 대기시간등을 계산하는 연구
•n : 평균 큐 길이
•w : 큐에서의 평균 대기시간
•ㅅ : 새로운 프로세스들이 큐에 도착하는 평균 도착률
•n= ㅅ * W ->Little's formula
•5.7.3 시뮬레이션
•5.7.4 구현