[CS/운영체제] CPU 스케줄링

💡 정의

• 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
• CPU 이용률을 최대화하여 항상 실행 중인 프로세스를 가지게 한다.

💡목표 (시스템에 따라)

1. Batch System
   1. 사용자와의 직접적인 상호작용 없이 작업을 일괄 처리하는 시스템
   2. 유사한 작업들을 그룹화하여 한 번에 처리 ⇒ 대랑의 데이터 처리, 정기적인 작업에 사용
   3. 목표: CPU 이용률 극대화, 처리량 극대화
2. Interactive System (대화형 시스템)
   1. 사용자와 컴퓨터 간 실시간 상호작용이 가능한 시스템
   2. 사용자의 입력에 즉각적으로 응답
   3. ex. 개인용 컴퓨터의 운영체제(Windows, macOS)
   4. 목표: 응답시간 최소화, 사용자 경험 향상
3. Real-time System
   1. 정해진 시간 제약 내에 작업을 완료해야하는 시스템
   2. 주로 임베디드 시스템, 제어 시스템 등에서 사용됨
   3. 목표: 정해진 기한(deadline) 내 작업 완료, 예측 가능성 확보

💡프로세스 우선순위

• I/O 작업이 많은 프로세스(=입출력 집중 프로세스)는 CPU 작업이 많은 프로세스(=CPU 집중 프로세스)보다 대기상태에 더 많이 머무르게 된다. 따라서 우선순위가 더 높다.

 

• 스케줄링 큐에서 프로세스들이 대기 (*FIFO 아님 우선순위대로!)
  • 준비 큐: CPU wait
  • 대기 큐: 입출력 wait

 

💡프로세스 상태

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.

• 인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.
• 스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것.

 

💡CPU 스케줄링

** CPU 스케줄러는 언제 스케줄링을 결정하는가?

1) 실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때 - I/O 발생

2) 실행(running) 상태에서 준비(ready) 상태로 전환(switching)될 때 - 인터럽트 발생

3) 대기(waiting) 상태에서 준비(ready) 상태로 전환(switching)될 때 - I/O 종료

4) 종료(Terminated)될 때

기준

• CPU 이용률(Utilization): 어느 기간 동안 또는 특정 SNAPSHOT에서의 CPU의 이용률
• 처리량(Throughput): 단위 시간당 완료된 프로세스의 개수로써 나타낼 수 있다.
• 총처리 시간(Turnaround Time): 실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될 때 까지 걸린 시간
• 대기 시간(Waiting Time): 대기 시간은 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합이다.
• 응답 시간(Response Time): 하나의 Request를 제출한 후 첫 번째 Response가 나올 때(실행)까지의 시간이다.

😀 CPU Utilization, Throughput 최대화
     Turaround Time, Waiting Time, Response Time 최소화

 

🔗 선점형 스케줄링 : 빼앗기

• Interrupt 발생하면 CPU 자원을 뺏어서 다음 프로세스에게 할당
• 장점
  • 어느 한 프로세스의 자원 독점을 막아 프로세스들에 골고루 자원 배분
  • 우선순위가 높은 프로세스 빠르게 처리할 수 있음 (효율성)
• 단점: 문맥 교환으로 인한 오버헤드 발생
• 예시
  • Priority Scheduling (우선순위 스케줄링)
    • 우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation 이 생길 수 있음
    • 문제 해결: Aging → 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
  • Round Robin
    • 선입 선처리 + Time slice ( =Time Quantum, 각 프로세스가 CPU를 사용할 수 있는 정해진 시간)
    • 타임 슬라이스의 크기 고려
  • Multilevel-Queue (다단계 큐)
    • 우선순위 별로 준비 큐를 여러 개 사용하는 스케줄링 방식
    • 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정 해주는 방식 사용
    • 우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당.
    • 장점: 프로세스 유형 별로 우선순위를 구분할 수 있다. 따라서 큐 별로 적합한 스케줄링을 다르게 적용해서 효율적인 처리가 가능하다.
    • 단점: 프로세스가 큐 간 이동 불가능 → 우선순위 이동 X → Starvation
  • Multilevel-Feedback-Queue (다단계 피드백 큐) → CPU 스케줄링의 가장 일반적인 방식
    • 다단계 큐의 문제 해결: 큐 간의 이동이 가능하도록 함
    • 일단 준비된 프로세스가 있으면 가장 우선순위가 높은 큐에 삽입 ⇒ 자신의 차례에 CPU를 할당받아 실행 ⇒ 자신의 Time Quantum을 다 채웠는데도 CPU를 더 필요로 하는 프로세스는 밑 순위 큐로 내림 → CPU 집중 프로세스 일수록 우선순위가 상대적으로 낮아짐
    • Aging 적용 가능
    • ⇒ 어떤 프로세스의 CPU 시간이 너무 길면 우선 순위가 낮아지고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높인다.
    • 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간을 줄여줌

🔗 비선점형 스케줄링: 기다리기

• 한 프로세스가 자원을 점거하고 있다면, 이 프로세스가 종료/대기하기 전에는 다른 프로세스가 끼어들 수 없음
• 장점: 처리시간 예측 용이
• 단점: 효율성이 상대적으로 낮음
• 예시
  • FCFS (First Come First Served)
    • 큐에 도착한 순서대로 CPU 할당
    • 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
  • SJF (Shortest Job First)
    • 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
    • FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
  • HRN (Hightest Response-ratio Next)
    • 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
    • 우선순위 = (대기시간 + 실행시간) / (실행시간)

 

🗂️ 스터디 피드백
- 기아 현상은 아예 순서가 오지 않는 현상이다.
- 선점형의 대표 알고리즘으로 우선순위 스케줄링보다 Round Robin을 설명하는 것이 좋을 것 같다.
- 선점형과 비선점형을 비교할 때 시간이 아니라 중단을 기준으로 강조점을 주는 것이 좋을 것 같다. 왜냐하면 선점형의 우선순위 알고리즘은 타임 인터럽트가 적용되는 것이 아니기 때문이다.
- SRTF 방식은 SJF에 타임 인터럽트를 적용한 방식이다. 즉 SJF를 선점 방식으로 구현한 것이고, 이를 구현하려면 준비 큐에 새로운 프로세스가 도착했음을 알릴 때마다 인터럽트를 걸어야한다. 인터럽트가 발생하면 Context switching을 하고, 현재 실행 중인 프로세스의 잔여시간과 새 프로세스의 예상 실행시간을 비교한다.  만약 새 프로세스의 예상 실행시간이 더 짧다면, CPU 제어권을 넘긴다. 

 

* Context switching

1. 인터럽트가 발생하면, 운영체제는 현재 실행 중인 프로세스의 상태를 저장한다.

2. 스케줄러가 호출되어 준비 큐를 검사한다.