chapter 10 - multiprocessor and real time scheduling Flashcards
classification of multiprocessor systems?
loosely coupled, tightly coupled, functionally specialized processors
what is a loosely coupled multiprocessor?
distributed multiprocessor/cluster
Relatively autonomous systems, with each processor having its own memory and I/O channels
what is tightly coupled multiprocessesing?
Processors share main memory and are controlled by an operating system
what are functionally specialized processors?
Such as I/O processor controlled by a master processor
specialized processor controlled by a master processor
what is granularity?
the frequency of synchronization between the processes in a system.
what are the types of granularity?
independent parallelism, fine-grained, medium-grained, coarse, very coarse
what is independent parallelism?
unrelated processes, no synchronization
what is coarse-grained parallelism?
multiprocessing of concurrent processes in a multiprogramming environment
what is very coarse-grained parallelism?
distributed processing across network nodes to form a single computing environment
what is medium grained parallelism?
parallel processing or multitasking within a single application (threads)
what is fine-grained parallelism?
parallelism inherent in a single instruction stream
what do independent, coarse, and very coarse parallelism have in common?
supported by either a multiprogrammed uniprocessor or multiprocessor with little to no impact on scheduling
what makes medium grained parallelism unique?
scheduling decisions of one thread can affect the entire application’s performance
3 issues that come with scheduling on a multiprocessor
- assignment of processes to processor
- use of multiprogramming on individual processors
- actual dispatching of a process
assignment of processes to processor (issue 1) - static assignment
assigns process to a processor where it stays until finished
assignment of processes to processor (issue 1) - static assignment - advantages
May require less overhead in the scheduling function since processor assignment is only made once.
Permits group or gang scheduling
assignment of processes to processor (issue 1) - static assignment - disadvantages
Doesn’t distribute workload well (process could wait while a CPU is free)
Could periodically redistribute processes to balance the queues.
assignment of processes to processor (issue 1) - variable assignment -
Assign process from single queue to any free processor.
Distributes work-load more evenly among processors.
2 approaches for assignment of processes to processors (issue 1)
master/slave, peer approach
what is the master/slave approach in assignment of processes to processors (issue 1)
one CPU (or set of CPUs) is dedicated to OS. Schedules all jobs. Simplifies OS, but not as fault-tolerant and may be performance bottleneck.
a variation uses multiple CPUs for kernel processes
what is the peer approach in assignment of processes to processors (issue 1)
processors do self-scheduling. Complicates the OS but is more fault-tolerant
why is multiprogramming desirable in uniprocessor systems? (issue 2)
achieves better processor utilization
having a single processor be busy all the time when there are many processors may not be ideal as having applications perform better on average
explain process dispatching (issue 3)
When a single processor is used, different scheduling algorithms may be used to increase system performance or meet system objectives.
However, studies show that the particular scheduling algorithm chosen for multiprocessor systems is less important than for uniprocessor systems.
FCFS is the best for a multiprocessor system
what are the 4 approaches for multiprocessor thread scheduling?
load sharing, gang scheduling, dedicated processor assignment, dynamic scheduling
what is load sharing (approach 1)?
one of the simplest, most used schemes. processes not assigned to any particular processor, CPUs self schedule from a global queue of ready threads
what are the advantages of load sharing (approach 1)?
Even distribution of work across CPUs.
No centralized scheduler required (each CPU self-schedules).
Each processor selects a process from a global ready queue using any of the schemes
what are the disadvantages of load sharing (approach 1)?
The global queue may become a bottleneck to system performance.
Preempted threads unlikely to resume on same CPU, therefore less efficient caching.
Unlikely to have all threads of a program in execution at the same time, so if threads have high degree of coordination, not very efficient.
what is gang scheduling (approach 2)
Scheduling threads of a single process to run at the same time.
If a thread is running and needs to wait on another thread that is not running, a thread-switch must occur to bring in the needed thread. - can reduce performance
improves performance in medium-grained applications where synchronization is important
what are the approaches for gang scheduling?
uniform division, division by weights
what is uniform division?
gang scheduling approach
If there are M processes and N processors, give each process all N processors for 1/M amount of time.
Unfortunately, if for example there are two processes, one with 4 threads and one with 1 thread, then 3 CPUs are idle when the 1-thread process runs.
what is division by weights?
gang scheduling approach
If there are M processes and N processors, give each process all N processors for 1/M amount of time.
Unfortunately, if for example there are two processes, one with 4 threads and one with 1 thread, then 3 CPUs are idle when the 1-thread process runs.
In the above situation, let the 4-thread process have 4/5 of the time, and the 1-thread process 1/5 of the time.
what is dedicated processor assignment (approach 3)
extension of gang scheduling
dedicate group of processors to an application for duration of its execution
avoids process switching of the application - improves speedup
what is dynamic scheduling? (approach 4)
Involves cooperation between the OS and the application in dynamically deciding on the number of threads to run.
The OS gives the process some number of processors on which to run.
The process makes decisions about which of its threads to run on the available processors.
Still somewhat experimental.
what is real-time scheduling?
A real-time computing system must not only assure the correct results, but also assure the time at which they are produced.
types of real-time tasks?
hard real-time task, soft real-time task, aperiodic, periodic
what is a hard real-time task?
must meet deadline or system fails
what is a soft real-time task?
should meet deadline but isn’t mandatory
what is aperiodic real-time task?
has deadline or time constraint it needs to finish in
what is periodic real-time task?
has to finish exactly T time units apart
5 characteristics of real time operating systems?
determinism, responsiveness, user control, reliability, fail-soft operation
what is determinism? (characteristic 1)
Determinism is the extent to which the OS performs an operation at fixed, predetermined times or within predetermined time intervals.
time to acknowledge interrupt/request
what is responsiveness? (characteristic 2)
time to process request
Responsiveness is concerned with how long it takes to service an interrupt once it has been acknowledged.
Determinism (time to acknowledge interrupt) plus responsiveness (time to service interrupt) together make up the response time.
what is user control? (characteristic 3)
user given high degree of control over scheduling of tasks in real-time OS
what is reliability? (characteristic 4)
how reliable system is
what is fail-soft operation? (characteristic 5)
ability to fail in a way to preserve as much capability and data as possible
stability is important aspect - meet the most critical ones if you can’t get all the requests
how does fail-soft differ from fail-safe?
fail-soft: maintains partial functionality
fail-safe: avoids unsafe behavior
4 approaches to real-time scheduling
static table-driven, static priority-driven, dynamic planning-based, dynamic best effort
what is static table-driven approach?
real-time scheduling approach.
schedule is computed in advance from set of jobs and their requirements. Predictable, but not flexible. New job requires schedule to be redone.
what is static priority-driven approach?
real-time scheduling approach.
priorities are assigned to jobs in advance from set of jobs and their requirements, but no explicit schedule is produced. Relies on normal priority-driven preemptive scheduler.
what is dynamic planning based approach?
real-time scheduling approach.
allows accepting new tasks at run-time. Does feasibility analysis of existing jobs plus new job to see if new job can be fit in.
what is dynamic best effort approach?
real-time scheduling approach.
assigns priorities based on task characteristics. System tries to meet all deadlines, and aborts jobs that do not. Easy to implement, but until a deadline arrives, it is unknown whether it will be met.
7 scheduling factors
ready time, starting deadline, completion deadline, processing time, resource requirements, priority, subtask structure
what is rate monotonic scheduling?
can be used for periodic tasks
assigns priorities to tasks on the basis of their periods (high priority = shorter period)
