cs-study-04 | 운영체제 (스케줄링)

스케줄링

• CPU가 어느 프로세스를 먼저 처리하도록 할 것인가 결정하는 것
• 목적
  • 자원 할당의 공정성
  • 단위시간당 처리량 극대화
  • 오버헤드,응답시간,반환시간,대기시간 최소화
  • 자원 사용의 균형 유지
• 스케줄링의 대상 : ready queue에 들어온 프로세스
• 스케줄링의 기법
• 선점 기법 (preemptive) : 프로세스가 CPU를 점유하고 있는 동안 I/O ( 메모리에서 읽기, 쓰기 )나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데 다른 프로세스가 해당 CPU를 강제로 점유할 수 있다. 즉, 프로세스가 정상적으로 수행중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있는 것이다
  • 비선점 기법 (nonpreemptive) : 한 프로세스가 한 번 CPU를 점유했다면 , I/O나 인터럽트 발생 또는 프로세스 종료가 될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것이다.
• 스케줄링 척도
  1. CPU 활용도
  2. 처리량
  3. 소요(반환) 시간 : 작업이 메모리에 들어가기 까지 걸린 시간, 준비 큐에 머무르는 시간, 실행시간, 입출력 시간 등 작업을 완료하는데 소요된 시간
  4. 대기 시간 : 프로세스가 실행 되기 전까지 대기되는 시간
  5. 응답(반응) 시간 : 작업을 요청한 시간부터 반응을 시작하는 시간까지의 간격

FSFC 스케줄링 (First Come First Serve )

• 비선점형 스케줄링
• CPU를 먼저 요청한 프로세스가 먼저 CPU를 배정 받는 스케쥴링 방법이다
• FIFO 큐를 사용하여 간단하게 구현 가능하다
• 호위효과 (Convoy Effect) : 앞선 프로세스가 수행하는 동안 나머지 프로세스들이 그만큼 오래 기다리는 것이 단점이다 (평균대기시간이 길어진다)
• 평균 반환시간 = (6+14+21+24) / 4 = 16.25 (동시에 도착했음)
• 평균 대기시간 = (0+6+14+21)/4 = 10.25

SJF 스케줄링 (Shortest-Job-First)

• 비선점형 스케줄링
• 가장 짧게 수행되는 프로세스가 먼저 CPU를 배정 받는 스케쥴링 방법이다
• 현실적인 컴퓨터 환경에서 프로세스의 CPU 점유 시간을 알 수 없기에 매우 비현실적이다
• 평균 반환시간 = (3+9+16+24) / 4 = 13 (동시에 도착했음)
• 평균 대기시간 = (0+3+9+16)/4 = 7

SRTF (Shortest-Remaining Time First)

0초 P1(6)

1초 P1(5) P2(8)

2초 P1(4) P2(8) P3(7) => P1(4) P3(7) P2(8)

3초 P1(3) P3(7) P2(8) P4(3) => P1(3) P4(3) P3(7) P2(8)

4초 P1(2) P4(3) P3(7) P2(8)

• SJF의 선점형 방식이다
• 먼저 온 프로세스가 CPU를 할당받고 있더라도 남은 처리 시간이 뒤에 온 프로세스의 처리 시간 보다 길면 CPU를 빼앗긴다
• 평균 대기시간이 가장 짧은 알고리즘이다
• 잦은 문맥교환이 일어나고 그에 따른 오버헤드가 커진다 , 기아현상 ( 원하는 자원을 계속 할당받지 못하는 상태 : 시간이 긴 프로세스는 영원히 CPU를 할당 받을 수 없다. ) 이 더 심각하게 발생할 수 있다
• 평균 반환시간 = P1(6-0) P4(9-3) P3(16-2) P2(24-1) »»> (6+6+14+23) / 4 = 12.25
• 평균 대기시간 = (0+3+7+15) / 4 = 6.25

p4는 3초 기다림 (6-3) /// p3는 7초 기다림 (9-2) /// p2는 15초 기다림(16-1)

HRN 스케줄링 (High Response Ratio Next)

• 비선점 스케줄링
• SJF의 단점 (실행시간이 긴 프로세스와 짧은 프로세스의 지나친 불평등 ) 을 개선한 기법, 각 작업의 우선순위로 CPU 할당 해주는 스케줄링
• CPU를 할당받기 위해 기다렸던 대기시간 또한 스케줄링 하는데 고려할 점으로 사용한다
• 우선순위 = (대기시간+실행시간) / 실행시간

우선순위 스케줄링 (Priority)

• 선점 스케줄링 & 비선점 스케줄링
• 우선순위가 높은(작은 정수 값) 프로세스가 먼저 선택된다
• 문제점 -기아(Starvation) : 우선순위가 낮아 아무리 오래 기다려도 CPU 할당을 못받는 것이다
• 해결방법 - 노화 (aging) : ready queue에서 기다리는 동안 일정 시간이 지나면 우선순위를 일정량 높여주는 것이다

라운드 로빈 스케줄링(Round-Robin)

• 선점 스케줄링
• 시분할 시스템 ( 같은 시간을 여러개로 쪼개어 병행작업을 할 때 사용하는 시스템)을 위해 설계됐다
• 시간 할당(Time quantum)만큼 수행을 한 프로세스는 큐의 마지막으로 들어가 재할당을 기다린다
• ready queue는 원형 queue이다
• 컴퓨터 자원을 사용할 수 있는 기회를 프로세스에게 공정하게 부여하는 스케줄링 알고리즘이다
• 시간 할당량이 크면 FCFS와 비슷해지고, 작아질수록 문맥교환의 오버헤드가 커지게 되서 효율이 떨어진다
• 평균대기시간 P1 (0+9) P2 (3+9+3) P3(6+9+2) P4(9) ===> (9+15+17+9) / 4 = 12.5

현재 우리의 운영체제는 Priority + RR 형태로 스케줄링 되어 있다

프로세스의 5가지 상태

• 생성 (Create) : 프로세스가 생성되는 중이다
• 실행 (Running) : 프로세스가 CPU를 차지하여 명령어들이 실행되고 있다
• 준비 (Ready) : 프로세스가 CPU를 사용하고 있지 않지만 언제든지 사용할 수 있는 상태로 CPU가 할당되기를 기다리고 있다
• 대기 (Waiting): 프로세스가 입출력 완료, 시그널 수신 등 어떤 사건을 기다리고 있는 상태를 말한다
• 종료 (Terminated) : 프로세스의 실행이 종료되었다