Operating Systems Principles II (Master)

Winter
2013/14

Operating Systems Principles II (Master)

Computer Science Department
Systems Architecture Group

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:

Praktische Informatik, Master, 8 SP.
Offered regularly, at least once every two years, usually in winter.
2 lectures per week, 2h each, over one semester (4SWS VL).
1 lab (Übungen/Praktikum) per week, 2h each, over one semester (2SWS UE).

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.

Lab (Praktikum):

Lab-0: Lab-Overview, Matlab (examples), Lab-0 (Make-Performance)
Lab-1: Events & Threads (Beispiele)
Lab-2: EventQueue (Beispiele, Aufgabenvorlage)
Lab-3: C++11 (Beispiele)
Lab-4: FUSE (Beispiel: hello_fs), Aufgabe (securefs), Vorlage für die Aufgabe, Readlink
Lab-5: Valgrind (Beispiele)
Lab-6: Cache Performance (Beispiel)
Lab-7: Byzantine generals
Lab-8: Byzantine generals 2
Lab-9: Consistency
Lab-10: Overview

Syllabus:

Getting Started

Lecture slides: Getting Started

Requitred Reading: how-to-read-a-paper

How to read a scientific paper?

Read for an overview. What is the purpose of this work?
Read again, with focus on the "story". Annotate the paper.
Read one more time, with focus on the details. Have a discussion with others. Take notes of arguments that came up during the discussion.

Examples	original paper	anotated paper	discussion notes
Rethink the Sync	rethink-sync	rethink-sync_a	rethink-sync_n
Practical, transparent operating system support for superpages	superpages	superpages_a	superpages_n
Memory Resource Management in VMware ESX Server	esx	esx_a	esx_n
Eliminating Receive Livelock in an Interrupt-Driven Kernel	livelock	livelock_a	livelock_n
Generalized File System Dependencies	featherstitch	featherstitch_a	featherstitch_n

Thread vs. Event -based Concurrency
Lecture Slides: (final set as of 2013-11-14)

Required Reading: Threads Cannot Be Implemented As a Library by Hans-J. Boehm

Recommended Reading:
- Threads Basics by Hans-J. Boehm (original: http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/threadsintro.html )
- Eraser: A Dynamic Data Race Detector for Multithreaded Programs by Stefan Savage
- Why Threads Are A Bad Idea (for most purposes) by John Ousterhout
- Why Events Are A Bad Idea (for high-concurrency servers) by Rob von Behren, Jeremy Condit and Eric Brewer
- On the Duality of Operating System Structures by Roger M. Needham
- Cooperative Task Management without Manual Stack Management (or: Event-driven Programming is Not the Opposite of Threaded Programming) by Atul Adya, Jon Howell, Marvin Theimer,William J. Bolosky, John R. Douceur
Additional Reading:
- POSIX Threads Programming. https://computing.llnl.gov/tutorials/pthreads/
- SEDA: An Architecture for WellConditioned Scalable Internet Services by Matt Welsh, David Culler, and Eric Brewer
- Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism by Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy
- Transactional Memory Specification Draft (2012) (this is work in progress)
Local (HDD) Filesystems - revisited

( The hard life of a hard drive - The tension between performance and durability/reliability. )
Lecture Slides: (final set as of 2013-12-17)

Required Reading: Failure_Trends_in_a_Large_Disk_Drive_Population
optional (not required): More than an interface — SCSI vs. ATA

Recommended Reading:
- Disks from the perspective of a file system
  (HDD Caches. When is data actually committed to disk? Write-reordering. Native Command Queuing)
- Rethinking the Sync
  (External Synchrony)
- Finding a needle in Haystack:Facebook’s photo storage (clustering related data)
- Towards practical, high-capacity, low-maintenance information storage in synthesized DNA
Additional Reading (common production file systems):
- ZFS (2002?): The Zettabyte File System
- ZFS: End-to-end Data Integrity for File Systems: A ZFS Case Study
- ZFS: Raid-Z: https://blogs.oracle.com/bonwick/entry/raid_z (cached)
- ZFS: Howto: https://www.freebsd.org/doc/de/books/handbook/filesystems-zfs.html (cached)
- BSD-FFS (1984): A Fast File System for UNIX
- ext1 (1992), ext2 (1993), vfs: Design and Implementation of the Second Extended Filesystem
- ext3 (1998): Journaling the Linux ext2fs Filesystem
- ext4 (2007): Ext4 block and inode allocator improvements. Kumar,Cao,Santos,Dilger. (mathur)
- Sprite-LFS (1991). The Design and Implementation of a Log-Structured File System. Rosenblum, Ousterhout.
- BSD-LFS (1993). An Implementation of a Log-Structured File System for UNIX. Seltzer, Bostic, McKusick, Staelin,
- WAFL (19994). Write Anywhere File Layout. File System Design for an NFS File Server Appliance. Technical Report.
- ReiserFS (2001?): The structure of the Reiser file system
- Fsck − The UNIX File System Check Program. Marshall Kirk McKusick, 1996
- Soft Updates: A Solution to the Metadata Update Problem in File Systems.Ganger, McKusick, Soules, Patt. 2000
- Venti: a new approach to archival storage (annotated) (deduplication)
- Fast, Inexpensive Content-Addressed Storage in Foundation
Remote (access to) Filesystems
Lecture Slides: (final set as of 2014-01-08)

