Chapter 10 Scheduling (Multiprocessor)
Classifications of Multiprocessor Systems
•Loosely coupled or distributed multiprocessor, or cluster
•Functionally specialized processors
•Tightly coupled multiprocessor
Grain(粒度)
Independent Parallelism（无约束并行性）
进程间没有显式的同步
•each user is performing a particular application
•because more than one processor is available, average response time to the users will be less
Coarse and Very Coarse Grained Parallelism
一组运行在a multiprogrammed uniprocessor（单处理器）的并发进程
–can be supported on a multiprocessor with little or no change to user software
Medium-Grained Parallelism
•Single application can be effectively implemented as a collection of threads within a single process
Fine-Grained Parallelism
•Represents a much more complex use of parallelism than is found in the use of threads
Design issues
•assignment of processes to processors(把进程分配到处理器)
需要决定static or dynamic
如果一个进程从被激活到完成，一直被分配给同一个处理器，那么就需要每个处理器维护一个专门的short-term queue, 使用专用处理器允许一种gang scheduling（组调度策略）
缺点：一个处理器空闲，另一个处理器积压很多工作，
-
为防止这个情况, a common queue can be used， 所有的进程进入这个全局队列，然后调度到任何一个可用的处理器中
-
another option is dynamic load balancing
Approaches
–Master/Slave
操作系统的核心功能总是在某个特定的处理器上运行
•Master is responsible for scheduling
•Slave sends service request to the master
•Conflict resolution is simplified because one processor has control of all memory and I/O resources
–Peer
•Kernel can execute on any processor
•Each processor does self-scheduling from the pool of available processes
•actual dispatching of a process
•use of multiprogramming on individual processors
Process Scheduling
有很多个基于优先级的队列
a multi-server queuing
对于双处理器，调度原则不如在单处理器中重要
Thread Scheduling
Load Sharing
系统维护一个就绪线程的全局队列，每个处理器只要空闲就从队列中选择一个线程。
缺点
- 处理器很多时，出现bottleneck
- 抢占线程不太可能在同一处理器上执行
- it is unlikely that all of the threads of a program will gain access to processors at the same time
Gang Scheduling
一组相关线程一对一对应到一组处理器上运行
Dedicated Processor Assignment
提供通过将线程分配给处理器定义的隐式调度
调度应用程序时，将其每个线程分配给一个处理器，该处理器将一直专用于该线程，直到应用程序运行到完成为止
•If a thread of an application is blocked waiting for I/O or for synchronization with another thread, then that thread’s processor remains idle
在具有数十或数百个处理器的高度并行系统中，处理器利用率不再像效率或性能指标那样重要
在程序的生命周期中完全避免进程切换应该会导致该程序的显著加速
Dynamic Scheduling
进程中的线程数可以在执行过程中更改
Real-Time Systems
Hard and Soft Real-Time Tasks
Hard必须在ddl之前 否则造成damage
Soft希望在ddl之前，之后完成也可以
Periodic and Aperiodic Tasks
周期性 非周期性
Characteristics of real time systems
-
Determinism可确定性
-
Responsiveness可响应性
Determinism is concerned with how long an operating system delays before acknowledging an interrupt. Responsiveness is concerned with how long, after acknowledgment, it takes an operating
system to service the interrupt.
-
User control用户控制
-
Reliability可靠性
-
Fail-soft operation故障弱化操作
Deadline Scheduling
RMS 最短周期任务具有最高优先级
