Chapter 10 (Multiprocessor and Real-Time Scheduling) Flashcards
What are the classifications of multiprocessor systems?
Loosely coupled
Tightly coupled
Functionally specialized
Which classification of multiprocessor systems have its own memory and I/O channels?
Loosely coupled
Which classification of multiprocessor systems share main memory and are controlled by an OS?
Tightly coupled
What are the different levels of granularity?
Independent parallelism
Course/Very coarse-grained parallelism
Medium-grained parallelism
Fine-grained parallelism
What is independent parallelism?
Unrelated processes, no synchronization
What is course/Very coarse-grained parallelism
Gross level of synchronization
What is medium-grained parallelism
Parallelism within an application (threads)
What is fine-grained parallelism
Parallelism within an instruction stream
Which granularity has this characteristic: Scheduling decisions of one thread may affect the performance of the entire application.
Medium-grained parallelism
Which granularity has this characteristic: Supported by either a multiprogrammed uniprocessor or a multiprocessor with little or no impact on scheduling.
Independent, course, and very-course parallelsim
What are the two methods of assigning processes to processors?
Static assignment
Variable assignment
Advantages of static assignment
May require less overhead in the scheduling function since processor assignment is only made once
Permits group or gang scheduling
What are the disadvantages of static assignment?
Doesn’t distribute workload well (process could wait while CPU is free)
What are characteristics of variable assignment?
Assigns process from single queue to any free processor
Distributes work load more evenly
Cost of scheduling a process is independent of the particular processor on which it is scheduled
What are some means to decide which process will execute on which processor?
Master/slave
Peer approach
What is the peer approach?
Processors do self-scheduling
What is the master/slave approach?
One CPU dedicated to OS and schedules all jobs
T/F The particular scheduling algorithm chosen for multiprocessor systems is less important than for uniprocessor systems
T
What are four approaches for multiprocessor thread scheduling?
Load sharing
Gang scheduling
Dedicated processor assignment
Dynamic scheduling
Advantages of load sharing
Even distribution of work across CPU’s
No centralized scheduler required
Each processor selects a process from a global ready queue
Disadvantages of load sharing
Global queue may become a bottleneck
Preempted threads unlikely to resume on same CPU, less efficient caching
Unlikely to have all threads of a program executing at the same time
What is gang scheduling?
Scheduling threads of a single process to run at the same time
How does dedicated processor assignment result in a speedup?
Avoids process switching by dedicating a group of processors to an application for the duration of its execution
What are unused allocated processors in dedicated processor assignment similar to?
Fragmentation
What is a hard real-time task?
One that must meet its deadline or else it could cause system failure
What is a soft real-time task?
One that should meet its deadline but is not mandatory.
What are aperiodic real-time tasks?
Has a deadline or time constraint by which it must start or finish
What are periodic real-time tasks?
Once per time period T, or exactly T time units apart
What are the characteristics of real-time operating systems?
Determinism Responsiveness User control Reliability Fail-soft operation
What is determinism?
The extent to which the OS performs an operation at fixed, predetermined times or within predetermined time intervals
What is responsiveness?
How long it takes to service an interrupt once it has been acknowledged
What is user control?
User is given a much higher degree of control over the scheduling of tasks in a real-time OS
What is fail-soft operation?
The ability to fail in such a way as to preserve as much capability and data as possible
What’s the difference between fail-safe and fail-soft?
Fail-soft maintains partial functionality while fail-safe avoids unsafe behavior
What are the four basic approaches to real-time scheduling?
Static table-driven
Static priority-driven
Dynamic planning-based
Dynamic best effort
What is static table-driven scheduling?
Schedule is computed in advance from set of jobs and their requirements
What is static priority-driven?
Priorities are assigned to jobs in advance from set of jobs and their requirements
What is dynamic planning-based?
Allows accepting new tasks at run-time
What is dynamic best effort?
Assigns priorities based on task characteristics
T/F Rate-Monotonic scheduling performs worse than earliest deadline scheduling
F, it performs almost as well as earliest deadline
T/F Rate-Monotonic can be easier to achieve stability by giving essential tasks shorter periods and thus higher priorities
T
