Computer Science/Operating System

운영체제 - 프로세스 스케줄링

개발사전 2021. 9. 21. 18:08

자원 관리 정의

컴퓨터 자원을 효율적으로 관리하는 것.

 

자원 관리 종류

 

1. 시간 분할 관리 : CPU 자원을 시간으로 분할하여 사용. (프로세스 스케줄링 = CPU 스케줄링)

2. 공간분할 관리 : 메모리 공간을 분할하여 사용. (메모리 관리)

 

프로세스 스케줄링 정의

자원을 어느 시점에 어떤 프로세스에게 줄 것인가 결정.

스케줄링이 필요 없는 프로세스 : 인터럽트 처리, 오류 처리, 사용자의 시스템 호출

스케줄링이 필요한 프로세스 : 사용자 프로세스, 시스템 프로세스

 

프로세스 스케줄링 목적

 

1. 자원을 공정하게 사용하기 위해

2. 우선순위가 높은 작업을 먼저 처리하기 위해

3. 단위 시간당 처리량을 높이기 위해

4. 적절한 반환시간을 보장해주기 위해

 

스케줄링 선택 기준

 

1. 시스템 특성에 맞는 스케줄링 선택

2. 우선 순위에 맞는 스케줄링 선택

3. 총 실행시간이 짧은 스케줄링 선택

4. 프로세서 버스트

5. 입출력 버스트

프로세서 버스트 : 프로세스가 프로세서를 사용할 때
입출력 버스트 : 프로세스가 입출력 결과를 기다리고 있을 때
입출력 중심 프로세스 → 프로세서 중심 프로세스 : 짧은 지연
프로세서 중심 프로세스 → 입출력 중심 프로세스 : 긴 지연
프로세서 버스트와 입출력 버스트를 적절히 혼합하여 스케줄링해야 함.

프로세서 버스트와 입출력 버스트

스케줄러 종류

 

1. 장기 스케줄러(Long-term scheduler, job scheduler)

디스크에서 메모리로 어떤 작업을 올릴지 결정.

드물게 수행되는 스케줄러.

메모리에 몇 개의 프로그램을 올릴지 제어하는 역할.(degree of Multiprogramming)

보통의 컴퓨터(time sharing system)에서는 장기 스케줄러가 없음.

 

2. 중기 스케줄러(Medium-term scheduler, Swapper)

어떤 프로세스를 스왑 인, 스왑 아웃을 할지 결정.

I/O로 인해 실행 중인 프로세스가 CPU를 사용하지 않을 때 대기 상태로 변경.

메모리에 몇 개의 프로그램을 올릴지 제어하는 역할.(degree of Multiprogramming)

장기 스케줄러와 단기 스케줄러 사이를 중재해줌.

중기 스케줄러가 생기며 프로세스의 상태 중 "Suspended(stopped)" 상태가 생김.

 

3. 단기 스케줄러(Short-term scheduler, CPU scheduler)

메모리에 준비 상태로 있는 프로세스 중 어떤 프로세스를 실행시킬지 결정.

준비 상태인 프로세스를 디스패처(프로세스에 프로세서를 할당해줌)로 실행 상태로 변경함.

가장 자주 수행됨.

충분히 빨라야 함

 

※ 시분할 시스템에서는 장기 스케줄러가 없고, 계속해서 메모리에 프로세스를 올리기만 합니다. 프로그램이 시작되면 무조건 메모리에 올라가 Ready 상태가 됩니다. 하지만 메모리에 프로세스가 너무 많이 올라가도 각 프로세스 별 갖고 있는 메모리 공간이 작아, CPU가 해당 프로세스를 작업할 때 필요한 데이터가 없어 I/O가 자주 발생하게 되는 문제가 발생하고, 너무 적게 올라가도 메모리에 올라온 프로세스가 모두 I/O 작업을 수행하면 CPU가 놀게되는 문제가 발생합니다. 이를 중재하기 위해 중기 현대에는 중기 스케줄러를 사용합니다.

장기, 중기, 단기 스케줄러와 프로세스 상태

스케줄링 단계

 

1. 작업 스케줄링 : 어떤 작업에 자원을 할당할지 선택하는 스케줄링 (장기 스케줄러)

2. 작업 승인& 프로세스 결정 스케줄링 : 어떤 프로세스에 프로세서 사용 권한을 부여할지 선택하는 스케줄러 (중기 스케줄러)

3. 프로세서 할당 스케줄링 : 어떤 프로세스에 프로세서를 할당할지 선택하는 스케줄러 (단기 스케줄러)

스케줄링 단계

스케줄링 큐

 

1. 준비 큐 : 준비 상태인 프로세스가 프로세서를 할당받기 위해 기다리는 곳.

2. 입출력 장치 큐 : 입출력 장치를 사용하기 위해 프로세스가 기다리는 곳.

스케줄링 큐

 

스케줄링 큐 구조

 

큐는 PCB를 연결 리스트로 연결한 구조.

head 부분은 첫 번째 PCB, tail은 마지막 PCB를 가리킴.

스케줄링 큐 구조(연결 리스트)

스케줄링 알고리즘 종류

 

1. 선점 스케줄링(RR, SRTF, MLQ, MFQ)

  • 다른 프로세스가 프로세서 제어권을 빼앗을 수 있음.
  • 빠른 응답 시간을 유지할 수 있음.
  • 우선순위가 존재.
  • 우선순위가 높은 프로세스를 긴급하게 처리할 때 유용.
  • 자주 프로세스를 바꿔 오버헤드가 발생.

