ABOUT ME

네트워크 개발자

Today
Yesterday
Total
  • [Chapter-4] cpu 스케줄링
    개발공부/OS 2024. 7. 21. 17:49

    cpu burst : cpu만 연속적으로 사용
    i/o burst : io만 연속적으로 사용
    - 두가지를 반복하며 사용, 프로그램마다 다름
        - io bound job : io가 많이 끼어든 작업
        - cpu bound job : io가 별로 안끼어든 작업

    스케줄링에서 io bound job 이 문제
    이 중 cpu 보단 io 에 더 비중을 줘서 interactive job 에게 적절한 response를 기대함

    io bound ps : cpu를 잡고 계산하는 시간보다 io에 많은 시간이 필요
    cpu bound ps : cpu 위주

    cpu 스케줄러 : ready 상태 프로세스 중 이번에 cpu를 줄 프로세스를 고른다.

    dispatcher : cpu의 제어권을 스케줄러에 의해 선택된 프로세스에게 넘겨주는 역할을 하는 친구 ==> 이 과정을 context switch라 한다.

    스케줄링이 필요한 경우
    1. running => blocked(io요청)
    2. running => ready (할당 시간 만료)
    3. blocked ready (io 완료후 인터럽트)
    4. terminate

     


    cpu 스케줄링 

    크게 아래 두분류

    1. nonpreemptive(= 비 선정형 ): 자진반납 
    2. preemptive (= 선정형): 강제로 뺏기(뺏기가 가능하다)

     

    - scheduling criteria(cpu 성능척도)

    1. 시스템 입장에서의 성능 척도

    • uitilization(이용률) : 놀지않고 일한 시간
    • throughput(처리량) : 

    2. 프로세스 입장에서의 성능 척도

    • 소요시간 : 식당에서 보내는 풀 시간
    • 대기시간 : 기다리는 시간
    • 응답시간 : 첫번째로 음식이 나오는 시간

     

     

    cpu스케줄링 알고리즘

    1. fcfs = fast come first-served

    - 고전적인 알고리즘

    - 그렇게 좋은 방법은 아니다. (처음 온 프로세스가 계속 잡고있으면 곤란 = convoy effect 유발)

    - waiting time : 기다린 총 시간

    - average time : 기다린 총 시간의 합 / 3

    ==> 처음 온 프로세스에 따라 time이 많이 달라짐

     

    2. sjf = shortest-job-first

    - 짧게 쓰는 프로그램에 (cpu 버스트가 제일 짧은) 스케줄을 줌

    ==> 가장 짧은 average waiting time을 보장

    - non-preemptive : 새치기가 불가능, 두번째 순서부터 줄세우기

    - preemptive : 새치기가 가능

    - 문제점 : starvation(긴 프로세스의 정체), 실제 본인의 프로세스가 얼마나 시간을 사용할지 모름

    but 과거의 cpu burst time을 통해 추정가능

     

    3. priority scheduling

    -  pid가 제일 높은 순서로 스케줄링

    - 마찬가지로 preemptive, nonpreemptive 가 있다.

    - 우선순위가 가장 높은 프로세스 = 가장 낮은 정수

    - 문제점 : starvation(pid가 높은 애들이 무시당함)

    - 해결책 : aging = 오래 기달리면 우선순위를 높여주자

     

    4. Round Robin (RR)

    - 현대 스케줄링은 보통 RR 에 기반

    - 각 프로세스는 동일한 크기의 할당시간(time quantum)

    - 시간이 끝나면 readyque

    - 응답시간이 빨라진다.

    - 할당시간이 커지면 fcfs처럼 되고, 작아지면 오버헤드가 커진다.

     

    5. Multilevel Queue

    - 여러줄서기 (foreground - RR이 적합, backgound - FCFS가 적합)

    - 줄 마다 우선순위가 있다.

    - 우선순위가 높은 큐가 비어있어야 다음 우선순위로 간다. (큐에 대한 스케줄링이 필요)

     

    6. Multilevel Feedback Queue

    - 프로세스가 다른 큐로 이동가능

    - 에이징 구현 가능

     

    7. Multiple-Processor scheduling

    - cpu가 여러 개인 경우 스케줄링은 더욱 복잡해짐

    - homogeneous processor :

    • Queue에 한줄로 세워서 알아서 꺼내가도록
    • but 특정 프로세서에서 수행되어야 하는 프로세스시 문제가 복잡

    - Load sharing : 

    • 부하를 적절히 공유
    • 별개의 큐, 공동 큐

    - SMP : 각 cpu가 알아서 스케줄링

    - asymmetric multiprocessing : 하나의 프로세스가 시스템 데이터의 접근, 공유를 책임

     

    8. Real-Time Scheduling

    - Hard real-time systems : 정해진 시간 안에 반드시

    - Soft real-time copmuting : soft real-time task는 높은 priority를 갖도록 해야함

     

    9. Thread Scheduling

    - Local Scheduling : 사용자 수준의 쓰레드 라이브러리에 의해 어떤 쓰레드를 스케줄 할지 결정

    - Global Scheduling : 커널의 단기 스케줄러가 어떤 쓰레드를 스케줄 할지 결정

     

     

    알고리즘 evaluation

    1. queueing models

    - 확률 분포로 주어지는 arrival rate, service rate, performance index 값을 계산

    - 요즘 별로 안씀

     

    2.  구현 & 성능측정

    - 실제 시스템에 알고리즘을 구현, 실제 작업에 성능을 측정, 비교

     

    3. simulation

    - 알고리즘을 모의 프로그램으로 작성후 trace를 입력

     

     

     

     

     

    '개발공부 > OS' 카테고리의 다른 글

    [Chapter-6] Deadlock  (0) 2024.08.10
    [Chapter-5] Process Synchronization  (0) 2024.08.04
    [Chapter-3] 프로세스 관리  (0) 2024.07.21
    [Chapter-2] 프로세스  (0) 2024.07.21
    [Chapter-1] 시스템 구조  (0) 2024.07.20
Designed by Tistory.