Page 89 - DCAP403_Operating System

Operating System

Notes
Example: Multilevel Feedback Queue

Three Queues

1. Q –RR with time quantum 8 milliseconds
0
2. Q –RR time quantum 16 milliseconds
1
3. Q –FCFS
2
Scheduling

1. A new job enters queue Q which is served FCFS. When it gains CPU, job receives 8
0
milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q .

1
2. At Q job is again served FCFS and receives 16 additional milliseconds. If it still does not
1
complete, it is preempted and moved to queue Q .
2

5.3.7 Real-time Scheduling

Real-time systems design is an increasingly important topic in systems research communities
as well as the software industries. Real-time applications and their requirements can be found
in almost every area of operating systems and networking research. An incomplete list of such
domains includes distributed systems, embedded systems, network protocol processing, aircraft
design, spacecraft design..., and the list goes on.

One of the most important responsibilities of a real-time system is to schedule tasks according
to their deadlines in order to guarantee that all real-time activities achieve the required service
level. Many scheduling algorithms exist for a variety of task models, but fundamental to many of

these are the earliest deadline first (EDF) and rate-monotonic (RM) scheduling policies.
A schedule for a set of tasks is said to be feasible if a proof exists that every task instance in the set
will complete processing by its associated deadline. Also, a task set is schedulable if there exists
a feasible schedule for the set.
The utilization associated with a given task schedule and resource (i.e. CPU) is the fraction of
time that the resource is allocated over the time that the scheduler is active.

82 LOVELY PROFESSIONAL UNIVERSITY