[CS 상식 - 운영체제] CPU 스케줄링 알고리즘

---

01. CPU 스케줄링 알고리즘

• 운영체제마다 다른 스케줄링 알고리즘을 사용

---

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

1. 선입 선처리 스케줄링 (FCFS, First Come First Served Scheduling)
   • 단순히 큐에 삽입된 순서대로 프로세스들을 처리하는 방식
   • 부작용: 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 점
   • 호위 효과(convoy effect): 짧은 실행시간임에도 앞서 실행된 프로세스를 기다리느랴 긴 시간을 기다려야하는 현상
2. 최단 작업 우선 스케줄링 (SJF, Shortest Job First Scheduling)
   
   • 큐에 삽입된 프로세스 중 CPU 이용 시간이 가장 짧은 프로세스부터 실행하는 방식
   • 기본적으로 비선점형 스케줄링 알고리즘이지만, 선점형으로도 구현 가능함
3. 라운드 로빈 스케줄링 (Round Robin Scheduling)
   • 선입 선처리 스케줄링 + 타임 슬라이스
   • 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미
   • 정해진 타임 슬라이스만큼의 시간 동안 돌아가며, CPU를 이용하는 선점형 스케줄링
   • 큐에 삽입된 프로세스들은 삽입된 순서대로 자원을 사용하지만 정해진 시간이 지나면 다음 프로세스가 넘겨 받음
   • 만약 아직 작업이 끝나지 않았다면 다시 큐의 맨 뒤에 삽입됨
   • 이 때 문맥 교환이 발생
   • 타임 슬라이스의 크기가 중요
     1. 지나치게 큰 경우: 선입 선처리 스케줄링과 다를 바가 없음, 호위 효과 발생
     2. 지나치게 작은 경우: 문맥 교환에 발생하는 비용이 커 CPU가 처리하는 일보다 프로세스를 전환하는데 비용이 많이 들게 됨
4. 최소 잔여 시간 우선 스케줄링 (SRT, Shortest Remaining Time)
   • 최단 작업 우선 스케줄링 + 라운드 로빈 알고리즘
   • 최소 잔여 시간 우선 스케줄링에서 프로세스들은 정해진 타임 슬라이스 만큼 CPU를 사용하되, CPU를 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스 먼저 선택됨
5. 우선 순위 스케줄링 (Priority Scheduling)
   • 프로세스들에 우선 순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
   • 근본적인 문제: 우선순위가 낮은 프로세스는 실행이 계속헤서 연기될 수 있음 (기아 문제)
   • 에이징 (aging): 오랫동안 대기한 프로세스의 우선순위를 높이는 것
6. 다단계 큐 스케줄링 (Multilevel Queue Scheduling)
   • 우선순위 스케줄링의 발전 형태
   • 우선 순위별로 준비 큐를 여러개 사용하는 스케줄링 방식
   • 장점
     1. 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리
     2. 큐 별로 타임 슬라이스를 여러개 지정할 수 있음
     3. 큐마다 다른 스케줄링 알고리즘 적용 가능
7. 다단계 피드백 큐 스케줄링 (Multilevel Feddback Queue Scheduling)
   • 다단계 큐 스케줄링의 발전된 형태
   • 기아 현상을 보완
   • 프로세스들이 큐 사이를 이동할 수 있음
   • 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있음
     
     

---