[운영체제] 스케줄링 관련 면접 대비 질문 정리

CS 지식/운영체제

[운영체제] 스케줄링 관련 면접 대비 질문 정리

지나가던 개발자 2023. 2. 20. 11:42

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

여러 프로세스가 있고, 이 프로세스들이 자원(CPU 등)을 동시에 요구하는데 자원은 제한되어 있습니다. 그럴 때 제한된 자원들을 어떻게(순서를 할당하는 등) 나눠줄 것인지에 대한 정책을 말합니다.

💡 CPU 스케줄링은 언제 발생합니까?

실행상태에서 대기상태로 전환될 때 (예, 입출력 요청) - Non preemptive(비선점)
실행상태에서 준비상태로 전환될 때 (예, 인터럽트 발생) - preemptive(선점)
대기상태에서 준비상태로 전환될 때(예, 입출력이 종료될 때)
종료될 때(Terminated)

💡 CPU 스케줄링의 목적은 무엇입니까?

1. 공평성

모든 프로세스가 자원을 공평하게 배정받아야 한다. 자원 배정 과정에서 배제되어서는 안 된다.

2. 효율성

시스템은 "유휴 시간(idle)"이 없도록 사용되어야 한다.
유휴 자원을 필요로 하는 프로세스에 "우선권"을 주어야 한다.
시스템 입장에서 유휴 자원은 CPU이다.

3. 안정성

시스템을 강제로 점유하거나, 파괴하려는 프로세스로부터 자원을 보호해야 한다.

4. 반응 시간 보장

적절한 시간 안에 프로세스의 요구에 반응해야 한다.

5. 무한 연기 방지.

특정 프로세스의 작업이 무한하게 연기되어서는 안 된다.

💡 스케줄링은 어떻게 분류합니까?

CPU 스케줄링은 규모에 따라 장기, 중기, 단기 스케줄링으로 구분됩니다.

1) 장기 스케줄링 (Long-term scheduler)

가장 큰 틀에서 이루어지는 CPU 스케줄링입니다. 고수준 스케줄링, 작업 스케줄링이라고도 합니다.
프로세스에 Memory(및 각종 자원)을 주는 문제를 스케줄링 합니다.
전체 시스템의 부하를 고려하여 작업 요청을 받아들일지, 거부할지에 대한 결정을 합니다. 즉 new 상태의 프로세스를 admitted 하는 작업을 장기 스케줄러가 합니다.
즉, 장기스케줄링의 결정에 따라 시스템 내의 프로세스 총 개수(degree of multiprogramming)가 정해집니다.
최근 운영체제에서는 보통 장기 스케줄러가 없습니다. 프로그램을 실행시키면 곧바로 ready 상태에 돌입하죠.

2) 중기 스케줄링 (Medium-term scheduler, Swapper)

장기스케줄링은 프로세스의 활성화 승인을 다룬다면 중기 스케줄링은 이미 활성화가 된 프로세스들에 대한 관리를 합니다.
시스템의 과부하를 막기 위해 활성화된 프로세스들의 중지 여부를 결정하여 활성화된 프로세스 수를 조절합니다.
즉, 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냅니다.(Swap out)
이 역시 degree of multiprogramming을 제어하는 것이죠.
중기 스케줄링에 의해 중지된 프로세스들은 보류 상태(Suspended, Stopped)가 됩니다.

3) 단기 스케줄링 (Short-term scheduler, CPU scheduler)

가장 작은 단위의 스케줄링을 단기 스케줄링이라고 합니다.
어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정합니다.
단기 스케줄러가어떤 기준에 따라 프로세스를 선택(스케줄링 알고리즘)하고 어느 정도 자원을 배분(Time slice와 관련)할지에 따라 시스템에 큰 영향을 끼칩니다.
단기 스케줄링은 스케줄링 중에서도 핵심인 부분이라 뒤에서 다룰 내용은 대부분 단기 스케줄링에 대한 내용입니다.

💡 CPU 스케줄링의 종류를 설명해주세요.

비선점(Non-preemptive) 스케줄링

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이다.
프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용한다.
일괄 처리 방식의 스케줄링(공정하지만 긴급 응답을 요하는 작업에 좋지 않다.)

