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

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

여러 프로세스가 있고, 이 프로세스들이 자원(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는 매번 명령을 수행하기 전에 인터럽트라인이 세팅되어있는지를 검사합니다.

---