[OS] Scheduling

다음 번에 실행할 프로세스와 대기해야 할 프로세스를 결정하기 때문에 스케쥴링 기법의 성능은 시스템 전체 성능에 큰 영향을 미침

스케쥴링이 얼마나 효율적이냐 하는 문제는 프로세스들이 일생 동안 각종 대기 큐에서 대기하는 시간을 얼마나 줄일 수 있냐의 문제

근본적으로 대기 큐의 구조를 최적화 하는 것도 스케쥴링 성능에 중요한 요소임

• 장기 스케쥴링 (long-term)
  • 프로세스가 CPU에 실행될 수 있는 자격을 부여할지 말지 결정

• 중기 스케쥴링 (medium-term)
  • 프로세스 이미지 전부 혹은 일부가 주 메모리에 올라갈 수 있는지 자격 결정

• 단기 스케쥴링 (short-term)
  • CPU에 의해 실행될 다음 번 프로세스로 어떤 프로세스를 선택할 지를 결정

Workload

• 일련의 프로세스들이 실행하는 상황(= 프로세스가 CPU를 열마나 사용하는지)

• 가정 (비현실적)
  1. 모든 작업은 같은 시간 동안 실행
  2. 모든 작업은 동시에 도착
  3. 각 작업은 시작되면 완료될 때 까지 실행
  4. 모든 작업은 CPU만 사용
  5. 각 작업의 실행 시간은 사전에 알려져 있다

스케쥴링 평가 항목

• Turn around time
  • 성능 평가
  • $T_{turnaround} = T_{completion} - T_{arrival}$ (반환시간 = 작업 완료시간 - 작업 도착시간)

• Fairness (공정성)
  • 성능과 상충되는 스케쥴링 기준

• Response time
  • $T_{response}=T_{firstrun}-T_{arrival}$
  • 작업이 시스템으로부터 첫번째 응답이 온 시간

FIFO (First In First Out)

• 먼저 들어온 것부터 실행

• Non preemption

• Convoy effect
  • 짧게 끝나는 프로세스들이 오랫동안 자원을 사용하는 프로세스의 종료를 기다리는 현상

• non-preemption (비선점, CPU를 빼앗기지 않는)

Shortest Jop First (=SJF) , Shortest Process Next (=SPN)

• 짧은 작업 우선

• Convoy effect 해결

• Starvation (기아) 생김
  • 오래 걸리는 프로세스는 실행 안됨

• non-preemption

Shotest Time-to-Completion First (=STCF), Shotest Remaining Time (=SRT)

• 최소 잔여시간 우선

• 새로운 작업이 들어오면 현재 프로세스를 중지시키고 잔여 실행 시간이 가장 적은 프로세스를 계산하여 수행

• preemption

Highest Response Ratio Next (HRRN)

• 응답성을 높이기 위해 대기 시간 고려
  • $T_{waiting} + T_{expectedService} / T_{expectedService}$(= $(w + s) / s$ )

• non preemption

Round Robin (RR, Time Slicing)

• 일정 시간(= time slice, scheduling quantum) 동안 실행한 후에 실행 큐의 다음 작업으로 전환

• preemption

• 현대 OS와 가장 유사, 동일하지는 않음

성능 비교

I/O 고려

• I/O 요청이 있으면 I/O를 마칠 때까지 해당 프로세스 Block(Sleep)
  • I/O를 마치면 인터럽트: block→ready
  • 가능하면 많은 프로세스를 메모리에 올려두고, ready 상태인 프로세스를 많이 올려두게 하면 성능이 높아짐

초기 Unix 스케쥴링

$Priority = (최근 CPU 사용량) / 2 + 60$ (60은 기본 수준 사용자 우선순위)

• I/O하면 CPU Count 값이 증가하지 않아서 우선순위가 높아짐

MLFQ (Multi Level Feedback Queue)

• 목적

  1. 짧은 작업을 먼저 실행시켜 반환 시간 최적화

  2. 응답시간을 최적화 하여 대화형 사용자(화면을 보는 사용자)에게 응답이 빠른 시스템이라는 느낌을 줌

