Multiprocessor and Real-time Scheduling

Presentation on theme: "Multiprocessor and Real-time Scheduling"— Presentation transcript:

1 Multiprocessor and Real-time Scheduling
Lecture #8 Multiprocessor and Real-time Scheduling 신라대학교 컴퓨터공학과 운영체제

2 다중 처리기의 분류 Loosely coupled multiprocessor
각 프로세서가 자기 고유의 지역 메모리와 I/O 채널을 가진다 Distributed system, clustered system 등 Functionally specialized processors I/O processor 등 master processor에 의해 제어된다 Tightly coupled multiprocessing 모든 프로세서가 주기억장치를 공유한다 SMP 등 신라대학교 컴퓨터공학과 운영체제

3 프로세스 병렬성(Process Parallelism)
Synchronization Granularity Independent Parallelism 다수의 연관성이 없는 프로세스 사이의 병렬성 Very coarse grained parallelism 네트워크 노드 상의 분산 처리(distributed processing) Coarse grained parallelism 다중 프로그래밍 환경에서 프로세스들의 다중 처리 (multiprocessing) Medium grained parallelism 하나의 응용에서의 병렬 처리(Parallel processing) Thread 수준의 병렬성 Fine grained parallelism 명령어 수준의 병렬성 신라대학교 컴퓨터공학과 운영체제

4 Independent Parallelism
Separate application or job No synchronization among processes Example is time-sharing system 신라대학교 컴퓨터공학과 운영체제

5 Coarse and Very Coarse-Grained Parallelism
Synchronization among processes at a very gross level Good for concurrent processes running on a multiprogrammed uniprocessor Can by supported on a multiprocessor with little change 신라대학교 컴퓨터공학과 운영체제

6 Medium-Grained Parallelism
Single application is a collection of threads Threads usually interact frequently 신라대학교 컴퓨터공학과 운영체제

7 Fine-Grained Parallelism
Highly parallel applications Specialized and fragmented area 신라대학교 컴퓨터공학과 운영체제

8 신라대학교 컴퓨터공학과 운영체제

9 Process Scheduling Single queue for all processes
Multiple queues are used for priorities All queues feed to the common pool of processors 신라대학교 컴퓨터공학과 운영체제

10 Thread Scheduling Executes separate from the rest of the process
An application can be a set of threads that cooperate and execute concurrently in the same address space Threads running on separate processors yields a dramatic gain in performance 신라대학교 컴퓨터공학과 운영체제

11 다중 처리기 스케줄링 (Multiprocessor Scheduling) (1)
Multiprocessor thread scheduling Load sharing processes are not assigned to a particular processor Gang scheduling a set of related threads is scheduled to run on a set of processors at the same time Dedicated processor assignment threads are assigned to a specific processor Dynamic scheduling number of threads can be altered during course of execution 신라대학교 컴퓨터공학과 운영체제

12 다중 처리기 스케줄링 (Multiprocessor Scheduling) (2)
Load Sharing(부하 분산) 부하를 모든 프로세서에 대해 적절하게 분산한다 유휴 프로세서가 없음을 보장 중앙 집중식 스케줄러가 필요 없다 global queue을 사용 단 점: global queue에 대한 상호배제  하나 이상의 프로세서가 동시에 실행할 작업을 얻고자 할 때에 bottleneck이 될 수 있다 선점된 스레드가 동일한 프로세서에서 실행을 재개할 가능성이 적다  캐시의 효율성을 떨어뜨린다 하나의 프로그램을 구성하는 모든 스레드가 동시에 프로세서를 얻어 실행할 가능성이 적다 신라대학교 컴퓨터공학과 운영체제

13 다중 처리기 스케줄링 (Multiprocessor Scheduling) (3)
Gang Scheduling 하나의 프로세스을 구성하는 모든 스레드들에 대해 동시 스케줄링 응용 프로그램의 부분적인 실행으로 성능이 심각하게 떨어지는 응용 프로그램에 대해서는 유용하다 스레드는 상호간에 동기화를 종종 요구한다 Dedicated Processor Scheduling 하나의 프로세스를 구성하는 모든 스레드를 하나의 프로세서에 할당한다 일부 프로세서가 유휴상태가 될 수 있다 process switching을 피한다 신라대학교 컴퓨터공학과 운영체제

14 다중 처리기 스케줄링 (Multiprocessor Scheduling) (4)
Dynamic Scheduling 프로세스를 구성하는 스레드 수가 실행되는 동안에 동적으로 변하는 경우 운영체제가 각 프로세서의 부하를 고려하여 프로세서를 할당한다 Assign idle processors New arrivals may be assigned to a processor that is used by a job currently using more than one processor Hold request until a processor is available Assign a processor to a job in the list that currently has no processors (i.e., to all waiting new arrivals) 신라대학교 컴퓨터공학과 운영체제

