CSE221 Notes

00 - Introduction and logistics

Couse Objectives & Logistics

• see course websites

Some questions to ponder on relating to “what is OS actually?”

• provide abstractions to upper layers

• manage resources from lower layers

• windowing environment?

• web browsers?

• network stack?

• memory allocation?

01 - Historical Perspectives: THE & Nucleus

The Structure of the “THE” Multiprogramming System

The Goals of the THE Multiprogramming System

• Reduce turn-around time (time between submitted and completed) for short program

• Efficient resouce usage (hardware resources such as cpu, devices, memory)

• Soundness wrt. both design and implementation

• Manage the complexity of the system, which is important for the previous goal for soundness.

Approach used to achieve the goals

• Level 0 - CPU Allocation: handle the clock interrupt and process scheduling. on top of layer 0 the processors shared lost their identities.

• Level 1 - Segment Controller(Memory Management): do the book-keeping stuffs related to virtual memory. Above this level other processes can use segment id instead of physical address to refer to an information unit.

• Level 2 - Message Interpreter(Console Management, virtualizing console I/O device): take care of the allocation of the console keyboard via which the operator communicate with higher-level processes. Above this level the actual physical console keyboard lost its identity.

• Level 3 - I/O Buffering / Un-buffering (Communication with peripherals): manage the communication with devices

• Level 4 - User Program

• Level 5 - Operator

Comments on layered-structure and program verification

Synchronization via semarphore

• Mutex

• Private Semarphore: like conditional variable today

Deadlock prevention

• by leveraging the process hierarchy. High level process will only wait for low level process but the reverse direction is not true.

Summary & take-away

• Layered OS Design

• Abstraction of Sequential Process

• Synchronization via semarphore

• Goal for correctness (easy for program verification)

Additional Notes: Layered OS today

• User Layer

• User-Kernel Interface

• Kernel Layer

• Apps

• Win32 Sub System

• User-Kernel Interface

• Kernel

• HAL (Hardware Abstraction Layer)

Additional Notes: Hardware Trends

The Nucleus of a Multiprogramming System

The Goals of the Nucleus

• extensibility

• flexibility

Components of System Nucleus

• Fundamental Process Control

• IPC via Message Buffering

• Interrupt, exceptions handling

• Scheduling

Components of OSes on top of Nucleus

• Scheduling

• High-level Process Control

• Memory Management

Economy of Abstractions

• Process
• Internal: normal program execution
• External: wrap hardware devices by process and access them in the way you access process

• Message
• buffer management
• synchronization

Summary & take-away

• flexible & extensible OS design

• The idea of System Nucleus, and layer OSes on top of it.

• Synchronization via Message Passing

• Small Number of Abstractions

02 - Historical Perspectives: TENEX & UNIX

TENEX, a Paged Time Sharing System for the PDP-10

Terminology

• different terms for same thing: monitor := kernel

• same term for different things: virtual machine
• OS-Syscall Interface (in TENEX)
• Virtualizing Hardware (VMWare)
• Language Runtime (JVM)

The Goals of the TENEX System

• SOTA virtual machine
• paged virtual memory
• multi-process with IPC
• file system

• good human engineering

• modular, maintainable

• backward compatibility

• efficiency

Virtual Memory

• Address Space (same as today)

• Memory Maps / Table: Page Table

• BBN Pager: TLB (page table cache)

Page Sharing

• Direct: points to a private page of a process

• Indirect: points to an entry of another process’s page table

• shared: points to an entry of the system’s page table

Backward Compatibility

• Add a compatibility layer: implement all TENEX Syscall by the new instruction JSys, and implement legacy system call by TENEX’s new system call.

Summary & take-away

• Virtual Memory - sharing & copy on write

• time sharing system

• support for backward compatibility

The UNIX Time Sharing System

The Goals of UNIX

• Unifying abstraction

• Easy to use

• Easy to extend

• maintainability

• simplicity

File System

• impose structure on file

• file size should be predeclared

• treat file as a sequence of uninterpreted bytes, no imposed structure.

• allow variable-length file

• no buffer cache in kernel

• different API for different access way (random, sequential …), a lot of work for programmers

• buffer cache in kernel, which means I/O operations are buffered

• unified API for different access method, which simplifies things for programmers.

• one directory per user

• directory represented different from regular file

• hierarchical namespaces

• directory is represented the same way as regular files, but the content is interpreted by the file system.

• files are independent of directory

• use different sets of system call for different kinds of devices.

• device independent I/O for most cases (wrap device as file)

• special syscall for device-specific functionality: ioctl

• list of users (multics does this)

• six bits, rwx, for owner and everyone else

• much like today, except today we have more bits

Process

• one process per user

• user can fork() & exec() syscall to create child process

• slightly different api from today’s fork()

Shell

• built into the kernel

• as a user program, so can be customized.

• featured with I/O redirection

Summary & take-away

• nice unifying abstraction

• careful decomposition(which should be put into kernel, which should be implemented in user space)