• 기본 규칙
  • 각 큐는 우선순위 부여
  • 실행 준비가 된 프로세스는 여러 큐중에 하나의 큐에 존재
  • 큐에는 여러개의 프로세스가 존재 가능
  • 같은 큐에 있는 프로세스는 같은 우선순위
  • 높은 우선순위의 큐에 있는 프로세스가 높은 우선순위
  • 우선순위가 같으면 Round Robin 형태로 스케쥴링

• 우선순위 정하는 방식
  • 고정 우선순위를 주는 것이 아니라 프로세스의 특징에 따라 우선순위 변화
  • I/O Bound Job vs CPU Bound Job
    • I/O를 하면서 다른 프로세스에게 CPU를 양보하면 우선순위 높힘
    • CPU를 집중적으로 사용하면 우선순위 낮춤

• 작업이 시스템에 진입하면 가장 높은 우선순위에 놓음

• 주어진 타임 슬라이스 다 사용하면 우선순위 낮아짐

• 타임 슬라이스 소진하기 전에 CPU 양도하면 우선순위 유지

단순 MLFQ의 문제점

• 기아 발생 가능성
  • 시스템 내에 너무 많은 대화형 작업 있으면 CPU 할당 못받음

• 프로그램을 자신에게 유리하게 작성
  • 타임 슬라이스가 끝나기 직전에 I/O 요청해서 우선순위 유지

• 시간에 따라 프로그램 특성 바뀌면 우선순위 조정 불가
  • CPU 위주의 작업이 대화형 작업으로 바뀌어도 우선순위 낮음

• 해결법
  • 일정 시간 S가 지나면 우선순위 최상위로 조정 (Boost)
    • 기아 해결
    • 작업의 특성 고려
    • 하지만 S를 정하는 것이 너무 어려운 문제임
  • 주어진 시간 할당량을 소진(CPU를 양도하는 것 상관없이)하면 우선순위 내림
    • 프로그램을 자신에게 유리하게 작성 해결

MLFQ 튜닝 이슈

• 큐 몇개가 적합한가?

• 큐별로 다른 Time quantum

Proportional share (비례 배분)

• Turn around time이나 response time을 최적화하는 대신 스케쥴러가 각 작업에게 일정 비율을 보장하는 것

• Lottery scheduling(추첨 스케쥴링)이 그 중 하나

비례 분배 기본 개념

• Ticket (추첨권)
  • 프로세스가 받아야할 자원의 몫
  • 프로세스가 소유한 티켓의 수와 전체 티켓에 대한 비율이 자신의 몫
  • ex) 100장의 티켓중 A프로세스가 70장, B 프로세스가 30장이면 70%를 A에 30%를 B에 할당

• Ticket Currency (추첨권 화폐) 기법
  • 사용자가 추첨권을 자신의 화폐 가치로 추첨권을 자유롭게 할당할 수 있도록 허용
  • 시스템은 자동으로 화폐 가치를 글로벌 화폐 가치로 변환
    • ex) A가 글로벌 화폐 100을 가지고 있는데 A의 화폐 500으로 만들어서 A1, A2한테 250씩 할당

• Ticket Transfer (추첨권 양도) 기법
  • 다른 프로세스에게 일시적으로 ticket을 넘겨줌
  • 클라이언트-서버 환경에서 유용
    • 클라이언트 프로세스는 서버에게 메세지를 보내 특정 작업을 해달라고 요청할때 특정 작업을 빨리 수행 할 수 있도록 서버에게 ticket을 양도하고 서버의 성능 극대화, 특정 작업 완료하면 다시 클라이언트한테 ticket 양도

• Ticket Inflation (추첨권 팽창) 기법
  • 프로세스는 일시적으로 자신이 소유한 ticket의 수를 늘이거나 줄일 수 있음
  • 프로세스들이 상호 신뢰할 때 유용
  • 이론적으론 가능하지만 실제론 불가능

• 장점
  • 구현이 간단함. 난수 발생기와 프로세스 집합을 표현하는 자료구조(ex. linked list)만 있으면 됨

Uploaded by N2T