Transcript Week 10

2P13
Week 10
Page 1
Page 2
Static table-driven approaches
• performs a static analysis of feasible schedules of dispatching
• result is a schedule that determines, at run time, when a task must begin execution
Static priority-driven preemptive approaches
• a static analysis is performed but no schedule is drawn up
• analysis is used to assign priorities to tasks so that a traditional priority-driven
preemptive scheduler can be used
Dynamic planning-based approaches
• feasibility is determined at run time rather than offline prior to the start of execution
• one result of the analysis is a schedule or plan that is used to decide when to dispatch
this task
Dynamic best effort approaches
• no feasibility analysis is performed
• system tries to meet all deadlines and aborts any started process whose deadline is
missed
Page 3
• Real-time operating systems are designed with the
objective of starting real-time tasks as rapidly as
possible and emphasize rapid interrupt handling and
task dispatching
• Real-time applications are generally not concerned
with sheer speed but rather with completing (or
starting) tasks at the most valuable times
• Priorities provide a crude tool and do not capture the
requirement of completion (or initiation) at the most
valuable time
Page 4
Ready time
Starting
deadline
Completion
deadline
Processing
time
• time task becomes
ready for execution
Resource
requirements
• resources required by
the task while it is
executing
Priority
• measures relative
importance of the task
• time task must begin
• time task must be
completed
• time required to execute
the task to completion
One or the
other but
not both
Subtask
scheduler
• a task may be
decomposed into a
mandatory subtask and
an optional subtask
Page 5
Table 10.2
Execution Profile of Two Periodic Tasks
Process
Arrival Time
Execution Time
Ending Deadline
A(1)
0
10
20
A(2)
20
10
40
A(3)
40
10
60
A(4)
60
10
80
A(5)
80
10
100
•
•
•
•
•
•
•
•
•
•
•
•
B(1)
0
25
50
B(2)
50
25
100
•
•
•
•
•
•
•
•
•
•
•
•
Page 6
Figure 10.5 Scheduling of Periodic Real-Time Tasks With Completion Deadlines (Based on
Table 10.2)
Page 7
Figure 10.6 Scheduling of Aperiodic Real-Time Tasks With Starting Deadlines
Page 8
Table 10.3
Execution Profile of Five Aperiodic Tasks
Process
Arrival Time
Execution Time
Starting Deadline
A
10
20
110
B
20
20
20
C
40
20
50
D
50
20
90
E
60
20
70
Page 9
Rate
Monotonic
Schedulin
g
Figure 10.7
Page 10
Periodic Task
Timing Diagram
Figure 10.8
Page 11
Table 10.4 Value of the RMS Upper Bound
n(21 n 1)
n

1
1.0
2
0.828
3
0.779
4
0.756
5
0.743
6
0.734
•
•
•
•
•
•

ln 2  0.693
Page 12
Page 13
• External devices that engage in I/O with
computer systems can be grouped into three
categories:
Human readable
• suitable for communicating with the computer user
• printers, terminals, video display, keyboard, mouse
Machine readable
• suitable for communicating with electronic equipment
• disk drives, USB keys, sensors, controllers
Communication
• suitable for communicating with remote devices
• modems, digital line drivers
Page 14
Page 15
Devices differ in a number of areas:
Data Rate
• there may be differences of magnitude between the data transfer rates
Application
• the use to which a device is put has an influence on the software
Complexity of Control
• the effect on the operating system is filtered by the complexity of the I/O module that controls the device
Unit of Transfer
• data may be transferred as a stream of bytes or characters or in larger blocks
Data Representation
• different data encoding schemes are used by different devices
Error Conditions
• the nature of errors, the way in which they are reported, their consequences, and the
available range of responses differs from one device to another
Page 16
• Three techniques for performing I/O are:
• Programmed I/O
– the processor issues an I/O command on behalf of a process to an I/O module;
that process then busy waits for the operation to be completed before proceeding
• Interrupt-driven I/O
– the processor issues an I/O command on behalf of a process
• if non-blocking – processor continues to execute instructions from the
process that issued the I/O command
• if blocking – the next instruction the processor executes is from the OS,
which will put the current process in a blocked state and schedule another
process
• Direct Memory Access (DMA)
• a DMA module controls the exchange of data between main memory and an
I/O module
Page 17
Techniques for Performing I/O
Page 18
1
2
3
4
• Processor directly controls a peripheral device
• A controller or I/O module is added
• Same configuration as step 2, but now interrupts are employed
• The I/O module is given direct control of memory via DMA
5
• The I/O module is enhanced to become a separate processor,
with a specialized instruction set tailored for I/O
6
• The I/O module has a local memory of its own and is, in fact, a
computer in its own right
Page 19
Page 20
Page 21
• Functions of the operating system should be separated
according to their complexity, their characteristic time
scale, and their level of abstraction
• Leads to an organization of the operating system into a
series of layers
• Each layer performs a related subset of the functions
required of the operating system
• Layers should be defined so that changes in one layer
do not require changes in other layers
Page 22
Page 23
Page 24
Page 25
Table 11.2 Comparison of Disk Scheduling Algorithms
(a) FIFO
(starting at track
100)
(b) SSTF
(starting at track
100)
(c) SCAN
(starting at track
100, in the
direction of
increasing track
number)
(d) C-SCAN
(starting at track
100, in the
direction of
increasing track
number)
Next
track
access
ed
Numb
er of
tracks
traver
sed
Next
track
access
ed
Numb
er of
tracks
traver
sed
Next
track
access
ed
Numb
er of
tracks
traver
sed
Next
track
access
ed
Numb
er of
tracks
traver
sed
55
45
90
10
150
50
150
50
58
3
58
32
160
10
160
10
39
19
55
3
184
24
184
24
18
21
39
16
90
94
18
166
90
72
38
1
58
32
38
20
160
70
18
20
55
3
39
1
150
10
150
132
39
16
55
16
38
112
160
10
38
1
58
3
184
146
184
24
18
20
90
32
Avera
ge
seek
length
55.3
Avera
ge
seek
length
27.5
Avera
ge
seek
length
27.8
Avera
ge
seek
length
35.8
Page 26
The End
Page 27