[SW 정글] 5/20 운영체제 - 스케쥴

배운거

 

Scheduling Criteria

 

CPU utilization(이용료) * CPU입장

- keep the CPU as busy as possible

- CPU가 쉬지 않고 일한시간

Throughput(처리량) * CPU입장

- 주어진 시간동안 얼마나 일했는지

Turnaround Time * 사용자 입장

- CPU가 들어오고 나가는 동안의 시간 (ready + running time)

Waiting Time * 사용자 입장

- ready queue에서 기다리는 시간

Response Time * 사용자 입장

- CPU를 처음 얻기까지의 시간

 

 

Scheduling Algorithms

 

FCFS(First-Come First-Served)

먼저 온놈 먼저 해주기

비선점형(non preemptive) 알고리즘

앞에놈이 실행시간이 너무 길면 오래 기다려야함 -> Convoy Effect

 

SJF(Shortest-Job First)

 

CPU burst time이 가장짧은 프로세스를 제일 먼저 스케쥴링하는 알고리즘

 

Nonpreemptive

- 일단 CPU를 잡으면 이번 CPU burst가 완료될때까지 CPU를 선점당하지 않음

Preemptive

- 현재 수행중인 프로세스에 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김

- 이 방법을 Shortest Remaining Time First(SRTF)라고도 함

주어진 프로세스들에 대해 minimum average wating time을 보장함

 

문제점

1. Starvation

- CPU 사용시간이 길면 영원히 실행 못할 수도 있음

2. CPU burst time 예측 불가능

- 과거의 CPU burst time을 이용하여 추정

- Exponential averaging (가장 최근의 cpu 사용률을 많이 반영)

 

 

Priority Scheduling

가장 우선순위가 높은 프로세스를 제일 먼저 스케쥴링하는 알고리즘

우선순위가 높은것이 숫자가 작다

SJF는 일종의 Priority Scheduling이다.

Nonpreemptive ,Preemptive가 있음

문제점

Starvation

해결법 ->  Aging 시간이지나면 우선순위가 높아짐

 

Round Robin (RR)

현대적인 스케쥴링은 이것을 기반함

각 프로세스를 동일한 크기의 할당시간(Time Quantum)을 가진다.

할당 시간이 지나면 선점당하고 ready queue의 제일 뒤로 가서 다시 줄을 선다.

장점 : 응답시간이 짧다

어떤 프로세스도 q time unit 이상 기다리지 않는다 

if ) q large  ➡️ FCFS

q small ➡️ context switch 오버헤드가 커진다

즉, 적당한 크기의 q가 중요 보통 10~100ms

 

일반적으로 SJF보다 average turnaround time이 같지만 response time이 더 짧다

 

Multilevel Queue

우선순위

1. stystem processes

2. intearctive processes

3. interactive editing processes

4. batch processes

5. student processes

 

foreground : 사람과 interaction하는 jobs

background : 백그라운드 잡만 하는 jobs

 

Ready queue를 여러개로 분할

- foreground : interactive

- background : batch - no human interaction

 

각 큐는 독립적인 스케쥴링 알고리즘을 가짐

- foreground : RR

- background : FCFS

 

큐에 대한 스케쥴링이 필요

- Fixed priority scheduling

    - serve all from foreground then from background

    - Possibillity of starvation

- Time Slice

    - 각 큐에 CPU time을 적절한 비율로 할당

    - ex) 80% to foreground in RR, 20% to background in FCFS

 

 

Multilevel Feedback Queue

프로세스가 다른큐로 이동가능. 실행시간이 짧으면 우선순위가 높음

 

Multiple-Processor Scheduling

CPU가 여러개인 경우

1. Homogeneous processor인 경우

    - queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.

    - 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐

2. Load sharing

    - 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요

    - 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 경우

3. Symmetric Multiprocessing (SMP)

    - 각 프로세서가 각자 알아서 스케쥴링 결정

4. Asymmetric multiprocessing

    - 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

 

Real time scheduling

Hard real-time systems

    - Hard real-time task는 정해진 시간안에 반드시 끝내도록 스케쥴링해야함

Soft real-time computing

    - Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야함

 

Thread Scheduling

Local Scheduling

    - User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케쥴할지 결정

Global Scheduling

    - Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 thread를 스케쥴할지 모름

 

 

Algorithm Evaluation

Queueing models

    - 확률 분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index 값을 계산

Implementaion(구현) & Measurement(성능측정)

    - 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교

Simulation (모의실험)

    - 알고리즘을 모의프로그램으로 작성 후 trace(input data)를 입력으로 하여 결과 비교

 

 

Process Synchronization 문제

공유데이터의 동시 접근은 은 데이터의 불일치 문제를 발생시킬 수 있다

일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘 필요

 

Race condition

    - 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황

    - 데이터의 최종연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

 

race condition을 막기 위해서는 concurrent process는 동기화되어야한다.

 

The Critical-Section Problem

- n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

- 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

 

problem

    - 하나의 프로세스가 critical에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야한다.

 

 

 

 

 

---

 

 

 

느낀거

컴퓨터공학을 전공했지만 들어보지도 못한것들이 나오기 시작했다.....

 

어룝다... 오늘도 열코다🔥

 

궁금한거

없음.