[OS] Basic Scheduling algorithms (프로세스 스케줄링 알고리즘)

Basic Scheduling algorithms

index

• FCFS(First-Come-First-Service)
• RR(Round-Robin)
• SPN(Shortest-Process-Next)
• SRTN(Shortest-Remaining Time Next)
• HRRN(High-Response-Ratio-Next)
• MLQ(Multi-Level Queue)
• MFQ(Multi-Level Feedack Queue)

FCFS (First-Come-First-Service)

• key points : 비선점, 선착순

• 스케줄링 기준

  • 도착 시간(ready queue 기준)
  • 먼저 도착한 프로세스를 먼저 처리한다.

• 자원을 효율적으로 사용이 가능하다. (High resource utilization!! )

  • why??

    -> 들어오는 순서로 처리하기 때문에 스케줄링의 오버헤드가 적다. 즉, CPU가 계속 일 할 수 있다.

• 일괄처리 시스템에 적합하고 대화형 시스템에는 부적합하다.

• 단점

  1. Convoy effect : 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시갖을 갖게 된다.
  2. 긴 평균 응답시간

• Code

  리스트를 사용하여 (또는 큐) 들어온 순서대로 처리한다.

  public ArrayList<ProcessInfo> FCFS_Scheduling(ArrayList<ProcessInfo> processInfo) {
          int runningTime = processInfo.get(0).getArrivalTime();        //진행한 시간
          for (int i = 0; i < processInfo.size(); i++) {
              ProcessInfo tmp = processInfo.get(i);
              runningTime += tmp.getBurstTime();
              setProcessInfo(runningTime, tmp);
          }
          return processInfo;
      }

RR (Round Robin)

• key points : 선점, 선착순

• 스케줄링 기준

  • 도착 시간(ready queue 기준)
  • 먼저 도착한 프로세스를 먼저 처리한다.

• 자원 사용 제한 시간(time quantum)이 있다.

  • 프로세스는 할당된 시간이 지나면 자원을 반납한다.
  • 특정 프로세스의작원 독점을 방지할 수 있다.
  • Context switch overhead가 크다.

• 제한 시간이 시스템 성능을 결정하는 핵심요소가 된다.

• 시분할, 대화형 시스템에 적합하다.

• Code

    public ArrayList<ProcessInfo> RR_Scheduling(ArrayList<ProcessInfo> processInfo, int timeQuantum) {
          Queue<ProcessInfo> readyQueue = new LinkedList<>();
          int runningTime = processInfo.get(0).getArrivalTime();        //진행한 시간
          int processInfoIdx = 0;                                       //ready queue에 넣을 process info의 idx
          readyQueue.add(processInfo.get(processInfoIdx));
          processInfoIdx++;
  
          while (!readyQueue.isEmpty()) {
              boolean isFinished = false;
              ProcessInfo tmp = readyQueue.poll();
              int remainingBurstTime = tmp.getRemainingBurstTime() - timeQuantum;
              if (remainingBurstTime <= 0) {
                  runningTime += tmp.getRemainingBurstTime();
                  setProcessInfo(runningTime, tmp);
                  isFinished = true;
              } else {
                  runningTime += timeQuantum;
              }
              //해당 시간에 도착한 프로세스들이 여러개일 수 있으니까 전체적으로 확인
              processInfoIdx = addProcessToReadyQueue(processInfo, readyQueue, processInfoIdx, runningTime);
  
              if (isFinished)
                  continue;
              tmp.setRemainingBurstTime(remainingBurstTime);
              readyQueue.add(tmp);
          }
  
          return processInfo;
      }

  선착순으로 처리하기 때문에 큐를 사용한다. 만약 제한시간 안에 처리를 다 못했을 경우 다시 큐안으로 넣어서 ready queue에 프로세스가 없을 때 까지 반복한다.

SPN (Shortest-Process Next) = SJF (Shortest-Job First)

• key points : 비선점, 짧은 것 먼저 처리

• 스케줄링 기준

  • 실행 시간(burst time 기준)
  • burst time이 가장 작은 프로세스를 먼저 처리한다.

• 장점

  • 평균 대기시간(WT) 최소화할 수 있다.
  • 시스템 내 프로세스 수 최소화할 수 있다.
  • 많은 프로세스들에게 빠른 응답 시간 제공할 수 있다.

• 단점

  • Starvation(기아현상 : 무한대기) 현상 발생
    • 실행 시간이 긴 프로세스는 자원을 할당 받지 못 할 수 있다.
      • aging으로 해결
  • 정확한 실행시간을 알 수 없다. 즉, 실행시간 예측 기법이 필요하다.

• Code

  public ArrayList<ProcessInfo> SPN_Scheduling(ArrayList<ProcessInfo> processInfo) {
          PriorityQueue<ProcessInfo> readyQueue = new PriorityQueue<>();
          int runningTime = processInfo.get(0).getArrivalTime();        //진행한 시간
          int processInfoIdx = 0;                                       //ready queue에 넣을 process info의 idx
          readyQueue.add(processInfo.get(processInfoIdx));
          processInfoIdx++;
  
          while (!readyQueue.isEmpty()) {
              ProcessInfo tmp = readyQueue.poll();
              runningTime += tmp.getRemainingBurstTime();
              setProcessInfo(runningTime, tmp);
              processInfoIdx = addProcessToReadyQueue(processInfo, readyQueue, processInfoIdx, runningTime);
          }
          processInfo.sort(idComparator);
          return processInfo;
      }

