1. real time OS와 general purpose OS
기억할 때까지 복습하자 ..
(1) real time OS : 응용 프로그램의 실시간 성능 보장을 목표로 하는 OS
-> 정확하게 프로그램의 시작, 완료 시간을 보장한다. 공정에 주로 쓰인다.
-> (ex) Hardware RTOS, Software RTOS
(2) general purpose OS : 프로세스 실행시간에 민감하지 않고, 일반적 목적으로 사용되는 OS
2. Scheduling
"누가 CPU를 사용할 것인가"
-> 멀티 프로그래밍을 통해 얻은 최대 CPU 활용률
-> CPU burst followed by I/O burst
CPU burst가 주요 문제이다.
I/O burst : I/O를 요청한 다음 기다리는 시간
CPU burst : 프로세스사 CPU 명령을 실행하는 것, CPU를 사용할 때
(burst : 특정 기준에 따라 한 단위로써 취급되는, 연속된 신호나 데이터의 모임)
다음 state 순서도 중에 [Ready] -> [Running] 단계 사이에서 Scheduling이 발생한다.
[사진]
<CPU Scheduler>
[준비 대기열에 있는 프로세스] 중에서 하나를 선택하고, CPU core를 프로세스 중 하나에 할당한다.
-> When [running -> waiting], [running -> ready], [waiting -> ready], [running -> exit] 상태 전환 시 사용
(1) nonpreemptive
중간에 끊김 없이 프로세스를 실행, 한 번 CPU는 계속 CPU 개념
[수행 -> 대기], [수행 -> 종료] 상황에서만 스케줄링이 발생한다.
When 프로세스가 종료되거나, I/O에 대해 자체적으로 차단될 때까지 계속 실행된다.
(2) preemptive
강제로 context switching을 하며 다른 task를 수행시킴
프로세스를 쫓아내고, [우선순위]를 근거로 CPU 자원을 선점한다.
OS kernel의 심판 역할을 함 -!! 프로세스 하나가 CPU를 오랫동안 독점할 수 없음 -!!
context switching이란? 한 상태 정보(CPU register 값)를 PCB에 보관, 다음 상태정보를 복구
<Dispatcher>
context switching의 일부분으로, PCB에 상태 정보를 저장하고 다음 상태 정보를 기다린다.
-> short-term scheduler가 선택한 프로세스에 CPU를 제어한다.
-> context 전환, 유저 모드로 전환, 프로그램 재시작을 위해 유저 프로그램을 적절히 이동
-> Dispatch Latency : 디스패치가 한 프로세스를 중지하고, 다른 프로세스 실행을 시작하는데 걸리는 시간
<Scheduling Criteria>
(1) CPU utilization : CPU의 최대 효율, CPU를 최대한 사용 중으로 유지
(2) Throughput(처리량) : 시간 단위당 실행을 완료하는 프로세스 수
(3) Turnaround time(처리 시간) : 특정 프로세스를 실행하는 데 걸리는 시간
(4) Waiting time(대기 시간) : 준비 대기열에서 프로세스가 대기한 시간
(5) Response time(응답 시간) : [요청이 제출된 시점]부터 [출력이 아닌, 첫 번째 응답] 생성까지 소요 시간
real time OS에서 쓰인다.
-> (1) MAX, (2) MAX, (3) MIN, (4) MIN, (5) MIN일 수록 좋다.
3. Nonpreemtive Scheduling Algorithm
<Definition of working process model>
-> di : context switching overhead, 컨텍스트 스위칭이 걸린 시간과 메모리를 의미
<First-Come-First-Served(FCFS)>
선착순 방식을 사용한다.
FIFO(가장 쉽고 간단한 CPU 스케줄링 알고리즘)와 같이, 먼저 요청하는 프로세스가 먼저 CPU를 할당받음
-> 우선순위 : CPU를 요청하는 순서대로
-> Enqueuer : 간단한 FIFO 데이터 구조로 구성됨
-> 멀티태스킹 OS에서는 잘 사용되지 X, 간단한 OS에서 사용된다.
-> T TRnd(p 0) = 350, T TRnd(p 1) = 475, T TRnd(p 2) = 950, T TRnd(p 3) = 1200, T TRnd(p 4) = 1275
-> T turnaroun= (350 + 475 + 950 + 1200 + 1275) / 5 = 850
-> W = (0 + 350 + 475 + 950 + 1200) / 5 = 595
<Shortest Job Next(SJN), SJF>
SJF(shortest job first)라고도 부른다.
수행시간이 가장 짧다고 예상된 것을 먼저 수행한다.
-> 평균 대기 시간을 최소화하는 방법으로 사용된다.
-> 준비 목록의 모든 작업을 서비스하는 동안, 다른 작업(프로세스)이 도착하지 않는다고 가정한다.
-> 대화형 시스템에서는 사용할 수 없다.
-> T TRnd(p 0) = 800, T TRnd(p 1) = 200, T TRnd(p 2) = 1275, T TRnd(p 3) = 450, T TRnd(p 4) = 75
-> T turnaroun= (800 + 200 + 1275 + 450 + 75) / 5 = 560
-> W = (0 + 75 + 200 + 450 + 800) / 5 = 305
<Priority Scheduling>
프로세스는 [외부적으로 할당된 우선 순위]에 따라 CPU에 할당된다.
-> Priority : 스케줄러는 항상 높은 우선순위의 프로세스를 선택한다. 낮은 우선순위가 starvation될 수 있다.
프로세스가 [기간 or 실행기록]에 따라 우선 순위를 변경하도록 허용한다.
-> 외부 우선 순위 : task의 중요도
-> starvation으로 인한 낮은 우선 순위 프로세스 : 우선 순위가 재계산될 경우 보상 가능
-> T TRnd(p 0) = 1275, T TRnd(p 1) = 375, T TRnd(p 2) = 850, T TRnd(p 3) = 250, T TRnd(p 4) = 925
-> T turnaroun= (1275 + 375 + 850 + 250 + 925) / 5 = 735
-> W = (0 + 250 + 375 + 850 + 925) / 5 = 480
<Deadline Scheduling>
Real-time sys 스케줄링이다.
일정 기한 전에 실행을 완료해야 하는 특정 프로세스들을 가진다.
-> deadline이 더 짧은 task가 먼저 수행된다.
4. Preemtive Scheduling Algorithm
<About Preemtive Strategies..>
-> 준비된 모든 프로세스 중 가장 우선순위가 높은 프로세스가 CPU에 할당된다.
-> 우선 순위가 낮은 모든 프로세스는 CPU를 요청할 때마다 [우선 순위가 가장 높은] 프로세스에게 양보한다.
-> 강제 context switching한다는 의미, 이 과정에서 상당한 비용이 들 수 있다.
** Preemptive version of SJN : 프로세스의 남은 시간을 가지고 순위 결정. 가장 짧게 남은 애 먼저 수행
-> 그림에서 (우선 순위가 제일 높은) Task3은 중요업무만 하고, CPU를 놔줘야 한다.
일시정지하는 프로세스들은 sleep(second) 함수를 사용하여, second 동안 suspend한다.
-> 우선 순위가 낮은 작업은 starvation이라는 문제에 직면한다.
<Round Robin>
시분할 시스템을 위한 선점형 스케줄링 알고리즘이다.
공평성을 위해 단위시간(Tiem quantum or Time slice)을 할당한다.
그 시간이 넘어가면 순번을 맨 뒤로 넘기고 다음 프로세스에게 기회를 준다.
-> T TRnd(p 0) = 1100, T TRnd(p 1) = 550, T TRnd(p 2) = 1275, T TRnd(p 3) = 950, T TRnd(p 4) = 475
-> T turnaroun= (1100 + 550 + 1275 + 950 + 475) / 5 = 870
-> W = (0 + 50 + 100 + 150 + 200) / 5 = 100 ** 다른 것들보다 이게 제일 짧다는 이점이 있다.
5. Multilevel Queue
<Multilevel Feedvback Queue>
프로세스는 다양한 대기열 간에 이동할 수 있으며, aging은 이러한 방식으로 구현될 수 있다.
우선 순위를 바꾸는 방법은 다양하다. 아래와 같다.
-> 그리고, 순위를 바꾸는 과정에서 determinism violation(결정론적 위반)이 발생한다는 문제가 있다.
<Example of Multilevel Feedback Queue>
Three queue를 보자.
-> Q0 : RR을 time quantum 8 동안, Q1 : RR을 time quantum 16 동안, Q2 : FCFS 실행
-> 새 작업이 FCFS로 제공되는 대기열 Q0에 들어간다. CPU가 증가하면, 작업에 8ms가 걸린다.
8ms 내에 완료되지 않으면 작업이 Q1 대기열로 이동된다. 1분기 작업에서 FCFS가 다시 제공되고
16ms가 추가된다. 그래도 완료되지 않으면, 선점되어 Q2 대기열로 이동한다.
6. 다양한 Scheduling
<Thread Scheduling>
사용자 레벨 스레드와, 커널 레벨 스레드의 구별하는 과정이다.
스레드가 지원되는 경우, 프로세스가 아닌 스레드 스케줄링을 수행한다.
(1) PCS(process-contention scope) : 내 프로세스 안에서 children끼리 경쟁, 우선 순위를 할당한다.
(2) SCS(system-contention scope) : 다른 프로세스랑도 다 경쟁한다.
** API를 통해 스레드 생성 중 PCS 또는 SCS 지정 가능하다.
<Multiple-Processor Scheduling>
CPU를 여러 개 사용할 수 있는 경우, CPU 스케줄링이 더 복잡하다.
멀티프로세스는 다음 아키텍처 중 하나일 수 있다.
-> 멀티코어 CPU, 멀티스레드 core, core 각각 안에 또 스레드 core 여러 개 존재하는 상황, NUMA 시스템 등
<Real-Time CPU Scheduling>
(1) Soft real-time systems
중요한 실시간 작업의 우선 순위가 가장 높지만, 작업의 예약시기에 대한 보장은 없다.
-> quality of service가 나쁘다. 그래도 수행하면 좋은 결과가 나온다.
보통 general purpose OS가 이에 해당한다.
(2) Hard real-time systems
작업을 deadline까지 처리해야 한다.
-> deadline 실패 시 더 나쁜 결과가 나올 수 있다.
real time OS가 이에 해당한다.
(*) Event latency
이벤트가 발생한 시점부터 서비스가 제공될 때까지 경과하는 시간이다.
(1) Interrupt latency : 인터럽트가 도착한 후, 서비스가 인터럽트되는 루틴이 시작될 때까지의 시간
(2) Dispatch latency : 현재 프로세스를 CPU에서 분리하고, 다른 프로세스로 전환하기 위한 스케줄 시간
<Priority-based Scheduling>
모든 Task는 주기성을 가진다. [대부분의 Task는 우선순위를 가지는 주기성 Task !!]
Task가 deadline의 garantee를 가지리 위해 주기를 가진다.
어느 Task가 deadline missing으로부터 손실이 덜한지 check한다.
-> 그림에서 t : Task가 돌 때의 CPU time, d : deadline, 반드시 이 안에서 처리해야함, p : 주기
그림에서 보다시피 0 =< t =< d =< p 이다. 그리고 periodic task의 속도는 1/p이다.
<Rate Montonic Scheduling> -> hard, no test(교수님 피셜)
짧은 period를 높은 우선 순위로 두고, period가 길수록 우선 순위가 낮다.
(ex) 그림에선 P1이 P2보다 높은 우선 순위를 가진다.
<Earliest Deadline First Scheduling>
그때 그때 계산하여, deadline이 먼저 다가오는 놈을 먼저 수행한다.
-> deadline이 빠를수록 우선 순위가 높고, deadline이 느릴수록 우선 순위가 낮다.
<Linux Process Scheduling>
Process priority는 동적이다. 스케줄러는 우선 순위를 늘리거나 줄인다.
(1) time-sharing algorithm : 여러 프로세스 간의 공정한 preemptive 스케줄링
credit based algorithm을 사용한다. (사진의 공식 참고)
(2) real-time algorithm : 공정성보다 [절대적인 우선 순위]를 더 중요시하는 알고리즘
7. Why GPOS not guarantee the Determiniam?
<GPOS의 기본 스케줄링 철학>
대화형(real-time, 실시간) 프로세스와 비대화형(time-sharing) 프로세스를 구분한다.
우선 순위가 높은 놈에게 time Quantum을 많이 준다.
-> priority가 동적으로 바뀐다.
-> CPU 사용량을 기준으로 time Quantum을 수정한다.
<왜 GPOS로 realtime OS를 구성하면 안될까?>
(1) GPOS는 fair 스케줄링을 한다.
우선 순위가 높을수록 time slice만 많이 할당할 뿐, 먼저 수행시키진 않는다. -> 응급성에 취약
(2) Task끼리 syncronize된다.
즉 순위 다른 Task들이 공유변수를 쓸 때, 낮은 순위가 변수를 꽉 잡고 있으면 높은 순위도 사용 불가
(3) page replacement로 Task를 동시에 수행할 수 있다.
그러나 이는, 시간 예측이 불가하다. 또한 수행이 안 되고, 교환만 계속 일어날 수 있다.
(4) GPOS는 유저 모드, 커널 모드를 분리한다. real time OS는 전부 커널 모드다.
(5) Garbage[danggling reference] leak를 찾아 반환해준다.
Garbage collector는 따라서 우선 순위가 높다.
그러나 내 Task 수행하다가 갑자기 다른 Task 들어오면 real time OS에서는 그거대로 문제 발생
'KNU_study > 운영체제' 카테고리의 다른 글
| 운영체제(6-2) IPC part (0) | 2023.06.12 |
|---|---|
| 운영체제(6) Synchronization Tools & Examples (0) | 2023.06.12 |
| 운영체제(4) Thread (0) | 2023.05.18 |
| 운영체제(3) Process (0) | 2023.05.16 |
| 운영체제(2) Operating-System Structures (0) | 2023.05.16 |