FCFS(FIFO) : 준비상태 큐에 도착한 순서에 따라 CPU를 할당하는 기법. 공평성은 유지되지만 짧은 작업이 긴 작업을, 중요한 작업이 중요하지 않은 작업을 기다리게 됨.
- 장점 : 평균 응답시간이 길다. (대화식 시스템에 부적합)
- 단점 : 도착 순서에 따라 공평하다.
SJF(Shortest Job First) : 실행시간이 가장 짧은 프로세스에 먼저 CPU를 할당하는 기법. 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘
- 장점 : 평균 응답 시간을 최소화 할 수 있다.
- 단점 : 실행시간이 긴 프로세스는 CPU를 할당받지 못하고 무한히 대기하는 현상 발생(starvation)
HRN(Highest Response ratio) : 실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로 우선순위 계산 결과 값이 높은 것부터 우선순위가 부여된다. 대기 시간이 길수록 계산 결과가 높다. 우선순위 = (대기시간 + 서비스시간 / 서비스시간) 큰 프로세스일수록 우선순위가 낮으므로 평균 응답시간도 단축
기한부(DeadLine) : 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법
우선순위(Priority) : 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법. 정적, 동적 우선순위 방법 존재

선점(Preemptive) 스케줄링

하나의 프로세스가 CPU를 할당받아 실행 하고 있을 때 우선순위가 높은 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법
선점으로 인한 많은 오버헤드가 발생한다.
시분할 시스템에 사용하는 스케줄링이다. (긴급을 요하는 우선순위를 갖는 시분할 처리, 실시간 처리에 유용)
선점을 위해 시간 배당을 위한 인터럽트용 타이머 클럭(Clock)이 필요한다.

SRT(Shortest Remaining Time) : 현재 실행 중인 프로세스의 남은 시간과 대기 큐에 프로세스의 실행시간이 가장 짧은 프로세스에게 CPU를 할당하는 기법 (비선점 기법인 SJF 알고리즘의 선점 형태로 변경한 기법)
- 단점 : 잦은 선점으로 인한 문맥교환의 부담, starvation 의 위험
선점 우선순위 : 준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
RR(Round Robin) : 시분할 시스템을 위해 고안된 방법으로, FCFS 알고리즘을 선점 형태로 변형한 기법. 대기 큐를 사용하여 먼저 대기한 작업이 먼저 CPU를 사용한다.
- 단점 : CPU를 사용할 수 있는 시간(Quantum)동안 CPU를 사용한 후에 다시 대기 큐의 가장되로 배치된다. 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 시간이 작을 경우 문맥교환 및 오버헤드가 자주 발생됨
MLQ(다단계 큐) : 프로세스를 특정 그룹으로 분류할 수 있는 경우 그룹에 따라 각기 다른 준비상태 큐를 사용한다. 작업들을 여러 종류의 그룹으로 분할. 큐들간에 프로세스 이동이 불가능하다. 각 큐는 자신만의 독자적인 스케줄링을 가진다. 상위 우선 순위의 큐가 Empty 이면 하위 우선순위의 큐의 프로세스가 수행된다.
MLFQ(다단계 피드백 큐) : 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법. 새로운 프로세스는 높은 우선순위, 프로세스의 실행이 길어질 수록 점점 낮은 우선순위 큐로 이동. 제일 마지막 단계에서는 RR/FCFS 처리. 우선순위가 높은 단계의 큐일수록 시간 할당량을 작게 설정한다. 기아 상태를 예방하는 Aging 방법. 현대 OS에서 RR방식과 함께 가장 많이 사용되는 스케줄링 기법.
RM(Rate Monotonic, 주기단조) 알고리즘 : 수행 주기가 가장 짧은 프로세스에 가장 높은 우선순위를 부여하는 실시간 스케줄링 알고리즘. 정적 스케줄링방식. 마감 시간과 주기가 일치.
- 장점 : 간단, 사용률이 0.69이하일때 항상 스케줄링 가능
- 단점 : 주기가 긴 태스크들의 우선순위가 낮아서 장시간 대기
EDF(Earliest Deadline First, 최단 마감시간 우선)알고리즘 : 프로세스의 마감시한이 가까울수록 우선순위를 높게 부여하는 선점방식의 동적 스케줄링
- 장점 : 이론적으로 총 이용률이 1이하면 스케줄링 가능
- 단점 : 태스크들의 수행 시간, 마감시간, 주기 등을 정확히 예측하는 것이 현실적으로 어려움.

