O/S Scheduling
Does the nth job need to run in approximately 1/n of the the CPU?
How do RR, FIFO, SJF scheduling algorithms affect the time to run n?
How does the O/S predict a process' future needs based on past usage?
How does Lottery Scheduling work?
How does scheduling change as you have more complete information about a set of processes?
Real-Time Scheduling
soft real-time vs. hard real-time
soft - e.g. display video frame every 30th of second
hard - e.g. anti-lock brakes on a car
Which jobs do you keep in memory?
How do you determine which subset gets written to disk?
How could Mitzenmacher prove his result?
Does it converge to optimal?
Showing posts with label Chad Salinas Notes. Show all posts
Showing posts with label Chad Salinas Notes. Show all posts
Monday, January 29, 2007
OS 6
CPU Scheduling
All I/O devices + CPU busy = n+1 fold speedup
CPU vs. I/O bursts
Universal Scheduling
What is the best way to run n processes on k nodes where n < k?
latency vs. throughput conflicts
speed vs. fairness
halting problem derivatives
How do Markov Chains and rival processes work?
Allocate resources across dimensions of time and space.
FIFO is the simplest scheduling algorithm.
Describe the Convoy Effect.
Round Robin Scheduling
You have to amortize the cost of context switches over the timeslice time.
What is "Priority Donation"?
Shortest Time to Completion First (STCF)?
Prove STCF given jobs a, b, c, & d.
How do you know a job's length?
Shortest Seek Time First (SSTF)
Which operations are most expensive?
Describe the Elevator Algorithm.
Use multi-level feedback queue (aka exponential Q)
All I/O devices + CPU busy = n+1 fold speedup
CPU vs. I/O bursts
Universal Scheduling
What is the best way to run n processes on k nodes where n < k?
latency vs. throughput conflicts
speed vs. fairness
halting problem derivatives
How do Markov Chains and rival processes work?
Allocate resources across dimensions of time and space.
FIFO is the simplest scheduling algorithm.
Describe the Convoy Effect.
Round Robin Scheduling
You have to amortize the cost of context switches over the timeslice time.
What is "Priority Donation"?
Shortest Time to Completion First (STCF)?
Prove STCF given jobs a, b, c, & d.
How do you know a job's length?
Shortest Seek Time First (SSTF)
Which operations are most expensive?
Describe the Elevator Algorithm.
Use multi-level feedback queue (aka exponential Q)
OS 5
When programming with monitors make sure the invariant is true.
Only one variable is usually updated (shared) by the two threads.
Don't need variable to determine whether buffer is full; you can just use buf.head less buf.tail == N.
Race conditions result from bad interleaving of processes.\
Instead of locks, you could use scheduler.
Compare & Exchange
Optimistic Concurrency
Could you write an entire O/S without locks?
Most O/S make heavy use of doubly-linked lists.
Intel's product roadmap assumes transactional memory to aid developers in wirting code to take advantage of multiple processors.
Deadlock -- what do you do when none of the threads are making progress?
Graph deadlock as a directed cycle with inter-thread dependencies.
4 necessary conditions for deadlock:
Only one variable is usually updated (shared) by the two threads.
Don't need variable to determine whether buffer is full; you can just use buf.head less buf.tail == N.
Race conditions result from bad interleaving of processes.\
Instead of locks, you could use scheduler.
Compare & Exchange
Optimistic Concurrency
Could you write an entire O/S without locks?
Most O/S make heavy use of doubly-linked lists.
Intel's product roadmap assumes transactional memory to aid developers in wirting code to take advantage of multiple processors.
Deadlock -- what do you do when none of the threads are making progress?
Graph deadlock as a directed cycle with inter-thread dependencies.
4 necessary conditions for deadlock:
- Limited Access
- No Preemption
- Multiple Independent Requests (hold & wait)
- Circularity in graph of requests
Circularity is the easiest condition to violate.
Two-Phase Locking -- simple deadlock control.
How have databases traditionally dealt with deadlocks?
OS 4
How much does blocking cost?
How long should you spin?
Spin for the length of the block cost. If you still don't have the lock, then block.
Idea is to pay the incremental cost until it equilibrates with the up-front cost, then switch.
Mutual Exclusion -- only have one process at a time in the critical section.
Make Progress
Multiple threads that are sharing state info create race conditions.
While (lock is not available)
spin - within your own process cache
...
What is the good, bad, and ugly of recursive locks?
What is synchronization modularity?
What characterizes trylocks?
Producer/Consumer design pattern
producer puts characters in an infinite buffer
consumers pulls characters out...
not so edge case of consumer reading to read while producer has fallen behind
release lock, go to sleep?
producer should wakeup the consumer as it posts a char.
Semaphores - non-negative integer counter with atomic increment and decrement. Semaphores block rather than going negative. Use semaphores for mutual exclusion and scheduling.
Emulate a lock using semaphores.
Monitors are easier and safer than semaphores.
Think about Java synchornized classes as monitors.
What is the difference between Hoare semantics and Mesa semantics?
How long should you spin?
Spin for the length of the block cost. If you still don't have the lock, then block.
Idea is to pay the incremental cost until it equilibrates with the up-front cost, then switch.
Mutual Exclusion -- only have one process at a time in the critical section.
Make Progress
Multiple threads that are sharing state info create race conditions.
While (lock is not available)
spin - within your own process cache
...
What is the good, bad, and ugly of recursive locks?
What is synchronization modularity?
What characterizes trylocks?
Producer/Consumer design pattern
producer puts characters in an infinite buffer
consumers pulls characters out...
not so edge case of consumer reading to read while producer has fallen behind
release lock, go to sleep?
producer should wakeup the consumer as it posts a char.
Semaphores - non-negative integer counter with atomic increment and decrement. Semaphores block rather than going negative. Use semaphores for mutual exclusion and scheduling.
Emulate a lock using semaphores.
Monitors are easier and safer than semaphores.
Think about Java synchornized classes as monitors.
What is the difference between Hoare semantics and Mesa semantics?
Thursday, January 18, 2007
Crypto 2
Stream Ciphers
Why do you replace the "random pad" with a "Pseudo-random pad"?
Why is PRG a deterministic function? Does it have to be deterministic? What if you chose a non-deterministic function.
What is the unpredictability property? Given the first i bits of output, could an adversary guess the next i+1 bit?
What is meant by "semantic security"?
Don't use the UNIX PRG for crypto.
Does SSL give you a new stream cipher key for every connection?
Why are stream ciphers so fast?
What is the difference between a "strong cipher" and a "fast cipher"?
Why do you have to completely re-encrypt a file after making even a small change to the file?
What is meant by "highly malleable"?
How can you guarantee the integrity of your CipherText?
RC4
Simply elegant!!!
How could you predict the next byte given a segment of data?
What RC4 attacks exist?
What is the probability that the second byte of the output is zero?
What other bytes have some inherent bias?
Would there be any bias if you ran the s-array through 256 cycles before using its output for RC4?
What is the probability of seeing two consecutive zeroes in the output?
How is RC4 used in (read incorrectly) 802.11b WEP?
Why shouldn't you use CRC for integrity checking?
Look at Fluhrer-Mantin-Shamir (2001)
Look at WEPCrack
Need to get to 802.11i
Hardware Stream Ciphers
What is an Linear Feedback Shift Register (LFSR)?
How is a single LFSR predictable?
Why is LFSR easy to break given about a kb of plaintext and a kb of ciphertext?
Why do you replace the "random pad" with a "Pseudo-random pad"?
Why is PRG a deterministic function? Does it have to be deterministic? What if you chose a non-deterministic function.
What is the unpredictability property? Given the first i bits of output, could an adversary guess the next i+1 bit?
What is meant by "semantic security"?
Don't use the UNIX PRG for crypto.
Does SSL give you a new stream cipher key for every connection?
Why are stream ciphers so fast?
What is the difference between a "strong cipher" and a "fast cipher"?
Why do you have to completely re-encrypt a file after making even a small change to the file?
What is meant by "highly malleable"?
How can you guarantee the integrity of your CipherText?
RC4
Simply elegant!!!
How could you predict the next byte given a segment of data?
What RC4 attacks exist?
What is the probability that the second byte of the output is zero?
What other bytes have some inherent bias?
Would there be any bias if you ran the s-array through 256 cycles before using its output for RC4?
What is the probability of seeing two consecutive zeroes in the output?
How is RC4 used in (read incorrectly) 802.11b WEP?
Why shouldn't you use CRC for integrity checking?
Look at Fluhrer-Mantin-Shamir (2001)
Look at WEPCrack
Need to get to 802.11i
Hardware Stream Ciphers
What is an Linear Feedback Shift Register (LFSR)?
How is a single LFSR predictable?
Why is LFSR easy to break given about a kb of plaintext and a kb of ciphertext?
Wednesday, January 17, 2007
OS 3
What is the cost for a context-switch?
Do virtualized processes really run in about 1/n slower than real CPU?
What economies can you gain by duplicate a subset of state data?
Why is it so difficult to get an "isolated" process today?
Try to debug the results of multiple processes that share state data!
What is the probability of a race condition when you have two processes that both read, increment, then write?
Break down operations into their atomic units aka "critical section".
Why do you need compiler support to atomicity in a uniprocessor environment?
No trap + No interrupt = No context switch
How can you mask interrupts?
Don't mask interrupts by increasing the thread's priority only to have your thread go into an infinite loop.
What are the pros and cons of locking a thread?
What idiomatic expression connotes acquiring and releasing the lock?
Don't disable preemption and then go into an infinite loop.
When implementing multiprocessing locks, how can you leverage the hardware?
Can you build up a lock from more primitive instructions?
What is a "spin lock"?
What are the issues associated with spinning?
Do virtualized processes really run in about 1/n slower than real CPU?
What economies can you gain by duplicate a subset of state data?
Why is it so difficult to get an "isolated" process today?
Try to debug the results of multiple processes that share state data!
What is the probability of a race condition when you have two processes that both read, increment, then write?
Break down operations into their atomic units aka "critical section".
Why do you need compiler support to atomicity in a uniprocessor environment?
No trap + No interrupt = No context switch
How can you mask interrupts?
Don't mask interrupts by increasing the thread's priority only to have your thread go into an infinite loop.
What are the pros and cons of locking a thread?
What idiomatic expression connotes acquiring and releasing the lock?
Don't disable preemption and then go into an infinite loop.
When implementing multiprocessing locks, how can you leverage the hardware?
Can you build up a lock from more primitive instructions?
What is a "spin lock"?
What are the issues associated with spinning?
Subscribe to:
Posts (Atom)
