[Operating System] CPU Scheduling (6)

dandb3·2023년 3월 16일
0

Operating system

목록 보기
19/31

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가 존재
      1. CFS scheduling algorithm을 사용하는 default scheduling class
      2. real-time scheduling class
      3. 추가 가능.
  • 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
  • 쉽고 빠르지만, 특정한 케이스에 대한 검증만 가능하다 -> 그래서 설명하거나 예시를 제공하는 데에만 주로 쓰인다.
  • 조건들이 정확하게 주어지고, 이 과정이 실제로 여러 번 반복되는 케이스에서는 deterministic modeling이 효과적이다. 또한 trend도 만들어낼 수 있다. 위 예시같이 정해진 시간에 동시에 여러 프로세스가 들어오는 경우, SJF policy가 가장 효율적이라는 trend를 얻을 수 있다.

Queueing Models

  • 몰루 -> 뒷내용은 맛보기만 하고 넘어가는 것 같아서 넘김.

참고 자료

  • Abraham Silberschatz, Operating System Concepts, 10th edition
profile
공부 내용 저장소

0개의 댓글