CPU 스케쥴링

스케쥴링

• CPU를 잘 사용하기 위해 프로세스를 잘 배정하는 것
• 조건 : 오버해드 적게 / 사용률 높게 / 기아현상 적게
• 배치 처리 시스템
  • 프로그램 순차적으로 실행, 여러 프로그램 동시 실행 X
  • 목표 : 가능하면 많은 일을 수행, 시간보다는 처리량(throughout)이 중요
• interactive 시스템
  • 목표 : 빠른 응답시간, 적은 대기시간
• real-time 시스템
  • 목표: 기한 맞추기
• 시분할 시스템
  • 목표 : 다중사용자 지원, 응답시간 최소화

멀티 태스킹 / 멀티 프로그래밍 / 멀티 프로세싱

• 멀티 태스킹 : 단일 CPU에서 여러 응용프로그램을 동시에 실항하는것처럼 보이게 하는 시스템
• 멀티 프로그래밍: 최대한 CPU를 일정 시간당 많이 활용하는 시스템
• 멀티 프로세싱: 여러 CPU에서 하나의 응용 프로그램을 병렬로 실행해서, 실행속도르르 높이는 기법

선점 / 비선점 스케쥴링

• 선점 : OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우 (처리시간 예측 어려움)
• 비선점 : 프로세스 종료 또는 I/O 등의 이벤트가 있을때까지 실행 보장(처리시간 예측 용이)

프로세스 상태

선점: Interrupt, I/O or Event Completion, I/O or Event Wait, Exit
비선점 :I/O or Event Wait, Exit

• 승인 (Admitted) : 프로세스 생성이 가능하여 승인됨.

• 스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것.

• 인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.

• 입출력 또는 이벤트 대기 (I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것.

• 입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것.

CPU 스케쥴링의 종류

비선점 스케쥴링

• FCFS(First Come First Served)
  • 큐에 도착한 순서대로 CPU 할당
  • 실행시간이 짧은게 뒤로가면 평균 대기시간 길어짐
• SJF(Shortest Job First)
  • 수행시간이 짧다고 판단되는 작업을 먼저 수행
  • FCFS보다 평균 대기시간 감소, 짧은 작업에 유리
• HRN(Highest Response-ratio Next)
  • 우선순위를 계산하여 점유 불평등 보완 (SFJ 단점 보완
  • 우선순위 = (대기시간 + 실행시간) / 실행시간

선점 스케쥴링

1. Priority scheduling

• 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
• 우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation 이 생길 수 있음
• Aging 방법으로 Starvation 문제 해결 가능

2. Round Robin

• FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할달 받음
• Time Quantum or Time Slice : 실행의 최소 단위 시간
• 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환 (Context Switching) 잦아져서 오버헤드 증가

3. Multilevel - Queue

• 작업을 여러 종류의 그룹으로 나누어 여러 단계의 큐를 이용하는 기법
• 우선순위가 낮은 큐들이 실행되지 못하는걸 방지하고자 각 큐마다 다른 time quantum을 설정해주는 방식 사용
• 우선순위 높으면 time quantum 작게, 우선순위 낮으면 time quantum 길게

4. Multilevel - Feedback - Queue

• 다단계 큐에서 자신의 time quantum을 다 채운 프로세스는 밑으로 내려가고 다 채우지 못한 프로세스는 원래 큐 그대로
• 짧은 작업에 유리하고, 입출력위주(interrupt가 잦은)작업에 우선권을 준다.
• 처리시간이 짧은 프로세스를 먼저 처리하기 때문에 turnaround 평균시간을 줄여준다.

CPU 스케줄링 척도

• Response Time
  : 작업이 처음 실행되기까지 걸린 시간
• Turnaround Time
  : 실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될 때 까지 걸린 시간