관리 메뉴

커리까지

[운영체제] 11. CPU Scheduling 2 / Process Synchronization 1 본문

KOCW

[운영체제] 11. CPU Scheduling 2 / Process Synchronization 1

목표는 커리 2021. 7. 9. 04:40
728x90
SMALL

강의출처 : kocw 반효경

  • round robin이 좋은 점은 전에 작업하고 있던 부분을 세이브해줌

Multilevel Queue

  • Ready queue를 여러 개로 분할
    • foregorund(interactive)
    • background(batch - no human interaction)
  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
    • foreground - RR
      • 사람과 응답하는 것이니
    • background - FCFS
      • batch잡이니 fcfs가 더 효울적임
  • 큐에 대한 스케줄링이 필요
    • Fixed priority scheduling
      • serve all from foreground then from background
      • Possibility of starvation
    • Time slice
      • 각 큐에 CPU time을 적절한 비율로 할당
      • Eg., 80% ro foreground in RR, 20% to background in FCFS

Multilevel Queue

23

  • 줄마다 우선순위 존재
  • 밑으로 갈수록 우선순위가 낮음
  • 태어난 프로세스가 어떤 형식인지에 따라 우선순위가 정해짐
    • 변하지 않음
  • 프로세스를 어느줄에 넣을 것이냐

Multilevel Feedback Queue

24

  • 약간 우선 순위가 낮은 프로세스라도 올라갈 수 있음

  • 여러 줄로 줄서기해서 때에 따라 계급 이동 가능

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

  • 에이징(aging)을 이와 같은 방식으로 구현할 수 있음

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

    • Queue의 수
    • 각 큐의 scheduling algorithm
    • Process를 상위 큐로 보내는 기준
    • Process를 하위 큐로 내쫒는 기준
    • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
  • cpu 버스트가 짧으면 바로 빠져나갈 수 있지만 길면 아래 큐로 이동해서 할당시간을 더 받을 수 있음

  • cpu 버스트 시간이 짧은 프로세스에게 우선 순위를 더 많이 주고 긴 프로세스는 밑으로 내려가게 함

  • 짧은 시간에 먼저 배정하기 때문에 예측 할 필요 없음

Example of Multilevel Feedback Queue

  • Three queues:
    • Q0 - time quantum 8 milliseconds
    • Q1 - time quantum 16 milliseconds
    • Q2 - FCFS
  • Scheduling
    • new job이 queue Q0로 들어감
    • CPU를 잡아서 할당 시간 8 milliseconds 동안 수행됨
    • 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려감
    • Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행됨
    • 16ms에 끝내지 못한 경우 queue Q2로 쫓겨남

Multiple-Processor Scheduling

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

Real-Time scheduling

  • 주기적으로 실행되도록 하거나 데드라인이 정해져있음

  • Hard real-time systems

    • 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
  • Soft real-time computing

    • 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
    • 데드라인을 보장하지는 않음

Thread scheduling

  • Local Scheduling
    • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
    • 운영체제가 thread의 존재를 모름
    • 사용자 프로세스가 직접
  • Global scheduling
    • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
    • 운영체제가 알기에

Algorithm Evaluation

25

  • Queueing models
    • 굉장히 이론적임
    • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
    • 예전에는 많이 썼지만 요즘에는 덜 씀
  • Implementation(구현) & Measurement (성능 측정)
    • 실제 시스템에 알고리즘을 주현하여 실제 작업(workload)에 대해서 성능을 측정 비교
  • Simulation(모의 실험)
    • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
    • 구현과 성능측정이 어려우면 이 방법을 사용
    • trace
      • 측정에 사용되는 input 값

Process Synchronization

데이터의 접근

26

  • 데이터를 읽어와서 수정하고 저장하는 경우 문제가 발생할 수 있음

Race Condition

27

  • 서로 초록 박스를 가져가서 더하거나 빼고 싶어함
  • 여러 주체가 하나의 데이터에 접근하는게 경쟁상태가 됨
    • 이러한 것을 조율해주는게 필요함
  • 멀티 프로세서에서는 문제가 생길 수 있음
  • 더 중요한 문제는 커널과 관련된 문제들
    • 커널의 코드가 실행되면서 커널에 접근하면 문제 발생 할 수 있음

28

  • 연산을 수행하는 cpu가 메모리에 저장

OS에서 race condition은 언제 발생하는가?

  1. kernel 수행 중 인터럽트 발생 시
  2. Process가 system call을 하여 kernal mode로 수행 중인데 context switch가 일어나는 경우
  3. Multiprocessor에서 shared memory내의 kernal data

OS에서의 race condition(1/3) interrupt handler v.s kernel

29

  • 커널이 cpu에서 실행하고 있음
    • count를 증가시키고 있었음
    • 인터럽트가 들어오면 인터럽트 루틴으로 넘어감
    • 인터럽트 핸들러가 처리되는 도중에 count-- 가능
  • 커널 데이터를 양쪽에서 건드리면 하나만 저장됨
  • 중요 변수를 인터럽트가 들어오면 작업이 끝날 때 까지 인터럽트를 처리하지 않고 먼저 작업이 끝나야 인터럽트를 수행함
  • 즉, 순서를 정해주면 됨
    • 이걸 어떤 식으로 처리하는게 효율적인지 판단해서

OS에서의 race condition(1/3) Preempt a process running in kernal?

30

If you preempt CPU while in kernel mode...

31

  • A라는 프로그램이 cpu를 잡고 있다가 끝나고 b가 끝나면 a로 넘어옴
  • a가 시스템 콜을 해서 커널을 실행중이고 1을 증가시키고 있는 도중이었는데 할당 시간이 끝나서 b로 넘어감
  • b도 하다가 할당 시간이 끝나서 a로 넘어감
    • 아까 하던거 이어서 함
    • 밑에서 증가한거는 반영안 됨
    • 증가시키기 전의 값이 b가 끝난 후 a로 실행할 때 불러와지기 때문에
  • 커널 모드가 끝나고 user모드를 빠져나갈 때 b로 넘어감

OS에서의 race condition(3/3) multiprocessor

32

  • 앞에서 설명한 것들로는 해결이 안됨
  • 인터럽트로 막아서 해결이 안 됨
  • 작업주체가 여럿이기 때문에 문제가 생김
  • 데이터에 접근할 때 lock를 걸어야 함
    • 다른 누구도 접근 못하게
    • 작업이 끝나고 락을 품
  • 커널 접근 하는 cpu를 하나로 접근하도록
    • 비효율적
  • 각각 데이터 락을 걸로 풀고 하는게 더 효율적

Process Synchronization 문제

  • 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있음
  • 일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 메커니즘 필요
  • Race condition
    • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
    • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
  • race condition을 막기 위해서는 concurrent process는 동기화되어야 함

Example of a Race Condition

33

  • 단순히 p1에서 p2로 넘어갈때는 큰 문제가 발생하지 않음
  • 서로 같은 공유데이터에 접근하는게 문제임

The Critical-Section Problem

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

34

  • 공유데이터 접근에서 자유로울 때 공유데이터에 접근할 수 있어야 함
    • 기다려야 함
728x90
LIST

'KOCW' 카테고리의 다른 글

[kocw] 01. 자료구조소개1  (0) 2021.09.23
[운영체제] 12. Process Synchronization 1  (0) 2021.07.23
[운영체제] 10. CPU Scheduling 1  (0) 2021.06.23
[운영체제] 9. Process Management 2  (0) 2021.06.18
[운영체제] 8. Process Management 1  (0) 2021.06.16
Comments