Scheduling 개념
Scheduling 이란?
- Process에게 CPU 사용을 어떻게 할당할지
- 목표: CPU가 노는시간 없이 처리량 최대화하기 위함
Process 수행 사이클의 구성(CPU-I/O Burst Cycle)
CPU Burst: CPU로 연산을 수행하는 시간
I/O Burst: I/O 처리를 위해 기다리는 시간
Scheduling 종류
비선점형 스케줄링(OS가 강제로 너 나와 못함)
- Running 에서 Waiting 상태로 (I/O디바이스들)
- 수행 종료
선점형 스케줄링(너 나와)
- Running 에서 Ready 상태로 (time 스케쥴링)
- process의 수행을 정지할 수 있음
스케줄링 기준
CPU 사용률
- 전체 시간중에 CPU 작업을 처리하는 시간 비율
처리량
- CPU가 단위시간 당 처리하는 프로세스의 개수
응답시간
- Interaction system에서 요청 후 첫 응답이 올때까지의 시간
대기시간
- Process 가 ready Queue 내에서 대기하는 시간의 총합
Turnaround Time
- 프로세스가 시작해서 끝날때까지 걸리는 시간
슈퍼컴퓨터 - CPU 사용률 우선시
개인 PC - 응답시간 우선시
워크 스테이션(특정 job을 계속 수행하는) - 처리량 우선시
스케줄링 알고리즘
First-come, First-served(FCFS)스케줄링
- 먼저온 애 먼저라 운영체제가 관여할 수 없음
- 대기시간이 랜덤 갸차임 => 짧은 대기시간을 항상 보장X
Shortest-Job-First 스케줄링
- Job 짧은애부터 무조건 수행
비선점형에서는
중간에 끼어들기 못함
선점형에서는
돌고있어도 중간에 끼어드는 얘가 더 빠르면 끼어들기함
Priority 스케줄링
- 미리 주어진 우선순위에 따라서 CPU 할당
비선점형에서는
한번 CPU 받으면 내 CPU Burst 시간 끝나기전까지 계속
선점형에서는
새로 실행된 애중에 우선순위 높은 애 오면 바꿈
단점
기아상태
- Burst time이 긴편인 애는 시작이 빨라도 우선순위 애들한테 계속 밀림.
해결방법
Aging 기법
기다리는 시간에 따라 우선순위를 높여주자
라운드로빈 스케줄링
- Time sharing과 유사
- 선점형 방식
- Time Quantum(일정시간) 만큼 지나면 너 나와
- 큐를 정할때 1.스위칭 오버헤드 2.평균 버스트 타임 고려해야함
ex) 큐가 클경우: =>FCFS 되서 의미X
큐가 작을경우: context Switching에 필요한 시간보다 낮다면 효율 넘 떨어짐. (포카락로 생선 발라먹는 느낌)
장점
응답시간이 짧다
단점
문맥전환이 많음
멀티레벨 큐 스케줄링
- ready 큐를 여러개 줘서 각각에 대해 다른 스케줄링 알고리즘을 부여
=> 프로세스들을 구분해줌
Foreground Queue
- Interactive한 동작이 필요한 프로세스를 위한 큐 => Round Robin 기법사용
Background Queue
- CPU 연산만 묵묵히 하는 Process를 위한 큐 => FCFS 기법사용
멀티레벨 피드백 큐 스케줄링
- 멀티레벨 큐에서 프로세스들이 서로 다른 큐로 이동할 수 있는 스케줄링 방법
- Aging의 방법으로도 사용됨
- 언제 한단계 높은 큐로 올릴지, 내릴지 고민해야함
