Process Scheduling (Week 6) Flashcards
what is scheduling
The task of managing CPU sharing among a pool of ready processes/threads and is possible only with context switching facility.
what is a scheduler
The scheduler chooses one of the ready threads to allocate to the CPU when it is available.
what is a scheduling policy
The scheduling policy determines when it is time for a thread to be removed from the CPU and allocated to another thread.
what is a scheduling mechanism?
The scheduling mechanism determines how the process manager can determine it is time to interrupt the CPU, and how a thread can be allocated to and removed from the CPU.
how many logical parts is the scheduling mechanism composed of ?
3 logical parts
what are the 3 logical parts
enqueuer, dispatcher, and context switcher
what is the enqueuer
–> When a process/thread is changed into the ready state, the enqueuer enqueues the corresponding descriptor into a list of processes that are waiting for the CPU (or the ready list).
–> The enqueuer may place the new process anywhere in the list, depending on the scheduling policy.
what is the dispatcher
–> The dispatcher is invoked after the current process is removed from the CPU.
–> The dispatcher removes one of the threads from the ready list and then allocates it to the CPU by loading its CPU registers in the thread’s descriptor into the CPU.
what is the context switcher?
–> When the scheduler switches the CPU from executing one process to another, the context switcher saves the contents of all CPU registers (PC, IR, condition status, processor status, and ALU status) for the thread being removed into its descriptor.
_______ and ________ can have a
dramatic effect on the performance of a multiprogrammed computer.
Scheduler and its scheduling policy
how is the time take to finish a process by the processor determined
dependent on how often it gets to execute on the CPU as dispatched by the scheduler
what is the aim of the scheduler
–> decrease average time taken by a process to execute on the computer
–> increase the throughput of a computer in terms of the number of processes that get executed per unit time
what can a policy control
–> CPU utilization (busy and not kept idle)
–> Avg time a process waits for a service (reduce the time)
–> avg amount of time to complete a job (reduce the time)
what is the wait time W(pi)
W(pi) = Total time Pi spent waiting in the ready list (wait time)
Waiting time is defined as the total time which a process spends waiting for the CPU in the ready list.
what is the turnaround time [T trnd(pi)]
Let T trnd(pi) = Time from pi first enter ready to last exit ready (turnaround time)
Turnaround time is the time from the arrival of the process to its completion by the CPU. This includes the time it spent waiting for the CPU
what are the 2 types of schedulers
preemptive
non-preemptive
what are non - preemptive schedulers
when a process gets the CPU it will not be interrupted or cut short (pre-empted). It will have the oppourtunity to fully complete before the CPU is given to the next process.
types of non preemptive schedulers
First-Come-First-Served (FCFS)
Shortest Job First (SJF) (Non preemptive)
Priority (PR) (Non preemptive)
what are preemptive schedulers
the process take turns to share the CPU and they can be interrupted midway and the CPU can be allocated to another process before the process can finish
what are the types of Preemptive (involuntary) Schedulers
Shortest Job First (SJF) (Preemptive)
Priority (PR) (Preemptive)
Round Robin (RR)
Multi-level Queues
what is the first come first serve scheduling algorithm
Scheduler picks up first job to arrive in the
ready list.
advantage of first come first serve scheduling algorithm
Simplest CPU scheduling algorithm
disadvantage of first come first serve scheduling algorithm
Convoy effect: short process behind long process and waiting for the long process to finished. This results in lower CPU and devices utilization.
how does the first come first serve scheduling algorithm work
–> The process to request first will be allocated the CPU first
–> It is non-preemptive
–> Using a FCFS queue, PCB of new process will be linked to the tail of the queue
–> When CPU is free, process at the head of the FCFS queue will be allocated the CPU
what is Shortest Job First (SJF) (Nonpreemptive)
Scheduler picks up shortest job to arrive in
the ready list.
Once CPU is allocated to a process it cannot
be preempted until it completes its service time.
what is the concept behind Shortest Job First (SJF)
–> Each process is associated with the length of its service time.
–> When the CPU is available, it is assigned to the process that has the smallest (remaining) service time.
what is Shortest Job First (SJF) (preemptive)
A current process is preempted if a new process arrives with service time length lesser than the current process’s remaining service time.
Shortest-Job-First (SJF) is also called __________
Shortest-Remaining-Time - First (SRTF)
why is Shortest-Job-First (SJF) optimal
it gives minimum average waiting time for
a given set of processes.
what is Priority Scheduling
Scheduler picks up the job with the highest priority in the ready list.
how does priority scheduling work ?
A priority number (integer) is associated with each process.
The CPU is allocated to the process with the highest priority.
Equal- priority processes are scheduled in FCFS order.
what is the problem with priority scheduling
the problem is Starvation where Low priority processes may never be executed.
what is the solution for the problem with priority scheduling
the Solution is Aging
Increase the priority of the process as time
progresses.
what is round robin
Scheduler gives a short time-slice to each job
explain how does round robin work
–> Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds.
–> After this time has elapsed, the process is preempted and added to the end of the ready queue.
–> New processes are added to the tail of the ready queue, which is a FCFS circular queue.
advantage of round robin
Fast response time. It is good for time sharing system.
what happens if service time is less than or equal to 1 time quantum
If service time is < 1 time quantum, process release CPU voluntarily.
what happens if service time is more than 1 time quantum
If service time > 1 time quantum, context switch will be executed.
explain what does performance in round robin depend on
It depends on size of time quantum:
–> large quantum (q). This is equivalent to FIFO
–> small quantum (q). It must be large with respect to the context switch, otherwise overhead is too high
what is multilevel queue
Implement multiple queues
(eg. Process all foreground processes before background processses, or 80% timeslice to foreground processes, 20% to background processes).
how do multilevel queues work
–> Processes are classified into groups based on some property of the process.
–> Ready queue is partitioned into separate
queues such as foreground (interactive),
background (batch).
–> The processes are permanently assigned to one queue.
–> Each queue has its own scheduling algorithm.
–> RR for foreground queue
–> FCFS for background.
To study policy performance, we need to consider _________
simplified model
what are we provided with to study policy performance
A schedule of processes
arrival time
CPU service time
what must we produce to study policy performance
Gantt chart
Average waiting and turnaround time
what is gantt chart
A Gantt chart is a ‘chart’ showing the actual
execution of a series of processes by the CPU.
It shows the start and end of execution of each process.
It does not show the arrival time of each process.
what is the assumption for the shortest job first when calculating waiting and turnaround time
all the jobs arrive at the same time
what does modern OS include in their schedulers
–> involuntary CPU sharing – timer interrupts
–> priority based process selection
what happens in unix scheduling
–> Involuntary CPU Sharing
–> Preemptive algorithms
–> 32 Multi-Level Queues
what happens in windows scheduling
–> Involuntary CPU Sharing across threads
–> Preemptive algorithms
–> 32 Multi-Level Queues
in unix scheduling queues 0 - 7are reserved for ___________
system functions
in unix scheduling queues 8 - 31 are reserved for ___________
space functions
what is nice
influences queue level
in windows scheduling Highest 16 levels are ________
real time
in windows scheduling Next lower 15 are for _________
system/user threads
in windows scheduling lowest level is for ______-
idle thread
