SI411 Operating Systems

Fall AY07

Final Exam Objectives

Final Exam: Time: 0755, Tuesday, 12 December 2006, Location: MI300

· Please muster in with your section leader prior to the start time for the exam.

· As per the course policy, only non-programmable calculators may be used on the exam.

· The exam is cumulative, and covers chapters 1,2,3,4, 5, 6, 7, 8, and 9 of the Silberschatz text, and chapters 2, 15, and 16 of the Deitel text.

· The following exam objectives are intended to aid you in your preparations for the course's examinations. However, the following are not considered to be inclusive of all the testable material from this course. All assigned reading material, supplemental handouts, class lectures, class discussions, homework, labs, programming projects, and in-class problem-solving sessions are considered testable material.

================= 6 Week Exam Objectives =================

Introduction to operating systems

• explain the benefits of having an operating system supervise user processes.
• determine the amount of wasted CPU time given the amount of time an I/O or other operation takes, and the amount of time the CPU is involved in the I/O operation.
• identify the activities the operating system must deal with to support multitasking
• distinguish symmetric multiprocessor systems from asymmetric multiprocessor systems
• distinguish tightly coupled distributed systems from loosely coupled distributed systems

Computer system operation

• explain the concept of an interrupt driven operating system
• describe why it is necessary for a CPU and I/O operations to be overlapped
• describe interrupt driven data transfer
• describe DMA data transfer
• compare interrupt-driven and DMA driven data transfer
• identify the storage structures of computer memory
• explain protection mechanisms that support the OS such as dual-mode, I/O, Memory, and CPU protection.
• understand the role of the base and limits registers in providing protection
• apply knowledge of base and limits registers to determine is a memory reference is within the portion of memory allocated to a process.

OS Structures

• describe the resources needed for process management
• list the five major activities of an operating system with regard to process management.
• describe the role of volatility on memory management
• understand the role of the command-interpreter system with respect to the operating system and system calls.
• understand the shared-memory form of communication between processes
• understand the shared-memory form of communication between processes
• be able to compare and contrast the shared-memory and message-passing models of inter-process communication.
• determine the communication model being used between multiple processes.
• explain the approach to system structure taken by the MS-DOS operating system
• explain the approach to system structure taken by the UNIX operating system
• explain the approach to system structure taken by the IBM VM operating system
• compare and contrast the approaches to system structure taken by the MS-DOS, UNIX, and IBM VM operating systems.

Processes

• describe a process
• understand how an operating system impacts the progression of a process from creation to termination.
• explain the concept of process state
• understand the context of a process
• describe the role of process control blocks with regard to a process
• explain the role of process scheduling queues
• understand the role of the short-term scheduler
• understand the role of the medium-term scheduler
• understand the role of the long-term scheduler
• understand the characterization of a process as I/O bound.or CPU bound
• be able to characterize a process as I/O bound or CPU bound
• describe the impact of the characterization of a process as I/O bound or CPU bound on the scheduling of the process
• describe context switching
• understand the impact of context-switching on the throughput of an operating system.
• understand the role of the UNIX system call fork() in process creation
• understand independent vs cooperating processes
• be able to evaluate multiple processes to determine if they are independent or cooperating
• explain the basic producer-consumer problem
• distinguish between bounded and unbounded buffers.

Threads

• define a process
• define a thread
• distinguish between a process, a lightweight process a heavyweight process and a thread
• explain the hybrid approach that Solaris 2 takes to threads
• explain the resource needs of Solaris 2 kernel threads, lightweight processes, and user-level threads
• distinguish between physical concurrency and logical concurrency
• describe the actions taken by the kernel to context switch between kernel-level threads in Solaris 2.
• describe the actions taken by the thread library to context switch between user-level threads in Solaris 2.

CPU Scheduling

• Understand the role of CPU-I/O burst cycles with regard to short-term scheduling.
• Analyze a process's CPU-I/O burst cycle and characterize it as CPU Bound or I/O bound
• Understand the role of characterizing CPU bound or I/O bound jobs on CPU scheduling
• Describe the role of offered load on CPU scheduling
• Describe non-preemptive CPU scheduling
• Describe preemptive CPU scheduling
• Regarding the process life cycle, explain the opportunities that exist for invoking preemptive and/or non-preemptive scheduling
• Understand the criteria used to evaluate CPU scheduling algorithms.
• Distinguish between the various CPU scheduling algorithms.
• Understand how the various CPU scheduling algorithms are applied
• Be able to apply the CPU scheduling algorithms to a given set of arriving process burst times.
• Analyze a scheduling situation and be able to describe which scheduling algorithm would be most appropriate to use.
• Understand Multilevel queue scheduling, and multilevel feedback queue scheduling
• Describe the various approaches for evaluating CPU scheduling algorithms

Java Programming Language Issues

