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

강의출처 : 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

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

Multilevel Feedback Queue

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

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

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

• 에이징(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

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

Process Synchronization

데이터의 접근

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

Race Condition

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

• 연산을 수행하는 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

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

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

If you preempt CPU while in kernel mode...

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

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

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

Process Synchronization 문제

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

Example of a Race Condition

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

The Critical-Section Problem

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

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