ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [OS] - CPU Scheduling
    CS/면접준비 2022. 9. 29. 18:34

    CPU Scheduling


    Processor(CPU)가 Process를 적절하게 배정하여 사용률을 높이고 Overhead와 Starvation을 낮추기 위함

     

    목표

    1. Batch System : 가능하면 많은 일을 수행한다. (일을 한개씩 하는 것보다 100개씩 처리하는것이 좋다)

    2. Interactive System : 빠른 응답 시간, 적은 대기 시간

    3. Real-time System : Deadline

     

    Preemptive vs NonPreemtive

    Preemptive

    • OS가 Cpu를 Process를 선점할 수 있는 경우 강제로 변경 가능하다.

     

    NonPreemptive

    • Process Exit , I/O Event가 있을 때 까지는 Process의 실행을 보장하여 준다.

     

    Process State

    • Process는 Preemptive와 Nonpreemtive 차이에 따라 State 변경이 달라질 수 있다.
    • Preemptive는 Interrupt와 EventCompletion이 발생하면 바로바로 처리가 가능하다.
    • 그에 반면에 NonPreemptive는 현재 Process가 동작이 완료되거나 Event가 발생할 때까지 대기해야한다.

     

    CPU Scheduling


    Non-Preemptive Scheduling

    1. FCFS (First Come FisrtServed)

    Q에 도착한 순서대로 처리한다.

    뒤에 온 Process들은 대기 시간이 길어진다.

     

    2. SJF (Shortest Job First)

    수행시간이 짧다고 판단되는 작업을 먼저 수행

    FCFS보다 평균 대기 시간 감소

    수행시간이 길면 처리시간이 계속 밀리게 된다.

     

    3. HRN(Highest Response-ratio Next)

    우선 순위를 계산하여 SJF의 단점을 보완

    우선 순위 = (실행시간+대기시간)/실행시간

     

    문제점 : 수행시간을 어떻게 알것인가?

     

    Preemptive Scheduling

    1. Prioirty Scheduling

    • 우선 순위를 부여하여 우선순위가 높은 작업부터 처리
    • 우선 순위가 낮으면 Starvation 발생 -> Aging ( 시간이 오래 되면 우선순위를 올려준다 )

     

    2. Round Robin

    • FCFS에 의해 Process들이 보내지면, 동일한 시간의 Time Quantum 만큼 Processor(CPU)를 할당
    • Time Quantum에 따라 커지면 FCFS와 유사하고 너무 낮으면 Context-swithing으로 Overhead가 많이 발생

     

    3. Multi-Level Q

    • 각 Q는 Round-Robin 형태로 동작
    • 작업들을 여러 종류로 나누어 Q마다 Time Quantum을 다르게 설정
    • 우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당.
    • 프로세스는 한번 정해진 Q에서 다른 Q로 이동이 불가

    4. Multi-Level Feedback Q

    • 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로
    • 짧은 작업에 유리, 입출력 위주의 Interrupt가 잦은 Job에 대해 우선권
    • 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간이 줄어든다.
    •  

     

     

    Scheduling 기준 척도

    1. Response time

    • 대기 시간 = 작업되기 까지 걸린 시간

    2. Turnaround time

    • 실행 시간 + 대기 시간을 합한 시간으로 작업이 완료될 때 까지 걸린 시간

    'CS > 면접준비' 카테고리의 다른 글

    [OS] - Semaphore / Mutex  (0) 2022.09.30
    [OS] - DeadLock  (0) 2022.09.29
    [OS] - IPC  (0) 2022.09.29
    [OS] - System call / PCB  (0) 2022.09.29
    [OS] - Interrupt  (0) 2022.09.29

    댓글

Designed by Tistory.