스케줄링

정의

프로세서 스케쥴링이란, 프로세스가 생성되어 실행할때, 필요한 여러자원을 할당하는 작업입니다.

CPU 스케쥴링이란, 어느 작업이 CPU를 사용할 것인지 결정하는 작업입니다.

• 이때, 생성되어 완료될때까지 프로세스는 여러 종류의 스케줄링 과정 거치게 됩니다.
• 목적 : CPU나 자원을 효율적으로 사용하기 위해 씁니다.
  • 공정성, 처리율 증가, CPU 이용률 증가, 우선순위 제도, 오버헤드 최소화, 응답시간 최소화, 반환시간, 반환시간 최소화, 대기시간 최소화

말 : 여러 프로세스들이 존재하고, 이 프로세스들이 자원 ( CPU 등 )을 동시에 요구하는 경우가 발생하게 되면, 자원은 부족하게 되어 문제가 발생하게 됩니다. 이때 제한된 자원들을 어떤 기준과 방식으로 나눠줄 것인지에 대한 결정하는 정책입니다. 이를 프로세스 스케줄링이라고 합니다. 이를 이용하면 다중 프로그래밍이 가능하게 됩니다.

말 : 하나인 CPU는 동시에 여러 프로세스를 처리할 수 없습니다. 따라서 한 순간에 특정 프로세스를 지정하여 CPU를 사용할 수 있도록 결정해야 하는데 이를 CPU 스케줄링이라고 합니다. 이것은 여러 프로그램이 번갈아 수행되도록 스케줄링 합니다. 이로인해, CPU 이용률이 극대화됩니다.

좋은 스케쥴링

• CPU 사용 효율이 높게 스케쥴링합니다.
• 우선 순위가 높은 프로세스를 먼저 수행하고 처리합니다.
• 문맥 교환에 들어가는 오버헤드를 최소화합니다.
• 작업을 요청하였을 때, 반응하는데 걸리는 응답 시간을 최소화합니다.
• 프로세스를 시작하여 실행을 완료하는데 걸리는 반환 시간을 최소화합니다.
• 무한정 대기하는 작업이 발생하지 않게 합니다.

스케줄링 종류

1. 장기 스케줄링

   어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태를 큐로 보내는 작업

   다른 말 : 작업 스케줄링, 상위 스케줄링

2. 중기 스케줄링

   어떤 프로세스가 CPU를 할당 받을 것인지 결정하는 작업을 의미

   CPU를 할당받으려는 프로세스가 많을 경우 프로세스를 일시 보류시킨 후 활성화해서 일시적으로 부하를 조절

3. 단기 스케줄링

   프로세스가 실행되기 위해 CPU 할당받는 시기와 특정 프로세스를 지정하는 작업을 의미

   다른말 : 프로세서 스케줄링, 하위 스케줄링

프로세서 스케쥴링 기법

비선점형 스케쥴링

• CPU를 점유하는 작업이 있을 때, 다른 프로세스는 강제로 CPU를 점유할 수 없습니다.
• 프로세스가 한번 스케줄링 되면, 그 프로세스가 끝날때까진 다른 프로세스는 끼어들 수 없다.
• 프로세스가 CPU 할당받으면 해당 프로세스가 완료될 때까지 CPU 사용
• 일괄 처리 방식의 스케쥴링
• 프로세스 응답 시간 예측 가능
• 단점 : 중요하지 않는 작업이 CPU를 점유하고 있다면, 중요한 작업이 대기하는 상황이 발생
• 종류 : FIFO, SJF, HRN, 우선순위 등
  • FIFO
    • 먼저 대기하는 작업을 먼저 CPU 사용하게 하는 방법
    • 가장 단순
    • First In First Out
  • SJF
    • 실행 시간이 짧은 프로세스를 먼저 CPU 사용하게 하는 방법
    • 탐욕 기법에 의해 평균 대기 시간을 최소로 만듬
    • 단점 : 실행 시간이 긴 프로세스는 무한 대기 상태 빠질 수 있음
    • Shortest Job First
  • HRN
    • 대기 시간과 실행 시간을 혼합하여 어느 작업이 CPU 사용할 지 결정
    • HRN 값 = ( 대기 시간 + 실행 시간 ) / 실행 시간
    • Highest Response Rate Next
  • 우선순위
    • 우선 순위가 높은 작업이 먼저 CPU를 사용하게 하는 방법
    • 단점 : 우선순위가 낮은 작업이 무한 대기 상태 빠질 수 있음

선점형 스케쥴링

• CPU를 점유하는 작업이 실행 중일때, 우선 순위가 높은 프로세스는 강제로 CPU를 점유 가능

• 현재 실행중인 프로세스를 중간에 멈추고 문맥교환을 이용하여 다른 프로세스가 중간에 끼어들 수 있다

• 단, 선점이 가능하도록 일정 시간 배당에 대한 *인터럽트용 타이머 클록이 필요 ( 독점 방지 )

• 대화식 시분할 시스템에 사용하는 스케줄링 → 주로 빠른 응답시간 요구할 때 사용하는 방식

• 장점 : 우선순위 높은 프로세스를 빠르게 처리

• 단점 : 잦은 문맥 교환에 오버헤드 발생

• 종류 : Round Robin, SRT, 다단계 큐, 다단계 피드백 큐

  • RR

    • 대기 큐를 사용하여 먼저 대기한 작업이 먼저 CPU 사용
    • Response Time을 최소화 하기 위해 time quantum 만큼 돌아가며 스케줄
    • 지정된 CPU를 사용할 수 있는 시간 후 다시 대기큐에 배치하여 대기
    • Quantum이 작으며 작업 시간이 작은 프로세스에 유리
    • Round Robin

  • SRT

    • 현재 실행 중인 프로세스의 남은 시간과 대기큐에 프로세스의 실행 시간이 가장 짧은 프로세스가 CPU 사용
    • Shortest Ramaining Time

  • 다단계 큐

    • 프로세스의 우선 순위에 따라 대기하는 큐를 다르게
    • Multi Level Queue

  • 다단계 피드백 큐

    • 다단계 큐 방식에서 오래 대기한 프로세스가 높은 레벨의 대기 큐로 이동

    • 여러 개의 ready queue를 사용하여, queue마다 우선순위와 time quantum을 할당하고, 프로세스가 들어오면 가장 상위 queue에 넣었다가, time quantum이 지나면 하위 queue로 끌어내림

      이때 가장 하위의 queue에서는 RR방식 스케줄링을 한다.

      일정 시간동안 수행되지 못하고 남아있는 프로세스는 다시 상위 큐로 끌어올려준다.

• 인터럽트용 타이머 클록 : 하나의 시스템 내에서 동작하는 장치들을 감시하기 위해 주기적인 신호를 발생하는 것으로, 하나의 프로세스가 자원을 독점하지 못하도록 방지하기 위해 사용