ECE 329 Spring 2006 Section 01 Exam 1 Review Guide:
Exam Format:
The exam will potentially consist of true-false, short answer (1 or 2 sentences), multiple choice, short essay, and matching type questions. Although there may also be a few problems to work out based on techniques discussed in class and in the book, the exam will primarily be concept-oriented, where you must compare and contrast ideas and draw conclusions using logical well thought-out supporting evidence. The exam will be CLOSED-BOOK.
Important Topics:
Chapter 1:
The characterizations of batch, multi-programmed, and time-shared systems.
The difference between hard and soft real-time systems.
Chapter 2:
What the interrupt vector is, and what it is for.
The difference between asynchronous and synchronous I/O.
What the device status table is, and what it is for.
What DMA is, and what are its benefits are.
The difference between memory-mapped and programmed I/O.
The significance of storage device hierarchy.
The difference between volatile and non-volatile storage.
The importance of caching and the issues surrounding cache management.
The difference between cache consistency and coherency.
Chapter 3:
The difference between message-passing and shared-memory models of communication.
The difference between monolithic and microkernel approaches to OS design and implementation.
Chapter 4 – Process Management:
What a process is, and the contents commonly found in the PCB to establish its state.
Understand the process state transition diagram found in Figure 4.1 on page 97.
Understand the queueing-diagram representation of process scheduling in Figure 4.5 on page 101.
The difference between a long-term and short-term scheduler.
The definition of the degree of multi-programming.
The distinction between I/O and CPU bound processes, and the importance of a good process mix.
The significance of a medium-term scheduler.
The definition of a context switch.
The difference between independent and cooperating processes.
The benefits of providing a system that allows cooperating processes.
The definition of the classic producer-consumer problem.
The difference between bounded and un-bounded buffers.
The definition of interprocess communication.
The distinction between direct and indirect communication and the pros/cons.
The difference in behaviors of blocking/non-blocking rends and receives.
The difference between zero, bounded, and unbounded buffers.
Chapter 5 – Threads:
The relationship between a process and a thread.
The benefits of multi-threaded programming.
The difference between user-level and kernel-level threads.
Multi-threading models: Many-1, 1-1, and Many-Many. Know the differences.
Chapter 6 – CPU Scheduling:
The motivation behind CPU scheduling, what does it improve ?
Understand that a typical program sequence will have an alternating sequence of CPU and I/O bursts, why ?
The difference between preemptive and non-preemptive scheduling.
Under what 4 circumstance would CPU scheduling need to take place ?
The definition of dispatch latency.
The difference among the scheduling criteria: CPU utilization, throughput, turnaround time, waiting time and response time.
The difference between optimizing the variance versus the average.
Scheduling algorithms: FCFS, SJF, SRTF, RR.
Be able to generate a Gantt chart from a set of processes, arrival times, burst times, and a particular scheduling algorithm.
Understand how an exponential average might be used in conjunction with SFJ.
Understand priority-based scheduling.
What is starvation, and why is it important to consider it in the context of CPU scheduling?
What is process aging, and how it is used?
In RR scheduling, what is a time quantum?
The relationship between time quantum and the number of context switches, and therefore the relationship with the context-switch overhead, and ultimate system performance.
What is multilevel queue scheduling?
What is multilevel feed-back queue (MLFBQ) scheduling, and what are some of the benefits?
With MLFBQ scheduling, what is one of the most difficult practical issues associated with its usage?
What are the limitations of results obtained from deterministic modeling evaluations of scheduling algorithms?
What is queueing-network analysis? What are some of the limitations of this analytical technique?
How can simulation-based evaluations help?
Chapter 7 – Process Synchronization
What is a race condition? In the producer-consumer problem, what causes one to be present?
What is a critical section, and what are the three requirement of an effective solution of if? What do these requirements mean/imply?
What is the only assumption of these solutions? What do they NOT depend on?
In what context is the bakery algorithm applied? Why can it not guarantee that each process receives a unique number?
What is atomicity, and how is that related to the whole critical section problem?
What are some hardware primitives that can be used in helping the solution of critical section problem, and why do they help?
What are semaphores, and what are they useful for?
What do the classical definitions of the P and V (wait and signal) semaphore operators?
What is a mutex lock?
What is a busy-wait and a spinlock? What are the drawbacks of semaphores that rely on theses?
How can the implementation be changed to alleviate busy-waits?
To do this, what is needed? (block and wakeup)
Once a semaphore implementation uses a waiting queue, what may potentially occur as a result?
What is the difference between a counting and binary semaphore?
What is the reader-writers problem? What is the difference between the two classic types?
What is the classic definition of the dining philosophers problem?
How can deadlock happen?
What are some ways to prevent deadlock in the DP problem?
What is the difference between deadlock-free and starvation-free?
What are critical regions and how do they present an improvement over the straight semaphore usage?
What is needed to actually use critical regions?
What is a monitor? How does it protect access to local variables?
Chapter 8 – Deadlocks
What is a deadlock and what 4 conditions must simultaneously hold for it to occur?
Understand what a resource-allocation graph is, and the meaning of the notation used.
What is the difference between deadlock prevention and avoidance?
What is a safe state? What is a safe sequence? What is an unsafe state?
Understand the distinction between being in a deadlock state and an unsafe state.
What is the resource-allocation graph algorithm? In what situation can it be used?
What is the difference between a claim and request edge?
What is the Banker’s algorithm? How is it more useful than the resource-allocation graph algorithm?
What is one of the practical drawbacks of the Banker’s algorithm?
What is the safety algorithm? What is the resource-request algorithm?
Be able to use these two algorithms in an example (like the ones we did in class).
What is deadlock detection, and how does it differ from avoidance and prevention?
What is the difference between a resource-allocation graph and a wait-for graph?
Understand the deadlock detection algorithm in the book, and be able to apply it to an example (like the ones in class).
What happens after a deadlock is detected? What are some of the decisions that must be made?
Practical Issues:
Make sure you understand the implementation of the queue and thread projects that you have submitted. I may ask a question regarding a C-programming concept. It may include a code fragment, and you must determine what it does / prints / etc.