7주차

💡 Queue

• Multilevel queue

  

  • 줄마다 우선순위가 있다.
    • system queue는 가장 우선순위가 높음.
    • 우선순위가 높은 queue가 있다면 가장 먼저 할당 받는다.
    • 고려해야할 점이 있다
      • 프로세스를 어느 queue에 넣을 것인가?
      • 우선순위가 낮은 프로세스는 starvation 발생
  • Ready queue를 여러개로 분할
    • foreground(interactive)
    • background(batch - no human interaction)
  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
    • foreground - RR
    • background - FCFS
  • 큐에 대한 스케줄링이 필요
    • 고정 우선순위 스케줄링
      • foreground에서 모두 제공한 다음 background에서 제공
      • Starvation의 가능성이 있다.
    • Time slice
      • 각 큐에 CPU time을 적절한 비율로 할당
      • Ex) 80% to foreground in RR, 20% to background in FCFS

• 라운드 로빈만으로 부족하다.

  • CPU burst time이 짧은 process 가 우선순위를 더 받는 것이 안된다.
  • CPU 사용시간이 짧은 시간에게 우선순위를 더 많이 주고 긴 프로세스는 밑으로 내려간다.

• Three queues:

  • Q0 : time quantum 8
  • Q1 : time quantum 16
  • Q2 : FCFS

• 스케줄링

  • new job이 queue Q0로 들어감
  • CPU를 잡아서 할당 시간 8ms동안 수행됨
  • 8ms 동안 다 끝내지 못했으면 Q1 으로 내려감
  • Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행됨
  • 16ms에 끝내지 못한 경우 Q2로 내려감.

• Multiple-Processor Scheduling

  • CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
  • Honogeneous processor인 경우
    • Queue에 한줄로 세워 각 프로세스가 알아서 꺼내가게 할 수 있다.
    • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에 문제가 더 복잡해짐
  • Load Sharing
    • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
    • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
  • Symmetric Multiprocessing(SMP)
    • 각 프로세서가 각자 스케줄링 결정
    • 모든 CPU들이 대등하다.
  • Asymmetric multiprocessing
    • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
    • 여러개의 CPU중 하나의 CPU가 전체적인 제어를 담당한다.

• Real-Time Scheduling

  • Hard real-time systems
    • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야함
    • 미리 스케줄링을 해서 deadline이 보장되도록 함
  • Soft real-time computing
    • Soft real-time task는 일반 프로세스에 비해 높은 우선순위를 갖도록 해야 함

• Thread Scheduling

  • Local Scheduling
    • 사용자 프로세스가 직접 쓰레드를 관리하고 운영체즈는 쓰레드를 모름.
    • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
  • Global Scheduling
    • 운영체제가 쓰레드의 존재를 이미 알고있음.
    • Kernel level thread의 경우 일반 프로세스의 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
    • 프로세스 스케줄링 하듯이 운영체제가 알고리즘에 기반해 CPU 할당을 결정한다.

• Algorithm Evaluation

  • Queueing models

    

    • 확률 분포로 주어지는 arriave rate와 service rate 등을 통해 각종 performance index 값을 계산

  • Implementation (구현) & Measurement (성능 측정)

    • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교

  • Simulation(모의 실험)

    • 알고리즘을 모의 프로그램을 작성 후 trace를 입력으로 하여 결과 비교
    • 실제로 돌리는 것이 아님.
    • trace = input data. 시뮬레이션 프로그램에 input으로 들어갈 데이터
      • 실제값을 기반으로 하면 좀 더 좋은 성능을 낼 수 있다.

💡 Synchronization

• 데이터의 접근

  

  

  • 하나의 값에 연산이 여러번 되는 경우 값이 반영이 안될 수 도있음

    • Synchronization라고 부른다.

    • CPU가 여러개 있는 system은 메모리를 공유하기 때문에 Race Condition의 문제가 생길 수 있음.

    • OS에서 Race Condition이 발생하는 시기

      1. Kernel 수행 중 인터럽트 발생 시

         

         • interrupt handler = 커널 코드
         • Count—는 저장이 안되고, Count++만 저장됨.
           • 양쪽에서 CPU를 얻어가 처리를 했기 때문에.

      2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우

         

         

         • A가 잡고 있다가 B에게 넘어감
           • Count++ 작업 중 CPU를 선점당한 상황
           • 이 때, B의 Count++는 반영이 되지 않음.
           • B가 증가하기 전에 A가 이미 Count 값을 읽어들였기 때문.
           • Syncronization 문제 발생.
           • 해결법: 커널 모드에서 진행 중일 땐 처리가 끝날 때 까지 CPU를 뺏지 않는다

      3. Multiprocessor 에서 shared memory 내의 kernel data

         

         • 방법 1.
           • 한 번에 하나의 CPU만.
             • 비효율적이다.
         • 방법 2.
           • 데이터에 접근할 때 lock을 걸어야 한다.
           • 변경 후 데이터 unlock.
             • 방법 1에 비해 효율적이다.

• Process Synchronization 문제

  • 공유 데이터(Shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다.

  • 일관성(consistency)유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정해주는 메커니즘 필요

  • Race Condition

    • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
    • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

  • Race Condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 한다.

    

• The Critical-Section Problem
  • n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
  • 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 Critical Section이 존재
  • Problem
    • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다