Unit Three                   CSCI523                 Operating Systems

Linux Kernel Development, 2nd ed. - Robert Love
Chapter Four - Process Scheduling
 1)Define concurrency, contrast cooperative versus preemptive process
   schedulers, and explain the idea of a quantum slice of time. p. 39-40
   a)One computer can only run one task at a time.
   b)Because Humans cannot discriminate events that occur within a few
     tenths of a second or less, the computer appears to be running tasks
     concurrently.
   c)Most programs surrender control of the CPU when they wait for slow
     I/O devices; however, when compute bound, tasks must remember to
     give up control (cooperative scheduling) or, because of a timer
     interrupt, control is taken from the task (preemptive scheduling).
   d)To make things fair, a preemptive scheduler allows each task to
     run for an arbitrary fixed (100 ms) interval or time slice before
     switching to another task.
 2)Explain how a scheduler employs the concept of priority to implement
   a scheduling policy that provides fast response time (low latency)
   and a high number of programs per minute (throughput) in Unix.
   p. 40-43
   a)Tasks are programmed to run to completion if allowed.
   b)Tasks that give up the CPU and wait for I/O are given a higher
     priority than compute bound tasks which are forced to surrender
     the CPU at the end of their quantum.
   c)I/O devices interrupt the CPU which suspends the current running
     task and signals that the I/O command has completed. The previously
     blocked (I/O waiting) task is now set ready-to-run.
   d)Last, the interrupt routine either returns to the suspended task
     or the scheduler is called to pick the next task to execute.
 3)Contrast a multi-user versus real-time schedulers and explain why
   reentrance is required.
   a)In multi-user Unix implementations, the I/O interrupt service
     routine (ISR) always returns to the interrupted task so that it
     may complete its quantum and received its fair share of CPU time.
   b)All tasks in a multi-user kernel have exclusive control over the
     CPU until they either: wait for I/O completion, or they consume
     their allotted quantum. Thus, tasks may use global variables without
     concern that another task will change the value of a variable.
   d)In real-time Unixen the ISR returns to the scheduler, instead of
     the interrupted task. The scheduler selects the highest priority
     task to run next which is usually the task waiting for the device
     that just interrupted.
   c)This real-time action continues the suspension of the interrupted
     task which means that there cannot be any global kernel variables
     left which may have been set by the suspended task.
   e)A reentrant kernel allows only stack (local) variables and constants
     for each task. In this way, any task may restart anywhere in the
     kernel without worry of modifying another task's data.
   f)Since a task in a real-time kernel never knows exactly when it will
     be able to complete its quantum, the time interval name is changed
     to "time slice" to indicate this uncertainty.
 4)Assuming a today's 3 GHz CPUs execute about 1.5 billion instructions per
   second or 1.5 million instructions per millisecond, describe the typical
   task to scheduler interaction using a 100 ms time slice.
   a)Most tasks probably run to completion with only a million or so
     instruction sequence which means that most tasks can run to 
     completion within less than one hundredth of the assigned time slice.
   b)A typical task spends most of its time waiting for I/O devices which
     further decreases the role of the time slice.
   c)Allows for quick reshuffling of background compute-bound jobs (SETI at
     home).
   d)But for most tasks, scheduler code is unused and when it is needed the
     slow hard disk means the system becomes too slow for practical use.

Linux Kernel Development, 2nd ed. - Robert Love
Chapter Five - Interrupts and Interrupt Handlers
Omit)Contrast an IRQ, ISR (p. 76-77), and interrupt context (p. 84).
 2)Despite hardware IRQ vectors, explain why OSs typically funnel I/O through
   centralized dispatchers. p. 86
   a)Employ space/time tradeoff by not duplicating common code for all
     devices.
   b)IBM AT allows shared interrupts and a centralized dispatcher can test each
     device on the interrupt line to see if it was the one that interrupted.
   c)Debugging spurious interrupts, identifying failed hardware, or faulty
     interfaces sharing interrupt lines with good interfaces.
   d)Although SMP support circuits allow any CPU to respond to an interrupt,
     the centralized dispatcher may direct IRQs to one CPU or a sub-group.
 3)Describe the contents of /proc/interrupts and how the data is used. p. 87-88
Omit)Contrast the use of cli()/sti() versus the newer local_irq_save() and
   local_irq_restore() p. 88-90
 5)Contrast and give the rationale for in_interrupt() and in_irq(). p 91

Linux Kernel Development, 2nd ed. - Robert Love
Chapter Sixteen - Modules
 1)Describe the role of a kernel module and give its design tradeoff. p. 279-280
 2)Describe the two required entry points for loadable modules and how they
   change if the module is compiled into the kernel. p. 280
 3)Describe the modifications to the kernel source tree for a new module. p. 281-283
   a)Select a position below the drivers directory.
   b)If a new sub-directory, then add the sub-directory name in the parent Makefile.
   c)If conditional complication, Add command line macro names to (b).
   d)Add the driver name to the local Makefile. 
   e)If multi-file driver code, add list each file to be included in module object.
   f)Makefile directives specify ".o" extension, but gcc names them ".ko" files.