비선점형 : FCFS, 비선점형 SJF

선점형 : RR, MLQ, MLFQ, 선점형 SJF(SRF), RM(Rate Monotonic), EDF

💡 선점 스케줄링과 비선점 스케줄링의 차이점에 대해 설명해주세요.

선점 : CPU를 할당받아 실행 중인 프로세스로부터 CPU를 선점(빼앗는 것)하여 다른 프로세스를 할당 할 수 있는 방식입니다.

Ex) RR, SRT, MLQ, MFQ

비선점 : CPU를 할당받은 프로세스가 스스로 CPU를 반납할 때까지 CPU를 독점하여 사용 방식입니다.

Ex) FCFS, SJR, HRN

💡 스케줄링 알고리즘의 평가 기준을 설명해주세요.

CPU 사용률(Utilization)

전체 시스템 시간 중에서 CPU가 작업을 처리하는 시간의 비율입니다.

유휴 시간이 적을수록 CPU 사용률이 높습니다.

CPU 사용률을 극대화하려는 많은 노력이 있지만 현재는 90% 정도가 최대 사용률이라고 합니다.

처리량(Throughput)

CPU가 단위 시간당 작업을 마친 프로세스의 수 입니다.

CPU 사용률이 높고 프로세스들에 적정한 시간을 공평하게 제공했다면 처리량이 높습니다.

정확한 계산은 어려운 편이라고 합니다.

응답 시간(Response Time)

대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간입니다.

짧을수록 좋습니다.

대기 시간(Waiting Time)

프로세스가 준비(ready) 큐에서 대기하는 시간들의 총합입니다.

대기시간이 짧을수록 좋습니다.

반환 시간(Turnaround Time) [ 대기 시간 + 실행 시간]

프로세스의 시작부터 끝날 때까지 걸리는 시간입니다.

💡 전면 프로세스, 후면 프로세스에 대해 설명해주세요.

전면 프로세스란 GUI를 사용하는 OS에서 화면 맨 앞에 놓인 프로세스를 말합니다.

사용자와 상호작용이 있는 프로세스입니다.

사용자 측면에서는 입출력이 중요하기에 사용자 측면에서는

대기시간, 응답 시간, 반환 시간을 줄여줄 수 있는 스케줄링을 활용해야 합니다.

후면 프로세스란 사용자와 상호작용이 없는 프로세스입니다.

시스템 측면에서는 시스템의 자원을 최대한 활용할 수 있는 처리량 + CPU 사용률이 높게 해주는

스케줄링을 활용해야 한다.

어떠한 상호작용 없이 순수 로직을 처리하는 프로세스를 의미합니다.

💡 인터럽트에 대해 설명해주세요.

CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치나 예외상황이 발생하여 처리가 필요할 경우에 마이크로프로세서에게 알려 처리할 수 있도록 하는 것을 말합니다.
인터럽트는 크게 하드웨어 인터럽트와 소프트웨어 인터럽트로 나뉩니다.

💡 하드웨어 인터럽트에 대해 설명해주세요.

하드웨어가 발생시키는 인터럽트로, CPU가 아닌 다른 하드웨어 장치가 cpu에 어떤 사실을 알려주거나 cpu 서비스를 요청해야 할 경우 발생시킵니다.

💡 소프트웨어 인터럽트에 대해 설명해주세요.

소프트웨어가 발생시키는 인터럽트입니다. 소프트웨어(사용자 프로그램)가 스스로 인터럽트 라인을 세팅합니다.
종류: 예외 상황, system call

인터럽트를 발생시키기 위해 하드웨어/소프트웨어는 cpu내에 있는 인터럽트 라인을 세팅하여 인터럽트를 발생시킵니다.
cpu는 매번 명령을 수행하기 전에 인터럽트라인이 세팅되어있는지를 검사합니다.