운영체제 스터디 4주차 - CPU Scheduling

케이·2022년 3월 2일
운영체제스터디
0

운영체제 스터디

목록 보기
4/11

해당 게시글은 운영체제 스터디를 위해 반효경 교수님 운영체제 강의를 보고 기록한 게시물입니다. 틀린 정보가 있다면 언제든 지적해주세요🙏🏻

프로세스

  • fork() 시스템 콜: 프로세스 생성. 부모 프로세스가 fork 함수를 호출해서 자식 프로세스를 만든다
    복제생성. 메모리의 주소 까지 같게 복사.

  • exec() 시스템 콜: 하나의 프로세스를 완전히 새로운 프로세스로 덮어 씌워서 실행.

  • wait() 시스템 콜: 자식을 만든 다음에 부모 프로세스의 결과 값이 0이 아닌경우에 웨이트 시스템 콜을 해주게 되면 자식이 끝날 때까지 부모 프로세스를 blocked 상태로, sleep을 시키게 됨.

  • exit() 시스템 콜: 프로세스 종료.

    • 자발적 종료: 자발적 종료는 마지막 statement 수행후 exit 시스템 콜을 통해 종료되는 경우.
    • 비자발적 종료: 부모 프로세스가 자식 프로세스를 강제 종료시킴. 키보드로 kill, break를 친경우 또는 부모가 종료되는 경우.

프로세스의 협력

  • 독립적 프로세스
  • 협력 프로세스
  • 프로세스 간 협력 메커니즘
  • 인터 프로세스 커뮤니케이션을 통해서 프로세스가 협력을 주고 받음: message passing 방식과 shared memory 방식이 있음.

  1. Messaging Passing
  • 메시지 시스템 : 프로세스 사이에 공유 변수를 일체 사용하지 않고 통신하는 시스템
  • 다이렉트 커뮤니케이션, 인다이렉트 커뮤니케이션
  • 다이렉트는 양자간에 명시한 것이고 인다이렉트는 명시하지 않은것.
  1. Shared Memory
  • 메모리를 서로 공유하는 방법

곁다리) 쓰레드는 별도의 프로세스가 아니고 그냥 쓰레드가 만들어 지는 것 자체가 메모리 주소공간이 공유되는 것임

CPU SCHEDULING

  • 프로세스의 일생은 CPU Burst와 I/O Burst로 구성됨.

    • CPU Burst: CPU에서 기계어를 실행하는 작업.
    • I/O Burst: I/O 작업을 하는 것.

  • CPU Bound Job - CPU를 길게 쓰는 작업

  • I/O Bound Job - CPU를 짧게 쓰고 사람하고 인터랙션 하는 프로그램들이 많음.

CPU Scheduler 와 Dispatcher

  • 둘 다 소프트웨어. 운영체제 안에 있는 코드. 운영체제의 일부
  • CPU Scheduler: Ready 상태의 프로세스 중에서 CPU를 줄 프로세스를 결정
  • Dispatcher: CPU Scheduler로 부터 결정된 프로세스에게 제어권을 넘기는 역할을 하고 이 과정을 Context switch(문맥 교환)라고 한다.

Preemptive / nonpreemptive

  • 스케쥴링은 빠른게 좋다? 소요시간, 반환시간, 대기시간, 응답시간과 관련한 것들.

  • CPU Utlization: 전체시간 중에서 CPU가 일한 시간

  • Through put: 단위 시간당 처리량 - 시스템 입장. CPU가 얼마나 많은 일을 했느냐에 초점.

  • Turnaround time: CPU를 사용한 시간과 기다린 시간의 합.

  • Waiting time: CPU를 쓰러와서 기다린 전체 시간. 기다린 시간의 합

  • Response time: 어떤 프로세스가 CPU를 쓰러 들어와서 최초로 CPU를 얻기까지 걸린 시간.

  • 모든 프로그램이 CPU Burst나 I/O Burst가 균일하게 나타나는 것이 아님.
    I/O Burst는 사람들과 인터랙션 하는 경우이고 CPU Burst는 복잡한 연산을 해야하는 경우인데 이 두 작업들이 섞여서 작업들이 진행되기 때문에 CPU Scheduling이 필요하다

