운영체제 #2

[yoonminsang]

4. 스케줄링 알고리즘

1. 선입선출 스케줄링(First-Come First-Served: FCFS)

• 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
• 콘보이 현상(Convoy effect): CPU 버스터가 긴 프로세스가 먼저 도착하면 이후 CPU 버스트가 짧은 프로세스들이 실행되지 않기 때문에 평균 대기시간이 길어진다.

2. 최단작업 우선스케줄링(Shortest-Job Fist: SJF)

• CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
• 평균 대기시간을 가장 짧게 하는 최적 알고리즘
• 비선점형(nonpreemptive) 방식: CPU를 획득하면 자진 반납하기 전까지는 CPU를 빼앗지 않는 방식
• 선점형(preemptive) 방식: 준비 큐에서 CPU 버스트가 가장 짧은 프로세스에게 CPU를 할당했다 하더라도, CPU 버스트가 더 짧은 프로세스가 도착할경우 CPU를 빼앗아 더 짧은 프로세스에게 부여하는 방식. SRTF(Shortest Remaining Time First)
• 현실적으로 어려운건 프로세스의 CPU 버스트 시간을 미리 알 수 없다.
• τₙ₊₁ = α·tₙ + (1-α)·τₙ
  (τₙ: n번째 CPU 버스트 시간,
  α: 0과 1 사이의 상수. 어느정도 반영할지 조절하는 매개변수
  더 오래된 과거일수록 영향력이 적어짐)
• 평균 대기시간을 줄이는게 항상 좋은건아니다.
• 기아 현상(starvation):CPU 버스트가 짧은 프로세스가 계속 도착할경우 기존 프로세스는 영원히 CPU를 할당받지 못한다.

3. 우선순위 스케줄링(priority scheduling)

• 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
• 우선순위는 CPU 버스트 시간 등 다양한 값을 정의할 수 있음.
• 비선점형, 선점형 방식 모두 존재
• 기아현상이 발생할 수 있기 때문에 노화(aging) 기법을 사용할 수 있다.
• 노화 기법: 시간이 길어지면 조금씩 우선순위를 높여서, 언젠가는 가장 높은 우선순위가 된다.

4. 라운드 로빈 스케줄링(Round Robin scheduling)

• 지금까지와 달리 시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링
• 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 CPU를 회수해 다음 준비 큐의 프로세스에게 CPU를 할당한다.
• 공정하다는 장점
• 할당시간(time quantum): 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간
• 할당시간이 너무 길면 FCFS와 같다.
• 할당시간이 너무 짧으면 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 커진다.
• 일반적으로는 수십 밀리초 정도로 설정한다.
• 기본적인 목적: CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록 하는 것과 동시에,
  CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것.

5. 멀티레벨 큐(multi-level queue)

• 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법
• 일반적으로 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 둔다.
• 일반적으로 준비큐는 대화형 작업을 담기 위한 전위 큐(foreground queue), 계산 위주의 작업을 담기 위한 후위 큐(background queue)
• 전위 큐에서는 응답시간을 짧게 하기 위해 라운드 로빈, 후위 큐에서는 응답시간이 중요하지 않기 때문에 FCFS 스케줄링
• 큐 자체에 대한 스케줄링: 여러개의 준비 큐에 대해 어느 큐에 먼저 CPU를 할당할것인지.
  • ex) 고정 우선순위 방식(fixed priority scheduling): 큐에 고정적인 우선순위 부여
  • 타임 슬라이스 방식. 기아 현상을 해소. 각 큐에 CPU 시간을 적절한 비율로 할당

6. 멀티레벨 피드백 큐(Multilevel Feedback Queue)

• 멀티레벨 큐와 거의 동일한데, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.
• ex) 노화 기법을 사용할 수 있다. 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격
• 라운드 로빈(할당시간 5) > 라운드 로빈(할당시간 10) > FCFS
  • CPU 사용시간이 짧은 대화형 프로세스들은 우선순위가 가장 높은 큐에서 서비스 받고 작업 온료
  • CPU 버스트 시간이 긴 프로세스들은 할당시간이 10인 하위큐로 내려감.
  • 이후에도 완료되지 않으면 CPU를 오래사용하는 계산 위주의 프로세스로 간주 FCFS 적용
• 라운드 로빈 스케줄링을 한층 더 발전.
  프로세스의 CPU 작업시간을 다단계로 분류.
  작업시간이 짧은 프로세스일수록 더욱 빠르게,
  작업시간이 긴 프로세스는 문맥교환 없이 CPU 작업에만 열중할 수 있는 FCFS 방식 채택

7. 다중처리기 스케줄링(multi-processor system)

• CPU가 여러 개인 시스템
• CPU가 하나인 시스템에서보다 더욱 복잡하다.
• 프로세스를 준비 큐에 한 줄로 세워서 CPU가 알아서 꺼내어가도록 할 수 있다.
  • 그런데 반드시 특정 CPU에서 수행되어야하는 프로세스가 있는 경우 더 복잡해진다.
• 위 경우에는 여러 줄로 줄 세우기를 할 수 있다.
  • 이때 작업이 편중되는 현상이 발생할 수 있다.
  • 부하균형(load balancing) 매커니즘이 필요하다.
• 대칭형 다중처리(symmetric multi-processing): 각 CPU가 각자 알아서 스케줄링 결정
• 비대칭형 다중처리(asymmetric multiprogramming): 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 거기에 따라 움직이는 방식

8. 실시간 스케줄링(real-time system)

• 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야 한다.
• 경성 실시간 시스템(hard rea-time system): 미사일 발사, 원자로 제어 등 시간을 정확히 시켜야하는 시스템
• 연성 실시간 시스템: 데드라인이 존재하지만 지키지 못해도 위험하지는 않음. ex)멀티미디어 스트리밍
• 빠른것도 중요하지만 데드라인을 지키는게 더 중요하다. 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earliest Deadline First) 스케줄링 사용

5. 스케줄링 알고리즘의 평가

• 큐잉모델: 주로 이론가들이 수행. 확률분표로 프로세스들의 도착률, CPU 처리율을 입력값으로 주면 복잡한 수학적 계산을 통해 각종 성능지표인 CPU 처리량, 프로세스 평균 대기시간 등을 구함.
• 구현 및 실측: 이론가와 정반대인 구현가들이 수행. 커널의 CPU 스케줄링 코드를 수정해서 컴파일 한 후 시스템에 설치 + 동일한 프로그램을 이전 커널과 현재 커널에서 수행시켜서 실행시간 측정
• 시뮬레이션: 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떠한 결과가 나오는지를 확인
  • 트레이스(trace): 실제 시스템에서 추출한 입력값. 몇 초에 어떤 프로세스가 도착하고, 각각 CPU 버스트 시간을 얼마로 하는지에 대한 정보를 시간 순서대로 적어놓은 파일