OS - scheduling

Question 1

what does the scheduler determine?

Answer 1

• 1. Who will run*
• 2. When it will run*
• 3. For how long*

Question 2

Regarding scheduling; what does “fairness” refer to?

Answer 2

Comparable processes should get comparable service.

Question 3

Regarding scheduling; what does “efficiency” refer to?

Answer 3

keep CPU and I/O device busy

Question 4

Regarding scheduling; what does “response time” refer to?

Answer 4

Response time is the total amount of time it takes to respond to a request for service. That service can be anything from a memory fetch, to a disk IO, to a complex database query, or loading a full web page. Ignoring transmission time for a moment, the response time is the sum of the service time and wait time.

Question 5

Regarding scheduling; what does “turnaround time” refer to?

Answer 5

Average time required for a job to complete, from submission time to completion.

Question 6

Regarding scheduling; what does “waiting time” refer to?

Answer 6

minimize the average time in ready queue over processes

Question 7

Regarding scheduling; what does “Throughput” refer to?

Answer 7

number of completed jobs per time unit.

Question 8

Why is there a conflict between response time and turnaround time?

Answer 8

The process’ state changes to “running”, for the first time, quite fast. it takes a lot of time for it to finish its job though.

Question 9

Why is there a conflict between Fairness and Throughput?

Answer 9

• process 1: size x*
• process 2: size x*
• process 3: size 200x*
• according to fairness - process 3 should get 100 times more CPU time than process 1 and 2. According to Throughput: we can have process 1 and 2 completed much faster if we gave them more CPU.*

Question 10

What is an “interactive computing”

Answer 10

This term refers to software which accepts input from the users as it runs. Non-interactive programs, by comparison, operate without user intervention; compilers and batch processing applications that are pre-programmed to run independently

Question 11

What is a script?

Answer 11

A programming language for a special run-time environment(terminal) that automates the execution of tasks. the tasks could alternatively be executed one-by-one by a human operator. Scripting languages are often interpreted(rather than compiled)

Question 12

What is a batch file?

Answer 12

A script file which consists of a series of commands to be executed by the command-line interpreter, stored in a plain text file.

Question 13

Provide an example of CPU utilization vs turnaround time conflict

Answer 13

• 5 interactive jobs: 10% CPU, 20% Disk, 70% terminal; total time for each job 10 sec.
• Batch job b: 90% CPU, 10% disk. total time 50 sec.

Option A:

• Choose batch job and one of the interactive jobs to work in parallel:
• CPU 100% utilized and Disk 30% utillized.

Option B:

• Choose 5 interactive jobs to work in parallel:
• Disk 100% utilized and CPU just 50% utilized but more jobs finish their work in less time.

Question 14

• 5 jobs i1…i5,* each takes: 10% CPU 20% Disk, and 10 sec to complete.
• One job b takes 90% CPU 10% Disk and 50 sec to complete.*
• case 1: running i1..i5 in parallel and then b.
• case 2: running b and each of i’s(in turn) in parallel.

What is the CPU utilization and Turnaround time for case 1 and 2?

Answer 14

Case 1:

• UT=(10*0.5+50*0.9)/60
• TA=(10*5+60*1)/6

Case 2:

• UT=(50*(0.9+0.1))/50
• TA=(10+20+30+40+50+50)/6

Question 15

what’s the difference between preemptive SJF(Shortest job First) and non-preemptive SJF?

Answer 15

if all processes arrive at the same time both behave the same. if not, Non-preemptive chooses the shortest job within the existing process and it doesn’t change its decision even if a shorter job process has arrived. in contrast, preemptive SJF will switch jobs if a shorter jobs has arrived.

Question 16

What is the Round Robin method?

Answer 16

Each process gets a small unit of CPU time(time -quantum), usually 10-100 milliseconds.

Question 17

how much is a millisecond?

Answer 17

1/1000 second

Question 18

why does Round-Robin approaches FCFS(First-come-first-served) as the time quantum grows?

Answer 18

because if the time quantum is quite big, the process would finish their jobs before they are ask to(due to termination, I/O, or voluntarily).

Question 19

If the time quantum is about the time it takes for switching then …?

Answer 19

we’ll have relatively a large waste of CPU time(50%) but a good response time

Question 20

If time quantum is much longer than the time it takes for switching then …?

Answer 20

we’ll have long response(waiting) time but better CPU utilization

Question 21

Assume context switch takes 5 ms. compute the time wasted on switching for 100 ms quantum time?

Answer 21

overall time: context switch + quantum time = 5 + 100. switch/overall = 5/105 = 1/21 -> less than 5% which is a quite good ratio

Question 22

what is the guaranteed scheduling?

Answer 22

Scheduling that guarantees fairness by monitoring the amount of CPU time spent by each user and allocating resources accordingly.

Question 23

What is the main drawback of priority scheduling? how can we avoid that?

Answer 23

starvation. Can be avoided by changing priorities dynamically: increase priorities of waiting processes at each clock tick.

Question 24

• 1. What is I/O bound process?*
• 2. What is CPU bound process?*

Answer 24

A process who’s completion time is determined principally by:

1. The period spent waiting for I/O
2. The speed of the CPU

Question 25

How can we increase the priorities of I/O bound?

Answer 25

we can set priority to be 1/f where f is the fraction of time-quantum used. for instance; if q = 100 ms, and the process used only 25 ms then f = 1/4 and it’ll have priority 4.

Question 26

What is a Two-Level Scheduling?

Answer 26

It has to do with swapped out processes: One low-level CPU scheduler for in-memory processes and another High-level scheduler which is responsible for swapping,

Question 27

What is the critera for which the swapping scheduler swaps?

Answer 27

• 1. Elapsed time since process swapped in/out*
• 2. CPU time allocated to process*
• 3. process memory size*
• 4. process priority*

Question 28

What is Unix?

Answer 28

• A family of multi-tasking, multi-user OS.*
• first written in assembly and then in C.*

Question 29

what is xv6?

Answer 29

modern reimplementation of the Sixth Edition Unix in ANSI C for multiprocessor x86 systems.

Question 30

How is scheduling performed in Unix

Answer 30

• Two-Level Scheduling:*
• 1. Low level(CPU) scheduler uses multiple queue for each priority: processes in the kernel have negative priorities and user mode processes have positive priorities(lower is higher). Blocked processes are removed from queue but when the event occurs they’re back to top priority. *Each queue is Robin-Round handled.*
• 2. High level(memory) scheduler moves processes from memory to disk and back, to ensure that all processes recieve their share of CPU time*

Question 31

Think of examples to processes in the kernel…

Answer 31

• By priority, recall - lower is higher:*
• -5: waiting for a disk*
• -4: waiting for disk buffer*
• -3: waiting for terminal input*
• -2: waiting for terminal output*
• -1: waiting for child to exit*

Question 32

How red-black tree, per-CPU data structure, helps maintain CFS(completely Fair Scheduler)?

Answer 32

Red-Black Tree is a tree where left children of node correspond to threads with less vruntime(CPU time) and right children to more vruntime. Leaves don’t play any role. Periodically, increment running thread’s vruntime, and compare to current leftmost node, if it is still minimal - continue running it, if not - insert to the tree and run minimal vruntime thread.

Question 33

How CFS (completely Fair Scheduler) time slice work?

Answer 33

It varies according to target latency parameter and number of ready threads. If too many ready threads decrease time slice such that it may cause constant context switch, then time-slice is fixed to minimum(1 ms) and target latency is increased accordingly. In addition, CFS changes rate at which a running thread’s virtual time passes according to priority.