스케쥴러
한정적인 메모리를 여러 프로세스가 효율적으로 사용할 수 있도록 다음 실행 시간에 실행할 수 있는 프로세스 중에 하나를선택하는 역할- 즉, 자원을 할당하는 작업
그러면 스케쥴링은 왜 하는가 ?
- 공정한 스케쥴
- 처리량의 극대화, 응답시간 최소화(Maximize CPU use)
- 균형있는 자원 사용, 실행의 무제한 연기
- 반환시간 예측가능
두가지
I/O bound process
CPU bound process
프로세스 스케쥴링 Queue 세가지
- Job Queue: 현재 시스템 내에 있는 모든 프로세스의 집합
- Ready Queue: 현재 메인 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
- Device Queue: Device I/O 작업을 대기하고 있는 프로세스의 집합
- 과정
- 프로세스가 시스템에 들어오면
Long-Term scheduler (= Job scheduler)
- 스케줄링이 발생하는 시간이 비교적 오래걸림
- 보조기억장치(하드디스크)에 존재하는 프로세스 중 어떤 프로세스를 주 메모리(ready Queue)로 load 할지 결정해주는 역할
- 즉 Secondary storage에 저장되어 있는 프로세스가 사용자에 의해 메모리에 적재되고 ready 상태로 되는 것이다.
- 프로세스의 상태 (new -> ready(in memory))
- 메모리와 디스크 사이에 스케쥴링을 담당
- 최근들어서 가상메모리 발달로 사용이 줄음
Short-Term scheduler (= CPU scheduler)
- ready Queue에서 CPU로 빼내옴 (어떤 프로세스를 running state로 둘지를 결정)
- CPU와 메모리 사이의 스케쥴링을 담당
- Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정.
- 프로세스에 CPU를 할당(scheduler dispatch)
- 프로세스의 상태 (ready -> running -> waiting -> ready)
- 매우 빠른시간내에 이루어짐 ⇒ CPU maximize
- 현대에 여러 프로그램을 동시에 사용하는 것 처럼 느끼게 하는 것(CPU scheduler가 빠르기 때문)
✅ CPU scheduling 척도
- CPU 이용률(Utilization) : CPU를 이용한 수치의 백분율
- Throughput(처리율) : 단위 시간당 완료된 프로세스의 수
- Turnaround time(반환 시간) : 프로세스가 Ready Queue에 진입한 순간부터 완료되기까지 걸린 시간
반환 시간 =
Waiting Time+BurstTime(CPU에 할당된 시간)+I/O Time
- Response Time(응답 시간):
: 작업 요청 후 응답이 오는데 걸리는 시간
- Waiting Time(대기 시간): 프로세스가 CPU를 점유하기 위해 대기한 총 시간
Ready Queue에서 있었던 총시간
선점형과 비선점형 스케쥴링
선점형 스케쥴링
-
개념
- 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제(OS)가 프로세스로 부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
-
장점
- 공정성
- 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있다.
- 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합
- 공정성
-
단점
Context Switching에 의한 오버헤드 크다.오버헤드(overhead) :어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 * 메모리등을 말함
- 스케줄러 호출 빈도 높다.
-
선점 프로세스 스케줄링
- RR 스케줄링(Round Robin Scheduling)
- SRTF 스케줄링(Shortest Remaining-Time First Scheduling)
- 다단계 큐 스케줄링(Multilevel Queue Scheduling)
- 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)
- RM 스케줄링(Rate Monotonic Scheduling)
- EDF 스케줄링(Earliest Deadline First Scheduling)
비선점형 스케쥴링
- 개념
- 하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수 없다.
- 장점
- 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있으며 선점 방식보다 스케줄러 호출 빈도가 낮고
Context Switching에 의한 오버헤드가 적다. - 일괄 처리 시스템에 적합
- 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있으며 선점 방식보다 스케줄러 호출 빈도가 낮고
- 단점
Starvation(기아 현상)- CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점
- 비선점 프로세스 스케줄링
- FCFS 스케줄링(First Come First Served Scheduling)
- SJF 스케줄링(Shortest Job First Scheduling)
- HRRN 스케줄링(Highest Response Ratio Next Scheduling)
✅ CPU scheduling 알고리즘
🔑 **CPU Burst Time** : 프로세스가 CPU를 사용하여 연산을 수행하는 시간FCFS(First Come First Served) / SJF(Shortest-Job-First) / SRTF(Shortest-remaining-time-first) / (Priority Scheduling) / (RR) Round Robin / 다단계 큐 스케줄링(Multilevel Queue Scheduling)/ 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)/ RM 스케줄링(Rate Monotonic Scheduling) / EDF 스케줄링(Earliest Deadline First Scheduling)
💡CPU scheduling:FCFS(First Come First Served)
: 처음 들어온 놈들부터 먼저 처리하자
- 단점
- 꼭 좋은 성능을 내는 것은 아님
- Convey effect (호위 효과) : 뒤에 있는 애들은 끊임 없이 기다림
💡CPU scheduling:SJF(Shortest-Job-First) → Non-Preemptive (비선점형)
:Convey effect 피하려면 제일 수행시간이 짧은 자식부터 처리하자
- 장점
- SJF 스케줄링은 평균대기 시간을 줄일 수 있다.
- 단점
- CPU brust time 예측하기 어렵다. ⇒ 그래서 거의 SJF못씀
starvation발생
💡CPU scheduling:SRTF(Shortest-remaining-time-first) → Preemptive (선점형)
SJF
:SJF랑 비슷하지만, 근데 이건 그때그때마다 최신한다.(Preemptive)
- 선점형 SJF의 경우 실행 중이던 프로세스보다 도착한 프로세스의 남은 시간이 짧으면 해당 프로세스로 전환된다.
- 장점
- SJF 스케줄링은 평균대기 시간을 줄일 수 있다.
- 단점
- SJF 랑 비슷하게 CPU brust time 예측하기 어렵다. ⇒ 그래서 거의 SRTF못씀
- 이론상 좋다. 하지만 구현하기 어려움
starvation발생 가능- Dispatch Latency 많다.
- 즉, context switching이 많음
- → 시간이 같으면
Context switching안일어나는게 좋음
💡CPU scheduling:(Priority Scheduling)
:운영체제가 어떤걸 우선순위로 두는지에 대한 스케쥴링 → 우선순위 여러개일 수 있음
- SJF 중 Process의 burst time은 길지만 지금 바로 수행해야 하는 경우
- 장점
- 프로세스의 중요성을 정확하게 정의 가능
- 실시간 시스템에 사용 가능
- 단점
Starvation(기아) 발생 : 우선순위가 낮은 프로세스는 무한정 연기가 된다.- 해결책:
Aging시간이 지날수록 점차 우선순위를 올려주면 된다.
- 해결책:
💡CPU scheduling:RR(Round Robin) → Preemptive (선점형)
: 각각의 프로세스에 동일한 CPU 할당시간 부여
→ 컴퓨팅 자원을 사용할 수 있는 기회를 프로그램 프로세스들에게 공정하게 부여하기 위한 방법
- 할당시간내에 처리 못할 경우 다음 프로세스로 넘어감
- 라운드 로빈은 스케쥴링 알고리즘으로 많이 사용
- 장점
- 응답시간을 빠르게 할 수 있다.
- 균형된 처리율 : 타임슬라이스가 크면 FCFS에 가까움, 적으면 SJF/SRTF에 가까움
- 라운드로빈(Round Robin) 스케줄링의 타임슬라이스 크기가 작아질수록, 해당 알고리즘의 특성이 SJF(Shortest Job First) 또는 SRTF(Shortest Remaining Time First)와 유사해질 수 있습니다. 라운드로빈은 각 프로세스에 동일한 크기의 타임슬라이스를 할당하고 순환적으로 실행하는 방식입니다. 만약 타임슬라이스가 크다면, 각 프로세스는 상대적으로 오래 실행될 수 있으며, 이는 FCFS(First-Come, First-Served)와 유사한 효과를 가져올 수 있습니다. 즉, 먼저 도착한 프로세스가 먼저 실행되고 완료되어 처리율이 좋아질 수 있습니다. 하지만 타임슬라이스가 작아지면, 각 프로세스는 더 작은 시간 동안 실행될 것입니다. 이 경우에는 실행 시간이 짧은 작업이 먼저 실행되는 SJF 또는 SRTF와 유사한 효과를 가져올 수 있습니다. 타임슬라이스가 작으면 짧은 작업들이 상대적으로 빠르게 실행되고 완료되므로, 처리율 측면에서 SJF 또는 SRTF와 유사한 특성을 나타낼 수 있습니다. 따라서 라운드로빈의 타임슬라이스 크기가 작아질수록 FCFS에 비해 SJF 또는 SRTF에 가까워지는 경향이 있습니다. 그러나 라운드로빈은 여전히 각 프로세스에 일정한 실행 기회를 부여하고, 우선순위를 고려하지 않는 특성을 가지고 있기 때문에 완전히 SJF 또는 SRTF와 동일하게는 되지 않습니다.
- 라운드로빈(Round Robin) 스케줄링의 타임슬라이스 크기가 작아질수록, 해당 알고리즘의 특성이 SJF(Shortest Job First) 또는 SRTF(Shortest Remaining Time First)와 유사해질 수 있습니다. 라운드로빈은 각 프로세스에 동일한 크기의 타임슬라이스를 할당하고 순환적으로 실행하는 방식입니다. 만약 타임슬라이스가 크다면, 각 프로세스는 상대적으로 오래 실행될 수 있으며, 이는 FCFS(First-Come, First-Served)와 유사한 효과를 가져올 수 있습니다. 즉, 먼저 도착한 프로세스가 먼저 실행되고 완료되어 처리율이 좋아질 수 있습니다. 하지만 타임슬라이스가 작아지면, 각 프로세스는 더 작은 시간 동안 실행될 것입니다. 이 경우에는 실행 시간이 짧은 작업이 먼저 실행되는 SJF 또는 SRTF와 유사한 효과를 가져올 수 있습니다. 타임슬라이스가 작으면 짧은 작업들이 상대적으로 빠르게 실행되고 완료되므로, 처리율 측면에서 SJF 또는 SRTF와 유사한 특성을 나타낼 수 있습니다. 따라서 라운드로빈의 타임슬라이스 크기가 작아질수록 FCFS에 비해 SJF 또는 SRTF에 가까워지는 경향이 있습니다. 그러나 라운드로빈은 여전히 각 프로세스에 일정한 실행 기회를 부여하고, 우선순위를 고려하지 않는 특성을 가지고 있기 때문에 완전히 SJF 또는 SRTF와 동일하게는 되지 않습니다.
- 단점
- 진짜 많은 Dispatch Latency
- RR을 쓰는 이유: Dispatch Latency가 단점이지만 별로 안중요할 만큼 거의 작다.
starvation(기아) 현상이 발생 x
- 진짜 많은 Dispatch Latency
💡CPU scheduling:다단계 큐 스케줄링(Multilevel Queue Scheduling)
→Preemptive (선점형) Non-Preemptive (비선점형)
- 준비 큐가 여러 개의 큐들로 나뉜다.
- 각 큐는 각자의 스케줄링 알고리즘을 가지고 있다. (큐마다 다른 스케줄링 알고리즘 사용)
- 각 큐 사이에서 프로세스들이 이동할 수 없다.
- 일반적으로 Foreground 프로세스들은 Round Robin 방식을 사용하고, Background 프로세스는 FCFS를 사용한다.
- 기아(Starvation) 문제가 발생할 수 있다.
- 보통 CPU 시간의 80%는 Foreground의 RR, 20%는 Background의 FCFS에 할당된다.
- 장점
- 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리함
- 단점
Starvation(기아) 발생 : 우선순위가 낮은 프로세스는 무한정 연기가 된다.- 해결책:
Aging시간이 지날수록 점차 우선순위를 올려주면 된다.
- 해결책:
💡CPU scheduling:Multilevel Feedback Queue(MFQ) → Preemptive (선점형)
: Multilevel Queue와 비슷하지만, MFQ는 각 큐 간에 프로세스들이 이동할 수 있다.
- 입구가 한개가 아니다. 설계자가 설정하는 입구를 여러개 설정할 수 있음
- 단점
Starvation(기아) 발생 : 우선순위가 낮은 프로세스는 무한정 연기가 된다.- 해결책:
Aging시간이 지날수록 점차 우선순위를 올려주면 된다.
- 해결책:
Real-time scheduling
⏰ Real-time scheduling:RM 스케줄링(Rate Monotonic Scheduling)
→ Preemptive (선점형) 정적 우선순위 스케줄링(Static-priority scheduling)
:주기를 기반으로 우선순위를 할당 (주기가 짧을수록 더 높은 우선순위를 가짐)
- 우선순위 변화하지 않고 고정 (정적 우선순위 스케줄링)
- 들어온 순간마다 Priority를 판단하는 것이 아니라 처음부터 rate 를 사용해서 priority를 정해주고 그 prioriy 그대로 스케줄링 해주는것
CPU 이용률 = t/p (수행시간 / 주기)
⏰ Real-time scheduling:EDF 스케줄링(Earliest Deadline First Scheduling)
→ Preemptive (선점형) 동적 우선순위 스케줄링(Dynamic-priority scheduling)
: Deadline이 다가왔을 때 가장 급한 놈 먼저 스케줄링하는기법
- task들이 들어올때마다 deadline을 비교해보고 Prority 정함
- 장점
- 마감 시간 보장
- EDF 스케줄링은 각 작업의 마감 시간을 기준으로 우선순위를 결정합니다. 이로 인해 작업의 마감 시간을 보장할 수 있습니다. 따라서 실시간 시스템에서 마감 시간을 엄격하게 지켜야 할 경우에 유용합니다.
- 최적성
- EDF 스케줄링은 모든 작업이 마감 시간을 지킬 수 있는 경우에는 최적의 스케줄링을 제공합니다. 즉, 다른 선점형 스케줄링 알고리즘보다 더 작업을 효율적으로 스케줄링할 수 있습니다.
- 유연성
- EDF 스케줄링은 작업의 우선순위를 동적으로 조정할 수 있습니다. 작업의 마감 시간이 변경되면 우선순위도 변경될 수 있습니다. 이러한 유연성은 실시간 시스템에서 작업의 중요도가 변할 수 있는 경우에 유용합니다.
- 리소스 활용도
- EDF 스케줄링은 시스템 리소스를 최대한 활용할 수 있습니다. 작업의 마감 시간에 가까워질수록 우선순위가 높아지기 때문에, 작업이 빠르게 완료될 수 있도록 리소스가 할당됩니다.
- 마감 시간 보장
- 단점
- 과부하 시,
도미노 현상(Domino effect)이 발생할 수 있다.- 도미노 현상 : 주기의 길이 차이가 작은 경우 연속해서 deadline missing이 발생하는 것
- 과부하 시,
RM 스케줄링 vs. EDF 스케줄링
1. RM 스케줄링
- 구현이 상대적으로 단순하다.
- 우선순위가 고정되기 때문에, 우선순위가 높은 태스크의 예측성(Predictability)이 좋다.
- CPU 이용률(Utilization)이 높지 않다.
- 작업의 주기와 실행 시간의 관계: RM 스케줄링에서 작업의 주기가 짧을수록 높은 우선순위를 가지게 됩니다. 따라서 작업의 주기가 긴 경우, 해당 작업은 상대적으로 낮은 우선순위를 가집니다. 작업의 주기가 길면 스케줄링 가능성이 감소하므로 이용률이 낮아질 수 있습니다.
- 작업의 실행 시간과 주기의 불균형: 작업들 간에 실행 시간과 주기의 불균형이 있을 경우, RM 스케줄링에서 이용률이 낮아질 수 있습니다. 예를 들어, 실행 시간이 긴 작업이 주기가 짧은 작업보다 우선순위를 갖는 경우, 해당 작업의 실행 시간이 상대적으로 길어져 이용률이 낮아집니다.
- 리소스 제약: 시스템에 제한된 리소스가 있는 경우, 작업들을 동시에 실행하는 데 제약이 생길 수 있습니다. 리소스가 부족하면 작업들이 동시에 실행될 수 없으며, 따라서 이용률이 낮아집니다.
- 작업의 중복 실행: RM 스케줄링에서는 주기성을 가진 작업들에 대해 스케줄링을 수행합니다. 따라서 동일한 작업이 여러 번 실행될 수 있습니다. 작업들이 중복 실행되면 이용률이 낮아지게 됩니다.
2. EDF 스케줄링
- CPU 이용률이 이론적으로는 100%가 가능하여 최적의 스케줄링이다.
- 과부하 시에 도미노 현상 문제가 발생한다.
Mid-Term scheduler (= CPU scheduler)
시분할 시스템과 같은 일부 운영체제들은 medium-term scheduler를 도입했다.
medium-term scheduler의 핵심 아이디어는 메모리에서 프로세스들을 제거하여, 즉 CPU를 위한 경쟁에서 제거하여, 다중 프로그래밍의 정도를 완화하는 것이다.
차후에 다시 프로세스를 메모리로 불러와서 중단되었던 지점에서부터 실행을 재개한다. 이러한 기법을 swapping이라고 한다. swapping은 프로세스 혼합 상태를 개선하기 위하여 혹은 메모리가 가용 메모리를 초과하여 메모리를 비우기 위해 필요하다.
- 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping)
- 프로세스에게서 memory를 deallocate
- degree of Multiprogramming 제어
- 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러
- 프로세스의 상태 (ready -> suspended)
======================================================================
커널 수준 쓰레드 vs 사용자 수준 쓰레드
커널 수준 Thread
장점: 커널에서 직접 제공하기 때문에 안정성과 다양한 기능성 제공
단점: 유저 모드에서 커널 모드로의 전환이 빈번하기 때문에 느림
사용지 수준 Thread
장점: 유저 모드에서 커널 모드로의 전환이 필요없기 때문에 빠름
단점: 프로세스 단위 블록킹 발생
Thread Scheduling : One- to-many
- 하나의 Kernel Thread가 여러개의 Thread를 관리함
- 장점
- 경량화된 PC에 유리
- 나름 합리적인 구조
- 모든 스레드에게 우선순위가 있음
- 커널 개입 없이 user끼리 스위칭이 발생하기 때문에 one-to-one 모델보다 빠르다
- 단점
- 하지만, starvation(기아)가 발생 할 수 있음
- Mapping을 너무 많이함 (context switching 처럼)
race-condition(경쟁 상태) 발생 가능
✅
Race Condition
: race-condition이란 두 개 이상의 프로세스가 공통 자원을 병행적(concurrently)으로 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 말한다. Race의 뜻 그대로, 간단히 말하면 경쟁하는 상태, 즉 두 개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황을 말한다.
경쟁 프로세스는 세 가지 제어 문제에 직면한다. Mutual exclusion, deadlock, starvation
[Multual exclusion(상호 배제)]
- 하나의 프로세스만 임계구역을 사용할 수 있도록 다른 프로세스의 접근을 차단하는 것이다.
- 상호배제를 위한 4가지의 요구조건이 충족되어야 한다.
- 두 개 이상의 프로세스들이 동시에 임계구역에 있으면 안 됨
- 어떤 프로세스도 임계구역에 진입하는 것이 무한정 연기되면 안 됨
- 임계구역 안에 있는 프로세스가 다른 프로세스의 임계구역 진입을 막을 수 있어야 함
- 프로세스들의 상대적인 속도(각 프로세스들의 처리 속도, 접근 방법, 상태)에 대해 어떠한 가정을 하면 안 됨
[Dead Lock(교착 상태)]
프로세스가 각자 프로그램을 실행하기 위해 두 자원 모두에 엑세스 해야 한다고 가정할 때 프로세스는 두 자원 모두를 필요로 하므로 필요한 두 리소스를 사용하여 프로그램을 수행할 때까지 이미 소유한 리소스를 해제하지 않는다. 이러한 상황에서 두 프로세스는 교착 상태에 빠지게 되는 문제
다음 네 가지 조건이 모두 성립할 때 교착상태 발생 가능성이 있다.
- 상호배제(Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.
- 점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
- 비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
- 순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
[Starvation(기아 상태)]
특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당 받지 못하는 상태를 말한다.
Thread Scheduling : One- to-one
: 한 개의 Kernel Thread가 한 개의 Thread를 관리한다.
- 장점
- 고성능 PC에 유리
- one-to-many보다 빠른 처리량
- 멀티코어를 잘 활용함
- 한 스레드가 블락이 되어도 다른 스레드 잘 동작함
- 단점
- kernel thread를 생성하는 overhead가 큼 (유저쓰레드 만큼 생성해야해서)
- 기타 특징
- 스레드 관리를 OS에 위임
- 스케줄링 또한 커널이 수행
- 자바 1.2 이후부터 사용 중인 방식
Thread Scheduling : many- to-many
: 여러 개의 Kernel Thread가 여러 개의 Thread를 관리한다.
- 장점
- one-to-many보다 빠른 처리량
- kenerl thread를 생성하는 오버헤드 줄였음
- 커널 개입 없이 유저 스레드끼리의 스위칭이 발생하기 때문에 one-to-one 모델보다 빠르다.
race condition발생 가능성 적음
- 단점
- 결국 실제로 동작하는 건 커널 스레드 하나 이기 때문에 멀티 코어를 활용 못함
- 한 스레드가 블락이 되면 모든 스레드 블락 됨
- 기타 특징
- Block 방지를 위해 non Block I/O 방식을 진행한다
Thread Scheduling : hybrid
- 앞에 장단점 합쳐서 보안
- 그래도 성능 좋으면 one-to-one이 최고임
Thread 동작 누가 정해 ??
- 어떤 프로세스 동작시킬지 누가정함 ?
- 레디큐에서 Short- term scheduler(
CPU 스케쥴러)
- 레디큐에서 Short- term scheduler(
- 어떤 쓰레드 동작시킬지 누가정함 ?
LWP(Lightweight Process)
Reference & Additional Resources
https://velog.io/@ragnarok_code/OS-스케쥴러-Scheduler란
https://velog.io/@hyun0310woo/6.-운영체제-스케줄링-알고리즘-선점형과-비선점형
https://eunajung01.tistory.com/67
https://code-lab1.tistory.com/45
https://velog.io/@narcoker/운영체제-스케줄러와-운영체제의-성능-지표
