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ählungDijkstra: The structure of the THE multiprogramming system (THE)
    AufzählungCorbato: An Experimental Time-Sharing System (CTSS)
    AufzählungFeiertag: The Multics Input Output system (MULTICS)
    AufzählungRitchie: The UNIX time-sharing system (UNIX)
    AufzählungRashid: Accent - A communication oriented network OS kernel (MACH)
     
    AufzählungKaashoek: Exterminate all operating system abstractions
    AufzählungKaashoek: Exokernel: An operating system architecture for application-level resource management
     
    AufzählungA Guide to Programming on Intel IA32 PC Architecture
    AufzählungIA32 Intel Architecture Software Developer's Manual, Volume 1: Basic Architecture
    AufzählungIA32 Intel Architecture Software Developer's Manual, Volume 2: Instruction Set Reference Manual
    AufzählungIA32 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ählungJones: Virtual Linux  (nice overview/introduction from 12/2006)
    AufzählungRosenblum: Virtual Machine Monitors: Current Technology and Future Trends
    AufzählungRose: Survey of System Virtualization Techniques
    AufzählungBarham: Xen and the art of virtualization
    AufzählungRobin: Analysis of the Intel Pentium's Ability to Support a Secure Virtual Machine Monitor
    AufzählungUS Patent 6397242: Virtualization system including a virtual machine monitor for a computer with a segmented architecture (VmWare)
    AufzählungHand: Self-Paging in the Nemesis Operating System
    AufzählungBugnion: 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ählungUnix 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ählungMitzenmacher:The Power of Two Choices in Randomized Load Balancing
      Aufzählunglinux-cfs.pdf
      Aufzählungsched-design.CFS.txt
       
    3. Threads  [ slides]
      User-level/kernel-level threads. Shared variables. Lost update problem.
       
      AufzählungAn Introduction to Programming with Threads
      AufzählungGetting Started With POSIX Threads
      AufzählungMultithreaded Programming Guide
      AufzählungEngelschall: 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ählungLamport: A fast mutual exclusion algorithm
      AufzählungFast Mutual Exclusion for Uniprocessors (Restartable Atomic Sequence)
      AufzählungLampson: Experience with Processes and Monitors in Mesa
      AufzählungThe Little Book of Semaphores
       
    5. Deadlocks    [ slides]
      Coffman Conditions. Deadlock Prevention, Avoidance, Detection&Recovery; Lifelock.
       
      AufzählungCoffman: System Deadlocks
      AufzählungEWD 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ählungHow To Write Shared Libraries
      AufzählungELF format.pdf
      AufzählungGNU Assembler
      AufzählungLinkers 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ählungReference Guide - Hard Disk Drives: http://www.storagereview.com/guide/guide_index.html
      AufzählungRAID: High-Performance, Reliable Secondary Storage
       
    2. File Systems   [ slides]
      Dos-FAT, Unix-FS (i-node), NTFS.
       
      AufzählungNTFS: 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ählungNetApp's WAFL (file system snapshots)

       

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

     

Further Readings:

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