04. CPU 스케줄링

Minseok-Choi·2022년 3월 1일
0

OS Study

목록 보기
4/12

wait() 시스템콜

  • 프로세스A가 wait() 시스템 콜을 호출하면 커널은 child가 종료될 때까지 프로세스A를 sleep시킨다 (block 상태)
  • Child 프로세스가 종료되면 커널은 프로세스A를 깨운다 (ready 상태)
  • 터미널에서 명령어를 입력할 때 vi 에디터를 실행하면, 부모 프로세스가 block상태가 되는 것이다.

exit() 시스템콜

  • 프로세스의 종료

    • 자발적 종료

      • 마지막 statement 수행 후 exit() 시스템 콜을 통해서

      • 프로그램에 명시적으로 적어주지 않아도 main 함수가 리턴되는 위치에 컴파일러가 넣어줌

    • 비자발적 종료

      • 부모 프로세스가 자식 프로세스를 강제 종료시킴
        • 자식 프로세스가 한계치를 넘어서는 자원을 요청
        • 자식에게 할당된 테스크가 더 이상 필요하지 않음
      • 키보드로 kill, break 등을 친 경우
      • 부모가 종료하는 경우
        • 부모 프로세스가 종료하기 전에 자식들이 먼저 종료됨

프로세스 간 협력

독립적 프로세스

  • 프로세스는 각자의 주소 공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을 미치지 못함

협력적 프로세스

  • 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미칠 수 있음

프로세스 간 협력 메커니즘(IPC) Interprocess Communication

  • 메시지를 전달하는 방법

    • Message passing : 커널을 통해 메시지 전달
    • Message system : 프로세스 사이에 공유 변수(shared variable)를 일체 사용하지 않고 통신하는 시스템
    • Direct Communication : 통신하려는 프로세스의 이름을 명시적으로 표시
    • Indirect Communication : mailbox 또는 port를 통해 메시지를 간접 전달
  • 주소 공간을 공유하는 방법

    • Shared memory : 서로 다른 프로세스 간에도 일부 주소 공간을 공유하게 하는 shared memory 메커니즘이 있음
  • thread
    • 스레드는 사실상 하나의 프로세스이므로 프로세스 간 협력으로 보기는 어렵지만 동일한 프로세스를 구성하는 스레드들 간에는 주소 공간을 공유하므로 협력이 가능하다.

04. CPU 스케줄링

