Scheduling Flashcards
Where are multiple jobs managed?
memory
what kind of alternation takes place with jobs?
those waiting to use the CPU and those waiting for IO.
the key to multiprogramming is [x]
scheduling
what does the high level scheduler do?
determines which programs are admitted to the system for scheduling
the high level scheduler controls the [x x x]
degree of multiprogamming
In a batch system, where do newly scheduled jobs go and how are they held?
routed to disk and held in a queue or waiting line
when adding a job, the high level scheduler must take two decisions. what are they?
1) scheduler needs to know it can take on one or more processes
2) it needs to decide which jobs to turn into processes
how often does the high-level scheduler execute?
relatively infrequently.
what coarse decision does the scheduler usually make?
whether or not to take on a new process
what is the short term scheduler also known as
dispatcher
how often does the short term scheduler run
frequently
from a high level, what does the short term scheduler decide
which job to execute next
the status of a process at any point in time is its [x]
state
what are the five states of a process?
new ready running waiting halted
define new for a process state
the program has been admitted but is not ready to execute. It needs to be moved from the operating system to a ready state.
define ready for a process state
process is ready to execute and is awaiting access to the processor
define running for a process state
the process is being executed by the processor
define waiting for a process state
the process is suspended from execution waiting for some resource, like I/O
define halted for a process state
the process has terminated and will be destroyed by the operating system. Oooo errrr
what must the operating system hold about each process?
its state
where does the operating system hold the process state information?
process control block
what eight things are held in the process control block?
identifier state priority program counter memory pointers context data I/O status information Accounting information
define identifier for the process control block
a unique id associated with a process
define state for the process control block
the state of the process
define priority for process control block
relative priority to other processes
define program counter for process control block
the address of the next instruction in the program to be executed.
define memory pointer for process control block
the starting and ending location of the process in memory
define context data for process control block
data present in the registers while the process is executed
define I/O status information
includes outstanding I/O requests, I/O devices (eg., tape drives) assigned to this process, a list of files assigned to the process, and so on.
define accounting information
information on processor time and clock time being used
when the processor accepts a new job or a request, what does it do?
creates a blank process control block
when the process block is fully filled in, what happens to the process state?
it is moved to ready
What happens in an I/O operation?
Processor saves current context data and the program for A in A’s process control block.
The operating system may perform some work like initiating I/O stuff.
Short term scheduler decides which process should be executed next.
The operating system instructs processor to restore B’s context data and proceed with B.
What is the long-term queue
a lost of jobs waiting to use the system
What is the short-term queue
a queue of processes in the ready state
what is the general method for short term scheduling?
round robin, giving processes equal time
Talk about how jobs move through the system in terms of getting space on the CPU
Process request is placed on long-term queue.
When resources become available, a process request becomes a process.
Process then placed in ready state and put on short term queue.
Personal computers affected scheduling in two ways. Name them.
1) Most programs became single active process.
2) Computers are faster.
In addition to picking the right process, the scheduler has to worry about [x] because [y] is expensive
x = making efficient use of the CPU y = process switches are expensive
what happens with a process switch?
a switch from user mode to kernel mode happens
state of current process must be saved (including registers) in process table
a new process must be selected by running the scheduling algorithm
MMU must be reloaded with memory map of new process
new process is started
what does a process switch usually invalidate and what does this do?
entire memory cache
usually forces dynamic reloading
what is a compute-bound process?
a process that spends most of its time computing
what is an I/O bound process?
a process that spends most of its time waiting for I/O
compute-bound process typically have [x] CPU bursts and thus [y] I/O waits
x = long y = infrequent
I/O-bound process typically have [x] CPU bursts and thus [y] I/O waits
x = short y = long
what is the key factor with I/O-bound and compute-bound?
the length of the CPU burst, not the length of the I/O burst.
If an I/O bound process wants to run, it should [x]
get a chance so it can issue its disk request and keep the disk busy
what are the five time slots a scheduler has to make a decision
when a new process is created
when a process ends
when a process blocks on I/O and some other process has to be picked
when an I/O interrupt occurs
if a hardware clock provides interrupts, you’d need to schedule at the interrupt
what does a nonpreemptive scheduling algorithm do?
picks a process to run and then just lets it run until it blocks or until it voluntarily releases
what does a preemptive scheduling algorithm do?
picks a process and then lets it run for some fixed amount of time
what are the three systems to consider in scheduling?
batch
interactive
real time
what is important about a batch system
there are no users waiting at a terminal
what algorithms can be run on a batch system. why?
both types are fine. fewer process switches == better performance overall.
in an interactive environment, [x] is essential
preemptive
why is preemptive essential in an interactive environment
because you don’t want a process hogging the CPU when a user attempts to interact with the device
what is the key difference between an interactive and real-time environment?
real-time only run programs that are intended to further the application at hand.
interactive are general-purpose and user facing.
What is fairness for scheduling?
Comparable processes should get comparable service.
what is policy enforcement for scheduling?
seeing that stated policy is carried out
what is balance for scheduling?
all parts of the system should be busy
batch job scheduling: what is throughput
the number of jobs per hour that a system completed
batch system: what is turnaround time
the average time to complete a batch job
batch systems: what is CPU utilisation
making sure CPU is busy
interactive systems: what is response time
time between a command and a result
interactive systems: what is proportionality
meeting user expectations related to speed
real time system: what is meeting deadlines?
cannot lose data
think of computer that scrapes a source. it needs to do it otherwise there are failures. imagine GA
real time system: what is predictability?
avoiding multimedia degredation
Name the 3 batch system scheduling algorithms
FIFO
Shortest job first
shortest remaining time next
how is first come first serve implemented?
linked list
blocked process goes to end of queue
first come first serve is non or preemptive?
non preemptive
how is shortest run time implemented?
1) assumes run time in advance
2) only optimal when all jobs available
shortest run time is non or pre?
non preemptive
describe shortest remaining time next?
preemptive of shortest remaining time.
scheduler always chooses process with shortest remaining time.
means short jobs get priority.
describe round robin scheduling
process assigned a quantum.
if process exceeds, CPU preempted and process switch occurs. process put to end of queue.
describe quantum time decisions
too short = too many process switches and low CPU efficiency
too long = poor response to interactive requests.
describe priority scheduling
each process assigned a priority and the runnable process with the highest priority is allowed to run
to prevent high priority processes running forever, what two things might a scheduler do?
1) reduce priority of currently running process at clock tick. means if there’s a process that’s higher a process switch will occur.
2) use a quantum and if one uses it up, then process switch to next highest priority process
why might a priority scheduler give I/O bound processes CPU immediately?
given CPU to let it start it next I/O request, which can be taken care of in parallel with another process computing.
which scheduling algorithms risk starvation?
shortest process next, shortest remaining time.
which scheduling algorithms are high overhead?
shortest process next, shortest running time.
describe multiple queues and scheduling
moving processes down a priority if they exceed their quantum. in swapping out, it would be given an additional quantum.
what is the most common scheduling algorithm for threads?
round robin and priority scheduling
what should you think about with user threads and scheduling?
kernel not away of threads. it picks process A. decides to run A1. if quantum exceeds, it’ll block. if it resumes A1 is on again.
what is the major difference between switching for user and kernel threads?
thread switch with user-level is a bit of machine code.
thread switch at kernel level = full context switch, changing memory map, invalidating cache.
why is thread level scheduling good for I/O
having a thread block on I/O does not suspend entire process. user thread would.
what can user level threads employ that kernel threads cannot?
application-specific thread scheduler.
they know what each thread does and can sort optimise accordingly.
