[OS] 7. CPU 스케줄링 알고리즘

0. CPU 스케줄링 알고리즘의 종류

• 선입 선처리 스케줄링
• 최단 작업 우선 스케줄링
• 라운드 로빈 스케줄링
• 최소 잔여시간 우선 스케줄링
• 우선순위 스케줄링
• 다단계 큐 스케줄링
• 다단계 피드백 큐 스케줄링

 

1. 선입 선처리 스케줄링

• = FCFS(First Come First Served) 스케줄링
• 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
• 먼저 CPU를 요청한 프로세스부터 CPU 할당
• 단점: 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용(=호위 효과)
  • 실행시간이(17, 5, 2ms)인 프로세스들이 큐에 들어있을 때

 

2. 최단 작업 우선 스케줄링

• = SJF (Short Job First) 스케줄링
• 호위효과를 방지함
• CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 기간이 짧은 프로세스는 먼저 실행
• CPU 사용 기간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식

 

3. 라운드 로빈 스케줄링

• = RR(Round Robin) 스케줄링
• 선입 선처리 스케줄링 + 타임 슬라이스
• 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
  • 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용
  • 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입 (문맥교환)
• 타임 슬라이스의 크기가 중요
  • 크기가 지나치게 커지면 선입선처리스케줄링과 유사해짐
  • 크기가 지나치게 작으면 문맥교환에 발생하는 오버헤드때문에 CPU에 부담이 커짐

 

4. 최소 잔여 시간 우선 스케줄링

• = SRT (Shortest Remaining Time) 스케줄링
• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
  • 최단 작업 우선 스케줄링: 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
  • 라운드 로빈 스케줄링: 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
• 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택

 

5. 우선순위 스케줄링

• 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
• 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 C 우선순위 스케줄링
• 문제점과 해결책
  • 문제점 → 기아 현상 (starvation)
    • 우선순위 높은 프로세스만 주구장창 실행
    • 우선순위 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 실행 연기
  • 해결책 → 에이징(aging)
    • 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
    • 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
    • 우선순위가 낮아도 언젠가는 우선순위가 높아진다

 

6. 다단계 큐 스케줄링

• = Multilevel queue 스케줄링
• 우선순위 스케줄링의 발전된 형태
• 우선순위 별로 준비 큐를 여러 개 사용하는 스케줄링 방식
  • 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
  • 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
• 큐 간에 이동이 불가하여 기아현생 발생 여지가 있음

 

7. 다단계 피드백 큐 스케줄링

• = Multilevel feedback queue 스케줄링
• 다단계 큐 스케줄링의 발전된 형태
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
• 다단계 큐 스케줄링에서는 기본적으로 큐 간의 이동 불가
  • 우선순위 낮은 프로세스는 계속해서 실행 연기 우려
  • 기아 현상 발생 가능
• 준비상태의 프로세스를 가장 높은 우선순위 큐에 삽입→ 자기차례가 되면 CPU를 할당받음 → 타임슬라이스동안 실행이 다 안끝났으면 낮은 우선순위 큐로 이동해서 실행 → 반복
• 자연스럽게 CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고, 입출력 집중 프로세스의 우선순위는 상대적으로 높아짐
• 에이징 기법 적용하여 기아현상 예방하기도 함
• 즉, 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식
• CPU 스케줄링 방식의 가장 일반적인 형태로 알려져있음

 

 

 

---

 

 

 

『혼자 공부하는 컴퓨터 구조+운영체제』 강의 내용을 기반으로 작성된 글입니다