CPU-burst Time

  • 여러 종류의 job(process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다
    • I/O bound process : CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job (many short CPU bursts)
    • CPU bound process : 계산 위주의 job (few very long CPU bursts)
    • 빈도 : I/O bound job > CPU bound job
    • 기간 : I/O bound job < CPU bound job
  • Interative job에게 적절한 response 제공 요망
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

CPU Scheduler & Dispatcher

  • CPU Scheduler
    • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
  • Dispather
    • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
    • 이 과정을 context switch(문맥 교환)라고 한다.
  • CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.
    1. Running -> Blocked (nonpreemptive) (예:I/O 요청하는 시스템콜)
    2. Running -> Ready (preemptive) (예:할당시간 만료로 timer interrupt)
    3. Blocked -> Ready (preemptive) (예:I/O 완료후 인터럽트)
    4. Terminate (nonpreemptive)

nonpreemptive : 강제로 빼앗지 않고 자진 반납

preemptive : 강제로 빼앗음

Scheduling Criteria

Performance Index( = Performance Measure, 성능 척도)

  • CPU utilization (이용률)
    • 가능한 cpu의 유휴가 없도록 하는 것
  • Throughput (처리량)
    • 단위시간당 몇개의 프로세스를 실행 완료 시켰는가
  • Turnaround time (소요시간, 반환시간)
    • 프로세스를 사용한 시간과 대기시간을 모두 합친 시간
  • Waiting time (대기 시간)
    • 레디 큐에서 CPU를 기다린 전체 시간
  • Response time (응답 시간)
    • 프로세스가 레디큐에 들어와서 최초로 CPU를 얻기까지의 시간

FCFS (Frist-Come First-Served)

  • FIrst In First Come 선착순
  • 작업시간이 긴 프로세스가 먼저 들어오게되면, Average waiting time이 길어진다 -> Convoy effect : short process behind long process

SJF (Shortest-Job FIrst)

  • 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
  • CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
  1. Nonpreemptive
    • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
  2. Preemptive
    • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
    • 이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부른다.
  • SJF is optimal

    • 주어진 프로세스들에 대해 minimum average waiting time을 보장
    • Preemptive가 더 average wating time이 짧도록 최적화한다.
  • 문제점

    • Starvation : burst time이 긴 프로세스는 cpu를 얻지 못할 수 있다.
  • 다음번 CPU burst time을 어떻게 알 수 있을까?

    • 추정(estimate)만이 가능하다
    • 과거의 CPU burst time을 이용해서 추정
      • 최근의 CPU burst time에 더 높은 가중치를 부여해서 에측한다.

Priority Scheduling

  • 우선순위는 각 프로세스와 연관되어 있다.

  • highest priority를 가진 프로세스에게 CPU 할당 (smallest integer = highest priority)

  • SJF는 일종의 priority scheduling이다.

    • Priority = predicted next CPU burst time
  • 문제점

    • Starvation : 낮은 우선순위를 가진 프로세스는 실행되지 못한다.
  • 해결방안

    • Aging : 시간이 지날때마다 프로세스에 우선순위를 높여준다.

RR (Round Robin)

  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다. (일반적으로 10~100 milliseconds)

  • 할당 시간이 지나면 프로세스는 선점당하고 레디 큐의 가장 뒤에 가서 다시 줄을 선다.

  • n개의 프로세스가 레디 큐에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 cpu 시간의 1/n을 얻는다

    -> 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.

  • Performance

    • q large -> FCFS
    • q small -> context switch 오버헤드가 커진다.
  • 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다.

  • 모든 프로세스의 cpu burst time이 동일하거나 비슷할 경우 RR은 average turnaround timed이 길어지기 때문에 비효율적이다.

    • 짧은 job과 긴 job이 섞여있을 때 사용하는 것이 좋다.

Multilevel Queue

  • 레디 큐를 여러 개로 분할
    • Foreground(interacticve)
    • Background(batch - no human interaction)
  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
    • Foreground - RR
    • Background - FCFS
  • 큐에 대한 스케줄링이 필요
    • Fixed priority scheduling
      • Foreground를 모두 먼저 처리하고, backgroud를 처리한다.
      • stravation의 가능성이 있다.
    • Time slice
      • 각 큐에 CPU time을 적절한 비율로 할당
      • 예) RR foreground 80%, FCFS background 20%

Multilevel Feedback queue

  • 프로세스가 다른 큐로 이동 가능

  • aging을 이와 같은 방식으로 구현할 수 있다.

  • Multilevel-feedback-queue scheduler를 정의하는 파라미터들

    • Queue의 수
    • 각 큐의 scheduling algorithm
    • Process를 상위 큐로 보내는 기준
    • Process를 하위 큐로 내쫒는 기준
    • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
  • 예시

    • 3개의 큐가 있다.
      • Q0 : time quantum 8 milliseconds
      • Q1 : time quantum 16 milliseconds
      • Q2 : FCFS
    • 스케쥴링 예시
      1. New job이 queue Q0로 들어감
      2. CPU를 잡아서 할당시간 8 ms 동안 수행됨
      3. 8 ms 동안 다 끝내지 못했으면 queue Q1으로 내려감
      4. queue Q1에 줄서서 기다리다가 CPU를 잡아서 16 ms 동안 수행됨
      5. 16 ms에 끝내지 못한 경우 queue Q2로 쫓겨남

Multiple-Processor Scheduling

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

Real-Time Scheduling

  • Hard real-time systems
    • hart real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
  • Soft real-time systems
    • soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함 ( ex동영상 재생)

Thread Scheduling

  • Local Scheduling
    • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
  • Global Scheduling
    • Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
profile
차곡차곡

0개의 댓글