[OS] 스터디 3주차 : CPU 스케줄링

기아 상태가 무엇인가요?

: 스레드가 스케줄링 과정에서 선택되지 못한 채 오랫동안 준비 리스트에 있는 상황

 

우선순위를 기반으로 하는 시스템에선 높은 우선순위의 스레드가 계속 준비 리스트에 들어오면서 발생하며

실행 시간이 짧은 스레드를 우선 실행시키는 알고리즘이 사용되는 경우엔 계속 더 짧은 스레드가 준비리스트에 들어오면서 발생한다.  

기아 상태를 어떻게 해결할 수 있나요?

: 에이징(aging) 기법으로 해결할 수 있습니다. 에이징이란 스레드가 준비 리스트에 머무르는 시간에 비례하여 우선순위를 높여주는 기법입니다.

 

CPU 스케줄링에 대해 설명해주세요.

: 준비(Ready) 상태에 있는 스레드들 중 하나를 선택하여 CPU를 할당하는 과정입니다.

 

CPU 스케줄링의 기본 목표는 CPU 활용률 (CPU Utilization) 향상입니다. 사용자의 입장에서는 응답 시간 최소화가 스케줄링의 목표가 되기도 합니다.

 

오늘날 운영체제에서 실행 단위는 스레드이므로 CPU 스케줄링은 스레드를 대상으로 합니다.

다중 프로그래밍 + 시분할이기 때문에, 스레드간 우선순위에 따라 스케줄링될 때도 있고 타임 슬라이스에 따라 스케줄링될 때도 있습니다.

 

CPU 스케줄링이 실행되는 상황

 

1. 스레드가 I/O를 요청하는 시스템 호출을 실행하여 블록 상태가 되거나 자원을 기다리는 상태가 될 때 (CPU 유휴 시간 최소화)
2. 스레드가 yield 시스템 호출을 통해 자발적으로 CPU를 반환하는 경우, 현재 스레드를 준비 상태로 만들고 CPU 스케줄링 시행
3. 스레드에게 할당된 타임 슬라이스가 소진되어 타이머 인터럽트가 발생할 때 (시분할. 균등한 CPU 분배 목적)
4. 더 높은 우선순위의 스레드가 요청한 I/O 작업이 완료되어 I/O 인터럽트가 발생했을 때 (우선순위 지키려는 목적)

 

선점 스케줄링과 비선점 스케줄링의 차이가 무엇인가요?

 

비선점 스케줄링 : 스레드가 일단 실행을 시작하면, 완료되거나 CPU를 더 이상 사용할 수 없는 상황이 될 때까지 스레드를 강제로 중단시키지 않음.

 

다음의 상황이 되어야만 스케줄링 시행

• CPU를 더 이상 사용할 수 없게 된 경우 : I/O로 인한 블록 상태, sleep()
• 자발적 CPU 양보 : yield() 시스템 호출
• 스레드 종료

 

선점 스케줄링 : 현재 실행중인 스레드를 강제로 중단시켜 준비 리스트로 이동시키는 스케줄링 방식.

 

다음의 상황들에서 강제로 스케줄링함

• 타임 슬라이스가 소진되었을 때, 타이머 인터럽트 발생
• 인터럽트나 시스템 호출 종료 시점에서 더 높은 우선순위의 스레드가 대기 상태에 있을 때

 

현재 대부분의 운영체제는 선점 스케줄링을 이용함.

 

❗비선점 스케줄링은 다중 프로그래밍, 선점 스케줄링은 시분할 프로그래밍과 유사하다

 

스케줄러의 종류는 무엇이 있나요?

• 장기 스케줄러(작업 스케줄러) : 어떤 프로세스를 준비 큐에 넣을지 결정합니다. 즉 생성 상태를 관리합니다.
• 중기 스케줄러 : 메모리에 적재된 프로세스의 수를 관리합니다. 너무 많은 프로세스가 적재되어 시스템 성능이 저하되는 것을 방지하기 위함입니다.
• 단기 스케줄러(CPU 스케줄러) : 메모리 내의 준비 상태에 있는 프로세스들 중 실행할 프로세스를 선택하여 CPU를 할당합니다. 

 

선입선출 스케줄링(FCFS)에 대해 설명해주세요.

: FIFO 자료구조인 큐를 이용하는 알고리즘으로, 큐에 먼저 도착한 스레드를 먼저 스케줄링합니다.

 

먼저 도착한 스레드가 실행을 마칠 때까지 다음 스레드를 실행하지 않으므로 비선점 스케줄링입니다.

기아 상태는 특정 스레드가 무한 루프에 빠지지 않는 한 발생하지 않습니다.

 

단점 : CPU를 길게 점유하는 스레드가 생성되면 그 뒤의 스레드들은 오래 대기하여 시스템 전체가 느려지는 호위효과가 나타납니다. 

장점 : 단순하고 구현이 용이합니다

 

최단 작업 우선 스케줄링(SJF)에 대해 설명해주세요.

: 실행 시간이 가장 짧은 스레드를 먼저 실행시키는 스케줄링 기법입니다.

스레드들의 평균 대기 시간을 최소화하는데 목적이 있습니다.

 

SJF는 준비 큐에서 예상 실행 시간이 가장 짧은 스레드를 우선 선택합니다. 

 

선택된 스레드가 실행을 끝낼 때까지 중단시키지 않는 비선점 스케줄링입니다.

짧은 예상 실행 시간을 가진 스레드가 계속 큐에 도착하면 긴 스레드가 기아 상태에 빠질 수 있습니다.

 

스레드의 실행 시간을 예측할 수 없기 때문에 SJF는 현실에서 사용할 수 없습니다.

 

최소 잔류 시간 우선 스케줄링(SRTF) 방식에 대해 설명해주세요.

