[운영체제] cpu 스케쥴링

in CS on Cs, Operating System, Operating-system


CPU 스케쥴링

여러 프로세스 들이 번갈아가며 사용해야하는 자원이 있을 경우 주어진 시점에서 어떤 프로세스가 이 자원을 사용할 수 있도록 해줄 것인가를 결정 하는 것.

Multi programming 의 목적

항상 실행중인 프로세스를 가지게 함으로써 중앙처리 장치 이용률을 최대화 하는것. 그래서 한정된 자원으로 최대한 성능을 이끌어 내기 위해서는 CPU를 적절하고 효율적으로 사용해야 한다. 따라서 OS는 실행 대기중인 프로세스들에게 자원 배정을 적절히 하여 시스템의 성능을 끌어올릴 수 있다.

스케쥴링의 대상

  • 사용자 프로세스 및 시스템 프로세스가 대상 (프로세스 또는 스레드)
  • 트랩이나 인터럽트 처리는 하드웨어적 작동에 의해 커널 내 처리 함수가 호출되어 수행되므로 스케줄링 대상이 아님.

프로세스가 구동하려면 다양한 시스템 자원이 필요하다. 대표적으로 CPU (중앙 처리장치)와 입출력장치가 있는데 최고의 성능을 내기 위해 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것 을 CPU 스케쥴링 이라고 한다.

스케줄링의 목적과 기준

  • 사용자 관점 : 응답시간
  • 시스템 관점 : 처리량
  • 동시에 만족시키긴 힘들다.
  • CPU 연산 > 입출력 : CPU-Bound 프로세스 (비선점 스케줄링)
  • CPU 연산 < 입출력 : I/O-Bound 프로세스 (선점 스케줄링)

선점 스케줄링(Preemptive Scheduling)

  • OS가 나서서 CPU사용권을 선점하고, 특정 요건에 따라 각 프로세스의 요청이 있을때 프로세스에게 분배하는 방식
  • 가장 자원이 필요한 프로세스에게 CPU를 분배하여 상황에 따라 강제로 회수할 수도 있다.
  • 따라서 빠른 응답시간 을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어 할 수 있다.

대표적인 예시

  1. SRT(Shrtest Remaining Time) 스케줄링
  2. 라운드로빈(Round-Robin) 스케줄링
  3. 다단계 큐(Multi-level Queue) 스케줄링
  4. 다단계 피드백 큐 스케줄링

비선점 스케줄링(Non-Preemptive Scheduling)

  • 어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나, 입출력 요구가 발생하여 자발적으로 중지될 때 까지 계속 실행되도록 보장한다.
  • 순서대로 처리되는 공정성이 있고, 다음에 처리해야할 프로세스와 상관없이 응답시간을 예상할 수 있다.
  • 선점방식보다 스케줄러 호출 빈도가 낮고, 문맥교환에 의한 오버헤드가 적다.
  • 일괄처리 시스템에 적합
  • 자칫 CPU사용시간이 긴 CPU사용시간이 프로세스가 다른 프로세스들으르 대기시킬수 있으므로 처리율이 떨어질수 있다.(단점)

대표적인 예시

  1. HRN(Highest response ratio next) 스케줄링
  2. SJF(Shortest Job First) 스케줄링
  3. 우선순위(priority) 스케줄링
  4. 기한부(Deadline) 스케줄링
  5. FIFO 스케줄링

선점스케줄링과 비선점 스케줄링

비교할때 뺏을수 있냐 , 지가 직접 반환하냐로 구분하면 될것같다.

Dispatcher 란?

CPU의 제어를 단기 스케쥴러가 선택한 프로세스에게 부여하는 모듈.

  • 문맥을 교환하는 일을 한다.
  • 사용자 모드를 전환하는 일을 한다.
  • 프로그램을 다시 시작하기 위해서 사용자 프로그램의 적절한 위치로 이동하는 일을 한다.
  • 디스패치 지연(Dispatch latency) : 디스패처가 한 프로세스를 중단시키고 다른 프로세스의 수행을 시작하도록 하는 시간이다.

스케줄링이 일어나는 시점

