Process Scheduling (Week 6) Flashcards by Smashing Gaming vulture

what is scheduling

The task of managing CPU sharing among a pool of ready processes/threads and is possible only with context switching facility.

How well did you know this?

Not at all

Perfectly

what is a scheduler

The scheduler chooses one of the ready threads to allocate to the CPU when it is available.

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

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 well did you know this?

Not at all

Perfectly

how many logical parts is the scheduling mechanism composed of ?

3 logical parts

How well did you know this?

Not at all

Perfectly

what are the 3 logical parts

enqueuer, dispatcher, and context switcher

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

_______ and ________ can have a
dramatic effect on the performance of a multiprogrammed computer.

Scheduler and its scheduling policy

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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)

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

what are the 2 types of schedulers

preemptive
non-preemptive

How well did you know this?

Not at all

Perfectly

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.

How well did you know this?

Not at all

Perfectly

types of non preemptive schedulers

First-Come-First-Served (FCFS)
Shortest Job First (SJF) (Non preemptive)
Priority (PR) (Non preemptive)

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

what are the types of Preemptive (involuntary) Schedulers

Shortest Job First (SJF) (Preemptive)
Priority (PR) (Preemptive)
Round Robin (RR)
Multi-level Queues

How well did you know this?

Not at all

Perfectly

what is the first come first serve scheduling algorithm

Scheduler picks up first job to arrive in the
ready list.

How well did you know this?

Not at all

Perfectly

advantage of first come first serve scheduling algorithm

Simplest CPU scheduling algorithm

How well did you know this?

Not at all

Perfectly

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