15 실시간 시스템(Real-Time System)
Correctness of the system depends not only on the logical result of the computation but also on the time at which the results are produced Task Deadline - 외부 사건에 실시간을 대처하는 태스크의 시작 및 종료 시간 분 류 – deadline 준수 강도에 따라 경성 실시간 시스템(Hard Real-Time System) 연성 실시간 시스템(Soft Real-Time System) 예 : Control of laboratory experiments Process control plants Robotics Air traffic control Telecommunications 신라대학교 컴퓨터공학과 운영체제

16 실시간 운영체제의 특성 (1) Deterministic Responsiveness
Operations are performed at fixed, predetermined times or within predetermined time intervals Concerned with how long the operating system delays before acknowledging an interrupt and there is sufficient capacity to handle all the requests within the required time Responsiveness How long, after acknowledgment, it takes the operating system to service the interrupt Includes amount of time to begin execution of the interrupt Includes the amount of time to perform the interrupt Effect of interrupt nesting 신라대학교 컴퓨터공학과 운영체제

17 실시간 운영체제의 특성 (2) User control Reliability Fail-soft operation
User specifies priority Specify paging What processes must always reside in main memory Disks algorithms to use Rights of processes Reliability Degradation of performance may have catastrophic consequences Fail-soft operation Ability of a system to fail in such a way as to preserve as much capability and data as possible Stability 신라대학교 컴퓨터공학과 운영체제

18 실시간 운영체제의 기술적 특징 (1) Fast process or thread switch Small size
Ability to respond to external interrupts quickly Multitasking with interprocess communication tools such as semaphores, signals, and events 신라대학교 컴퓨터공학과 운영체제

19 실시간 운영체제의 기술적 특징 (2) Use of special sequential files that can accumulate data at a fast rate Preemptive scheduling base on priority Minimization of intervals during which interrupts are disabled Delay tasks for fixed amount of time Special alarms and timeouts 신라대학교 컴퓨터공학과 운영체제

20 Scheduling of a Real-Time Process (1)
신라대학교 컴퓨터공학과 운영체제

21 Scheduling of a Real-Time Process (2)
신라대학교 컴퓨터공학과 운영체제

22 Real-Time Scheduling Static table-driven
Determines at run time when a task begins execution e.g) Deadline scheduling Static priority-driven preemptive Traditional priority-driven scheduler is used e.g) Rate monotonic algorithm Dynamic planning-based Feasibility determined at run time Dynamic best effort No feasibility analysis is performed 신라대학교 컴퓨터공학과 운영체제

23 Deadline Scheduling (1)
Real-time applications are not concerned with speed but with completing tasks Information used for real-time task scheduling Ready time Starting deadline Completion deadline Processing time Resource requirements Priority Subtask scheduler 신라대학교 컴퓨터공학과 운영체제

24 Deadline Scheduling (2)
Earliest deadline scheduling 데드라인이 가장 임박한 태스크를 먼저 실행하도록 스케줄링 데드라인이 가장 가까운 태스크에게 높은 우선순위를 부여 데드라인을 만족시켜 주지 못하는 태스크의 수를 최소화 단일 처리기/다중 처리기 시스템 모두에 적용 가능 모드 태스크들이 주기적으로 실행되고 또 예측 가능하여야 함 자발적 유휴 시간을 허용하는 earliest deadline scheduling 기본적으로 earliest deadline scheduling 정책에 따라 스케줄링 충분한 데드라인을 가지는 타스크에 대해 유휴 시간을 가지게 함으로써 다른 타스크에 대한 스케줄링에 융통성을 제공 신라대학교 컴퓨터공학과 운영체제

25 Two Tasks 신라대학교 컴퓨터공학과 운영체제

26 신라대학교 컴퓨터공학과 운영체제

27 신라대학교 컴퓨터공학과 운영체제

28 신라대학교 컴퓨터공학과 운영체제

29 Rate Monotonic Scheduling
Assigns priorities to tasks on the basis of their periods Task period T 어떤 타스크의 인스턴스가 도착한 후부터 다음 번의 인스턴스가 도착할 때까지의 시간 타스크의 경성 데드라인 역할 Task rate R - 타스크 주기의 역수, Hz 단위로 표시 Highest-priority task is the one with the shortest period 주기적 실시간 다중 타스크들을 스케줄링할 때 발생하는 문제점들을 효율적으로 해결 신라대학교 컴퓨터공학과 운영체제

30 Periodic Task Timing Diagram
신라대학교 컴퓨터공학과 운영체제

