[운영체제] 10장: Multiprocessor and Real-Time Scheduling

Classifications of Multiprocessor Systems

• Loosely coupled or distributed multiprocessor, or cluster
  • 자율적으로 작동하는 시스템들의 집합
  • 각 프로세서들은 자신만의 메인 메모리와 I/O 채널, OS를 가지고 있다.
  • 독립적인 시스템들을 연결해서 하나의 시스템처럼 사용한다.
• Functionally specialized processors
  • 서로 다른 기능을 하는 프로세서들이 여러 개 있다.
• Tightly coupled multiprocessor
  • 여러 개의 프로세서들이 하나의 메인 메모리를 공유한다.
  • 하나의 OS로 시스템 전체가 관리된다.

Synchronization Granularity and Processes

• Independent: 어떠한 데이터도 주고 받지 않는 서로 무관한 프로세스들
  • 동기화가 발생하지 않는다.
• Very Coarse: 네트워크로 연결되어 가끔 데이터를 주고 받는 프로세스들
  • 아주 가끔 동기화가 발생한다.
• Coarse: 하나의 프로그램이 여러 프로세스로 구성
  • 가끔 동기화가 발생한다.
  • 프로세스끼리 메모리 공간을 공유하지 않기 때문에 OS를 통해 동기화된다.
• Medium: 하나의 프로그램이 여러 thread로 구성
  • 자주 동기화가 발생한다.
  • thread끼리는 메모리 공간을 공유하기 때문에 Coarse보다 동기화가 자주 발생한다.
• Fine: 굉장히 많은 thread들이 동시에 작업
  • 굉장히 자주 동기화가 발생한다.

Grain size에 따라 스케줄링 방법을 다르게 해야 한다.

Scheduling Design Issues

Assignment of Processes to Processors

• Permanently assign process to a processor
  • 각 프로세서는 자신만의 Ready queue를 가지고 있고 OS가 프로세스들을 각 queue로 분산시킨다.
  • overhead가 적다.
  • 일부 프로세서는 바쁘게 작업하고 다른 일부 프로세서는 쉬고 있는 idle-while-busy가 발생한다.
• Global queue
  • 여러 프로세서가 하나의 queue를 공유한다.
  • idle-while-busy가 발생하지 않는다.

Global queue 사용하자!

The Use of Multiprogramming on Individual Processors

• Coarse or Independent: 멀티 프로그래밍이 필요하다.
  • 주로 I/O 작업 때문에 blocked 된다.
• Medium: 멀티 프로그래밍을 안하는게 낫다.
  • I/O 작업은 물론이고 주로 세마포어 같은 동기화나 메시지 같은 통신 때문에 blocked 된다.
  • 유니 프로세서 시스템이라면? 빨리 프로세스 스위칭을 해서 내 blocked 상태를 풀어줄 작업이 실행되게 해야 한다.
  • 멀티 프로세서 시스템이라면? blocked queue로 가서 프로세스 스위칭이 발생하는 사이에 다른 프로세서에서 내 blocked 상태를 풀어줄 작업이 실행될 수 있기 때문에 blocked queue로 보내지 말고 프로세스 스위칭을 안하는 것이 좋다.

• Grain size에 따라서 멀티 프로그래밍이 필요할 때도 있고 그렇지 않을 때도 있다.
• busy-waiting이 오히려 필요한 경우도 있다.

Process Dispatching

- 가로축: 프로세스 간의 실행 시간 차이
- 세로축: throughput
- throughput 값이 1에 가까울 수록 FCFS와 성능 차이가 없다는 것이다.

• 프로세서가 여러 개라면 프로세스 간의 실행 시간 차이에 따른 성능 차이가 줄어든다. 즉 프로세스 스케줄링 기법이 중요하지 않게 된다.
• 실행 시간이 아주 긴 프로세스가 실행중이어도 다른 프로세서를 통해 실행 시간이 짧은 프로세스들이 실행될 수 있기에 차이가 줄어드는 것이다.

💡 결론 💡

• Grain size에 따라서 스케줄링 방법이 달라져야 한다.
• 프로세서 개수에 따라서 스케줄링 방법이 달라져야 한다.

Thread Scheduling

한 프로그램을 구성하는 thread들을 동시에 실행시키는 것이 성능에 좋다.

Load sharing

• 프로세서가 적어서 동시에 실행하고 싶어도 불가능하다.
• 프로세서가 실행을 멈추면 global queue에서 다음에 실행할 thread를 가져온다.
  • Load가 모든 프로세서에게 동일하게 분배된다. (load sharing)
  • idle-while-busy가 발생하지 않는다.
  • centralized schedular가 필요하지 않다.
• 구현 방법
  • FCFS
  • Smallest number of threads first (SPN 변형)
  • Preemptive smallest number of threads first (SRT 변형)

    기법 간 별 차이가 없어서 그냥 FCFS 사용한다.

