Summer
2012

Operating Systems Principles


Computer Science Department
Systems Architecture Group

VL: TUE. 15:00-16:30, RUD 26, 0.310; THU. 9:15-10:45, RUD 26, 0'310 - Dr. J-P. Bell

PR: THU. 11:15-12:45, RUD 26, 1'305  - R. Sombrutzki;  FRI. 11:15-12:45, RUD 26, 1'305  - R. Sombrutzki 

Examination: THU 26.7.2012  9:00-11:00, RUD 26. 0'115 (doors open 8:30)

 
Abstract: An operating system (OS) is the software responsible for controlling and managing hardware and basic system operations, as well as running application software such as word processing programs, Web browsers, and many others. In general, the operating system is the first layer of software loaded into memory when a computer starts up. All other software that gets loaded after it depends on the operating system to provide various common core services, such as disk access, memory management, process scheduling, and user interfaces. As operating systems evolve, ever more services are expected to be common core. These days, an OS may be required to provide network and Internet connectivity and also to protect the computer's other software from damage by malicious programs, such as viruses. Operating systems in widespread use on personal computers (PC) have consolidated into two families: the Microsoft Windows family and the Unix-like family. Mainframe computers and embedded systems use a variety of different operating systems, many with no direct connection to Windows or Unix.

Building Operating Systems is much about studying existing systems, knowing common problems, knowing what other people did, and figuring out if their ideas can be applied to a given new problem. These long-lasting principles - as opposed to implementation details and user interfaces of today's systems/software - is what this lecture is about.

 
Synopsis:
  • Half-Course, Praktische Informatik, Hauptstudium.
  • Offered regularly, at least once every two years, usually in spring.
  • 2 lectures per week, 2h each, over one semester (4SWS VL).
  • 1 lab (Praktikum) per 2 weeks, 2h each, over one semester (2SWS PR).

Credits and grading:

  • There will be a few, short, unannounced, closed-book quizzes to verify your existence and to test your understanding.
  • To qualify for the final written examination (at the end of the semester), you have to complete all lab assignments to the satisfaction of the teaching assistant (70% of all points).
  • Regular class attendance is expected; frequent absences are grounds for a failing grade regardless of other performance. You may be missing up to 1 lecture per semester without prior and reasonable excuse. 'prior' means notification by email before the end of business the day before the lecture. 'reasonable' means sickness or study-related events that require your attendance.
  • Lectures begin on time. Students arriving more than 10 minutes late will not be admitted to the lecture and will be counted as 'missing' that day.

Prerequisites:

 

Lab (Standard-Praktikum):

Prüfungsergebnisse

Die Liste mit den Ergebnissen der Prüfung findet sich hier. Am Donnerstag und am Freitag (02/03. August 2012) kann Einsicht in die Klausur genommen werden.


