지금까지는? 한 줄로 줄을 섰어. ready queue에서!

Multilevel Queue

• 여러 줄 서기

  • 맨 윗줄: 가장 높은 우선순위! 시스템 프로세스 등
  • 가장 아랫 줄: 가장 낮은 우선순위

• 멀티 큐는 완전 계급제!

  • 시스템 프로세스: 성골. 여기에 가장 먼저 배정.

• ready queue를 여러 개로 분할

  • foreground: interactive
  • background: 배치 프로세스와 같이 사람과 인터랙션이 없는 애들을 background queue에 배정

• 각 큐는 독립적인 스케쥴링 알고리즘을 가진다.

  • foreground - RR(라운드 로빈) : 사람과 상호작용하니 너무 오래 기다리게 하면 힘들어 ⇒ 라운드 로빈을 쓰는 게 좋음. 응답시간을 짧게!
  • Background - FCFS → CPU만 오래 쓰는 작업들에 해당. 응답 시간 짧게한다고 좋을 것 없음. context switch overhead를 줄이기 위해 먼저 온 애들부터 처리해주는 게 굳.

• 어떤 큐한테 CPU를 줄 것인가?

  • 이번에 어느 줄에 CPU를 줄 것인지? 누구한테 줄 것인지?
  • 우선순위 높은 줄이 비어있을 때만 낮은 줄 애한테 부여 ⇒ 이러면 starvation 발생할 수 있음.

• Time slice: 각 큐에 cpu time을 적절한 비율로 할당해준다.

  • 어느 정도는 cpu 시간을 나눠서 주는 방법 - 80프로는 foreground in RR, 20프로는 background in FCFS.

• 위의 큐는 신분이 우선순위로 정해지고 이 우선순위는 절대 바뀌지 않음. 평등한 구조가 아님.

멀티레벨 feedback queue

• 프로세스가 다른 큐로 이동이 가능(그냥 멀티레벨 큐에서는 이게 불가. 신분이 정해져있음)
• aging을 이와 같은 방식으로 구현 가능
• multilevel-feedback-queue scheduler를 정의하는 파라미터들
  • Queue의 수: 큐를 몇 개나 둘 것인가?
  • 각 큐의 scheduling algorithm: 각 큐에는 어떤 스케쥴링?
  • process를 상위 큐로 보내는 기준 & 하위 큐로 내쫓는 기준: 우선순위 높/낮 기준은 어떻게 정하고? 승격 기준은 어떻게 정하고?
  • 프로세스가 CPU 서비스를 받으려할 떄 들어갈 큐를 결정하는 기준 - 프로세스가 어디 큐로 들어갈 것인가?
• Three-queues:
  • 처음 들어오는 프로세스는 우선순위 가장 높은 큐에 배정. 이때 round robin의 time quantum을 매우 짧게 준다. (8ms)
  • 할당 타임이 끝나면 그 아래 큐로 배정 ⇒ 여기서는 TQ가 더 길어(여전히 라운드로빈) (16ms)
  • 그 아래부터는 FCFS로 진행.
• 스케쥴링 방식
  1. 새로운 job이 queue Q0에 들어감.
  2. CPU 잡아서 할당시간 8ms동안 수행
  3. 8ms 안에 다 못 끝내면 Q1으로 넘어감.
  4. Q1에서 줄서서 기다리다가 CPU 잡아서 16ms 동안 수행
  5. 16ms 안에 못 끝내면 Q2로 쫓겨남. 여기서부터는 FCFS. 하나 끝날 때까지 계속 진행.
• 특징
  • ⇒ CPU burst 시간이 짧은 애들은? 가장 높은 큐에서 진행 끝나버리고. 그보다 더 긴 애들은 점점 아래로 내려가는 식. CPU 시간 짧은 애들한테 더 많은 가중치를 주는 식. 긴 프로세스는 점점 밑으로 쫓아낸다.
  • CPU 사용시간이 긴지 짧은지 예측할 필요가 없음.

Multiple-Processor Scheduling