James Altmann scribe notes

Wednesday, February 1^st

OPERATING SYSTEM

monster control program, which manages devices, RAM, network, CPU.

Event-Driven Programming

In event-driven programming, apps divided into small chunks. 

Callbots, are each triggered by an event.

OS = for(;;){

                wait for next event e; invoke callback for e; c(e, ..);

}

Callbacks must work quickly, (cannot wait for input or other programs, cannot wait for output anything)

Callbacks can schedule a “deferred action” or schedule requests = e.g. “on input induce callback d”

Can also evoke events. e.g.  pretend a key was pressed.

Pros and Cons

Assumtion – callbacks are cooperative

Simple, good performance on one CPU, simple calculations

THREADS = process – file descriptors – memory – owner

Share all of these things inside the process it resides in

Threads do have: IP, regs, stack (own instruction pointer).

PROCESS

Threads can overwrite other threads stack, not much protection.  Must be cooperative in same process.

COOPERATIVE THREADS

- Each thread does a yield, every now and then. (voluntarily offers control of CPU)

- Yield between each instruction is slow

- Yields on every system call, is free since it already goes into the system

How to implement yield.

syscal à INT à trap à trap handler inside kernel à save registers of current thread into thread descriptors à look for another thread that needs to run à restore T2’s registors à Etc.

Works for cooperative threads

FOR UNCOOPERATIVE THREADS

- need preempt these

- timer interrupt, motherboard sends signal every 10 miliseconds to CPU along a wire.

- When CPU gets signal, CPU traps.  Acts like INT.  Kernel takes control.  Does everything yield syscall does.

- If it checks too fast, switching time dominates

- If it takes too long programs can’t switch fast enough

Policy vs Mechanism

When > 1 priority, it is a thread that want to run

long-term:  which jobs are admitted to system in first place?

medium-term: which processes reside in RAM and which can we temporarily swap to disk

short-term:  which thread get a CPU

Scheduling Metrics                                                                 run-time

|----------------------------------------------------|-----------------------------------------------|------------------------------------

arrival of order                                         start           1^st output                              finish

Other segments of time

|--------------------------|

wait time – time waiting for “arrival of order”

response time – time it takes to start working on order

turnaround time/latency – time it takes to get ready to send/receive an order

context switching -  time it takes to change jobs, overhead.

Get Averages - expected time

Worst case time – longest expected time for a job

utitilization (fraction of time the CPU is doing work, e.g making cards) 0<u<1

Throughput, rate at which useful work is being done

fairness – each thread get the CPU within a given interval

totally unfair – a thread never runs, starvation

Sceduling Policy Examples

A arrives on first cycle, B arrives second cycle, C third, and D fourth.

First come-First Served: FCFS

Job A a:0 r:5 , B a:1 r:2 , C a:2 r:9, D a:3 r:4, specify arrival times, runtime (time it needs the cpu)

][AAAAA][BB][CCCCCCCCC][DDDD]

Utilization: 20/20+ 3e  where e is the context switching time

Average wait time:

A: e

B: 4+2e

C: 5 + 3e

D: 13+4e

Total = (22 + 10e)/ 4 = 4.5 + 2.5e is average

Avg turnaround time: 10.5 + 2.5  (average wait time + average run time)

FCFS favors long jobs

+Very good about throughput

-Convoy effect, long jobs make short jobs wait a long time.

Shortest Job First SJF

][AAAAA][BB][DDDD][CCCCCCCCC][

utilization: 20/(20+4e)

avg wait:  e + 4+2e + 9+ 4e + 4 + 3e = 17 + 10e /  4   =   4.25 + 2.5e  ß minimal wait time

avg turnaround: 9.25 + 2.5e

-Starvation is possible

Round Robin Scheduling

Pick a quantum (10 ms), then run FCFS within that.

][A][B][C][D][A][B][C][D][A][C][D][A][C][D][C][C][C][C][C]

A: e

B: 2e

C: 3e

D: 4e

Avg wait time : 2.5e

Turnaround

A: 15 + 15e

B: 5 + 6e

C: 19 + 18e

D:  11 + 14e

Avg turnaround time:  50 + 53e / 4 = 12.5 + 13.25e

Throughput = Utilization: 20/(20+16e)

 Starvation possible if you put new processes at the front of the line.  Must put new processes at end of the line

Priority Scheduling

Let user assign priorities to jobs

External priorities

Let system assign priority (internal priority) FCFS, SJF

priority = arrival time + job length

niceness = -priority (can be easier to understand)