[til_211130][운영체제] CPU 스케줄링

- 비선점형 알고리즘(스케줄링) : 운영체제가 자원에 대한 우선권을 포기한 상태이다. 따라서 어떤 프로세스가 실행 상태에 들어가서 cpu를 사용하면 프로세스가 종료되거나 자발적으로 대기상태에 들어갈 때까지 계속 실행된다. 운영체제가 중간에 빼앗을 수 없다.
비선점형 알고리즘의 종류 => FCFS, SJF, HRN 스케줄링

- 선점형 알고리즘(스케줄링) : 운영체제가 자원을 선점하고 자원을 프로세스에게 빌려주는 형태이다. 따라서 어떤 프로세스가 실행 상태에 있어도 운영체제가 필요하다고 판단되면 그 프로세스의 작업을 강제로 중단시키고 자원을 다시 가져갈 수 있다. 하나의 프로세스가 cpu를 독점할 수 없고 운영체제가 관리하기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다.
선점형 알고리즘의 종류 => 라운드로빈, SRT, 다단계 큐, 다단계 피드백 큐 스케줄링

--- 비선점형 스케줄링 세 가지 ---

1) FCFS 스케줄링 : First Come First Served, 선입선출
준비큐에 도착한 순서대로, 즉 준비 큐에 먼저 도착한 프로세스가 먼저 실행됨.
비선점형 방식, ∴ 한 번 실행된 프로세스가 종료되어야 그 다음 프로세스가 실행될 수 있다.
단일 큐이기 때문에 모든 프로세스가 우선순위 동일.
- 단점?

• 우선순위가 먼저인 (대표적으로 커널 프로세스) 프로세스를 실행하는 게 중요한데도 중요하지 않은 프로세스 (예를 들어 프린터 제어 프로세스) 가 먼저 실행될 수 있음.
• "콘보이 효과" : 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려야 해서 시스템의 효율성이 떨어짐. 이 효과는 비선점형 방식에서만 나타난다. (종료되기까지 운영체제가 강제로 어떻게 할 수 없으니까)
• 만약 현재 작업 중인 프로세스가 입출력을 요청하는 경우, 입출력이 끝날 때까지 기다려야 하므로 CPU가 쉬는 시간이 많아진다. 중간에 강제로 종료시킬 수 없기 때문.

2) SJF 스케줄링 : Shortest Job First, 최단 작업 우선 스케줄링
준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU 할당.
비선점형 방식. 임에도 가장 짧은 작업부터 우선 실행되므로 최대한 짧은 시간만 대기할 수 있다. (낭비되는 시간을 줄임)
- 장점?

• 콘보이 효과 완화하여 시스템의 효율성을 높였다.

- 단점?

• 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다. 예를 들어 내가 현재 사용하고 있는 인터넷을 언제까지 사용할지 운영체제는 예측할 수 없기 때문에, 프로세스의 실행 시간을 정확히 알기 어렵다.
• 공평성의 문제 : 작업시간이 길다는 이유만으로 계속 뒤로 밀리는 건 공평성이 떨어진다. 들어가기 직전의 순서까지 오더라도 그 때 만약 효율이 좋은, 그러니까 실행시간이 짧은 프로세스가 나타나면 다시 뒤로 밀려버리고, 이게 반복되면 계속 뒤로 밀린다. 작업시간이 긴 프로세스가 계속 순서가 뒤로 밀리는 이 현상을 "아사(starvation) 현상" 이라고 한다.

아사 현상을 완화하는 방법으로 "에이징" 방식이 있다. 프로세스가 양보할 수 있는 상한선을 정하는 방식으로, 프로세스가 한 번 뒤로 밀릴 때마다 우선순위가 한 단계씩 올라가게 규정하는 것이다. 그러면 언젠가는 먼저 실행에 들어갈 수 있게 된다...

3) HRN 스케줄링 : Highest Response Rate Next, 최고 응답률 우선 스케줄링
서비스를 받기 위해 기다린 시간, CPU 사용시간을 고려하여 우선순위를 결정하는 스케줄링. 오래 기다렸으면 먼저 할당 받도록 대기시간까지 '함께' 고려.
SJF 에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어짐.
비선점형 알고리즘.
- SJF 에서 프로세스가 대기한 시간까지 함께 고려하여 아사 현상을 완화했지만, 여전히 공평성 위배, SJF 와 크게 바뀌지 않고 사실상 큰 개선효과가 없어 많이 쓰이지 않는다.

--- 여기서부턴 선점형 ---

4) 라운드 로빈 스케줄링
한 프로세스가 할당받은 '타임 슬라이스' 동안만 실행할 수 있고 그 안에 작업을 완료하지 못하면 운영체제에 의해 강제로 준비 큐의 맨 뒤로 가서 다시 자기 차례를 기다린다.
선점형 알고리즘. 의 가장 대표적이고 단순한 스케줄링 방식.
여기선 "타임슬라이스"를 적절히 설정하는 것이 중요한데, 너무 크면 FCFS와 다를 게 없어지고 (타임슬라이스 안에 작업이 다 완료되기 쉬우니까) , 너무 작으면 문맥교환이 너무 자주 일어나서 문맥교환하는 데 걸리는 시간이 많이 낭비된다.

* 문맥 교환 : 한 프로세스의 타임슬라이스가 다 하고 다음 프로세스로 실행이 옮겨질 때 일어나는 과정

5) SRT 우선 스케줄링 : Shortest Remaining Time

SJF 알고리즘을 선점형으로 변형한 방식.기본적으로 라운드로빈 스케줄링을 사용하면서, CPU를 할당받을 (실행상태로 옮겨질) 프로세스를 선택하는 그 때 그 때 남아 있는 작업 시간이 가장 적은 프로세스를 골라내어 먼저 실행 시킨다.

6) 다단계 큐 스케줄링

우선순위에 따라 준비 큐가 여러개 사용된다. 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다.여기서 우선순위는 고정형 우선순위.상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

'먼저 전 부실행 후'(X) '먼저 전부 실행 후'(O)

- 단점?

• 우선순위가 낮은 프로세스들은 CPU의 할당을 계속 못 받게 된다.

이를 해결한 게 다음 나오는 스케줄링이다.

7) 다단계 피드백 큐 스케줄링
프로세스가 CPU 할당받아 실행될 때마다 우선순위를 한 단계씩 낮추는 방식.
우선순위가 처음부터 낮았던 프로세스가 계속 뒤에서 실행이 연기되는 문제를 완화.
단, 우선순위가 낮아져도 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않음!

* 우선순위가 낮아질수록 CPU얻을 확률이 낮아지기 때문에 우선순위가 낮은 프로세스들은 한번 CPU를 할당받을 때 많이 작업하라고 타임슬라이스를 크게 한다.
마지막 큐에 있는, 우선순위가 가장 낮은 프로세스는 무한대의 타임슬라이스를 얻는다. 즉, 프로세스 작업이 완료될 때까지 시간을 계속 쓸 수 있는 것이다. 즉, 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 방식으로 동작한다.


+) 우선순위 스케줄링
프로세스의 중요도에 따른 우선순위를 반영한 스케줄링 알고리즘. 비선점형, 선점형 모두 가능.
* 비선점형 방식에서 우선순위 스케줄링 :
SJF 스케줄링 ( 작업시간이 짧은 프로세스가 높은 우선순위 )
HRN 스케줄링 ( 작업시간이 짧거나 대기시간이 긴 프로세스가 높은 우선순위 )
* 선점형 방식에서 우선순위 스케줄링 :
SRT 스케줄링 ( 남은 시간이 짧은 프로세스가 높은 우선순위 )