• 문제점
  • global queue는 critical section으로 구현되어야 한다. (mutual exclusion → bottleneck)
  • 한 프로세서에서 실행된 thread가 blocked queue에 갔다가 다음에 똑같은 프로세서에서 실행된다는 보장이 없기 때문에 cache가 무의미해진다.
  • thread들이 동시에 실행되지 않을 수 있다.

    하지만 일반적인 컴퓨터들은 적은 개수의 프로세서를 가지고 있기 때문에 가장 흔하게 사용되는 스케줄링 기법이다.

Gang scheduling

• 동시에 실행되어야 하는 thread는 무조건 동시에 실행한다.
• 프로세서가 굉장히 많은 시스템을 가정한다.
• 한 프로세스를 구성하는 thread들을 동시에 실행한다.
• 프로세스 단위로 Ready queue에 대기하고 실행 순서가 되면 프로세스의 thread 수만큼 프로세서를 할당하여 동시에 실행되도록 한다.
  • 프로세스를 구성하는 thread 수보다 프로세서 수가 훨씬 많아야 한다.
• medium-grained, fine-grained 수준의 프로그램을 가정한다.
• Time sharing(RR)
  • 각 프로세스에게 동일한 time quantum을 할당한다. (비효율적일 수 있음)
  • 프로세스를 구성하는 thread 수에 따라 가중치를 두어 time quantum을 할당한다. (CPU utilization 향상)
  • 프로세서를 효율적으로 사용하는 것이 아닌 프로세르르 구성하는 thread들을 동시에 실행하는 것이 목적이다.

Dedicated processor assignment

• 동시에 실행되어야 하는 thread는 무조건 동시에 실행한다.
• 프로세서가 굉장히 많은 시스템을 가정한다.
• Time sharing(RR) ❌
• 프로세스 단위로 ready queue에서 대기하고 실행 순서가 되면 프로세스의 thread 수만큼 프로세서를 할당하여 동시에 실행되도록 한다.
• I/O 작업이 필요할 때도 프로세스 스위칭을 하지 않고 끝까지 실행한다. 이때, 프로세서는 idle 상태이다.
• Processor fragmentation problem이 발생한다.
  • 사용 가능한 프로세서가 남아 있지만 그 수가 실행하려는 프로세스의 thread 수보다 적어서 사용 못하는 상황

Dynamic scheduling

• 동시에 실행할 수 있으면 하고 못하면 안하고
• OS는 각 프로세스에게 프로세서를 분배하는 역할을 한다.
  • 프로세스는 자기의 thread 수만큼 프로세서를 요청한다.
  • 나눠주는 프로세서의 수가 프로세스의 thread 수(요청량)보다 적을 수 있다.
• 프로세서를 분배 받았을 때 그것을 어떻게 사용할 지는 user level에서 결정한다.
• 새로운 프로세스를 실행해야 하는 상황에서 남아 있는 프로세서가 없다면?
  • 실행 중인 프로세스가 최소로 필요한 프로세서보다 더 많이 가지고 있다면 그것을 뺏어서 할당한다.
  • 실행 중인 모든 프로세스가 최소한의 프로세서만을 가지고 있다면 ready queue에서 대기한다.
• 프로세서가 실행을 마치고 idle 상태가 되었을 때
  • ready queue에서 대기하고 있는 프로세스들에게 프로세서를 하나씩 할당해준다.
  • 하나씩 할당해주고 남았다면 FCFS에 기반하여 나머지를 나눠준다.

Real-Time Scheduling

• Real-time computing: 연산의 결과가 정확한 것도 중요하지만 그 결과가 언제 나오는지도 중요하다.
  • Hard real-time task: Deadline을 반드시 지켜야 하는 작업
    • 지키지 않으면 시스템에 치명적 오류나 데미지를 줄 수 있다.
  • Soft real-time task: Deadline을 지키는게 바람직하지만 강제는 아닌 작업
    • 지키지 않으면 throughput에 포함이 되지 않는다.
    • 못 지킬 것 같으면 시작을 안한다.
• periodic task & aperiodic task

Real-Time Scheduling = Soft real-time task & periodic task

Earliest-deadline Scheduling

• Deadline이 가장 빠른 것부터 실행한다.
• Preemption: 실행하다가 Deadline이 더 빠른 task가 도착하면 프로세서를 넘겨준다.
• Deadline이 같을 경우에는 먼저 실행하고 있던 task를 계속 실행한다.
  

Rate Monotonic Scheduling

• 주기가 가장 짧은 것부터 실행한다.
  • 주기가 짧은 것은 곧 Deadline이 빠른 것이다.
• Preemption: 실행하다가 주기가 더 빠른 task가 도착하면 프로세서를 넘겨준다.
  

Priority Inversion

• 우선순위가 높은 task가 우선순위가 낮은 task가 작업하는 동안 기다리는 경우

  • OS가 방지할 수 있는 상황이 아니다.

