프로세스 스케줄링

몽이·2022년 7월 1일
0

운영체제

목록 보기
4/9

프로세스 스케줄링(Scheduling)

1) 프로세스 스케줄링의 개념

(1) 프로세스 스케줄링의 정의

  • CPU를 사용하려고 하는 프로세스들 사이의 우선 순위를 관리하는 것이다.
  • 장기, 중기, 단기 스케줄링이 있다.
    • 장기 스케줄링 : 어떤 프로세스를 커널에 등록할 것인가를 결정
    • 중기 스케줄링 : 어떤 프로세스에게 메모리를 할당할 것인가를 결정
    • 단기 스케줄링 : 어떤 프로세스에게 CPU를 할당할 것인가를 결정

(2) 프로세스 스케줄링의 원칙

  • 공정하게 배정되어야 하며 처리 응답 시간이 신속해야 한다.
  • 단위 시간당 가능한 최대의 처리가 될 수 있도록 해야 한다.
  • 응답 시간과 자원 활용 간의 적절한 균형이 유지되도록 해야 한다.

(3) 바람직한 프로세스 스케줄링 정책

  • CPU 이용률, 처리 능력을 높일 수 있도록 스케줄링한다.
  • 대기 시간, 응답 시간, 반환 시간을 줄일 수 있도록 스케줄링한다.

2) 비선점형(Non Preemption) 스케줄링

(1) 비선점형 방식의 개념

  • 현재 실행 중인 프로세스를 다른 프로세스가 강제적으로 중단시킬 수 없는 방식이다.
  • CPU를 사용하는 현재 프로세스가 종료되면 다른 프로세스에 CPU를 할당한다.
  • 응답 시간의 예측이 용이하며, 일괄 처리 시스템에 적당하다.
  • FIFO, SJF, HRN 등이 있다.

(2) FIFO(First In First Out)

  • 프로세스가 도착(입력)한 순서대로 처리한다.
  • 알고리즘이 가장 간단하지만, 평균 반환 시간이 길다.
    • 평균 실행 시간 = 총 실행 시간 / 프로세스 개수
    • 평균 대기 시간 = 총 대기 시간 / 프로세스 개수
    • 평균 반환 시간 = 평균 실행 시간 + 평균 대기 시간
    작업실행시간도착 시간대기 시간
    A2400
    B6124-1=23
    C3230-2=28
    평균 실행 시간11평균 대기 시간17
    평균 반환 시간28

(3) SJF(Short Job First)

  • 실행 시간이 가장 짧은 프로세스 순으로 처리한다.

  • 실행 시간이 긴 작업일 경우 무한 대기(기아) 상태가 발생할 수 있다.

  • 짧은 시간의 작업들이 많은 경우에 FIFO보다 평균 대기 시간이 작다.

    작업실행시간도착 시간대기 시간
    A2400
    B6127-1=26
    C3224-2=22
    평균 실행 시간11평균 대기 시간16
    평균 반환 시간27

(4) HRN(Highest Response-ratio Next)

  • FIFO와 SJF의 단점을 보완하여 개발된 방법이다.

  • 대기 시간이 긴 프로세스의 우선순위를 높여서 긴 작업과 짧은 작업간의 지나친 불평등을 해소할 수 있다.

  • HRN 우선순위 공식의 계산 결과가 큰 작업에 높은 우선순위를 부여(Aging)한다.

    • 우선순위 = (실행 시간) + (대기 시간)/(실행 시간)
    작업실행시간대기 시간우선 순위
    A20101.5
    B4206
    C6102.6

3) 선점형(Preemption) 스케줄링

(1) 선점형 방식의 개념

  • 현재 실행 중인 프로세스를 다른 프로세스가 강제적으로 중단시킬 수 있는 방식이다.
  • 다른 프로세스가 현재 사용 중인 프로세스를 중단시키고 CPU를 차지할 수 있다.
  • 빠른 응답 시간을 필요로 하는 대화식, 시분할, 실시간 처리에 적당하다.
  • RR, SRT, MFQ 등이 있다.

(2) RR(Round Robin)

  • 동일한 Time Slice를 사용하는 시분할 처리 시스템에 효과적으로 적용된다.

  • Time Slice 동안만 순서대로 프로세스를 처리하는 방식이다.

  • Time Slice가 실행 시간보다 크면 FIFO와 동일한 결과를 보인다.

  • Time Slice가 5초인 RR의 평균 반환 시간 계산

    작업실행 시간도착 시간
    A100
    B182
    C55
    D36
  • 계산 공식은 FIFO의 공식과 같다.

    작업ABCD
    남은 시간51300
  • C의 대기 시간 : 10 - 5 = 5

  • D의 대기 시간 : 15 - 6 = 9

    작업ABCD
    남은 시간0800
  • A의 대기 시간 : 15

    작업ABCD
    남은 시간0000
  • B의 대기 시간 : 20

  • 평균 실행 시간 = (10 + 18 + 5 + 3) / 4 = 9

  • 평균 대기 시간 = (15 + 20 + 5 + 9) / 4 = 12.25

  • 평균 반환 시간 = 9 + 12.25 = 21.25

(3) SRT(Shortest Remaining Tiime)

  • 작업이 끝나지 않은 프로세스의 남아 있는 실행 시간이 가장 작은 프로세스를 먼저 실행하는 방식이다.
  • SJF 기법을 선점 형태로 변경한 기법으로, 점유 시간이 길어도 중요한 프로세스를 먼저 할당할 수 있다.

(4) MFQ(Multilevel Feedback Queue)

  • 짧은 작업이나 입출력 위주의 프로세스에 우선순위를 부여하기 위해 개발된 방식이다.
  • 우선순위가 있는 각 큐(대기 리스트)가 있으며 큐마다 Time Slice가 존재한다.
  • 낮은 큐일수록 Time Slice는 커지며, CPU 사용을 마친 프로세스는 낮은 큐로 이동된다.
  • 맨 마지막 단계의 큐는 RR 스케줄링 방식을 사용한다.
profile
풀스택 개발자가 되는 날까지 달리자!

0개의 댓글