CSI400 Operating Systems course taught by S.Chaiken

Fall 2002 Archive Web Site

What is New:  Click here for current lecture links.

Click here for the course newsgroup/bulletin board if you're on a Univ. subnet computer

 If your're not on the Univ. Network, click here to telnet to ACUNIX, where you can access the sunya.class.csi400 newsgroup through emacs or pine

Get instructions for using pine for reading cscnews from LC-25 helpdesk
 
Instructor: Prof. S. Chaiken
LI-67A, 442-4282
sdc@cs.albany.edu		 M, W, F 10:30AM-12:00PM
and by appointment or not busy
Teaching Assistant: Xiaoyu Zheng
LI-96P, 442-4285
xz7223@albany.edu		 Tues, Thurs 12:00PM-2:30PM
and by appointment

Textbooks:

  1. Modern Operating Systems by Tannenbaum, publisher: Prentice-Hall
  2. Understanding the Linux Kernel by Bovet, publisher: O'Reilly
  3. Unix System Programming by Haviland, publisher: Addison-Wesley
  4. (optional, highly recommended for informative and authoritative answers on C and its standard libraries): C - A Reference Manual, by Harbison and Steele, publisher: Prentice-Hall
Other Resources:
  1. Online Single Unix Specification
      2.  from The Open Group
  2. Pthreads programming:
  3.  Lecture notes on Concurrency from MIT: (http://web.mit.edu/6.826/www/notes/
  4. Raphael Finkel's Operating Systems Vader Mecum book (out of print)
  5. comp.os.research FAQ
  • Notes (in progress) for Lectures (1 and) 2
  •   Course Policy, Syllabus, Readings, etc handout(.pdf)   (.ps)
  •  Programming Project 1 Due (originally 9/25 now 9/27) (.pdf)     (.ps)
  •  Outline for lectures 3 and on..
  • Lecture of Sept 11 addressed details of keyboard, terminal output and part1 process interactions.
  • Goals of Project 1: Provide experiences with concurrency including interprocess communication; introduce programming with system calls.
  • Lecture 3 covered "Roadmap of multprogramming": Address Spaces, User/Privileged Mode, Interrupts/Exceptions, Scheduler, Process Table, Context Switch/return from interrupt/exception operation.
  • Lecture 4: Completed "Roadmap".  MMU operation: base/limit register arithmetic and page tables; virtual addresses in assembly (machine) language and C. Timesharing of processor between operating system and user processes.  Contents of process table entry including saved registers.
  •  Lecture 5: "kernel"=="operating system", which runs in privileged mode.  Operating environment = OS+utilities; utilities run in user mode.  They include shells, Xserver, gcc/g++, telnet, netscape, mount, mail, pine, emacs..  Review of xspim window panes which show text segments, data segments, control buttons, and the registers.  What is virtual address space (just a huge coordinate system), it holds relatively sparse "intervals of legal virtual addresses" called segments.  Role of the EPC (exception program counter) and the PC field of a process table entry (or process control block) structure.  What OS does when there's an interrupt or exception.  Ordinary function or subroutine call instructions compared with system calls.  Steps of the read() system call.
  • The 3 main scheduling states of each process:  Blocked (aka waiting or sleeping), Running and Ready.  Blocked means waiting for some event ot occur, such as input from the terminal becoming available after a read system call is entered.  When the interrupt is handled, when the process blocked on the read is changed from the Blocked to the Ready state, when it actually runs (later!).
  •  Lecture 6: Reading and HW. assignment (see above).  Discussion of the difficulties with part4 of the project 1, stemming from the part4 program needing to watch input from two file descriptors:  reading from the file to detect end of input so the socket can be closed to tell the server to finish, and reading from the socket to tell the server is done.  Sketchy timing diagram, description of when various system calls block.  Simple solution: loop while no end of file on input file descr.  This works for small input files but fails for larger ones.    Glimpse at system call list: fork used to create processes in Unix but the first process after a system is booted is "hacked" together (using static variable definitions)
  • Lecture 7: Blocking (aka slow) compared with non-blocking systems calls.  Examples of unix and Win32 system call names; purposes of fork() and CreateProcess are the same but what the processes they create are different. Details of what the Linux kernel does during a blocking system call such as read():  (Digression on the use of a "dummy head" to simplify circular linked list implementation which was used for Linux wait queues).  Task state and TSS fields in the Linux process descriptor structure (Task State Segment  field contains saved CPU register values and its format is specified by the Intel ISA).  When the system call's service function (a subroutine in the kernel) determines the current process (which issued the system call) should block, it calls sleep_on.  Blocking is also known as waiting, and it is always "blocking on" or "waiting for" an event or condition.  Walk through of the sleep_on and the wake_up functions from Bovet pages 76-79.  (It would help to read p75 too now.)  The struct wait_queue node is allocated in sleep_on()'s What happens between the time schedule() is called and when schedule() returns.  Role of the separate stacks in the kernel for each process.
  • Lecture 8: Use of "suid" bit for turnin-csi400 executable; distinction between CPU mode (user/privileged) and superuser (root)/ordinary user user id (the latter controls which system calls are legal, privileged system calls made by ordinary user return EPERM error code.)   Thread attributes of a process distinguished from the others; where PC, register contents and stack exists for a running thread compared to a blocked thread.  Basic thread operation; review of function pointer constants, function pointer variables, calling the function pointed to by a function pointer; use of function pointer in the generic create_thread( ...  )  system call.  Demonstration of a simple threaded program in which there is a race involving a global variable, first in terms of an ordinary function call and then how another function is called by another thread.
  • Lecture 9: Discussion (advantages) of application programming with threads.(after Tanenbaum 2.2).  Sockets, pipes and files for interprocess communication, buffer in the kernel and read/write system calls.  Signal IPC mentioned.  Shared memory for IPC, use Unix system calls mmap and shm* family (belonging to System V but not POSIX), shared memory might be mapped to a file for permanent storage of its contents.  Synchronization primatives (such as semaphores) mentioned as IPC facilities too.  Threads important for applications programming over Unix, Java and Windows.  Kernels are in  herently multithreaded.  Problems with concurrent threads:  Races.
    • (1) Safety means correct operation.  (2) A lock or mutex is a facility for preventing races.  A lock is like a door:  If it is open, any thread can close it, but if it is closed, no other thread can close it.  (3) Deadlock can occur when locks are used.  (4) Liveness: every time a process is unblocked, it eventually runs.
  • Lecture 10: (system administration: ~acsi400 pathname substitution done by the shell)  Outine of single threaded web server, with details about the memory space for the request buffer and the in-memory cache.  Multi-threaded server.  Use of stack by a recursive function compared to the use of multiple stacks for a reentrant function; -D_REENTRANT needed in the compile command for re-enterant functions; global variables can make a function fail to be re-entrant. Where and when each thread blocks when the multithreaded server runs.  A blocking operation compared to a non-blocking operation.  All high-speed I/O devices on current computers have non-blocking operations to control them:  The operating system kernel implements blocking system calls with code that performs non-blocking operations.
  • Lecture 11: Explanation of fork and exec under unix.  Details of Copy On Write.  The Windows CreateProcess system call combines the fork and exec functionality and provides a large number of options to set attributes of the new process; under Unix, after the fork, the parent process can customize its attributes before it executes exec.  How programs can tell a non-blocking operation is complete: (1) Polling (use of is_operation_complete() boolean function) either to decide to do other work while waiting, or run busy wait loop.  (2) Interrupt or signal (show how thead execution location jumps to the interrupt handler and then returns to the point of interruption.)  Device drivers (in operating system kernels) read  device registers to quickly determine whether a device operation is complete.
  •  Lecture 12
  •  Lecture14
  •  Lecture 15
  •  Lecture 16
  •  Lectures 17-19
  • Lecture 20 (Prof. Lea's Readers and Writer's Problem Solution Pattern)
  • Review of solution based on "rc" count of active and "wanting" readers.  How the writers starve when a succession of readers keep the reading activity active, which means keep rc > 0
  • Java ReaderWriter class solution pattern from  Prof. Doug Lea
  • Slide 1     Slide 2     Slide 3
  •  Lectures 21-23 (mostly slide images)
  •  Lectures 24-26 Deadlock topic (finished.. explanations, notes with corrected slide images)
  •  Lecture 27-33 on Memory Management (FINISHED!)
  • Lecture 34(12/2) Some tips on the project:  A data structure is needed to keep track of which pages are simulated to be in memory.  The number of pages that occur in the reference string is unpredictable for simulations of realistic applications.  For your simulation, the simulated physical memory size measured in page frames will be either a run time or compile time parameter.
  • If you need a dynamically growable data structure, such as a linked list, here is an alternative:  Use a extendable array (described on the blackboard).
  •  Some old slides with notes about extendable array technique(.ps)
  •  Lecture slides and other materials on Files (Lectures 34-..)