31 신라대학교 컴퓨터공학과 운영체제

32 Earliest Deadline Scheduling(EDS) vs. Rate Monotonic Scheduling(RMS)
EDS가 이론적으로 더 높은 처리기 이용률을 달성하여 RMS보다 더 많은 주기적 타스크들을 스케줄링 가능 반면, 상용 실시간 시스템에서는 RMS를 광범위하게 사용 두 스게줄링 정책의 성능 차이가가 현실적으로 크기 않다 경성 실시간 타스크와 연성 실시간 타스크가 동시에 지원되는 환경에서 RMS는 경성 실시간 타스크 스케줄링 과정에서 발생하는 유휴 처리기 시간을 이용하 연성 실시간 타스크를 스케줄링함으로써 시스템 효율성을 높임 RMS가 EDS보다 높은 시스템 안정성을 확보 신라대학교 컴퓨터공학과 운영체제

33 Priority Inversion Can occur in any priority-based preemptive scheduling scheme Occurs when circumstances within the system force a higher priority task to wait for a lower priority task 신라대학교 컴퓨터공학과 운영체제

34 Unbounded Priority Inversion
Duration of a priority inversion depends on unpredictable actions of other unrelated tasks 신라대학교 컴퓨터공학과 운영체제

35 Priority Inheritance Lower-priority task inherits the priority of any higher priority task pending on a resource they share 신라대학교 컴퓨터공학과 운영체제

36 Thread Scheduling (1) Possible scheduling of user-level threads
50-msec process quantum / threads run 5 msec/CPU burst 응용 스레드 스케줄러 사용으로 보다 효율적으로 스케줄링 가능 스레드 문맥 교환은 운영체제의 개입이 필요 없어 간단 신라대학교 컴퓨터공학과 운영체제

37 Thread Scheduling (2) Possible scheduling of kernel-level threads
A1 스레드가 블록킹 된 후에 다른 스레드로 스케줄링할 때에 A2와 B1 스레드의 중요도가 같으나 문맥교환 비용이 B1이 높을 때에 다음에 실행될 스레드는? Possible scheduling of kernel-level threads 50-msec process quantum / threads run 5 msec/CPU burst 커널 스케줄러에 의해 스레드 스케줄링이 실행 스레드 문맥 교환 비용이 크다 신라대학교 컴퓨터공학과 운영체제

38 알고리즘 평가 Which one is best? The answer depends on: 평가 방법
on the system workload (extremely variable) hardware support for the dispatcher relative weighting of performance criteria (response time, CPU utilization, throughput...) evaluation method used 평가 방법 결정성 모형화(Deterministic Modeling) 큐잉 모형(Queueing Model) 모의실험(Simulation) 구현(Implementation) 신라대학교 컴퓨터공학과 운영체제

39 Linux Scheduling Scheduling classes
SCHED_FIFO: First-in-first-out real-time threads SCHED_RR: Round-robin real-time threads SCHED_OTHER: Other, non-real-time threads Within each class multiple priorities may be used 신라대학교 컴퓨터공학과 운영체제

40 신라대학교 컴퓨터공학과 운영체제

41 Non-Real-Time Scheduling
Linux 2.6 uses a new scheduler the O(1) scheduler Time to select the appropriate process and assign it to a processor is constant Regardless of the load on the system or number of processors 신라대학교 컴퓨터공학과 운영체제

42 신라대학교 컴퓨터공학과 운영체제

43 UNIX SVR4 Scheduling Highest preference to real-time processes
Next-highest to kernel-mode processes Lowest preference to other user-mode processes 신라대학교 컴퓨터공학과 운영체제

44 UNIX SVR4 Scheduling Preemptable static priority scheduler
Introduction of a set of 160 priority levels divided into three priority classes Insertion of preemption points 신라대학교 컴퓨터공학과 운영체제

45 SVR4 Priority Classes 신라대학교 컴퓨터공학과 운영체제

46 SVR4 Priority Classes Real time (159 – 100) Kernel (99 – 60)
Guaranteed to be selected to run before any kernel or time-sharing process Can preempt kernel and user processes Kernel (99 – 60) Guaranteed to be selected to run before any time-sharing process Time-shared (59-0) Lowest-priority 신라대학교 컴퓨터공학과 운영체제

47 SVR4 Dispatch Queues 신라대학교 컴퓨터공학과 운영체제

48 Windows Scheduling Priorities organized into two bands or classes
Real time Variable Priority-driven preemptive scheduler 신라대학교 컴퓨터공학과 운영체제

49 신라대학교 컴퓨터공학과 운영체제

50 신라대학교 컴퓨터공학과 운영체제