2. 비선점 스케줄링(FIFO, SJF, HRRN)

  • 응답 시간을 예측할 수 있음.
  • 오버헤드가 선점 스케줄러에 비해 적음.
  • 모든 프로세스가 공정하게 프로세서를 사용함.

알고리즘 선택 기준

 

1. 처리율 : 시간당 처리하는 작업 수가 많아야 함.

2. CPU 사용률 : CPU가 유휴시간 없이 계속 사용되고 있어야 함.

3. 반환 시간 : 작업이 완료하기까지 걸리는 시간을 최소화해야 함.

4. 대기 시간 : 작업이 프로세서를 할당받기 위해 기다리는 시간이 최소화해야 함. 이를 위해 준비 큐 안에 프로세스 개수를 제한해야 함.

5. 반응 시간 : 작업 요청 후 첫 번째 출력을 하기까지 걸린 시간으로 최소화해야 함.

작업 진행 상태에 따른 시간

스케줄링 알고리즘

 

공평성 중시 알고리즘 : FIFO(FCFS), RR

효율성 중시 알고리즘 : SJF, SRTF, HRN

 

※ 효율성 중시 알고리즘을 사용하기 위해서는 실행 시간을 알 수 있어야 하는 문제가 있습니다. 또한, 실행 시간을 예측하는데 부하가 발생합니다.

 

1. 선입선출 알고리즘(FIFO, FCFS)

  • 비선점 알고리즘
  • CPU를 먼저 요청한 프로세스가 먼저 실행됨
  • 장점
    1. 스케줄링 구현과 이해가 단순함.
    2. 오버헤드가 적음
    3. 일괄처리 시스템에 매우 효율적
  • 단점
    1.  응답 시간이 느림
    2.  호위 효과(convoy effect) : 긴 프로세스가 실행되는 동안 짧은 프로세스가 기다리는 현상

선입 선출 알고리즘

2. 라운드 로빈 알고리즘(RR)

  • 비선점 알고리즘
  • 시간 할당량을 정해 그 시간만큼만 프로세스 처리
  • 시분할 시스템을 위해 개발
  • 준비 큐를 순환 큐로 설계
  • 큐 자체는 FIFO로 설계하여 시간 할당량이 지난 프로세스를 제일 끝으로 이동
  • 장점
    1. 대부분 대화식 프로세스는 시간 할당량보다 짧은 시간 동안 프로세서를 사용하므로 빠른 반응 가능
    2. 모든 프로세스가 공정하게 프로세서를 사용하므로 기아 현상 발생하지 않음
    3. FIFO, SJF보다 평균 대기시간이 짧음
  • 단점
    1. 시간 할당량이 작으면 문맥 교환이 빈번하게 발생하여 오버헤드가 커짐(시간 할당량을 적당한 크기로 해줘야 함)

라운드 로빈 알고리즘

3. 우선순위 알고리즘

  • 선점 or 비선점 알고리즘
  • 프로세스의 우선순위를 비교하여 우선순위가 높은 프로세스부터 실행
  • 우선순위가 낮은 프로세스는 기아 상태에 빠질 수 있음
  • 실시간 시스템에 사용

4. 최소 작업 우선 알고리즘(비선점 : SJF, SPN 선점 : SRTF, SRTN)

  • 선점 or 비선점 알고리즘
  • 작업 시간이 가장 짧은 프로세스를 먼저 실행
  • 장점
    1. 평균 대기시간 최소화
    2. 시스템 내 프로세스 수 최소화(스케줄링 부하 감소, 메모리 절약)
    3. 빠른 응답
  • 단점
    1. 기아 현상 발생
    2. 매우 불공정함
    3. 정확한 실행 시간을 알 수 없음
    4. 선점일 경우 문맥 교환에 따른 오버헤드 발생

6. HRN 알고리즘(HRN, HRRN)

  • 비선점 알고리즘
  • SJF의 기아 현상 문제를 해결하기 위해 개발
  • 에이징 기법을 통해 대기 시간을 고려하여 우선순위를 선정함
  • 서비스받을 시간(실행 시간)을 예측할 수 있는 방법 필요

HRN의 우선순위

7. 다단계 큐 알고리즘(MLQ)

  • 선점 알고리즘
  • 작업을 서로 다른 묶음으로 묶을 수 있을 때 사용
  • 준비 큐를 작업 별로 하나씩 가짐
  • 큐는 자신만의 독자적인 스케줄링을 사용
  • 장점
    1. 빠른 응답
  • 단점
    1. 프로세스가 다른 큐로 이동 불가
    2. 여러 큐가 각기 다른 스케줄링을 수행하여 오버헤드가 발생
    3. 낮은 우선순위의 준비 큐는 실행되지 못하는 기아 현상 발생

다단계 큐 알고리즘

8. 다단계 피드백 큐 알고리즘(MFQ)

  • 선점 알고리즘
  • MLQ의 큐 간에 프로세스 이동 불가 문제를 해결하기 위해 만들어짐
  • 프로세스의 실행 시간이 길면 우선순위가 낮은 큐에서 대기
  • 입출력 중심 작업은 높은 우선순위 큐(실행시간이 짧기 때문)
  • 프로세서 중심 작업은 낮은 순위 큐(실행시간이 길기 때문)
  • 장점
    1. 준비 큐 간에 프로세스 이동 가능
    2. 에이징 기법(오래 기다리는 프로세스를 높은 우선순위 큐로 이동)을 통해 기아 현상 방지