[Operating System] Chapter 9 - Uniprocessor Scheduling

이한량·2024년 6월 8일
Operating System

Operating System

목록 보기
9/12

1. CPU Scheduling

  • CPU Scheduling : OS는 CPU를 효율적으로 사용하기 위해서 여러 알고리즘을 활용해 스케줄링한다. CPU 스케줄링의 주요 목표는 다음과 같다.

    • Long-term Scheduling : 프로세스가 New 상태에서 Ready 혹은 Ready/Suspend 상태로 전이할 때 관여하는 스케줄링.

    • Medium-term Scheduling : 프로세스가 Blocked/Suspend 상태에서 Blocked 혹은 Ready/Suspend 상태에서 Ready 상태로 전이할 때 관여하는 스케줄링.

    • Short-term Scheduling (Dispatcher) : 프로세스가 Ready 상태에서 Running 상태로 이동할 때 관여하는 스케줄링. 가장 빈번하게 일어나므로, OS 입장에서 반드시 최적화 해야만 하는 알고리즘이다.

  • Scheduling Criteria

    • CPU 사용률 높이기 : CPU 사용률을 높일수록 효율적으로 동작하지만, 100%에 가까운 CPU 사용률은 오히려 불안정하므로 적절한 수준으로 조절하는 것이 좋다.

    • 처리량 높이기

    • 대기 시간 및 반응 시간 줄이기

  • Preemptive : 현재 실행중인 프로세스보다 우선 순위가 높은 프로세스가 Ready Queue에 들어온다면, 현재 프로세스의 실행을 중단시키고 새로운 프로세스를 CPU에 할당한다.

  • Nonpreemptive : 현재 실행중인 프로세스보다 우선 순위가 높은 프로세스가 Ready Queue에 들어오더라도, 현재 프로세스의 실행을 그대로 유지한다.

  • Starvation : 특정 프로세스가 CPU Time을 충분히 할당 받지 못해 무한히 대기 상태에 빠지는 현상이다. 이는 주로 우선 순위가 낮은 프로세스에서 발생하는 문제로, 더 높은 우선 순위를 가진 프로세스들이 계속해서 도착하고 실행되면서 낮은 우선순위를 가진 프로세스는 계속해서 대기하게 된다. 이런 방식을 해결하기 위해 Aging 기법을 사용할 수 있다.

  • Aging : 시간이 지남에 따라 대기중인 프로세스들의 우선 순위를 점차 상승시켜, 장시간 대기하는 프로세스가 결국 CPU Time을 충분히 할당받을 수 있도록 하는 방법이다.

1-1. FCFS Algorithm

  • First Come First Service (FCFS) : 각 프로세스가 준비 상태가 되면, Ready Queue에 로드 된다. 현재 실행 중인 프로세스의 실행이 종료되면, 준비 큐에 제일 먼저 들어온 프로세스가 실행된다. 즉, 프로세스가 Ready Queue에 들어오는 순서대로 처리된다.

    • FCFS의 동작 방식

      • 세 개의 프로세스 P1,P2,P3P_1, P_2, P_3가 존재한다.

      • 각 프로세스의 서비스 타임 T1=24,T2=3,T3=3T_1 = 24, T_2 = 3, T_3 = 3이다.

      • 프로세스 1, 2, 3의 순서대로 실행된다면, 평균 웨이팅 타임은 다음과 같다.

        0(P1)+24(P2)+27(P3)/3=170(P_1) + 24(P_2) + 27(P_3) / 3 = 17

    • 특징

      • Convoy effect : 메모리 사용량이 크고 처리 시간이 긴 프로세스가 준비 큐에 먼저 도착하여 실행되고, 이후에 도착한 처리 시간이 짧은 프로세스들은 긴 시간을 대기해야하는 현상이다. CPU 처리 시간을 고려하지 않는 알고리즘이므로 위와 같은 경우, 프로세스들의 평균 대기 시간이 길어지는 문제가 발생한다. 이로 인해 응답 시간등이 길어질 수 있다.

      • Nonpreemptive 방식

1-2. SPN Algorithm

  • Shortest Process Next (SPN) : 가장 짧은 예상 처리 시간을 가진 프로세스를 선택하는 알고리즘이다. 이는 응답 시간 측면과 평균적인 대기 시간을 줄이는 효과를 기대할 수 있지만, 각 프로세스에 필요한 처리 시간을 알거나 추론하는 것은 어려운 작업이다.

    • SPN의 동작 방식

      • 세 개의 프로세스 P1,P2,P3P_1, P_2, P_3가 존재한다.

      • 각 프로세스의 서비스 타임 T1=24,T2=3,T3=3T_1 = 24, T_2 = 3, T_3 = 3이다.

      • 프로세스 2, 3, 1순으로 실행된다.

      • 평균 웨이팅 타임은 다음과 같다

        6(P1)+0(P2)+3(P3)/3=36(P_1) + 0(P_2) + 3(P_3) / 3 = 3

    • 특징

      • 현실적으로 프로세스 동작 이전에 프로세스 처리 시간을 계산하는 것은 불가능에 가깝다. 따라서 현실적에서 사용하기엔 어려운 방식이다.

      • Nonpreemptive 방식이다.