스케쥴링은 다음과 같은 프로세스의 상태변화가 일어날 때 발생된다.

image

1.수행 -> 대기 (Running->Waiting) : I/O요청이 발생하거나, 자식 프로세스가 종료 대기를 할 때

2.수행 -> 준비 (Running->Ready) : 인터럽트가 발생했을때

3.대기 -> 준비 (Waiting -> Ready) : I/O가 완료되었을때

4.수행 -> 종료 (Running -> Terminate)

여기서 1,4은 프로세스가 스스로 CPU를 반환하기에 비선점 스케쥴링이 발생되고 2,3은 강제로 할당해야 하므로 선점 스케쥴링 방식이다.

스케줄링의 단계별 비교

요구되는 시점으로 구분한다.

  • 장기 스케줄러.(Job-Scheduler)
    • 어떤 작업이 시스템에 들어와서 처리될 것인가를 결정.(Job Scheduling)
  • 일괄처리 : 작업이 들어오면 디스크에 두고 일괄처리 큐에서 대기후 장기 스케줄러를 거쳐 프로세스가 되도록 함.
    • 시분할 : 사용자의 접속시도를 허용할지 말지 결정.
  • 다중 프로그래밍 정도를 조절
    • 수행횟수가 적고 대부분 FIFO방식을 사용
    • 오프라인 작업을 위한 일괄처리 큐를 별도로 유지하는 경우에 필요
    • 실행된 작업을 하드디스크로부터 메모리로 적재.
  • 중기 스케줄러.
    • 보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가 (Swapping)
  • 단기 스케줄러.(CPU-Scheduler)
    • 준비상태의 프로세스 중에서 어느 프로세스에게 CPU를 할 당할지 결정.
    • 프로세스 스케줄러 or Dispatcher에 의해 수행.
    • 가상메모리 체제에서 너무 많은 프로세스가 적재되면 하드디스크 입출력이 과다해져서 시스템이 거의 멈추는 현상이 발생한다(Trashing).
    • 스와핑(swapping) – 일부 프로세스를 메모리에서 디스크로 내보내고(swap-out), 시간이 흘러 메모리의 여유가 생기면 다시 적재(swap-in)

스케쥴링 알고리즘

좋은 스케줄링이란?

  • CPU 사용률이 높게 스케줄링.
  • 처리량이 높다.
  • 우선순위가 높은 프로세스를 먼저 수행 하고 처리.
  • 문맥교환에 들어가는 오버헤드를 최소화
  • 작업을 요청했을 때 반응하는 데 걸리는 응답시간을 최소화.
  • 프로세스를 시작하여 실행을 완료하는 데 걸리는 반환시간을 최소화.
  • 무한정 대기하는 작업이 발생하지 않게 한다.(Starvation - 기아현상)

선점 스케줄링

1. SRT(Shortest Remaining Time) 스케줄링

  • 최단 잔여시간을 우선으로 하는 스케줄링.

  • 진행 중인 프로세스가 있어도, 최단 잔여시간인 프로세스를 위해 sleep시키고 짧은 프로세스를 먼저 할당한다.

  • 선점형 SJF 스케줄링이라 불린다.

  • 프로세스도착시간Burst Time종료시간Waiting TimeTurnaround Time
    P10817917
    P214504
    P329261524
    P4351027

  • P1 → P2 → P3 → P4 순서대로 왔어도 도착시간에서의 잔여 시간을 비교해 CPU를 할당한다.

  • image

2. Round Robin (라운드 로빈)

  • 정해진 시간할당량만큼 프로세스를 할당한 뒤, 작업이 끝난 프로세스는 준비완료 큐(순환큐)의 가장 마지막에 가서 재할당을 기다린다.
  • 시간 할당량이 중요하다
    • 너무 작으면 Context Switching이 너무많이 발생하여 문제
    • 너무 길면 FCFS와 다를바 없다.
  • 선점형 알고리즘 이다. 하다 중간에 멈추니까.

image

