Please enable JavaScript.
Coggle requires JavaScript to display documents.
Multiprocessor scheduling (Real-time scheduling (OS requirements (Fail…
Multiprocessor scheduling
Real-time scheduling
Tasks
Aperiodic
Starting and/or ending deadlines
Periodic
Once per period T
Exactly time T apart
Hard
Must meet deadline
Soft
Desirable, not mandatory deadline
OS requirements
Determinism
How long OS delays before acknowledging interrupt?
Responsiveness
How long until OS has serviced the interrupt?
User control
Control of priority
Reliability
Fail-soft operation
Ability to fail while preserving data and capability
Stability
At least meet critical deadlines if all cannot be met
Approaches
Static table-driven
#
Static analysis of feasible dispatch schedules
Analyse
Periodic arrival time
Periodic ending deadline
Relative priorities
Execution time
Predictable, inflexible
Static priority-driven pre-emptive
#
Static analysis to assign priorities
Dynamic planning-based
Determine feasibility @ runtime
Attempt new schedule after job arrival
Dynamic best-effort
#
No analysis, try to meet all deadlines
Deadline scheduling
Earliest-deadline
Rate monotonic scheduling
Shortest period > highest priority
Priority inversion
Unbounded priority inversion
Avoidance
Priority ceiling
Associate priorities w/ resources
Resource priority = 1+ higher than highest user
Assign resource priority to task while using
Priority inheritance
Lower-priority task inherits higher priority from task trying to access same resource
Disables unbounded inversion
Higher-priority task forced to wait for lower-priority
Low-priority holding locked resource
Granularity
= frequency of synchronization
Independent parallelism
No explicit synchro between processes
In time-sharing systems
Coarse-grained parallelism
On multiprogrammed uniprocessor
or multiprocessor, with little change
Medium-grained parallelism
Coordination among threads of a process
Fine-grained parallelism
Finer than thread cooperation
Scheduling issues
Assignment of processes to processors
Uniform architecture
Dynamic assignment
Static assignment
Short-term queue per processor
Advantages
Less overhead on scheduling function
Enables gang scheduling
Disadvantages
Idle & overbooked processors
Fix: common queue
Fix: dynamic load balancing
Master/slave
Key kernel functions on one processor (master)
Responsible for scheduling
User programs on others (slaves)
Request master for services (eg. I/O)
Disadvantages
Failure of master = rip
Master as bottleneck
Advantages
Simple, similar to uniprocessor multiprogramming
Peer
Kernel executes on any processor
Processors self-schedule
Disadvantages
Complicated
Preventing processors from picking same task?
Preventing processes from dropping from queue?
Resource competition?
Peer/master/slave fusion
Eg. group of processors as master
Use of multiprogramming on processors
#
Process dispatching
Thread scheduling
Approaches
Gang scheduling
Advantages
Less process switches
Scheduling related threads/processes together
Load sharing
Advantages
Simple, little change from uniprocessor environment
Load evenly on processors, no idling
Centralized scheduler not needed
Variants
FCFS
Threads of a new job placed at end of queue
Smallest # of threads first
Priority to jobs with less unscheduled threads
Pre-emptive smallest # of threads first
New job with smaller # of threads can pre-empt executing job
Disadvantages
Job queue must be accessed w/ mutex, can bottleneck w/ many processors
Pre-empted threads unlikely to resume on same processor, bad for caching
If threads scheduled irrespective of job, thread coordination takes a hit
Dynamic scheduling
Alters # of threads in process dynamically
Dedicated processor assignment
Dedicate group of processors to application
No multiprogramming