Syllabus:

    Administrative Information   [ slides]

  1. Introduction  
    What is an OS? History.    [ slides]
    Typical OS structures. System Call.    [ slides]
    Building an OS (SYSGEN), Booting.   [ slides]
     
    Dijkstra: The structure of the THE multiprogramming system (THE)
    Corbato: An Experimental Time-Sharing System (CTSS)
    Feiertag: The Multics Input Output system (MULTICS)
    Ritchie: The UNIX time-sharing system (UNIX)
    Rashid: Accent - A communication oriented network OS kernel (MACH)
     
    Kaashoek: Exterminate all operating system abstractions
    Kaashoek: Exokernel: An operating system architecture for application-level resource management
     
    A Guide to Programming on Intel IA32 PC Architecture
    IA32 Intel Architecture Software Developer's Manual, Volume 1: Basic Architecture
    IA32 Intel Architecture Software Developer's Manual, Volume 2: Instruction Set Reference Manual
    IA32 Intel Architecture Software Developer's Manual, Volume 3: System Programming Guide

     

  2. Processes   
    1. Process Abstraction (in Unix and Windows)     [ slides]
      Process state. Process Control Block. Context Switch. Protection.
       
      Unix Programming FAQ - Process Control
       
    2. CPU Scheduling     [ draft]
      Latency vs. throughput, Optimization goals. FIFO, Round Robin, SJF, Priority scheduling, multi-level feedback queue, lottery scheduling.
       
      Mitzenmacher:The Power of Two Choices in Randomized Load Balancing
      linux-cfs.pdf
      sched-design.CFS.txt
       
    3. Threads      [ draft]
      User-level/kernel-level threads. Shared variables. Lost update problem.
       
      An Introduction to Programming with Threads
      Getting Started With POSIX Threads
      Multithreaded Programming Guide
      Engelschall: Portable Multithreading  (signal stack trick for User-Level Threads)
       
    4. Concurrency and Synchronization    [ draft]
      Race condition. Atomic instructions. Mutual exclusion. Spin locks, blocking locks, semaphores, monitors, optimistic (wait-free) synchronization.
       
      Lamport: A fast mutual exclusion algorithm
      Fast Mutual Exclusion for Uniprocessors (Restartable Atomic Sequence)
      Lampson: Experience with Processes and Monitors in Mesa
      The Little Book of Semaphores
       
    5. Deadlocks    [ draft]
      Coffman Conditions. Deadlock Prevention, Avoidance, Detection&Recovery; Lifelock.
       
      Coffman: System Deadlocks
      EWD 623: The mathematics behind the Banker’s Algorithm

       

  3. Memory Management
    1. Virtual Memory    [ draft]
      Virtual Address. Page Table, MMU. Memory protection. Shared memory.
       
    2. Paging and Trashing     [ draft]
      Demand paging. Distributed shared memory. Trashing, Page fault frequency, Working set, Balance set. Transactional memory.
       
      Balady's Anomaly: FIFO anomaly is unbounded

       

    3. Linking     [ draft]
      Static linking (ELF). Dynamic linking. Shared libraries.
       
      How To Write Shared Libraries
      ELF format.pdf
      GNU Assembler
      Linkers and Loaders (book manuscript): http://www.iecc.com/linker/
       

     

  4. Mass Storage
    1. Disk Storage    [ draft]
      Hard Disk Drive (HDD), Access time (seek/rotational/transfer delay). RAID 0,1,2,4,5,6. Storage Center.
       
      Reference Guide - Hard Disk Drives: http://www.storagereview.com/guide/guide_index.html
      RAID: High-Performance, Reliable Secondary Storage

       

    2. File Systems   [ draft]
      Dos-FAT, Unix-FS (i-node), NTFS.

                         NTFS: http://www.ntfs.com


      ==== ENDE BACHERLOR-PROGRAMM =====================================================

       

    3. File System Performance   [ draft]
      Recovery     [ draft]
       
    4. Flash Memory File System   [ draft]
      NAND vs. NOR flash, Journaling file system. Yaffs.
       
    5. NFS and NetApp's WAFL 
      Filesystem snapshot

     

  5. Virtual Machines    [ draft]
    Virtual Machine Monitor. Virtualization types & techniques. Non-virtualizable x86 instructions. VmWare, VirtualPC, Xen.
     
    Jones: Virtual Linux  (nice overview/introduction from 12/2006)
    Rosenblum: Virtual Machine Monitors: Current Technology and Future Trends
    Rose: Survey of System Virtualization Techniques
    Barham: Xen and the art of virtualization
    Robin: Analysis of the Intel Pentium's Ability to Support a Secure Virtual Machine Monitor
    US Patent 6397242: Virtualization system including a virtual machine monitor for a computer with a segmented architecture (VmWare)
    Hand: Self-Paging in the Nemesis Operating System
    Bugnion: Disco: running commodity operating systems on scalable multiprocessors

 

Lab (Zulassung zur Prüfung)

Die Liste mit den Ergebnissen des Praktikums findet sich hier.

Prüfungsergebnisse

Die Liste mit den Ergebnissen der Prüfung findet sich hier. Am Donnerstag und am Freitag (02/03. August 2012) kann Einsicht in die Klausur genommen werden.

Further Readings:

Silberschatz, Galvin, Gagne. Operating System Concepts. 6th Edition. John Wiley & Sonns, 2003. ISBN 0-471-25060-0
William Stallings. Betriebssysteme – Prinzipien und Umsetzung. 4. Auflage. Prentice Hall, 2003. ISBN 3-8273-7030-2
Andrew Tanenbaum. Moderne Betriebssysteme. 2002. ISBN 3827370191
R. G. Herrtwich and G. Hommel. Kooperation und Konkurrenz - Nebenläufige, verteilte und echtzeitabhängige Programmsysteme. Springer-Verlag, 1989. ISBN 3-540-51701-4.
H. Kopetz. Real-Time Systems: Design Principles for Distributed Embedded Applications. Kluwer Academic Publishers, 1997. ISBN 0-7923-9894-7.
Joseph Pranevich, The Wonderful World of Linux 2.6.
http://www.kniggit.net/wwol26.html (cached pdf)
Unix Programming FAQ: http://www.erlenstar.demon.co.uk/unix/faq_toc.html
 Links
Middleware
(Prof.Redlich, HU-B)
Security Engineering
(Dr.Müller, HU-B)
Secure SysAdmin
(Dr.Bell, HU-B)
Unix API and Tools
(Dr.Bell, HU-B)
IBM Mainframes
(Profs.Redlich/Spruth)
Rechnerkommunikation I
(Dr.Sommer, HU-B)
Rechnerkommunikation II
(Dr.Sommer, HU-B)
Mobile/Embedded Systems
(Dr.Richling, HU-B)

Book: Silberschatz
OS Principles

Open VMS
HP Documentation

HPI-Potsdam
Prof. Polze: Operating Systems Principles

MIT
Exokernel Operating System

Legal disclaimer.   © 2016 Humboldt University Berlin, Computer Science Department, Systems Architecture Group.Contact: sar@informatik.hu-berlin.de .