CPU Scheduling

CPU Scheduling

개념

 

프로세스는 생성되고 난 후 여러 상태를 거치게 된다. 운영체제의 CPU 스케줄러는 Ready 상태의 프로세스 중에서 어떤 프로세스에게 CPU를 할당할지 결정한다. 

 

목적 

• 공평성: 프로세스에게 자원을 배분하는 과정이 공평해야 함
• 효율성: CPU가 놀면 안 됨
• 안정성: 프로세스가 증가해도 안정적으로 돌아가야 함 

성능 척도

1. 시스템 입장
   • CPU 사용률(CPU Utilization): 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
   • 처리량(Throughput): CPU가 단위 시간당 처리하는 프로세스의 개수 
2. 사용자 입장
   • 대기시간(Waiting Time): 프로세스가 준비 상태에서 CPU를 할당받을 때까지 대기한 시간
   • 응답시간(Response Time): 프로세스의 명령 요청 후 응답이 올 때까지의 시간
   • 반환시간(Turnaround Time): 프로세스가 시작해서 끝날 때까지 걸리는 시간

선점 및 비선점 스케줄링

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때(I/O, 이벤트 대기 발생)
2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때(인터럽트 발생)
3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때(I/O, 이벤트 완료)
4. 프로세스가 종료할 때

• 비선점 스케줄링: CPU가 한 프로세스에 할당되면 프로세스가 종료하든지 or 대기 상태로 전환해 CPU를 방출할 때까지 점유 (1, 4)
• 선점 스케줄링: 인터럽트나 시스템 호출 종료시에 더 높은 우선 순위 프로세스가 발생되었음을 알았을 때 (2,3)

*스케줄러 디스패치: 준비 상태의 프로세스 중 하나를 선택해 실행

*인터럽트: 예외가 발생해 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리(선점)

*I/O or 이벤트 대기: 실행 중인 프로세스의 입출력/이벤트가 모두 끝날 때까지 대기 상태

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

 

CPU 스케줄링의 종류

 

• 비선점 스케줄링
  1. FCFS(First Come First Served Scheduling, FCFS)
     • 큐에 진입한 순서대로 CPU 할당
     • 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
  2. SJF(Shorstest Job First Scheduling)
     • 수행시간이 가장 짧다고 판단되는 프로세스부터 순차적으로 CPU 할당 후 수행
     • 평균 대기 시간 감소
     • CPU 요구시간이 긴 작업과 짧은 작업간의 불평등이 심해 CPU 요구기간이 긴 프로세스는 기아 현상 발생
  3. HRN(Highest Response-ratio Next Scheduling)
     • 대기 중인 프로세스 중 현재 Response Ratio가 가장 높은 것을 선택
     • Response Ratio = (대기시간 + 서비스시간) / 서비스시간 
     • 대기 시간이 긴 프로세스일 경우 우선순위가 높아짐
     • CPU 요구시간이 긴 작업과 짧은 작업간의 불평등을 해소할 수 있음 
• 선점 스케줄링
  • 우선순위 스케줄링(Priority Scheduling)
    • 가장 높은 우선순위를 가진 프로세스에 CPU 할당(우선순위 같을 경우 FCFS 순서로 스케줄)
    • 우선 순위가 낮은 프로세스가 무한정 기다리는 기아현상(Starvation) or 실행 준비는 되어 있지만 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주하는 무한 봉쇄(Indefinite blocking) 상황 발생
    • 노화(Aging)는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킴
  • 라운드 로빈 스케줄링(Round Robin Scheduling, RR)
    • FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간 할당량(time quantum)만큼 CPU를 할당 받음
    • 할당 시간이 크면 FCFS와 동일하고, 작으면 문맥 교환이 잦아져서 오버헤드 증가
  • 다단계 큐 스케줄링(Multilevel Queue Scheduling)

    

    • 작업들을 여러 종류의 그룹으로 분할, 여러 개의 큐를 이용해 상위 단계 작업 선점 
    • 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 time quantum을 설정
    • 우선순위가 높은 큐는 작은 time quantum 할당, 우선순위가 낮은 큐는 큰 time quantum 할당
  • 다단계 피드백 큐 스케줄링(Multilevel-Feedback-Queue Scheduling)
    • 다단계 큐 스케줄링과 달리 프로세스가 큐들 사이를 이동하는 것을 허용
    • 다단계 큐에서 자신의 time quantum을 다 채운 프로세스는 밑으로 내려가고 다 채우지 못한 프로세스는 원래 큐 그대로 => 처리 시간이 짧은 프로세스에게 유리 

---

 

Q. FCFS에서 발생하는 문제의 용어?

A. Convoy Effect(호위 효과), 실행 시간이 긴 프로세스가 앞에 도착하면 그 프로세스를 기다리는 동안 다른 실행 시간이 짧은 프로세스가 무한정 대기

 

Q. CPU Bound 프로세스와 I/O Bound 프로세스의 시간 할당량의 차이? 그 이유?

A. CPU Bound 프로세스의 경우 주로 CPU 연산에 많은 시간을 소비하기에 시간 할당량이 커야 효율적이고, I/O Bound  프로세스의 경우 CPU 작업보다는 I/O 작업을 기다리는 시간이 더 많기 때문에 다른 프로세스가 CPU를 사용할 수 있도록 짧은 시간 할당량을 제공하는 것이 좋다. 

 

 

 

참고

https://imbf.github.io/computer-science(cs)/2020/10/18/CPU-Scheduling.html

[Operating System - Chapter 5] CPU 스케줄링

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/CPU%20Scheduling.md