1-3. Round-Robin Algorithm

  • Round-Robin Algorithm : Time Quantum을 정해놓는 방식이다. 즉, 프로세스의 실행 시간이 정해진 Time Quantum을 넘어가면 타임 인터럽트가 발생하여 현재 실행 중인 프로세스는 실행이 중단되고, 다음 프로세스가 FCFS 방식으로 선택되어 실행된다.

    • 특징

      • Time Quantum

        1). 타임 퀀텀이 너무 짧으면 프로세스들 사이의 Context Switch가 자주 일어나기 때문에 오버헤드가 커진다.

        2). 타임 퀀텀이 너무 커지면, FCFS와 차별점이 사라지는 결과가 나타난다.

        3). 따라서 타임 퀀텀을 적절히 조절해야 하는데, 일반적으로 80% 정도의 프로세스가 1 타임 퀀텀 안에 종료되도록 하는 타임 퀀텀을 채택한다.

      • 만약 Ready Queue가 하나밖에 없다면, 프로세스들의 실행 순서를 지정하는 데 어려움이 발생한다.

      • Context Switching이 자주 발생하는 알고리즘이다. 따라서 오버헤드가 FCFS보다 클 수 있다.

      • Preemptive 방식이다.

1-4. Priority Queue Algorithm

  • Priority Scheduling : 우선 순위 스케줄링은 각 프로세스에 우선 순위를 부여하고, 이 우선 순위에 따라 CPU 접근 순서를 결정하는 방식이다. 우선 순위는 다양한 기준으로 선정될 수 있으며, 대부분 동적으로 우선 순위를 결정한다.

1-5. Multi-Level Feedback Queue Algorithm

  • Multi-Level Feedback Queue (MLFQ) : 여러 크기를 가진 프로세스를 효율적으로 처리하기 위해 설계된 방식이다. Round-Robin과 Priority Queue를 합친 방식으로 이해할 수 있다.

    • 동작 방식

      • 프로세스가 처음 들어와 RQ0에 배치된다.

      • RQ0에 대기하던 프로세스가 정해진 Time Quantum동안 작업을 수행한다.

      • 타임 아웃이 걸렸을 때, 아직 작업 시간이 더 남았다면, RQ1에 배치된다.

      • 위 과정은 모든 작업이 끝날 때 까지 반복된다.

      • 이런 방식으로 작업 시간이 큰 프로세스는 점점 낮은 우선 순위 큐로 이동하게 된다.

    • 특징

      • Starvation이 발생할 수 있기 때문에, 이를 해결하기 위해 Aging 기법을 사용해야한다.

1-6. Scheduling Algorithms

  • 예제 테이블

    • Arrival time : 도착 시간(Ready Queue에 도달한 시간)

    • Finish time : 프로세스 종료 시간

    • Turn-around time : 프로세스를 완료하는 데 걸린 시간

      • Finish time - Arrival time (프로세스 종료 시간에서 프로세스 도착 시간을 빼면 프로세스를 완료하는 데 걸린 시간이 나온다.)

    • Waiting time : 프로세스가 Ready Queue에서 대기한 시간

      • Turn-around time - Service time (프로세스를 완료하는 데 걸린 시간에서 실제 동작 시간을 빼면 대기 시간이 나온다.)

2. CPU Scheduling with UNIX

  • UNIX(Linux) : UNIX 환경에서 CPU 스케줄링 알고리즘은 Round-Robin, Priority Queue, Multi-Level Feedback Queue, FCFS가 적절하게 혼합되어 있는 방식이다.

  • Scheduling Formula

    • CPUj(i)=CPUj(i−1)2CPU_{j}(i) = \frac{CPU_{j}(i - 1)}{2}

      • 프로세스 j의 CPU 사용량을 나타내는 지표이다.

      • CPUj(i)CPU_{j}(i) : 현재 시점 ii에서의 CPU 사용량을 의미한다.

      • CPUj(i−1)CPU_{j}(i - 1) : 이전 시점 i−1i - 1에서의 CPU 사용량을 의미한다.

      • 따라서 위 식은, 이전 시점의 CPU 사용량을 절반으로 줄여서 현재 시점에서의 CPU 사용량을 결정한다는 의미이다.

    • Pj(i)=Basej+CPUj(i)2P_{j}(i) = Base_{j} + \frac{CPU_{j}(i)}{2} + nice_j$

      • Pj(i)P_{j}(i) : 프로세스 j의 현재 시점 ii에서의 우선 순위이다.

      • BasejBase_{j} : 프로세스 j의 기본 우선 순위를 나타내는 값이다. 프로세스가 최초 생성될 때 할당되며, OS에 의해 동적으로 변경될 수 있다.

      • nicejnice_{j} : 프로세스 j의 nice 값이다. 이는 프로세스의 우선 순위를 조정하는 데 사용되는 값으로, -20에서 19까지의 범위를 갖는다. 사용자가 해당 값을 임의로 조정할 수 있다.

      • 따라서 위 식은 프로세스의 우선 순위를 결정하는 공식이다.

  • 동작 예제

    • 프로세스 A, B, C가 동시에 도착했다고 가정해보자.

    • 세 프로세스의 우선순위는 동일하므로, 프로세스 A부터 C까지 순서대로 실행됐다고 생각한다.

    • 프로세스 A가 1 Time Quantum동안 실행되어 작업을 수행(CPU 카운트가 0에서 60까지 상승)한다.

    • 1TQ가 끝날 때마다 우선 순위를 재조정(75, 60, 60)한다. 이때 CPU 카운트는 Scheduling Formula에 의해 항상 절반이 된다.

    • 프로세스 B가 마찬가지로 실행되고, CPU 카운트도 조정되어 우선 순위가 재조정된다(67, 75, 60).

    • 위 과정을 모든 작업이 종료될 때까지 반복한다.

profile
이한량
한량 극복 프로젝트
이전 포스트

[Operating System] Chapter 8 - Virtual Memory

다음 포스트

[Operating System] Chapter 10 - Multiprocessor Scheduling

0개의 댓글