SRTN (Shortest-Remaining Time Next)

• key points : 선점, SPN의 변형

• 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점된다.

• 장점

  • SPN 장점 극대화!!

• 단점

  • 프로세스 생성 시, 총 실행 시간 예측이 필요하다.
  • 잔여 실행을 계속 계산해야한다. 즉, 오버헤드가 증가한다.
  • Context switching overhead가 증가한다.

• 구현 및 사용이 비현실적이다.

• Code

   public ArrayList<ProcessInfo> SRTN_Scheduling(ArrayList<ProcessInfo> processInfo) {
          PriorityQueue<ProcessInfo> readyQueue = new PriorityQueue<>(SRTNComparator);
          int runningTime = processInfo.get(0).getArrivalTime();        //진행한 시간
          int processInfoIdx = 0;                                       //ready queue에 넣을 process info의 idx
          readyQueue.add(processInfo.get(processInfoIdx));
          processInfoIdx++;
          for (int i = 1; i < processInfo.size(); i++) {
              if (runningTime == processInfo.get(i).getArrivalTime()) {
                  readyQueue.add(processInfo.get(processInfoIdx));
                  processInfoIdx++;
              }
          }
          while (true) {
              boolean check = false;
              if (readyQueue.isEmpty())
                  break;
              ProcessInfo tmp = readyQueue.poll();
              runningTime++;
              tmp.setRemainingBurstTime(tmp.getRemainingBurstTime() - 1);
              if (tmp.getRemainingBurstTime() == 0) {
                  setProcessInfo(runningTime, tmp);
                  check = true;
              }
              for (int i = processInfoIdx; i < processInfo.size(); i++) {
                  if (runningTime == processInfo.get(i).getArrivalTime()) {
                      readyQueue.add(processInfo.get(i));
                  }
              }
              if (!check) {
                  readyQueue.add(tmp);
              }
          }
          processInfo.sort(idComparator);
          return processInfo;
      }

HRRN (High-Response Ratio Next)

• key points : 비선점, 기아현상 해결

• Aging concepts : 프로세스의 대기 시간을 고려하여 기회를 제공한다.

• 스케줄링 기준

  • Response ratio가 높은 프로세스 우선

• Response ratio = (WT+BT) / BT (응답률)

  • SPN의 장점 + Starvation 방지
  • 실행 시간 예측 기법 필요하다.

• Code

   public ArrayList<ProcessInfo> HRRN_Scheduling(ArrayList<ProcessInfo> processInfo) {
          PriorityQueue<ProcessInfo> readyQueue = new PriorityQueue<>(HRRNComparator);
          int runningTime = processInfo.get(0).getArrivalTime();        //진행한 시간
          int processInfoIdx = 0;                                       //ready queue에 넣을 process info의 idx
          readyQueue.add(processInfo.get(processInfoIdx));
          processInfoIdx++;
  
          while (!readyQueue.isEmpty()) {
              ProcessInfo tmp = readyQueue.poll();
              runningTime += tmp.getRemainingBurstTime();
              setProcessInfo(runningTime, tmp);
              processInfoIdx = addProcessToReadyQueue(processInfo, readyQueue, processInfoIdx, runningTime);
          }
          processInfo.sort(idComparator);
          return processInfo;
      }

MLQ (Multi-Level Queue )

• 작업 (또는 우선순위)별 별도의 ready queue를 가진다.
  • 최초 배정 된 queue를 벗어나지 못한다. -> 시스템 변화에 적응하기 힘들다.
  • 각각의 queue는 자신만의 스케줄링 기법을 사용할 수 있다.
• 단점
  • 여러 개의 queue 관리 등 스케줄링 overhead 증가한다.
  • 우선순위가 낮은 queue는 기아현상 발생한다.

MFQ (Multi-level Feedback Queue)

• 프로세스의 Queue간 이동이 허용된 MLQ
• Feedback 을 통해 우선 순위(동적이다.)를 조정한다.
• 프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있다.
• 단점
  • 설계 및 구현이 복잡하다.
  • 기아현상이 발생할 수 있다.

• Code

  private void setProcessInfo(int runningTime, ProcessInfo processInfo) {
      processInfo.setTurnaroundTime(runningTime - processInfo.getArrivalTime());
      processInfo.setWaitingTime(processInfo.getTurnaroundTime() - processInfo.getBurstTime());
      processInfo.setNormalizedTT(calNTT(processInfo));
  }
  
   private int addProcessToReadyQueue(ArrayList<ProcessInfo> processInfo, Queue<ProcessInfo> readyQueue, int processInfoIdx, int runningTime) {
          while (processInfoIdx < processInfo.size()) {
              ProcessInfo nextTmp = processInfo.get(processInfoIdx);
              if (runningTime >= nextTmp.getArrivalTime()) {
                  readyQueue.add(nextTmp);
                  processInfoIdx++;
                  continue;
              }
              break;
          }
          return processInfoIdx;
      }

더 자세한 코드는 아래를 참고해주세요. (혼자 공부하면서 작성한 것이라서 틀릴 수도 있으니 참고바랍니다.)

• https://github.com/johee96/OSStudy/tree/processScheduling

johee96/OSStudy

강의자료 및 강의의 저작권은 다음과 같습니다.

https://sites.google.com/view/hpclab/courses/operating-system

HPC Lab., KOREATECH - Operating System

문제시 삭제하겠습니다.