Chapter 10 (Multiprocessor and Real-Time Scheduling)

Question 1

What are the classifications of multiprocessor systems?

Answer 1

Loosely coupled

Tightly coupled

Functionally specialized

Question 2

Which classification of multiprocessor systems have its own memory and I/O channels?

Answer 2

Loosely coupled

Question 3

Which classification of multiprocessor systems share main memory and are controlled by an OS?

Answer 3

Tightly coupled

Question 4

What are the different levels of granularity?

Answer 4

Independent parallelism

Course/Very coarse-grained parallelism

Medium-grained parallelism

Fine-grained parallelism

Question 5

What is independent parallelism?

Answer 5

Unrelated processes, no synchronization

Question 6

What is course/Very coarse-grained parallelism

Answer 6

Gross level of synchronization

Question 7

What is medium-grained parallelism

Answer 7

Parallelism within an application (threads)

Question 8

What is fine-grained parallelism

Answer 8

Parallelism within an instruction stream

Question 9

Which granularity has this characteristic: Scheduling decisions of one thread may affect the performance of the entire application.

Answer 9

Medium-grained parallelism

Question 10

Which granularity has this characteristic: Supported by either a multiprogrammed uniprocessor or a multiprocessor with little or no impact on scheduling.

Answer 10

Independent, course, and very-course parallelsim

Question 11

What are the two methods of assigning processes to processors?

Answer 11

Static assignment

Variable assignment

Question 12

Advantages of static assignment

Answer 12

May require less overhead in the scheduling function since processor assignment is only made once

Permits group or gang scheduling

Question 13

What are the disadvantages of static assignment?

Answer 13

Doesn’t distribute workload well (process could wait while CPU is free)

Question 14

What are characteristics of variable assignment?

Answer 14

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

Question 15

What are some means to decide which process will execute on which processor?

Answer 15

Master/slave

Peer approach

Question 16

What is the peer approach?

Answer 16

Processors do self-scheduling

Question 17

What is the master/slave approach?

Answer 17

One CPU dedicated to OS and schedules all jobs

Question 18

T/F The particular scheduling algorithm chosen for multiprocessor systems is less important than for uniprocessor systems

Answer 18

T

Question 19

What are four approaches for multiprocessor thread scheduling?

Answer 19

Load sharing

Gang scheduling

Dedicated processor assignment

Dynamic scheduling

Question 20

Advantages of load sharing

Answer 20

Even distribution of work across CPU’s

No centralized scheduler required

Each processor selects a process from a global ready queue

Question 21

Disadvantages of load sharing

Answer 21

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

Question 22

What is gang scheduling?

Answer 22

Scheduling threads of a single process to run at the same time

Question 23

How does dedicated processor assignment result in a speedup?

Answer 23

Avoids process switching by dedicating a group of processors to an application for the duration of its execution

Question 24

What are unused allocated processors in dedicated processor assignment similar to?

Answer 24

Fragmentation

Question 25

What is a hard real-time task?

Answer 25

One that must meet its deadline or else it could cause system failure

Question 26

What is a soft real-time task?

Answer 26

One that should meet its deadline but is not mandatory.

Question 27

What are aperiodic real-time tasks?

Answer 27

Has a deadline or time constraint by which it must start or finish

Question 28

What are periodic real-time tasks?

Answer 28

Once per time period T, or exactly T time units apart

Question 29

What are the characteristics of real-time operating systems?

Answer 29

``` Determinism Responsiveness User control Reliability Fail-soft operation ```

Question 30

What is determinism?

Answer 30

The extent to which the OS performs an operation at fixed, predetermined times or within predetermined time intervals

Question 31

What is responsiveness?

Answer 31

How long it takes to service an interrupt once it has been acknowledged

Question 32

What is user control?

Answer 32

User is given a much higher degree of control over the scheduling of tasks in a real-time OS

Question 33

What is fail-soft operation?

Answer 33

The ability to fail in such a way as to preserve as much capability and data as possible

Question 34

What's the difference between fail-safe and fail-soft?

Answer 34

Fail-soft maintains partial functionality while fail-safe avoids unsafe behavior

Question 35

What are the four basic approaches to real-time scheduling?

Answer 35

Static table-driven Static priority-driven Dynamic planning-based Dynamic best effort

Question 36

What is static table-driven scheduling?

Answer 36

Schedule is computed in advance from set of jobs and their requirements

Question 37

What is static priority-driven?

Answer 37

Priorities are assigned to jobs in advance from set of jobs and their requirements

Question 38

What is dynamic planning-based?

Answer 38

Allows accepting new tasks at run-time

Question 39

What is dynamic best effort?

Answer 39

Assigns priorities based on task characteristics

Question 40

T/F Rate-Monotonic scheduling performs worse than earliest deadline scheduling

Answer 40

F, it performs almost as well as earliest deadline

Question 41

T/F Rate-Monotonic can be easier to achieve stability by giving essential tasks shorter periods and thus higher priorities

Answer 41

T