운영체제 - CPU스케줄링 알고리즘(선입 선처리, 최단 작업 우선, 라운드 로빈, 최소 잔여 시간 우선, 우선순위, 다단계 큐, 다단계 피드백 큐)

1. 선입 선처리 스케줄링(FCFS, First Come First Served)

단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링 방식이다. 즉 먼저 CPU를 요청한 프로세스부터 CPU를 할당한다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

호위 효과(Convoy Effect)

CPU 버스트 시간이 긴 프로세스가 준비 큐 앞에 위치하게 되면 그 뒤에 있는 짧은 CPU버스트를 가지는 프로세스들도 해당 프로세스의 끝을 기다려야 하는 현상이다.

---

2. 최단 작업 우선 스케줄링(SJF, Shortest Job First)

호위 효과를 방지하려면 CPU 사용이 긴 프로세스는 나중에 실행하고 CPU 사용시간이 짧은 프로세스는 먼저 실행하도록 한다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

 

최단 작업 우선 스케줄링은 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만 선점형으로 구현될 수도 있다. 선점형 최단 작업 우선 스케줄링이 뒤에 언급할 최소 잔여 시간 우선 스케줄링이다.

---

3. 라운드 로빈 스케줄링(RR, Round Robin)

선입 선처리 스케줄링 + 타임 슬라이스(Time Slice)

타임 슬라이스는 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다. 즉 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.

 

과정

1) 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용한다.

2) 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입한다. 이때 문맥교환이 발생한다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

타임 슬라이스가 중요하다.

타임 슬라이스가 너무 커지면 호위효과가 나타날 수 있고 너무 작으면 문맥교환이 빈번히 일어나 오버헤드가 발생할 수 있다.

---

4. 최소 잔여 시간 우선 스케줄링(SRT, Shortest Remaining Time)

최단 작업 우선 스케줄링 + 라운드 로빈 스케줄

정해진 시간만큼 CPU를 이용하되 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스를 선택한다.

---

5. 우선순위 스케줄링

프로세스들에 우선순위를 부여하고 우선순위 높은 프로세스부터 실행한다. 만약 우선순위가 같은 프로세스들을 선입 선처리로 스케줄링을 진행한다.

최단 작업 우선스케줄링, 최소 잔여 스케줄링 ⊂ 우선순위 스케줄

 

기아(Starvaiation)현상

우선순위가 높은 프로세스를 우선으로  처리하여 비교적 우선순위가 낮은 프로레스는 준비큐에 먼저 삽입되었음에도 불구하고 실행이 계속해셔 연기될 수 있다. 이를 기아현상이라고 한다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

에이징(Aging) - 기아현상 해결 방법

오랫동안 대기한 프로세스의 우선순위를 점차 증가시키는 방식이다. 즉 처음 우선순위가 낮았어도 언젠가는 우선순위가 높아지도록 한다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

---

6. 다단계 큐 스케줄링(Multilevel Queue)

우선순위 스케줄링의 발전된 형태이다. 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다.

우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스를 처리한다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

각 큐는 서로다른 우선순위를 가지며 다른 스케줄링 알고리즘을 가질 수 있다. 그러므로 다양한 프로세스 유형에 대해 다양한 스케줄링 전략을 적용할 수 있어 효율적인 시스템 운영이 가능하다.

 

기아 현상

프로세스가 한 번 큐에 들어가면 해당 큐에서의 실행을 마칠 때까지 큐를 빠져나오지 않는다. 그러므로 우선순위가 낮은 프로세스는 우선순위가 낮은 큐에 머무르게 되며 기아현상이 발생할 수 있다. 

---

7. 다단계 피드백 큐 스케줄링(Multilevel feedback queue)

여러개의 우선순위 큐를 사용하면서 프로세스가 큐 사이를 이동할 수 있는 스케줄링 방식이다.

 

과정

1) 프로세스 삽입

새로 준비가 된 프로세스는 우선순위가 가장 높은 큐에 삽입된다. 해당 큐에서 타임 슬라이스(일정 시간 동안의 CPU실행)동안 프로세스가 실행된다.

2) 큐 간의 이동

만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐로 이동한다. 그리고 또 해당 큐에 실행이 안끝나면 다음 우선순위 큐에 삽입되며 결국 CPU를 오래 사용해야 하는 프로세스는 우선순위가 점차 낮은 큐로 이동한다.

즉 CPU를 비교적 오래 사용해하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고 CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 우선순위가 높은 큐에서 실행이 끝난다.

3) 에이징

낮은 우선 순위 큐에서 너무 오래 기다록 있는 프로세스를 높은 우선순위 큐로 이동시켜 기아 현상을 예방한다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

 

즉 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위큐로 이동시키고 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동한다.

 

다단계 피드백 큐 스케줄링은 구현이 복잡하지만 가장 일반적인 CPU 스케줄링 알고리즘으로 알려져 있다.

 

 

 

 

 

참고 :  본 내용은개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제강의를 수강하여 작성하였습니다. https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard