CPU 스케줄링

📌 3주차 : CPU 스케줄링

• 기아상태
• 선점 스케줄링
• 비선점 스케줄링
• FCFS, SJF, SRTF
• 멀티레벨 피드백큐

CPU 스케줄링 알고리즘

• 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업
• 목표: CPU 이용률은 높게. 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답시간은 짧게

CPU and I/O Bursts in Program Execution

CPU-burst Time의 분포

• i/o bound job: 사람과 인터렉션이 많은 작업
• cpu bound job:
• 누구한테 cpu 먼저, 얼마나, 주는게 좋은걸까?
• I/O bound job(interactive job)한테 먼저 cpu 빨리 처리해주는게 좋음

프로세스의 특성과 분류

I/O-bound process

• cpu를 잡고 계산하는 시간보다 i/o에 많은 시간이 필요한 job
• many short cpu bursts

CPU-bound process

• 계산 위주의 job
• few very long CPU bursts

CPU Scheduler & Dispatcher

CPU Scheduler

• ready 상태의 프로세스 중에서 이번에 cpu를 줄 프로세스를 고른다

Dispatcher

• CPU의 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘긴다.
  • 이게 context switching

CPU 스케줄링 필요한 경우

1. Running → Blocked: 시스템 콜 - nonpreemptive(빼앗길 수 있는)
2. Running → Ready: time interrupt - preemptive
3. Blocked → Ready: i/o 완료 후 인터럽트 - preemptive
4. Terminate - nonpreemptive

Scheduling Criteria - 성능 척도

CPU untilization(이용률)

• 전체 시간중 일한 시간

Throughput(처리량)

• 시스템 입장
• 단위 시간당 처리량

Turnaround Time(소요 시간, 반환시간)

• 짧을 수록 좋아

Waiting time(대기 시간)

• 기다린 시간 전체 합

Response time

• 시간입장: 고객 입장

Scheduling Algorithms

비선점형 스케줄링

• 어떤 프로세스가 CPU를 점유하고 있다면 뺏을 수 없는 방식
• 문맥 교환으로 인한 부하가 상대적으로 적지만 프로세스 배치에 따라 효율성 차이가 많이 남

FCFS

• non-preemptive
• 만약에 엄청 긴 친구가 먼저 들어오면 뒤 작업들이 계속 줄 서서 기다림
  • 평균 대기 시간이 길어짐, 반대일 경우에는 짧아짐
  • Convoy effet(호위 효과): short process behind long process, 몇 개 시간이 오래 걸리는 프로세스로 인해 전체 OS가 느려지는 현상ㄴ
• 가장 먼저 요청한 프로세스에 CPU를 할당해주는 선착순 방식

SJF(shorteste-job-first)

• optimal 방법: 가장 이상적
• cpu burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 알고리즘
• 실제로는 프로세스의 cpu 실행 시간을 예측하기 어려움, 또한 긴 시간이 필요한 프로세스는 계속 밀려나서 기아 현상을 일으킬 수 있음
• two schemes
  • non-preemptive
    • 일단 cpu 잡으면 완료할때까지 선점 당하지 않음
     

• preemptive
  • 현재 수행중인 프로세스의 burst time보다 더 짧은 cpu burst time을 가지는 새로운 프로세스가 도착하면 cpu 빼앗김 → 이게 더 이상적이긴 함
  • SRTF(shorted remaining time first)
    • 평균대기시간이 제일 짧아
    • Starvation: 짧은 프로세스한테 먼저 우선적으로 줘서 긴 프로세스는 할당이 되지 않는 경우도 생김

Priorty(우선순위)

• 각각의 프로세스에 우선순위 넘버가 있는 알고리즘
• SJF + aging
  • 오래된 작업의 우선순위를 높여줌

 

선점형 스케줄링

• 현대 운영체제가 사용하는 방식
• 어떤 프로세스가 CPU할당받아

라운드 로빈

• 현대 컴퓨터가 사용하는 우선순위 스케줄링
• 각각의 프로세스에 동일한 할당 시간 부여 → 해당 시간동안만 CPU이용
• 다 처리 못하면 다음 작업으로 넘어감 ⇒ 선점형
• 할당 시간이 너무 크면 FCFS나 다름 없고, 할당시간이 너무 짧으면 process sharing(1/n)

SRF(SRTF)

• 현재 실행되는 프로세스 남은 시간보다 더 빨리 끝낼 수 있는 프로세스가 들어오면 현재 실행 프로세스 중단하고 짧은 프로세스 실행
• 평균 대기 시간 줄일 수 있지만 다음 프로세스의 CPU burst time을 예측하기 어려움

다단계 큐(Multilevel Queue)

• 우선순위에 따른 준비 큐가 여러 개의 큐들로 나뉘고 각각의 큐는 각자의 스케줄링 알고리즘 가짐
• 우선순위 높은 큐부터 처리됨 → 우선순위 낮은 큐는 기아 현상 발생 가능
• 각 큐 사이에서 프로세스들이 이동할 수 없어서 유연성 떨어짐

다단계 피드백 큐 스케줄링

• 프로세스가 큐들 사이를 이동하는 것을 허용
• 에이징과 기아를 예방
• 가장 일반적인 CPU 스케줄링 알고리즘
• 매개변수 값들을 선정하는 특정 방법이 필요하기 때문에 가장 복잡한 알고리즘

 

출처

https://velog.io/@qq7455/CPU-스케줄링-알고리즘-요약정리

CPU 스케줄링 알고리즘 요약정리

 

https://imbf.github.io/computer-science(cs)/2020/10/18/CPU-Scheduling.html

[Operating System - Chapter 5] CPU 스케줄링

http://www.kocw.net/home/search/kemView.do?kemId=1226304

운영체제

 

면접 질문 대비용

SJF에 대해 설명해주세요

 

CPU 실행시간이 가장 짧은 프로세스를 제일 먼저 스케줄링하는 우선순위 작업입니다. SJF는 실행시간이 짧은 걸 먼저 하다보니 가장 이상적인 방법이지만, 실제로는 프로세스의 cpu 실행시간을 예측하기 어려워서 사용이 어렵고, 또한 긴 실행 작업들은 계속 뒤로 밀리기 때문에 기아 현상이 발생할 수 있습니다.

CPU 스케줄링의 목적은 무엇인가요?

1. 공평성: 모든 프로세스는 자원을 공평하게 배정받아야합니다.
2. 효율성: 시스템에 유휴 시간이 없도록 만들어야합니다.
3. 안정성: 시스템을 강제로 점유하거나, 파괴하려는 프로세스로부터 자원을 보호해야합니다.
4. 반응 시간 보장: 적절한 시간내에 프로세스의 요구에 반응해야합니다.
5. 무한 연기 방지: 특정 프로세스의 작업이 무한 연기되지 않도록 합니다.

멀티레벨 큐와 멀티레벨 피드백 큐 알고리즘에 대해 말씀해주세요.

• 멀티레벨 큐: 레디 큐를 여러개 분할해서, 분할된 큐들의 우선순위를 서로 다르게 하는 것을 말함, 한번 배정되면 다른 큐로 이동이 불가능하빈다.
• 멀티레벨 피드백 큐: 한 번 큐에 배정된 프로세스더라도 CPU 실행시간에 따라 큐간 이동을 할 수 있는 것이 특징입니다.

CPU 스케줄링이란 무엇인가요?

여러 프로세스가 있고, 이 프로세스들이 자원을 동시에 요구할 때 자원은 한정되어 있습니다. 따라서 제한된 자원을 어떻게 나눠줄 것인지에 대한 정책을 말합니다.

라운드 로빈 스케줄링이란 무엇인가요?

시분할 시스템을 위해 설계된 선점형 스케줄링방식입니다. 프로세스들 사이에 우선순위를 두지않고 순서대로 일정 시간단위로 CPU를 할당하는 방식입니다.

현대에 들어 많이 적용된 스케줄링이지만, 할당 시간을 너무 크게 잡으면 FCFS와 다름없고, 너무 짧게 잡으면 문맥교환이 너무 많이 일어나기 때문에 오버헤드가 큽니다.

스케줄링 알고리즘의 평가 기준에 대해 아는대로 말씀해주세요.

1. CPU 이용률: CPU가 실제로 일을 하고 있는 시간의 비율 → 유휴 시간이 적을수록 좋음
2. 처리량: 주어진 시간동안 시스템이 완료한 프로세스의 수
3. 대기 시간: 프로세스가 대기 큐에서 기다린 시간의 합 → 짧을 수록 좋습니다.
4. 응답 시간: 프로세스가 요청을 제출한 시점부터 첫번째 응답을 받을 때까지의 시간
5. 반환 시간: 프로세스가 제출된 시점부터 완료될 때까지 걸린 시간

교착 상태와 기아 상태를 비교해서 설명 해주세요

• 교착 상태: 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태
• 기아 상태: 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태

RR 스케줄링 방식에서 CPU 할당 시간이 커질 경우와 작아질 경우 어떤 변화가 생길까요?

• 커질 경우: 충분한 CPU 점유 시간을 가지게 되어 FCFS방식과 같이 됩니다. 짧은 응답 속도의 장점을 잃어버리게 됩니다.
• 작아질 경우: 문맥 교환이 빈번해져 오버헤드가 발생할 수 있습니다.

콘보이 현상이란 무엇인가요? 이 현상이 발생될 수 있는 CPU 스케줄러 알고리즘은 무엇인가요?

콘보이 현상이랑 CPU 점유 시간이 짧은 프로세스가 CPU 점유 시간이 긴 프로세스보다 나중에 도착해 오랜 시간 기다리게 되어 효율성이 떨어지는 현상

이 현상이 발생할 수 있는 알고리즘은 FCFS가 있습니다. 먼저 큐에 들어온 작업부터 실행하기 때문에 긴 작업이 들어오면 콘보이 현상이 발생합니다.

스케줄링에서 발생할 수 있는 기아 현상을 해결할 수 있는 방안은 무엇인가요?

기아 현상을 방지 하기 위해서 에이징 기법을 사용할 수 있습니다. 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계 높여서 자원을 할당받을 수 있도록 하는 기법입니다.

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

• 선점 스케줄링: CPU를 할당받아 실행중인 프로세스로부터 CPU를 강제로 빼앗아 다른 프로세스를 할당할 수 있는 방식, 예로는 RR, SRT, MLQ, MFQ이 있습니다.
• 비선점 스케줄링: CPU를 할당받아 실행중인 프로세스가 스스로 CPU를 반납할 때까지 CPU를 독점하여 사용하는 방식 예로는 FCFS, SJF, HRN이 있습니다.

싱글 코어 cpu에서 사용한 스케줄링 기법을 멀티 코어 cpu에 그대로 사용하면 어떤 문제점이 생길까요 또 해결방법도 같이 제시해주세요

생기는 문제점으로 코어별 부하 불균형이 발생할 수 있습니다. 멀티 코어 환경에서 이를 그대로 적용하면 특정 코어에만 작업이 집중되고, 나머지 코어는 유휴 상태가 될 수 있습니다. 이는 멀티 코어의 장점을 전혀 살리지 못하는 비효율적인 자원 활용을 초래합니다.

해결 방법으로는 작업을 고르게 분산시켜 모든 코어가 균등하게 작업을 처리하도록 하는 로드 밸런싱(Load Balancing) 기법을 도입하면 됩니다.

SJF,SRTF 스케줄링이 사용하지 않는 이유를 설명해주세요

프로세스의 cpu 실행 시간을 예측하기 어려움, 또한 긴 시간이 필요한 프로세스는 계속 밀려나서 기아 현상을 일으킬 수 있어서 사용하기 어렵습니다.

CPU burst와 I/O burst를 설명해주세요

CPU Burst: CPU 코드가 집중적으로 실행되는 상황

I/O Burst : I/O장치에 의해 입출력이 이루어진 상황