CPU 알고리즘

  1. FCFS(First Come First Served)
  • 프로세스의 도착 순서대로 처리하는 방법.
  • Nonpreemptive.
  • CPU Scheduling에서는 굉장히 효율적이지 못한 방법
  • Convoy effect(호위 효과) short process behind long process
    -> 롱 프로세스가 먼저 도착해서 작업중이라 숏 프로세스가 오래 기다려야 하는 경우가 생김..
  1. SJF(Shortest Job First)
  • CPU 짧게 쓰는 프로세스에 먼저 CPU를 주는 방법.
  • 다른 CPU 어떤 알고리즘보다도 이 알고리즘보다는 대기시간을 짧게할 순 없다 - Optimal.
  • 두 가지 측면에서 살펴 볼 수 있는데
    • Nonpreemptive - 실행 중인 CPU Burst가 완료될 때까지 CPU를 선점 당하지 않음.
    • Preemptive - 수행중인 프로세스의 남은 버스트 타임보다 더 짧은 CPU Burst 타임을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김. 이 방법을 Shortest Remaining Time First(SRTF)라고 부른다. 이 방법이 옵티멀이다.
  • 단점: Starvation. 짧은 프로세스에게만 CPU를 주기때문에 long job은 영원히 CPU를 못 얻을 수도 있음. CPU Burst를 알수는 없지만 과거에서 예측은 할 수 있음
  1. Priority scheduling
  • 우선순위가 높은 친구에게 먼저 우선권을 주겠다.
  • SJF는 일종의 프라이어티 스케쥴링이다
  • 문제는 Starvation.
  • 솔루션: Aging - 오래 된 프로세스의 프라이어티를 높여줘서 CPU를 쓸 수 있게 해준다.
  1. Round Robin (RR)
  • 타이머가 붙어있어서 할당 시간이 끝나면 차례를 넘겨주는 방법.
  • Preemptive방법. Time quantum - 각 프로세스는 동일한 크기의 할당시간을 가짐
  • 할당 시간이 지나면 프로세스는 선점 - Preemptive - 당하고 레디 큐의 제일 뒤에 가서 다시 줄을 선다
  • 라운드는 Response Time이 짧다.
  • 일반적으로 SJF보다 Average Turn around Time이 길지만 Response Time은 더 짧다.
  1. Multilevel Queue
  • Ready Que를 여러개로 분할
  • Foreground: interactive
  • Background: batch - no human interaction
  • 각 큐는 독립적인 스케줄링 알고리즘을 가지고 큐에 대한 스케줄링이 필요하다.
    • Time slice: Foreground에 80을 분배하고 Background에 20을 할당하는 방법
    • Fixed priority scheduling: 모든 Foreground를 처리하고 Background를 처리하는 방식. Starvation 가능성 있음.
  • 한번 속하면 다른 큐로 이동 할 수 없음
  1. Multi Level Feedback Queue
  • 프로세스가 다른 큐로 이동 가능
  • aging을 이와 같은 방식으로 구현 할 수 있음.
  • 프로세스를 상위/하위 큐로 보내는 기준
  1. Multi Processor Scheduling
  • CPU가 여러개 있는 환경에서의 스케쥴링
  • CPU가 여러개인 경우 스케쥴링은 더욱 복잡해짐
profile
케이
삽질하며 깨닫고 배웁니다. (a.k.a 프로삽질러) + 이 구역의 회고왕
이전 포스트

운영체제 스터디 3주차 - 프로세스 관리

다음 포스트

운영체제 스터디 5주차 - Process Synchronization

0개의 댓글