Op Sys Quiz 2 - Cpu Scheduling

Front 1

Process execution consists of

Back 1

CPU execution and I/O wait

Front 2

Maximum CPU utilization obtained with

Back 2

multiprogramming
(CPU scheduled selects another process when current one is in I/O burst)

Front 3

What queue does CPU scheduler select processes from?

Back 3

ready queue

Front 4

CPU scheduling decisions take place when a process:

Back 4

1) switches from running to waiting state
2) switches from running to ready state
3) switches from waiting to ready state
4) terminates

Front 5

Nonpreemptive

Back 5

once the CPU has been allocated to a process, the process keeps it until terminates or waiting for I/O
(Also called cooperative scheduling)

Front 6

Preemptive

Back 6

processes can be rescheduled when a new process comes in. needs hardware support such as a timer

Front 7

Scheduling conditions are preemptive or nonpreemptive?

Switches from running to waiting state
Terminates

Back 7

Nonpreemptive

Front 8

Scheduling conditions are preemptive or nonpreemptive?

Switches from running to ready state
Switches from waiting to ready

Back 8

Preemptive

Front 9

2 solutions to preemption affecting OS kernel design

Back 9

1)waiting for either the system call to complete or I/O block

2) disable kernel preemption when updating shared data

Front 10

**Dispatch latency

Back 10

the time it takes for the dispatcher to stop one process and start another running

Front 11

Dispatcher module gives control of the CPU to the process selected by:

Back 11

the short-term scheduler

Front 12

**CPU utilization

Back 12

percentage of CPU being busy

Front 13

**Throughput

Back 13

number of processes that complete execution per time unit

Front 14

** Turnaround time

Back 14

the time to execute a particular process, from the time of submission to the time of completion

Front 15

**Waiting time

Back 15

the total time spent waiting in the ready queue

Front 16

**Response time

Back 16

the time it takes from when a request was submitted until the first response is produced

time it takes to start responding

Front 17

Scheduling algorithms seek to maximize ____ and _____, and minimize ____, ______, and ______.

Back 17

Maximize: CPU utilization and throughput

Minimize: turnaround time, waiting time, and response time

Front 18

First Come, First Served (FCFS) Scheduling -- preemptive or nonpreemptive?

Back 18

Non-preemptive

Just schedule processes as they come in

Front 19

**Convoy effect

Back 19

all other processes waiting until the running CPU bound process is done (FCFS)

Front 20

Shortest Job First Scheduling -- preemptive or nonpreemptive?

Back 20

Can be preemptive or nonpreemptive

Preemptive is shortest remaining time first

Provably optimal

Front 21

How to predict length of next CPU burst

Back 21

assuming it is related to previous CPU burst, can be predicted with exponential averaging

Front 22

Shortest remaining time first

Back 22

Preemptive SJF

Reschedule when a process arrives

Front 23

Priority Scheduling

Back 23

selects the ready process with highest priority

priority number is associated with each process

Front 24

Shortest job first (SJF) is a special case of priority scheduling - how?

Back 24

priority is the inverse of predicted next CPU burst time

Front 25

Priority scheduling - preemptive or nonpreemptive?

Back 25

Can be both, like SJF

Front 26

**Starvation

Back 26

low priority processes may never execute, because high priority processes are selected first

Front 27

**Aging

Back 27

gradually increase the priority of processes that wait in the system for a long time

Front 28

Round Robin (RR)

Back 28

selects processes in a round-robin fashion

each process gets a small unit of CPU time (Time Quantum q)

Once a process uses its time quantum, it is preempted and put to the tail of the ready queue

Front 29

Multilevel Queue

Back 29

ready queue is partitioned into separate groups

processes are permanently assigned to a given queue

each queue has its own scheduling algorithm

scheduling must be done among the queues

Front 30

Time slice

Back 30

In Multilevel Queue Scheduling, each queue gets a certain amount of CPU time which it can schedule among its processes

Front 31

Multilevel Feedback Queue

Back 31

uses multilevel queues
a process can move between various queues
tries to infer type of process

goal is to give interactive and I/O intensive processes high priority

Most general CPU-scheduling algorithm

Front 32

Multilevel Feedback Queues are defined by:

Back 32

1) number of queues
2) scheduling algorithm for each queue
3) method to determine when to assign a process a higher priority
4) method to determine when to demote a process
5) method to determine which queue a process will enter when that process needs service

Front 33

Thread scheduling

Back 33

OS kernel schedules kernel threads

Front 34

**System-contention scope

Back 34

competition among all threads in a system; kernel is not aware of user threads

Thread library schedules user threads onto light weight processes (LWP)

Front 35

**Process-contention scope

Back 35

scheduling competition within the process

usually based on priority set by the user

Front 36

Pthread Scheduling

Back 36

API allows specifying either Process-Contention Scope or System-Contention Scope during thread creation

Front 37

the Pthread scheduling API

Back 37

pthread_attr_set/getscope

Front 38

schedules threads using PCS scheduling

Back 38

PTHREAD_SCOPE_PROCESS

Front 39

schedules threads using SCS scheduling

Back 39

PTHREAD_SCOPE_SYSTEM

Front 40

Multiple-Processor Scheduling

Back 40

CPU scheduling when multiple CPUs are available

Front 41

**Asymmetric multiprocessing

Back 41

approach to multiple-processor scheduling

only one processor makes scheduling descisions, I/O processing, and other system activity

other processes act as dummy processing units

Front 42

**Symmetric multiprocessing

Back 42

approach to multiple-processor scheduling

each process is self-scheduling

scheduling data structures are shared, needs to be synchronized

used by common OS's

Front 43

**Processor affinity

Back 43

migrating process is expensive to invalidate and repopulate cache

Solution: let a process have an affinity for the processor currently running

SOFT and HARD affinity

Front 44

Multicore processors

Back 44

has multiple processor cores on same chip

Front 45

**Memory stall

Back 45

when accessing memory, a process spends a significant amount of time waiting for the data to become available

Complication of multicore processors

Front 46

Solution to memory stall

Back 46

Multithreaded CPU core

share the execute unit, but duplicate the architecture states (registers) for each CPU thread

one thread can execute while the other is in memory stall

Front 47

Virtualization

Back 47

may undo good scheduling efforts in the host or guests

Host kernel schedules multiple guests onto CPUs
each guest does its own scheduling
can result in poor response time and performance