Lecture #8 Multiprocessor and Real-time Scheduling

Operating System2 다중 처리기의 분류 n Loosely coupled multiprocessor u 각 프로세서가 자기 고유의 지역 메모리와 I/O 채널을 가진다 u Distributed system, clustered system 등 n Functionally specialized processors u I/O processor 등 u master processor 에 의해 제어된다 n Tightly coupled multiprocessing u 모든 프로세서가 주기억장치를 공유한다 u SMP 등

Operating System3 처리 병렬성 (Processing Parallelism) n Synchronization Granularity u Frequency of synchronization between processes n Independent Parallelism u 다수의 연관성이 없는 프로세스 사이의 병렬성 n Very coarse grained parallelism u 네트워크 노드 상의 분산 처리 (distributed processing) n Coarse grained parallelism u 다중 프로그래밍 환경에서 프로세스들의 다중 처리 (multiprocessing) n Medium grained parallelism u 하나의 응용에서의 병렬 처리 (Parallel processing) u Thread 수준의 병렬성 n Fine grained parallelism u 명령어 수준의 병렬성

Operating System4 Independent Parallelism n Separate application or job n No synchronization among processes u Multiple unrelated processes n Example is time-sharing system

Operating System5 Very Coarse-Grained Parallelism n Distributed processing across network nodes to form a single computing environment n Good when there is infrequent interaction among processes u overhead of network would slow down communications

Operating System6 Coarse Parallelism n Synchronization among processes at a very gross level n Good for concurrent processes running on a multiprogrammed uniprocessor u Can by supported on a multiprocessor with little change

Operating System7 Medium-Grained Parallelism n Parallel processing or multitasking within a single application u Single application is a collection of threads u Threads usually interact frequently

Operating System8 Fine-Grained Parallelism n Much more complex use of parallelism than is found in the use of threads u parallelism inherent in a single instruction stream n Highly parallel applications n Specialized and fragmented area

Operating System9

10 Design Issues of Multiprocessor Scheduling n 프로세스를 어느 처리기에 할당할 것인가 ? n 각 처리기에서 다중프로그래밍을 지원할 것인가 ? n 다음에 실행할 프로세스로 어떤 프로세스를 선택할 것인가 ?

11 Assignment of Processes to Processors (1) n Treat processors as a pooled resource and assign process to processors on demand n Permanently assign process to a processor u Known as group or gang scheduling u Dedicate short-term queue for each processor u Less overhead u Processor could be idle while another processor has a backlog

12 Assignment of Processes to Processors (2) n Global queue u Schedule to any available processor n Master/slave architecture u Key kernel functions always run on a particular processor u Master is responsible for scheduling u Slave sends service request to the master u Disadvantages F Failure of master brings down whole system F Master can become a performance bottleneck

13 Assignment of Processes to Processors (3) n Peer architecture u Operating system can execute on any processor u Each processor does self-scheduling u Complicates the operating system F Make sure two processors do not choose the same process

Operating System14 Process Scheduling n Single queue for all processes n Multiple queues are used for priorities n All queues feed to the common pool of processors

Operating System15 Thread Scheduling n Executes separate from the rest of the process n An application can be a set of threads that cooperate and execute concurrently in the same address space n Threads running on separate processors yields a dramatic gain in performance

Operating System16 다중 처리기 스케줄링 (Multiprocessor Scheduling) (1) n Multiprocessor thread scheduling u Load sharing F processes are not assigned to a particular processor u Gang scheduling F a set of related threads is scheduled to run on a set of processors at the same time u Dedicated processor assignment F threads are assigned to a specific processor u Dynamic scheduling F number of threads can be altered during course of execution

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

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

Operating System19 다중 처리기 스케줄링 (Multiprocessor Scheduling) (4) n Dynamic Scheduling u 프로세스를 구성하는 스레드 수가 실행되는 동안에 동적으로 변하는 경우 u 운영체제가 각 프로세서의 부하를 고려하여 프로세서를 할당한다 u 어떤 작업이 동적으로 하나 또는 그 이상의 처리기를 요구할 경우 : F Assign idle processors F New arrivals may be assigned to a processor that is used by a job currently using more than one processor F Hold request until a processor is available F Assign a processor to a job in the list that currently has no processors (i.e., to all waiting new arrivals)

Operating System20 실시간 시스템 (Real-Time System) n 실시간 시스템 (Real-Time System) u 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 u Task Deadline - 외부 사건에 실시간을 대처하는 태스크의 시작 및 종료 시간 u 분 류 – deadline 준수 강도에 따라 F 경성 실시간 시스템 (Hard Real-Time System) F 연성 실시간 시스템 (Soft Real-Time System) u 예 : F Control of laboratory experiments F Process control plants F Robotics F Air traffic control F Telecommunications