Recommended Reading:
- VFS - Vnodes: An Architecture for Multiple File System Types in Sun UNIX
- NFS - Design and Implemenation of the Sun Network Filesystem (NFS)
- AFS - An Overview of the Andrew File System
- AFS - The Andrew File System (AFS)
- LBFS - A Low-bandwidth Network File System (annotated)
Data Center Storage Clusters
Lecture Slides: (final set as of 2014-01-15)
Lecture Slides: (DHT,Dynamo - as of 2014-01-07)

Recommended Reading:
- Google-FS - The Google File System
- Google-FS - Case Study GFS: Evolution on Fast-forward
- BigTable - Bigtable: A Distributed Storage System for Structured Data
- RAMCloud - The Case for RAMCloud
- Dynamo - Amazon’s Highly Available Key-value Store
- Farsite - Federated, Available, and Reliable Storage for an Incompletely Trusted Environment
Concepts: Time, Consistency and Consensus
6.1 Consistency

Lecture Slides: (final set as of 2014-01-20)

Recommended Reading:
- Eventually Consistent. Werner Vogels (Amazon), 2009.

6.2 Time, Clocks

    Lecture Slides: Uhr-Zeit   (final set as of 2014-01-27)
    Lecture Slides: Clock Synchronization (final set as of 2014-01-27)
    Lecture Slides: Logical Time (final set as of 2014-01-27)

     Recommended Reading:

Probabilistic clock synchronization (Cristian' Algorithm). Flaviu Cristian, 1989.

An Election Algorithm for a Distributed Clock Synchronization Program (Berkeley's Algorithm). Riccardo Gusella, Stefano Zatti, 1985

Maintaining the Time in a Distributed System. Keith Marzullo, 1983

Time Synchronization in DCNET Hosts. Mills, 1981

Time, Clocks, and the Ordering of Events in a Distributed System (Lamport Time). Leslie Lamport, 1978.

Timestamps in Message-Passing Systems That Preserve the Partial Ordering (Vector Time). Colin J. Fidge, 1988.

Virtual Time and Global States of Distributed System (Vector Clocks, Consistent Cuts). Friedemann Mattern, 1989.

      Additional Material:

The Problem with Time & Timezones (youtube)

Theory of Relativity - Simultaneity of Events   (youtube)

6.3 Consensus

     Lecture Slides: RAFT (final set as of 2014-01-22)
     Lecture Slides: Byzantine Generals (final set as of 2014-02-06)

     Recommended Reading:

The Byzantine Generals Problem. Leslie Lamport, 1982.

Paxos. The Part-Time Parliament. Leslie Lamport, 1998.

Paxos made Simple. Leslie Lamport, 2001.

RAFT. In Search of an Understandable Consensus Algorithm. Diego Ongaro, John Ousterhout, 2013.

(Google's) Spanner
Lecture Slides: Spanner (final set as of 2014-02-12)

Recommended Reading:
- Spanner: Google’s Globally-Distributed Database , Google, 2012
System/Language-Level Security, Fault Isolation
Lecture Slides: not yet available
- Sandboxing
  - Native Client: A Sandbox for Portable, Untrusted x86 Native Code (annotated)
  - Singularity: Rethinking the Software Stack
    An Overview of the Singularity Project
- Virtualization
Lawyers, Guns and Money: Open Source Software
Lecture Slides: (very early draft - as of 2014-01-27)
- motivation for "free software" ("free" as in "free speech" and not as in "free beer")
- intellectual property law (US, Europe)
- common "free" License Models
- open software based business models
- famous open source projects / business models

Links


	Stanford CS 140



	Princeton Cos 318



	HPI-Potsdam Prof. Polze: Operating Systems Principles



	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




	MIT Exokernel Operating System


Legal disclaimer. . © 2024 Humboldt-Universität zu Berlin, Computer Science Department, Systems Architecture Group.	Contact: sar@informatik.hu-berlin.de .