• Unbounded priority inversion

  1. T3: s locked → T1 도착
  2. T1: attempt to lock s → fail → blocked → T3 실행 → T2 도착
  3. T2: 실행
     

     locking과 관련 없는 task가 lock 때문에 더 높은 우선순위의 task(blocked)보다 먼저 실행하게 되는 상황으로 막아야 한다.

• Priority inheritance: 우선순위가 낮은 task가 우선순위가 높은 task가 필요로 하는 자원을 가지고 있을 때, 전자의 우선순위를 일시적으로 높여주는 방식이다.

Windows Scheduling

• Multi-level Priority Queue(Global queue)
  • Real-time Priority Queues 16개
    • 고정된 우선순위를 사용한다.
    • 같은 우선순위를 갖는 task들은 RR을 사용한다.
  • Variable(non real-time) Priority Queues 16개
    • Feedback Queue 사용
    • 주어진 time quantum을 꽉 채워서 쓰면 우선순위가 내려가고, 덜 쓰거나 I/O 작업을 많이 하면 우선순위가 올라간다.
    • Burst time이 길면 우선순위가 내려가고, 짧으면 우선순위가 올라간다.
    • 일정 범위 내에서 우선순위가 변화한다.
• 우선순위 기반의 Preemptive 스케줄링
  • Process Priority: base priority(프로세스 종류에 따라 정해진다.)
  • Thread's Base Priority: base priority += 2
  • Thread's Dynamic Priority: 스케줄러가 결정하는 우선순위로 Thread's Base Priority의 최하한값보다 아래로 떨어지지 않는다.
    
• Multiprocessor Scheduling w / N Processors
  • 우선순위 큐가 global queue이기 때문에 idle-while-busy가 발생하지 않는다.
  • 다른 스레드보다 우선순위가 낮은 스레드가 먼저 실행되지 않는다.
  • N개의 가장 우선순위가 높은 스레드가 N개의 프로세서에서 실행된다.
  • Soft affinity: 같은 스레드는 같은 프로세서에서 실행되게 한다. (cache)
• starvation 발생 가능성이 있고 공평하지 않다.

UNIX SVR4 Scheduling

• 160개의 큐를 가지고 있다.
  • 우선순위가 가장 높은 159~100번 큐: real-time proceesses
  • 중간 순위의 99~60번 큐: kernel-mode processes
  • 우선순위가 가장 낮은 59~0번 큐: user-mode processes
• 큐가 많기 때문에 대부분의 큐가 비어 있을 것이다.
  • 큐에 프로세스가 들어 있으면 1, 없으면 0으로 표시한다.
  • 정수 5개와 32비트만 검사하면 우선순위가 가장 높은 큐에 들어있는 프로세를 꺼내서 실행할 수 있다.
  • 큐가 많아도 dispatching할 때 윈도우보다 시간이 더 걸리는 것은 아니다.
    
• 우선순위 기반의 Preemptive 스케줄링
• real-time class(159~100): 같은 우선순위인 프로세스들을 RR로 처리한다.
  • 고정된 우선순위와 고정된 time quantum
• time-sharing class(59~0): 우선순위 변화(피드백)
  • Processor-bound threads down
  • I/O-bound threads up
  • 우선순위가 낮은 프로세스들에게 높은 프로세스보다 더 많은 time quantum을 할당하여 starvation 발생 가능성을 줄이게 한다. 공정성도 고려한 것이다.

Linux Scheduling

• 우선순위 기반의 Preemptive 스케줄링
• Scheduling classes
  • SCHED_FIFO(0~99): real-time threads
    • real-time task의 실행 시간이 굉장히 짧다는 가정 하에 FIFO로 지정 가능하다. 시스템 설계자의 선택 사항이다.
  • SCHED_RR(0~99): real-time threads
  • SCHED_OTHER(100~139): non real-time threads
• SCHED_FIFO
  • 더 높은 우선순위 큐에서 프로세스가 나타나면 실행을 멈춘다. Preemptive
  • I/O 및 동기화 작업 등으로 blocked되면 실행을 멈춘다.
  • 시스템 콜을 호출하면 실행을 멈춘다.
  • 큐에 먼저 도착한 순서대로 실행한다.
• SCHED_RR
  • 타임 슬라이스를 해서 같은 우선순위의 프로세스들을 번갈아 가면서 실행한다.
• Non real-time threads scheduling
  • 40개의 active queue, 40개의 expired queue가 있다.
  • active queue에서 우선순위 순서대로 프로세스를 실행한다.
  • 주어진 time quantum을 다 쓰면 expired queue로 들어간다.
  • 주어진 time quantum을 다 못 쓰면 다시 active queue로 들어간다.
  • active queue가 빈 상태가 되면 expired queue를 active queue로, active queue를 expired queue로 바꾼다.
    • 바뀌면서 특정 프로세스의 우선순위가 바뀔 수 있다.
  • 앞 선 Windows, UNIX보다 starvation 발생 가능성이 훨씬 적고 fairness가 높다.