CS 3210 Operating System Design

Spring 2003, TuTh 1:35-2:25

 

Exam 2 Study Guide

 

Topics Covered:

·        Process Address Space (ch 8) – 2 questions

·        Signals (ch 10) – 2 questions

·        Process Scheduling (ch 11) – 1 question

·        Virtual Filesystem (ch 12) – 2 questions

·        Managing I/O Devices (ch 13) – 2 questions

·        Disk Caches (ch 14) – 1 question

 

Exam is closed-book. There will be 10 questions in 90 minutes with short answers (usually 2 or 3 well chosen sentences). I expect knowledge of general concepts, important ideas and some details. Questions are drawn mostly from the primary text. I highlight important info in class but may draw a detail question from something described in the text but mentioned in passing in class

 

I recommend using a top-down study strategy. Read the chapter, close the book and ask yourself, “What were the 3-5 most important ideas or concepts presented in this chapter?” A “brainstorming” approach is also useful. I do this in class as review sometimes. “Tell me everything you know about interrupts and exceptions.” Just list everything you know and then organize among the major topics you listed above.

 

I often try to highlight or emphasize things that are particularly interesting or unusual or not well-known. In addition, I try to relate implementation details in Linux to corresponding general principles in OS (from the Dinosaur book).

 

Another technique is to skim the chapter, looking at headings, subheadings, and so forth. You should probably know something about each section and subsection. As a random example, consider “IRQ distribution in multiprocessor systems” on page 136. Why is this an issue? Because interrupts are executed (usually) by a single processor. So there is a policy issue that arises. Which processor should respond? How is this resolved in Linux? You should at least understand the basic SMP interrupt architecture using APICs. There is a “front-end APIC” and a per-cpu “local APIC” that share a communication bus. At a further level of detail you might recall that Intel hardware has a way to direct interrupts to the “lowest priority” task but that Linux simply uses the “round-robin” arbitration circuitry present in the hardware to handle situations in which two or more tasks have the same priority.

 

Process Address Space

          address space (AS): set of addressable memory locations

                in theory 0-4GB on 32 bit machine

                in Linux 0-3GB (kernel is mapped in high 1GB)

                in reality 0-3GB – high 128MB (used for “high mem”, vmalloc, etc.)

        AS mapping: valid (mapped) versus invalid (unmapped)

                attempts to touch unmapped location: SEGV

                mapping ultimately done via mmap() sys call

        AS lifecycle: fork -> exec -> mmap -> munmap -> brk -> shmat -> exit

        AS example events:

                create a process (fork, exec)

                grow the stack (automatic growth)

                grow the heap (via malloc)

                dynamic linking/loading

                terminate a process

                system v shared memory: shmat/shmdt

                file mapping: mmap()

        file mapping

                little known, popular with kernel hackers

                make file look like memory

                        reads access file, writes flush through (eventually)

                compare to /proc/kmem – memory that looks like a file (!)

                “backing” file

                optimizes file access (avoids a copy)

                        regular: file to kernel buffer, kernel to user buffer (2 copies)

                        file mapped: file to user space (1 copy)

                executables are “file mapped”

                        implements loading!

                “standard” read/write uses file mapping internally

        Note: page fault doesn’t change AS mapping

                page fault (faulting in a page) just allocates/loads page frame

                mapping must already be defined

                attempting to touch unmapped region -> exception (SEGV)

        Data structures

                memory descriptor (current->mm)

                        shared (ref counted) by threads sharing AS

                        important fields: mmap, mm_rb, mm_cache, pgd

                memory region descriptor (vm_area_struct; VMA)

                        contiguous mapped range with uniform permissions

                        vma list: linked list of these descriptors

                        red-black tree: balanced tree of VMAs for fast access

                        vm_ops: function table for loading, etc.

                        VMA access writes

                                Intel only has 2 bits for permissions!

                        utility functions for manipulating address range intervals

        /proc/*/maps – shows mapped regions

                bug: contents shown twice

        be familiar with mmap() – man mmap

                do_mmap

                so called ANONYMOUS pages

        updating page tables, tlb when AS is modified

        page fault exception handler

                complex case analysis – be familiar with cases

        copy-on-write: how it’s implemented

                VMA says RW, page table says RO

                attempt to write triggers page fault

                page fault handler notices “ah, this is copy on write situation”

 

Signals

          basic ideas

                old “event delivery” mechanism

                simplest form of IPC – just 1 bit (an event happened)

                software analog of hardware interrupts

                signals have names and numbers, default actions

                        some platform, architecture dependent (exceptions)

                        know a few example signals

                processes can “send” signal to another process, group

                kernel can send signals (e.g. in response to hw exception)

                signals are sent (generated, raised) then delivered (handled, caught)

                        sending (kill) occurs in context of generating process

                        delivery in context of receiving process

                        signals are delivered on transition from kernel to user

                                pretty frequently: happens at least 100 times per second!

                possible to “catch” signals: user-specified handlers

                        can’t catch KILL or TERMINATE

                “regular” signals

                        1-31, “can’t count”

                “realtime” signals

                        32-63, user-defined, queued (“can count”)

                        bounded queue (~1000) to prevent denial of service

                        separate API

                blocking, masking, pending

                        blocking – don’t deliver if generated

                        masking – block current signal during delivery

                        pending – generated (sent) but not delivered

                                short interval even if not blocked

                                pending but blocked is possible (sigpending())

                                blocked but not pending possible (not generated yet)

                        possible to specify signals to be masked during handler

                signals and system calls

                        blocking (slow) system calls terminated by signal delivery

                                returns EINTR

                        possible to specify “auto restart” (BSD)

                                specified when registering signal handler (per signal)

                unusual BSD feature – alternate signal stack

        APIs

                3 separate APIs, old API still available

                old “unreliable” signals (signal())

                        bug: not masked (reentrant), default action reinstalled

                        result: window of vulnerability

                        not possible to reliably catch all signals sent

                new POSIX “reliable” signals (sigaction())

                        no window of vulnerability but signals still “can’t count”

                        old semantics available as parameters of sigaction()

                new POSIX “realtime” signals (rt_sigaction())

                        possible to include a little extra info

                        signal struct added to queue when generated

                        subtle semantics: interactions between regular, realtime

        data structures

                signal sets: array of 2 ints as a bitmask (1 per signal)

                there is no signal 0 (used for testing delivery permissions)

                pending, blocked signal sets

                pending signal queue

                sigpending (convenience Boolean – any pending, non-blocked)

                sig struct – contains array of handlers, flags, masks

                utility routines on signal sets (ugly bit tricks!)

        generating signals

                send/force_sig_info()

                check permissions

                some signals cancel out others

                ultimately, setting bit in target process task struct

                        actually, regular signals are queued (once) in Linux

                        seems to be a code simplicity technique

                        bit is still set if queue is full

                for realtime, setup info packet, enqueue

        delivering signals         

                   much more complex than generating

                default actions pretty easy

                executing handlers must be done in user space

                        place a special stack frame on user-mode stack

                must execute all pending, non-blocked

                so must return to kernel after finishing handler

                        special system call: sigreturn()

                        returning to kernel executes code on user-mode stack!

                so called “trampoline code”: kernel to user to kernel to user …

                be familiar with sample code on page 333

                be able to explain flow of control in Figure 10-2

                be familiar with signal stackframe layout in Figure 10-3

        kill() system call

                possible to send to process group, all processes, specific process

        sigsuspend() – mask, wait for delivery atomically

                sigpending() followed by sleep() not the same!

                understand why …

       

Process Scheduling

         

Virtual Filesystem

         

Managing I/O Devices

         

Disk Caches