Operating System21 실시간 운영체제의 특성 (1) n Deterministic u Operations are performed at fixed, predetermined times or within predetermined time intervals u 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 n Responsiveness u How long, after acknowledgment, it takes the operating system to service the interrupt u Includes amount of time to begin execution of the interrupt u Includes the amount of time to perform the interrupt u Effect of interrupt nesting

Operating System22 실시간 운영체제의 특성 (2) n User control u User specifies priority u Specify paging u What processes must always reside in main memory u Disks algorithms to use u Rights of processes n Reliability u Degradation of performance may have catastrophic consequences n Fail-soft operation u Ability of a system to fail in such a way as to preserve as much capability and data as possible u Stability

Operating System23 실시간 운영체제의 기술적 특징 (1) n Fast process or thread switch n Small size n Ability to respond to external interrupts quickly n Multitasking with interprocess communication tools such as semaphores, signals, and events

Operating System24 실시간 운영체제의 기술적 특징 (2) n Use of special sequential files that can accumulate data at a fast rate n Preemptive scheduling base on priority n Minimization of intervals during which interrupts are disabled n Delay tasks for fixed amount of time n Special alarms and timeouts

Operating System25 Scheduling of a Real-Time Process (1)

Operating System26 Scheduling of a Real-Time Process (2)

Operating System27 Real-Time Scheduling n Static table-driven u Determines at run time when a task begins execution u e.g) Deadline scheduling n Static priority-driven preemptive u Traditional priority-driven scheduler is used u e.g) Rate monotonic algorithm n Dynamic planning-based u Feasibility determined at run time n Dynamic best effort u No feasibility analysis is performed

Operating System28 Deadline Scheduling (1) n Real-time applications are not concerned with speed but with completing tasks n Information used for real-time task scheduling u Ready time u Starting deadline u Completion deadline u Processing time u Resource requirements u Priority u Subtask scheduler

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

Operating System30 Two Tasks

Operating System31

Operating System32

Operating System33

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

Operating System35 Periodic Task Timing Diagram

Operating System36

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

Operating System38 Priority Inversion n Can occur in any priority-based preemptive scheduling scheme n Occurs when circumstances within the system force a higher priority task to wait for a lower priority task

Unbounded Priority Inversion Operating System39 n Duration of a priority inversion depends on unpredictable actions of other unrelated tasks

Priority Inheritance Operating System40 n Lower-priority task inherits the priority of any higher priority task pending on a resource they share

Operating System41 Thread Scheduling (1)  Possible scheduling of user-level threads u 50-msec process quantum / threads run 5 msec/CPU burst u 응용 스레드 스케줄러 사용으로 보다 효율적으로 스케줄링 가능 F 스레드 문맥 교환은 운영체제의 개입이 필요 없어 간단

Operating System42 Thread Scheduling (2)  Possible scheduling of kernel-level threads u 50-msec process quantum / threads run 5 msec/CPU burst u 커널 스케줄러에 의해 스레드 스케줄링이 실행 F 스레드 문맥 교환 비용이 크다 A1 스레드가 블록킹 된 후에 다른 스레드로 스케줄링할 때에 A2 와 B1 스레드의 중요도가 같으나 문맥교환 비용이 B1 이 높을 때에 다음에 실행될 스레드는 ?

Operating System43 알고리즘 평가 n Which one is best? n The answer depends on: u on the system workload (extremely variable) u hardware support for the dispatcher u relative weighting of performance criteria (response time, CPU utilization, throughput...) u evaluation method used n 평가 방법 u 결정성 모형화 (Deterministic Modeling) u 큐잉 모형 (Queueing Model) u 모의실험 (Simulation) u 구현 (Implementation)

Operating System44 Linux Scheduling n Scheduling classes u SCHED_FIFO: First-in-first-out real-time threads u SCHED_RR: Round-robin real-time threads u SCHED_OTHER: Other, non-real-time threads n Within each class multiple priorities may be used

Operating System45

Operating System46 Non-Real-Time Scheduling n Linux 2.6 uses a new scheduler the O(1) scheduler n Time to select the appropriate process and assign it to a processor is constant u Regardless of the load on the system or number of processors

Operating System47

Operating System48 UNIX SVR4 Scheduling n Highest preference to real-time processes n Next-highest to kernel-mode processes n Lowest preference to other user-mode processes

Operating System49 UNIX SVR4 Scheduling n Preemptable static priority scheduler n Introduction of a set of 160 priority levels divided into three priority classes n Insertion of preemption points

Operating System50 SVR4 Priority Classes

Operating System51 SVR4 Priority Classes Real time (159 – 100) u Guaranteed to be selected to run before any kernel or time- sharing process u Can preempt kernel and user processes Kernel (99 – 60) u Guaranteed to be selected to run before any time-sharing process n Time-shared (59-0) u Lowest-priority

Operating System52 SVR4 Dispatch Queues

Operating System53 Windows Scheduling n Priorities organized into two bands or classes u Real time u Variable n Priority-driven preemptive scheduler

Operating System54

Operating System55