• understand the three basic components of Java
• describe the role of the Java Virtual Machine.
• explain the process/mechanisms through which Java programs can be written on a computer architecture different from the architecture of the computer on which the Java code is executed.
• understand how Java applications are executed
• describe the byte-oriented nature of Java I/O
• understand the role of exception handling in Java
• be able to compare C++ exception handling with Java exception handling
• classify various models of inheritance
• distinguish between "extends" and "implements" in the context of inheritance
• describe the states that a Java thread can be in
• explain the rationale for "deprecating" a Java method
• describe the mechanism's that Java provides for thread synchronization.
• understand how a Java thread transitions from one state to another
• explain how a Java thread is created
• explain how a Java thread is started
• describe communication between a Java thread and a "main" Java application
• understand how Java threads can be made to "share" a common structure such as an array

 ================= 12 Week Exam Objectives =================

(In addition to the 6 week Objectives given above)

Process synchronization

• Understand critical data
• Describe race conditions
• Describe an atomic operation
• Understand the significance of requiring an operation to be atomic in terms of process synchronization.
• Evaluate source code and identify critical data
• Understand the critical-section problem
• Describe the role of shared data in a solution to the critical section problem.
• Identify the conditions that any algorithm that solves the critical section problem must meet.
• Describe the role of critical data in the critical section problem
• Given an algorithm, be able to prove whether the algorithm represents a valid solution to the critical section problem.
• Describe the role of semaphores in solving the critical section problem
• Understand the behavior of a semaphore wait operation
• Understand the behavior of a semaphore signal operation
• Describe the effect of various initial semaphore values
• Evaluate a semaphore solution to an synchronization problem
• Identify invalid uses of semaphore operations
• Be capable of correctly using semaphores as a general synchronization tool
• Understand deadlock and starvation in terms of semaphore use
• Understand the dining philosophers problem
• Be able to evaluate the suitability of a proposed solution to the dining philosophers problem
• Understand Dijsktra’s concept of safety in terms of the dining philosophers problem
• Understand Dijsktra’s concept of liveliness in terms of the dining philosophers problem
• Describe Dijsktra’s Monitor concept in terms of process synchronization

Deadlock

· Be able to define deadlock

· Understand the role of resource allocation in deadlock

· Understand the role of resource allocation graphs in determining if a system is in deadlock

· Describe the significance of a cycle in a resource allocation graph

· Given a resource allocation graph, determine whether or not a cycle exists

· Given a resource allocation graph, determine whether or not deadlock exists

· Be able to distinguish between shareable, consumable and serially reusable resources

· Understand the effect on deadlock if a resource is preemptive

· Understand the effect on deadlock if a resource is non-preemptive

· Be able to characterize a resource as preemptive or non-preemptive

· Understand the conditions that must hold for deadlock to occur

· Be able to describe the various mechanisms through which an operating system can deal with the issue of deadlock.

· Understand the role of Dijkstra's "Banker's Algorithm" with regard to deadlock

· Describe the meaning of "safety" in terms of the Bankers algorithm

· Be able to determine whether a system's allocation of resources is "safe"

· Be capable of determining whether a process's request for a resource should be granted with respect to the banker's algorithm.

Java Programming Language Issues (12 week)

• Understand the role of the JVM in Java thread scheduling
• Describe the actions resulting from messages passed to threads, such as notify(), notifyAll(), yield(), wait(), etc
• Identify Java thread priorities
• Understand how Java threads can change priority
• Understand how semaphores can be implemented in Java
• Understand synchronized methods and Java’s object locks in terms of Dijkstra’s Monitor concept
• Be able to apply knowledge of object locks, synchronized methods, entry sets and wait sets.

================= Final Exam Objectives =================

(In addition to the 6 and 12 week objectives given above)

Main Memory Management

· Understand the significance of the degree of multiprogramming in terms of the performance of the operating system

· Understand contiguous vs. non-contiguous memory

· Understand the role of memory partitions

· Be able to allocate memory using the first-fit approach

· Be able to allocate memory using the best-fit approach

· Be able to allocate memory using the worst-fit approach

· Be capable of determining the best case in terms of CPU utilization based on the degree of multiprogramming and the percentage of time processes are blocked.

· Be capable of determining the worst case in terms of CPU utilization based on the degree of multiprogramming and the percentage of time processes are blocked.

· Be capable of determining the expected case in terms of CPU utilization based on the degree of multiprogramming and the percentage of time processes are blocked.

· Understand the significance of relocatable code in terms of memory management

· Understand the role of the memory management unit in terms of memory management

· Understand the significance of swapping in terms of memory management

· Be able to compare and contrast the various approaches to dynamic allocation of memory

· Understand internal fragmentation

· Understand external fragmentation

· Understand the memory fragmentation that may occur in both contiguous and non-contiguous memory

· Understand Paging

· Understand Segmentation

· Be capable of tracing a memory reference using page tables

· Understand the rational for including associative registers in a memory management scenario

· Be capable of tracing a memory reference using page tables in combination with associative registers

· Understand effective access time

· Be capable of computing the effective access time to an instruction in main memory