Summer
2008

Operating Systems Principles
[32 211] half-course, 4VL + 2PR

VL: Tuesday, 09:30-11:00, RUD 25, 3.001; Lecturer: Prof. Redlich
VL: Thursday, 09:30-11:00, RUD 26, 0.110; Lecturer: Prof. Redlich
PR: Tuesday, 11:15-12:45, RUD 25, 4.113; Lecturer: Dipl-Inf. Kurth
PR: Thursday, 11:15-12:45, RUD 26, 1.303; Lecturer: Dipl-Inf. Kurth


Computer Science Department
Systems Architecture Group

Klausurergebnisse vom 17.7.2008 finden Sie   >> hier <<

 
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 week, 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 (Praktikum):

  • Worksheets:  [lab1]  [lab2]  [lab3]  [lab4] [lab5]
    (links to the lab worksheets will be added just in time during the course)
NEU: Wie in der Vorlesung angesprochen, können sich interessierte Studenten bereits die Praktikums-Aufgaben für das nächste Jahr ansehen. Dort wird in einer Folge von 6 Aufgaben ein kleines Betriebssystem selbst implementiert. Wer sich dazu in der Lage sieht, kann anstelle des aktuellen Praktikums auch einige dieser Aufgaben lösen. Bitte beachten Sie dabei aber:
  • Die Aufgaben bauen aufeinander auf; Sie müssen also mit dem Lab 1 anfangen , danach Lab 2, ...
  • Generell ist dieses Lab "praktischer" und anspruchsvoller als das der aktuellen Vorlesung - dafür lernen Sie aber auch mehr :-)
    Es ist also eher etwas für diejenigen, die den Vorlesungsstoff etwas genauer kennenlernen wollen.
  • Das Rohmaterial für die Aufgaben habe ich zwar von Kollegen übernommen, die ähnliches bereits erfolgreich durchgeführt haben; dennoch besteht die Möglichkeit, dass sich im Material an einigen Stellen der Fehlerteufel eingeschlichen hat.

Hier die einzelnen Aufgaben:

  1. Lab 1: Booting a PC
  2. Lab 2: Memory Management
  3. Lab 3: User Environments
  4. Lab 4: Preemptive Multitasking
  5. Lab 5: File Systems and Spawn
  6. Lab 6: The Shell

Für Feedback jeglicher Art bin ich dankbar. Rückfragen bitte generell an mich (J.-P. Redlich).


Syllabus:

    Administrative Information [ slides]

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

     

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

     

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

       

  4. Memory Management
    1. Virtual Memory   [ slides]
      Virtual Address. Page Table, MMU. Memory protection. Shared memory.
       
    2. Paging and Trashing  [ slides]
      Demand paging. Distributed shared memory. Trashing, Page fault frequency, Working set, Balance set. Transactional memory.
       
    3. Linking   [ slides]
      Static linking (ELF). Dynamic linking. Shared libraries.
       
      Aufzählung How To Write Shared Libraries
      Aufzählung ELF format.pdf
      Aufzählung GNU Assembler
      Aufzählung Linkers and Loaders (book manuscript): http://www.iecc.com/linker/

       

  5. Mass Storage
    1. Disk Storage  [ slides]
      Hard Disk Drive (HDD), Access time (seek/rotational/transfer delay). RAID 0,1,2,4,5,6. Storage Center.
       
      Aufzählung Reference Guide - Hard Disk Drives: http://www.storagereview.com/guide/guide_index.html
      Aufzählung RAID: High-Performance, Reliable Secondary Storage
       
    2. File Systems   [ slides]
      Dos-FAT, Unix-FS (i-node), NTFS.
       
      Aufzählung NTFS: http://www.ntfs.com
       
    3. File System Performance   [  slides]
       
    4. Flash Memory File System   [ extra-slides]
      NAND vs. NOR flash, Journaling file system. Yaffs.
       
    5. NFS and NetApp's WAFL 
      Filesystem snapshot.
       
      Aufzählung NetApp's WAFL (file system snapshots)

       

  6. OS Subsystems
    1. IO Devices and Drivers      [ extra-slides]

     

Further Readings:
Aufzählung Silberschatz, Galvin, Gagne. Operating System Concepts. 6th Edition. John Wiley & Sonns, 2003. ISBN 0-471-25060-0
Aufzählung William Stallings. Betriebssysteme – Prinzipien und Umsetzung. 4. Auflage. Prentice Hall, 2003. ISBN 3-8273-7030-2
Aufzählung Andrew Tanenbaum. Moderne Betriebssysteme. 2002. ISBN 3827370191
Aufzählung R. G. Herrtwich and G. Hommel. Kooperation und Konkurrenz - Nebenläufige, verteilte und echtzeitabhängige Programmsysteme. Springer-Verlag, 1989. ISBN 3-540-51701-4.
Aufzählung H. Kopetz. Real-Time Systems: Design Principles for Distributed Embedded Applications. Kluwer Academic Publishers, 1997. ISBN 0-7923-9894-7.
Aufzählung Joseph Pranevich, The Wonderful World of Linux 2.6.
http://www.kniggit.net/wwol26.html (cached pdf)
Aufzählung 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. .  © 2024 Humboldt-Universität zu Berlin, Computer Science Department, Systems Architecture Group. Contact: sar@informatik.hu-berlin.de .