Operating-System Examples
Example: Linux Scheduling
- 커널 버전 2.5 이전 : traditional UNIX scheduling algorithm
- SMP시스템 지원이 되지 않아서 multiple processor의 경우 제대로 작동되지 않는다.
- 여러 processes의 경우 poor performance를 가짐.
- 커널 버전 2.5 : 프로세스의 수와 무관한 O(1) 스케줄링 알고리즘을 가지고 있다.
- SMP system을 포함하여 processor affinity, load balancing을 모두 지원함.
- interactive process에는 poor performance를 가진다.
- 커널 버전 2.6.23 : Completely Fair Scheduler(CFS) -> default Linux scheduling system.
- scheduling classes
- 각 클래스는 정해진 우선순위를 가진다.
- high-priority scheduling class에서 high-priority task를 선정해서 실행한다.
- standard Linux kernel에는 두 종류의 scheduling classes가 존재
- CFS scheduling algorithm을 사용하는 default scheduling class
- real-time scheduling class
- 추가 가능.
- CFS scheduler는 task별로 정해진 nice value를 사용해서 계산되는 processing time을 각 task별로 할당한다.
- nice value : -20 ~ +19, 낮을수록 높은 우선순위를 가진다, default nice value = 0.
(어원 : nice한 이유는 nice value를 증가시키면 다른 프로세스들에게 양보해주는 것이므로 이런 의미에서 nice하다고 하는 것.) - CFS는 time slice 대신에 targeted latency를 사용함.
- targeted latency : 매 실행가능한 task가 적어도 한 번 실행되어야 하는 시간.
넘 어렵다... 더 배우고 나서 다시 보는걸루
Algorithm Evaluation
- 알고리즘을 선택하는 방법?
- 기준을 세우고 그에 따라 최선의 알고리즘을 선택한다. -> 기준에 따라 알고리즘을 평가해야 함.
- 평가 방법들 소개
Deterministic Modeling
- Analytic evaluation : 주어진 알고리즘과 시스템 workload를 통해 퍼포먼스를 평가하는 공식이나 숫자를 만들어낸다.
- Deterministic Modeling : analytic evaluation의 한 종류로, 미리 결정된 workload를 가지로 각 알고리즘을 적용시켜 performance를 결정한다. 아래 예시를 보자.
- 5 프로세스들이 time 0에 순서대로 오고, ms단위이다.
- FCFS, SJF, RR(quantum = 10ms)에 대해서 average waiting time이 가장 적은 알고리즘을 찾아보자.
- FCFS
- average waiting time = 28ms
- SJF
- average waiting time = 13ms
- RR algorithm
- average waiting time = 23ms
- FCFS
- 5 프로세스들이 time 0에 순서대로 오고, ms단위이다.
- 쉽고 빠르지만, 특정한 케이스에 대한 검증만 가능하다 -> 그래서 설명하거나 예시를 제공하는 데에만 주로 쓰인다.
- 조건들이 정확하게 주어지고, 이 과정이 실제로 여러 번 반복되는 케이스에서는 deterministic modeling이 효과적이다. 또한 trend도 만들어낼 수 있다. 위 예시같이 정해진 시간에 동시에 여러 프로세스가 들어오는 경우, SJF policy가 가장 효율적이라는 trend를 얻을 수 있다.
Queueing Models
- 몰루 -> 뒷내용은 맛보기만 하고 넘어가는 것 같아서 넘김.
참고 자료
- Abraham Silberschatz, Operating System Concepts, 10th edition
공부 내용 저장소