스케줄링 2A 200512015 박남규.

Presentation on theme: "스케줄링 2A 200512015 박남규."— Presentation transcript:

1 스케줄링 2A 박남규

2 1. 스케줄링 정의 : 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미한다.
* 목적 : CPU나 자원을 효율적으로 사용하기 위한 정책

3 2. 스케줄링 기법 프로세서 스케줄링은 프로세서들이 언제 어느 프로세서에 할당될 지를 결정한다. 1단계 스케줄링(작업스케줄링)은 어느 작업이 시스템에 준비상태에 있는 프로세스들 중 어느 것에 CPU를 할당할 것인지를 결정한다. 2단계스케줄링은 어느 프로세서에게 CPU를 사용할 권한을 줄지를 결정하며 시스템의 부하가 변화함에 따라 어느 프로세서를 잠정적으로 정지 시킬 지의 여부를 결정한다. 스케줄링 기법은 공정해야 하며 단위 시간당 처리량을 최대화 시켜야 하고 많은 대화식 사용자들이 적절한 시간 내에 응답을 받도록 하는 등의 여러 가지 조건을 가지면 이런 조건들은 서로 상충되는 것들도 있으므로 스케줄링은 더욱 복잡한 문제가 된다. 현재 가장 많이 사용되는 스케줄링 기법은 다단계 피드백 큐잉 네트워크 기법으로 특히 다양한 특성의 작업이 혼합되어 있는 경우에 유용하다.

4 3. 스케줄링의 단계 1단계 스케줄링 - 어느 작업부터 시스템 내의 자원들을 실제로 사용하도록 할 것인지를 결정.
- 작업들이 시스템에 들어오는 것을 허용하는 것이므로 승인 스케줄링. - 일단 승인이 되면 작업들은 프로세스들 또는 프로세스의 그룹들을 형성. 2단계 스케줄링 - 어느 프로세스부터 CPU를 차지할 수 있도록 할지를 결정. - 프로세스들의 보류와 활성화를 통해 시스템의 단기적 부하를 조정. - 시스템에의 작업 승인과 이 작업들에 대한 CPU배당 사이의 완충 역할. 3단계 스케줄링 CPU가 이용 가능할 때 어느 프로세스에게 배당할지를 결정 디스패쳐에 의해 수행. ※ 디스패쳐는 항시 주기억 장치에 상주

5 4. 스케줄링의 목적 공정성 단위시간당 처리량 최대화 대화식 사용자에게 빠른 응답 예측이 가능 오버헤드 최소화
자원 사용의 균형 응답시간과 자원 활용간의 균형유지 무한정 연기의 회피 우선 순위 제도 도입 주요 자원을 차지하고 있는 프로세스에 대한 우선권 바람직한 행동을 하는 프로세스에 대한 서비스 시스템에 부하가 많은 경우 완만한 성능 체증 발생

6 5. 스케줄링 정책 비선점 스케줄링(Non-Preemptive)  프로세스가 CPU를 사용하고 있으면 그 프로세스의 작업이 완료되기 전까지의 다른 프로세스가 강제적으로 CPU를 점유할 수 없는 스케줄링 기법이다.  종류 : FIFO, SJF, HRN, 우선순위, 기한부 스케줄링 선점 스케줄링(Preemptive)  하나의 프로세스가 프로세서의 점유하고 있을 때 다른 프로세스가 프로세서를 빼앗을 수 있는 방법이다.  종류 : RR, SRT, MFQ 스케줄링

7 6. 비선점 스케줄링 종류 FCFS(First Come First Service, 선입 선출)
- 준비 상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법. SJF(Shortest Job First, 단기작업 우선) - 실행 시간이 가장 짧은 프로세스에게 먼저 CPU할당. - 평균 대기시간이 가장 적은 알고리즘. - 실행시간이 긴 프로세스가 순위기 밀려 무한 연기상태가 발생될 수 있다. 우선순위 - 프로세스마다 우선순위 부여 - 우선순위가 동일한 경우 FCFS 기법으로 할당 - 가장 낮은 순위를 부여 받은 프로세스는 무한 연기 또는 기아상태가 발생할 수 있다.

8 6. 비선점 스케줄링 종류 HRN(Highest Response-ratio Next)
- 실행시간이 긴 프로세스가 불리한 SJF기법 보완. - 우선순위 공식을 이용하여 실행시간이 짧은 프로세스나 대기 시간이 긴 프로세스에게 우선순위를 줌. - 우선순위를 계산하여 숫자가 높은 것부터 우선순위가 부여됨. - 우선순위 계산식 = (대기시간+실행시간)/실행시간. 기한부(Deadline) - 일정시간 동안 프로세스 완료하는 기법. - 제한된 시간 안에 완료되지 않을 경우 제거 되거나 처음부터 다시 실행해야 함. - 여러 프로세스들이 동시에 실행되면 스케줄링이 복잡해지며, 프로세스 실행 시 집중적으로 요구되는 자원관리에 오버헤드가 발생한다.

9 7. 선점 스케줄링 종류 Round Robin 시분할 시스템을 위해 고안된 방식, FCFS 기법 변형.
각 프로세스는 시간 할당량 동안만 실행한 후 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치. 할당된 시간이 클수록 FCFS와 같다. 시간이 작을 수록 문맥교환과 오버헤드가 자주 발생. 다단계 큐 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비단계 큐 사용. 시스템, 대화형, 편집, 일괄처리 프로세스 등으로 분류. 준비상태 큐 마다 다른 스케줄링 기법 사용가능. 다른 준비상태 큐로 이동 불가. 하위단계 준비 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면 상위단계 프로세스에게 CPU를 할당.

10 7. 선점 스케줄링 종류 SRT(Shortest Remaining Time) SJF 기법을 변형, 선점 SJF라고도 한다.
실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당. 준비상태 큐에 있는 프로세스의 실행 기간 추적으로 오버헤드 증가. 다단계 피드백 큐 다단계 큐 기법 개선하여 다른 준비상태 큐로 이동 가능. 각 큐마다 시간 할당량부여 시간 동안 완료 되지 못한 프로세스는 다음 단계 큐로 이동. 마지막 단계 큐에서는 RR스케줄링으로 할당. ☞ 참고사항 ※ Dispatch : 준비 상태에서 대기하고 있는 프로세스 중 하나가 프로세서를 할당 받아 실행 상태로 전이되는 과정. ※ 실행 시간 = 서비스 시간 = 버스트 시간. ※ 에이징(Aging)기법 : 대기 시간 등에 따라 우선순위를 높여주는 것을 의미.

11 8. HRN 예제 우선순위=(대기시간+서비스시간)/서비스시간
작업 대기시간 서비스시간 A 6 4 B 10 5 C 15 3 A : (6+4)/4 = 2.5 B : (10+5)/5 = 3 C : (15+3)/3 = 6 결과는 C 가 우선순위가 가장 높다.