Scheduling Flashcards
1
Q
Where are multiple jobs managed?
A
memory
2
Q
what kind of alternation takes place with jobs?
A
those waiting to use the CPU and those waiting for IO.
3
Q
the key to multiprogramming is [x]
A
scheduling
4
Q
what does the high level scheduler do?
A
determines which programs are admitted to the system for scheduling
5
Q
the high level scheduler controls the [x x x]
A
degree of multiprogamming
6
Q
In a batch system, where do newly scheduled jobs go and how are they held?
A
routed to disk and held in a queue or waiting line
7
Q
when adding a job, the high level scheduler must take two decisions. what are they?
A
1) scheduler needs to know it can take on one or more processes
2) it needs to decide which jobs to turn into processes
8
Q
how often does the high-level scheduler execute?
A
relatively infrequently.
9
Q
what coarse decision does the scheduler usually make?
A
whether or not to take on a new process
10
Q
what is the short term scheduler also known as
A
dispatcher
11
Q
how often does the short term scheduler run
A
frequently
12
Q
from a high level, what does the short term scheduler decide
A
which job to execute next
13
Q
the status of a process at any point in time is its [x]
A
state
14
Q
what are the five states of a process?
A
new ready running waiting halted
15
Q
define new for a process state
A
the program has been admitted but is not ready to execute. It needs to be moved from the operating system to a ready state.
16
Q
define ready for a process state
A
process is ready to execute and is awaiting access to the processor
17
Q
define running for a process state
A
the process is being executed by the processor
18
Q
define waiting for a process state
A
the process is suspended from execution waiting for some resource, like I/O
19
Q
define halted for a process state
A
the process has terminated and will be destroyed by the operating system. Oooo errrr
20
Q
what must the operating system hold about each process?
A
its state
21
Q
where does the operating system hold the process state information?
A
process control block
22
Q
what eight things are held in the process control block?
A
identifier state priority program counter memory pointers context data I/O status information Accounting information
23
Q
define identifier for the process control block
A
a unique id associated with a process
24
Q
define state for the process control block
A
the state of the process
25
define priority for process control block
relative priority to other processes
26
define program counter for process control block
the address of the next instruction in the program to be executed.
27
define memory pointer for process control block
the starting and ending location of the process in memory
28
define context data for process control block
data present in the registers while the process is executed
29
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.
30
define accounting information
information on processor time and clock time being used
31
when the processor accepts a new job or a request, what does it do?
creates a blank process control block
32
when the process block is fully filled in, what happens to the process state?
it is moved to ready
33
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.
34
What is the long-term queue
a lost of jobs waiting to use the system
35
What is the short-term queue
a queue of processes in the ready state
36
what is the general method for short term scheduling?
round robin, giving processes equal time
37
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.
38
Personal computers affected scheduling in two ways. Name them.
1) Most programs became single active process.
| 2) Computers are faster.
39
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
```
40
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
41
what does a process switch usually invalidate and what does this do?
entire memory cache
| usually forces dynamic reloading
42
what is a compute-bound process?
a process that spends most of its time computing
43
what is an I/O bound process?
a process that spends most of its time waiting for I/O
44
compute-bound process typically have [x] CPU bursts and thus [y] I/O waits
```
x = long
y = infrequent
```
45
I/O-bound process typically have [x] CPU bursts and thus [y] I/O waits
```
x = short
y = long
```
46
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.
47
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
48
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
49
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
50
what does a preemptive scheduling algorithm do?
picks a process and then lets it run for some fixed amount of time
51
what are the three systems to consider in scheduling?
batch
interactive
real time
52
what is important about a batch system
there are no users waiting at a terminal
53
what algorithms can be run on a batch system. why?
both types are fine. fewer process switches == better performance overall.
54
in an interactive environment, [x] is essential
preemptive
55
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
56
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.
57
What is fairness for scheduling?
Comparable processes should get comparable service.
58
what is policy enforcement for scheduling?
seeing that stated policy is carried out
59
what is balance for scheduling?
all parts of the system should be busy
60
batch job scheduling: what is throughput
the number of jobs per hour that a system completed
61
batch system: what is turnaround time
the average time to complete a batch job
62
batch systems: what is CPU utilisation
making sure CPU is busy
63
interactive systems: what is response time
time between a command and a result
64
interactive systems: what is proportionality
meeting user expectations related to speed
65
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
66
real time system: what is predictability?
avoiding multimedia degredation
67
Name the 3 batch system scheduling algorithms
FIFO
Shortest job first
shortest remaining time next
68
how is first come first serve implemented?
linked list
| blocked process goes to end of queue
69
first come first serve is non or preemptive?
non preemptive
70
how is shortest run time implemented?
1) assumes run time in advance
| 2) only optimal when all jobs available
71
shortest run time is non or pre?
non preemptive
72
describe shortest remaining time next?
preemptive of shortest remaining time.
scheduler always chooses process with shortest remaining time.
means short jobs get priority.
73
describe round robin scheduling
process assigned a quantum.
| if process exceeds, CPU preempted and process switch occurs. process put to end of queue.
74
describe quantum time decisions
too short = too many process switches and low CPU efficiency
too long = poor response to interactive requests.
75
describe priority scheduling
each process assigned a priority and the runnable process with the highest priority is allowed to run
76
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
77
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.
78
which scheduling algorithms risk starvation?
shortest process next, shortest remaining time.
79
which scheduling algorithms are high overhead?
shortest process next, shortest running time.
80
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.
81
what is the most common scheduling algorithm for threads?
round robin and priority scheduling
82
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.
83
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.
84
why is thread level scheduling good for I/O
having a thread block on I/O does not suspend entire process. user thread would.
85
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.