Omit)Contrast the commands: make modules_install, depmod -A, and the file: modules.dep.
Omit)Contrast the commands: insmod hello, rmmod hello, and modprobe [-r] hello.
 6)Describe the following Kconfig directives: config, tristate, default, help,
   depends, and select. p. 284-286
 7)Explain the role of module_param and its variants. p.286-287
 8)Explain the role of EXPORT_SYMBOL() versus EXPORT_SYMBOL_GPL() as they relate to
   modules. p. 288-289

Linux Kernel Development, 2nd ed. - Robert Love
Chapter Twelve - The Virtual File System
 1)Explain how the concept of a VFS is a uniquely Linux contribution to OS theory.
   a)Historically OSs file system formats were considered proprietary and OS designers
     presented their "best-of-breed" file managers as a competitive advantage.
   b)Initial versions of Linux were cross developed with Andrew Tanenbaum's Minix
     OS and Linux used the Minix file system instead of having one of its own.
   c)The VFS was created so that Linux could migrate to its own file manager.
   d)But a new file manager proved to be a moving target, Linux file managers
     quickly went from Minix, Ext, Xia, Ext2, FAT, and onto tens of others.
   e)The many types of file managers allowed Linux to be compatible with other
     popular OSs and it allowed continual best-of-breed file manager upgrades
     without loosing compatibility with earlier formats. Presently there are more
     than fifty defined file manager types.
   f)Because of its VFS, Linux is the one OS that can seamlessly move data among
     tens of existing file formats as well as have unique file manager abstractions
     such as the multi-volume and RAID file managers.
   g)Oddly, the simple, stripped down, Minix file manager is still in use today. It's
     the preferred file format for initial RAM disks (initrd) employed at system boot
     time.
 2)Describe the overall flow of control of a the write() system service. p. 211
 3)Describe the Unix terms "filesystem" and "namespace."  Describe the "chroot"
   command and how it interacts with a filesystem. p. 211
 4)Contrast named volumes (C:) versus a namespace and give the design tradeoff. p. 211
 5)Contrast "byte stream" versus "record" files and file managers and give the
   tradeoff. p. 211
 6)Describe the conundrum of attaching a FAT filesystem to Linux.
   a)FAT has no concept of owner, group, and others.
   b)FAT file names are case insensitive with a maximum length of six characters and a
     required file type field.
   c)FAT text files use a two character end-of-line marker, but they may be valid data
     for other ASCII files.
   d)Generally all of this is not an issue because FAT file types are used to transfer
     information rather than act as an active OS storage element.
 7)Describe the two public and two private roles of a file manager and explain how
   Linux has used the VFS to accommodate multiple file formats.
 8)Describe the role of superblock and explain the statement sb->s_op->write_super(sb)
   and explain why the quota and inode jump tables are in the superblock. In other
   words, would it not be more efficient to have these structures above the superblocks
   and not duplicated them within each superblock?  p. 213-215
 9)If an inode describes a file, and a file is a byte stream, then explain why we need
   the functions in the inode operations table? Describe how each of these are a
   special exception to a byte stream file philosophy: mkdir, mknod, symlink, permission,
   and getattr. p. 217-222
10)Superblocks and inodes are storage roadmaps to the disk blocks that make up a file.
   Explain how this relates to the abstractions /proc and /sys. Describe the output of
   the mount command.
11)Describe the role of namei() and its general algorithm steps. Explain how BSD, and
   then Linux, improved upon this design. 
12)Describe the role of dentry states: used, unused, & negative. Explain the role of
   dhash() and the dcache "used" entries with their associated pinned icache entries.
   Explain the role of the doubly linked LRU list of unused and negative dentry entries.
   p. 223-224
13)Describe the role of the "file object" and its ability share a file view or create
   multiple views of a file's content. p.226-230
14)We have seen jump tables in the superblock object, the inode object, and now the
   file object. Explain how these tables relate to file managers.
15)Describe the data structures pointed to be the task (process) descriptor fields
    "files," "fs," and "namespace."


Cell Computer Architecture
 1)Describe the relationship among The PowerPC Processing Element (PPE), the
   Synergistic Processing Element (SPE), the L2 Cache, the internal Element
   Interconnect Bus (EIB), the shared Memory Interface Controller (MIC), and the
   FlexIO interface.

Lecture on 386-based PC/AT System Architecture
 1)Explain the apparent contradiction of one physical 80xxx bus and the two
   logical buses show in the Figure.
 2)Explain the apparent contradiction of a bus architecture and radial
   interrupt lines (explain the design tradeoff).
 3)Describe the nesting of interrupt controllers and relate the controllers
   to the four steps of an interrupt cycle.
 4)Define DMA and describe the implementation differences between a
   traditional DMA implementation and the IBM PC implementation.
 5)Describe the IBM PC/ATX System Architecture north/south bridge components
 6)Describe the next generation effort to improve CPU-memory performance.