: SJF의 선점 스케줄링 버전으로, 남은 실행 시간이 가장 짧은 스레드를 우선 스케줄합니다.

현재 실행중인 스레드의 시간보다 더 짧은 실행 시간을 갖는 스레드가 큐에 도착하면 현재 스레드를 중단시키고 도착한 스레드를 실행시킵니다.

 

선점 스케줄링입니다.

 

SJF와 마찬가지의 이유로, 긴 스레드가 기아 상태에 빠질 수 있습니다.

 

단점 : 스레드의 실행 시간을 예상하기 어렵기 때문에 현실에선 사용되지 않습니다. 

 

 

라운드 로빈 스케줄링에대해 설명해주세요.

: 스레드들에게 공평한 실행 기회를 주기 위해 큐에 대기중인 스레드들을 타임 슬라이스 주기로 돌아가면서 선택하는 스케줄링 기법입니다.

스레드는 실행이 시작된 후에 타임 슬라이스가 지나면 커널에 의해 강제 중단되어 큐 끝에 다시 삽입됩니다.

 

선점 스케줄링입니다.

타임 슬라이스만큼 돌아가면서 스케줄되며 우선순위가 없으므로 기아 상태는 발생하지 않습니다.

 

단점 : 잦은 스케줄링으로 인해 스케줄링과 컨텍스트 스위칭에 소요되는 시간이 크다는 단점이 있습니다. 타임 슬라이스가 작을수록 성능 저하가 심해집니다.

장점 : 공평하고 기아 상태가 없습니다. 구현이 쉽습니다.

 

라운드 로빈 스케줄링은 타임 슬라이스의 크기에 따라 FCFS와 SJF 사이의 균형을 취하는 스케줄링이라고 할 수 있습니다.

타임 슬라이스가 클수록 타임 슬라이스 내에 바로 완료되는 스레드의 비율이 높아져 FCFS에 가까워지며, 타임 슬라이스가 작을수록 거의 모든 스레드들이 여러 번에 걸쳐 실행되므로 처리 시간이 짧은 스레드가 먼저 종료할 가능성이 높아지므로 SJF에 가까워집니다.

 

우선순위 스케줄링에 대해 설명해주세요.

: 철저히 우선순위에 따라 스레드를 실행시키려는 목적의 알고리즘입니다.

 

선점, 비선점 방식 모두 가능합니다. 더 높은 우선순위의 스레드가 생성될 때 현재 실행되는 스레드를 중단시킨다면 선점, 종료될 때까지 실행시킨다면 비선점 방식이 됩니다.

 

지속적으로 높은 우선순위의 스레드가 생성된다면 기아 상태가 발생할 수 있습니다.

그러나 큐 대기 시간에 비례하여 일시적으로 우선순위를 높이는 에이징 기법을 결합하면 기아 문제를 해결할 수 있습니다.

 

일반적으로 우선순위가 높은 스레드이루록 대기시간이나 응답 시간이 짧기 때문에, 우선순위 스케줄링은 스레드마다 고정 우선순위를 갖는 실시간 시스템에서 주로 사용됩니다.

 

멀티 레벨 큐 스케줄링에 대해 설명해주세요.

: 스레드들을 n개의 우선순위 레벨로 구분하여 n개의 레벨 큐로 관리하는 스케줄링 기법입니다. 우선순위가 높은 스레드를 우선 처리할 목적으로 설계되었습니다.

 

선점, 비선점 방식 모두 가능합니다.

우선순위 스케줄링과 마찬가지로 우선순위에 따른 스레드 중단 여부에 따라 방식이 나뉩니다.

 

기아 상태도 우선순위 스케줄링과 마찬가지로 낮은 우선순위에 스레드들에 대해 발생합니다.

 

 

멀티 레벨 피드백 큐 스케줄링에 대해 설명해주세요.

: CPU burst가 짧은 스레드나 I/O 작업이 많은 스레드, 대화식 스레드를 우선 실행시키는 스케줄링 기법입니다.

스레드의 평균 대기시간을 줄여 사용자의 응답시간을 짧게 하고 스레드에 기아 상태가 발생하지 않도록 하려는 목적으로 설계되었습니다.

 

우선순위로 구분된 n개의 큐를 둡니다.

큐마다 타임 슬라이스가 다르게 설정되는데, 낮은 레벨로 내려갈수록 타임 슬라이스가 크게 설정됩니다.

 

스레드들은 우선순위를 갖지 않으며 도착할 때 가장 높은 레벨의 큐에 삽입됩니다.

타임 슬라이스 전에 스레드의 CPU burst가 끝나면 스레드는 동일한 큐에 다시 삽입됩니다. 반대로 CPU burst가 타임 슬라이스를 넘어가면 강제 중단되어 아래 레벨 큐로 이동됩니다.

그러므로 CPU시간을 작게 소모하고 I/O가 빈번한 스레드가 높은 우선순위로 실행되게 됩니다.

 

타임슬라이스에 따라 스레드를 중단시키므로 선점 스케줄링입니다.

 

이론적으로 MLQF는 에이징 기법을 사용하여 낮은 레벨의 큐에서 너무 오랜 시간 대기하면 하나 높은 레벨의 큐로 이동시키기 때문에 기아 상태는 발생하지 않습니다. 

 

 

 

🤔 그래서 오늘날 우리가 사용하는 컴퓨터에서는 어떤 스케줄링 기법이 사용되는거지?

배운 점

• 큐와 같은 자료구조나 정렬 알고리즘이 운영체제 개념들과 연결되는게 재밌다.

참고 자료

• 명품 운영체제 - 황기태
• https://imbf.github.io/computer-science(cs)/2020/10/18/CPU-Scheduling.htmlhttps://gmlwjd9405.github.io/2018/09/14/process-vs-thread.html