Exam 1 Topics
Fall 2005
Exam Date: Thursday, 20 October, 5:30-7:30 PM.
References: Silberschatz chapters 1-6, Linux system programming as
described in the Understanding Unix/Linux Programming book, and
the class slides.
Note: This is a closed book exam. You may
use the Beginning Linux Programming and/or the Understanding Unix/Linux
Programming books if there are no marks in them.
- Chapter 1
- Ok, there's not much here. Know the abstraction layer
and be able to talk about abstractions as given on page 3-6.
- Know what multiprogramming is and how it speeds up computation.
- Know what bootstraping is and how a computer starts up with Linux.
- Understand the memory hierarchy (called the storage-device hierarchy in
the book).
- Understand the different types of computer-system architectures are such
as single-processor systems and mulitporcessor systems (both asymmetric multiprocessing
and symmetric multiprocessing (SMP)).
- Know common operating-system structures as described in section 1.4.
- Understand how modern operating systems operate (section 1.5), especially
how interrupts and dual-mode operation works.
- Understand, in general, what the operating systems managers do, especially
the process manager, the memory manager, the file (or storage) manager, and
the device manager. These are all described in chapter 1 of your book and in
the slides.
- Process management.
- Main-Memory Management.
- File Management.
- I/O Management.
- Secondary-Storage Management.
- Networking.
- Protection system.
- Command-Interpreter System.
- You are not responsible for sections 1.9 through 1.12
- Chapter 2, operating-system structures.
- Be able to talk about the various operating-system services.
- Program execution.
- I/O operatoins.
- File-system manipulation.
- Communications.
- Error detection.
- Resource allocation.
- Accounting.
- Protection.
- Understand what system calls are, know how they work in Linux, and
be able to describe the different types of system calls.
- Know what systems programs are, the various types, and examples.
- Know the different types of operating-system structures such as layered
structures, microkernels, monolithic kernels, and modules.
- Know what virtual machines are and be able to describe them and give examples.
- Know how the Linux kernel is organized.
- Chapter 3. Processes (also Nutt chapter 4 slides)
- Know what a process is, what a PCB is and what it contains, how a process goes through different
states.
- Know how process scheduling works, what schedulers are, the different types
of schedulers, what dispatchers
are, what context switching is and how it works.
- Know how to create and control processes in Linux (fork, wait, exec, etc.)
- Know how interprocess communication works: shared memory, message-passing
and pipes.
- Be able to use Linux pipes in programs. Also be able to use send/capture
signals.
- You are not responsible for section 3.6.
- Chapter 4, threads.
- Know what threads are and how they differ from processes.
- Understand the benefits of threads
- Know the different models for thread implementation: many-to-one,
one-to-one, and many-to many.
- Be able to program using the pthread library. You are not responsible
for Win32 threads or Java threads.
- Know the issues with threads such as thread pools, thread-specific data,
and scheduler activiations.
- Know how linux threads are used/implemented.
- Chapter 5, CPU scheduling.
- Know about the CPU-IO burst cycle.
- Know the difference between the short-term scheduler, the medium term scheduler,
and the long term scheduler.
- Know how preemptive scheduling works and what the dispatcher's role is in this.
- Know about the different scheduling criteria: CPU utilization, throughput, turnaround
time, waiting time, response time.
- Know how to estimate CPU utilization using the arrival rate and service rate.
- Know how the following scheduling algorithms work, their differences and their
similarities. Be able to draw Gnatt charts for each algorithm.
- First-come first-served. Also know how to predict wait time.
- Shortest-job-first.
- Preemptive SJF (also called shortest remaining time first).
- Estimation techniques for SJF (the tau equation).
- Priority scheduling. Know what starvation is and how aging can be used
to overcome it.
- Deadline scheduling.
- Round Robin scheduling.
- Mulitlevel Queue Scheduling.
- Multilevel feedback queue scheduling.
- Know what the relationship between time quantum size and number of
context switches is.
- Know how multiple-processor scheduling is done, especially issues like
affinity, load-balancing, push/pull migration,
- Know what symmetric multi-threading is and how it relates to
hyperthreading.
- Understand thread scheduling and the difference between PCS and SCS.
- You are not responsible for real-time scheduling.
- Know how scheduling is done in Linux. You are not responsible for
Windows scheduling.
- Know how scheduling is done in Solaris.
- You are not responsible for Windows scheduling, BSD scheduling or
Java thread scheduling.
- Understand how to do pthread scheduling.
- You are not resposndible for section 5.7, Scheduling algorithm evaluation.
- Chapter 6, Process Synchronization.
- Know what the critical section problem and race conditions are.
- Know what the critical section problem is and the three criteria for the CS.
Be able to prove that algorithms meet/don't meet these criteria.
- Mutual exclusion.
- Progress
- Only processes that want into their CS can participate in the decision.
- Some process must get into its CS.
- Bounded waiting.
- Know what Peterson's solution is and how to use it.
- Know how to use the test-and-set and swap instructions to solve the critical
section problem and to implement primatives such as semaphores.
- Know how to use semaphores to solve the critical section problem and how to
synchronize processes using semaphores.
- Know the difference between binary and counting semaphores and how to use
each of these types of semaphores.
- Know what active and passive semaphores are.
- Know deadlock and starvation can occur when using semaphores.
- Know and be able to solve the three classical synchronization problems and
similar problems.
- The bounded-buffer problem.
- The readers-writers problem.
- The dining-philosophers problem.
- Know what monitors are and be able to ues them to solve snchronization problems.
- Know how to use condition variables in monitors.
- Know the difference between Hoare semantics and Mesa semantics with condition
variables.
- Know the potential problems with monitors.
- You do not have to know how to implement monitors.
- You do not have to know about atomic transactions (section 6.9).
- You do not have to know about Java synchronization.
- Know how to use Linux semaphores and semaphores in pthreads.
- You do not have to know about synchronization in Windows.