3.Multilevel-Queue (다단계 큐)

  • 준비완료 큐를 여러개의 큐로 분류하여 각 큐가 각각 다른 스케쥴링 알고리즘을 가지는 방식.
  • 큐와 큐사이에도 스케줄링이 필요하다.
    • 우선순위 방식 혹은 시분할 방식으로 한다.
      • 우선순위 방식
        • 고정 우선순위 선점 방식으로 구현, 우선순위에 따른 큐의 스케줄링은 필수적이다.
        • 우선순위가 높은 Forground Queue
          • 대화형 프로세스를 위한 큐
          • Round Robin
        • 우선순위가 낮은 Background Queue
          • 연산작업을 처리하는 프로세스 큐
          • FCFS
        • 여기서 Forground큐가 비어있지 않는한 Background큐가 먼저 실행될 수 없으며, Background큐가 먼저 실행중이더라도 Forground큐에 프로세스가 들어오면 선점된다.

4. Multilevel-Feedback-Queue (다단계-피드백 큐)

  • 기존 다단계 큐 방식은 특정프로세스가 큐에 고정되는 방식
  • 여기서는 큐와 큐사이에 프로세스가 이동하는 걸 허용한다.
  • 큐를 구분하는 기준은 CPU버스트
  • 입출력 중심의 프로세스와 대화형 중심의 프로세스를 높은 우선순위의 큐에 넣는다.
    • 기아상태를 예방하기위한 노화정책(aging)도 진행된다.
  • 다단계 큐와 비교했을때 구현이 복잡하다.
    • 프로세스를 버스트타임이나 기타 우선순위에 따라서 큐에 올리거나 내리고 해야되는 부분 때문.

비선점 스케줄링

1. HRN(Highest response ration next) Scheduling

  • 짧은 작업에 유리한 SJF의 단점을 개선 한 기법, 각 작업의 우선순위로 서비스 해주는 스케줄링
  • 에이징 : 오랫동안 대기하는 프로세스의 우선순위를 증가시키는 방법
  • 기아상태를 해결할수 있다.
  • 우선순위 = (대기시간+서비스시간) / 서비스시간

2. SJF(Shorted Job First)

  • 최단 작업 우선 스케쥴링 알고리즘. (최단 작업이란 CPU 버스트 타임이 가장 짧은 프로세스.)

  • 가장 적은 평균 대기시간 을 가진다.

  • CPU 버스트 시간이 동일하다면 FCFS방식을 따른다.

  • 비선점형 스케줄링

    • 중간에 빨리끝나는 프로세스가 있어도 일단 시작한 프로세스를 먼저 끝낸다.

  • 아래의 경우는 비선점의 경우임.

    image

3. Priority Scheduling(우선순위 스케쥴링)

  • 미루어진 프로세스의 우선순위에 따라서 스케줄링하는 방식 이다. SJF도 Priority Scheduling 의 일종이다.그냥 최소 버스트 시간 기준일뿐.

  • 우선순위가 낮은 프로세스는 할당 되지 않기도 한다. 이를

    기아(Starvation)

    이라 한다.

    • 이에대한 해결 방법 - Aging(노화)
      • 기다리는 시간에 따라 우선순위를 증가 시켜주는 방식이다.
      • 우선순위가 같다면 FCFS를 적용한다.

  • 이것도 선점형과 비선점형이 둘다 있다.

image

4. Deadline Schedulling(기한부 스케쥴링)

  • 작업을 명시된 시간이나 기한 내에 완료하도록 계획

5. FCFS(First Come, First Serve) -> FIFO라고 하기도함.

  • 선입 선처리 스케쥴링. CPU를 요구하는 순으로 할당한다.
  • 비선점형 스케줄링
  • 먼저 도착한 프로세스를 먼저 처리하는 알고리즘.
  • 비 선점형 FIFO큐를 이용하여 간단하게 구현한다.

image

Reference

  • https://github.com/qkraudghgh/coding-interview/blob/master/OS/CPUScheduling.md
  • https://dduddublog.tistory.com/23
  • https://m.blog.naver.com/three_letter/220334644682
  • https://preamtree.tistory.com/19
  • https://chobodogfootruler.tistory.com/17
  • https://hyunah030.tistory.com/4


on Cs, Operating System, Operating-system