Unit Three Objectives, CSCI 423, Introduction to Operating Systems Tobin Maginnis Updated: 16-Oct-07 Lecture - General OS Structure Handout 1)Explain how the Figure shows four layers of functionality in an OS. 2)Describe three levels of state saving and explain how they are employed in an OS. Omit)Describe those programs that exist at the highest layer. Explain the UNIX tradeoff of using user space GUI and daemons. 4)Name and describe the role of six mid-level agents (kernel API). 5)Define device independence and explain how the logical unit table (LUT) is the key to device independence. 6)Define system abstraction and explain how to implement it with the LUT. a)OS abstractions are used to simplify an otherwise complex interface. Or abstractions collect primitive routines into one that provides easy access to sophisticated services. b)The logical unit table is organized so that columns represent operations and rows represent sequential logical addresses. c)Table cells contain addresses of functions which carry out the operation for a given column. d)For example, row five provides open, read/write access, and close services just like any other row, however, the row of addresses point to a logical driver such as the "null driver" or a "pseudo terminal." 7)Describe the role of a device driver. 8)Describe a Linux VFS jump table and explain how it leads to additional system abstractions. a)Linux has inserted jump tables in the superblock, file array, and inode. b)Unlike a LUT, these jump tables have just one row and are initialized at filesystem mount time. c)In this way the mount command can dynamically load different file manager back-ends (mapping & data movement) for every mounted file system. d)The file manager back-end can be for a physical file system or for a logical driver. e)Logical back-ends, such as /proc and /sys, appear to be simple data files, but are actually logical drivers that return dynamically create file contents which report system status. When these file abstractions are written to, the logical drivers use the data to modify system variables indicated by the file names. 9)By rearranging OS components, explain how to make network access transparent. a)To make the network transparent, the networking services such as socket(), accept(), connect(), etc. would be replaced with file access services such as open(), read(), write(), and close(). b)By placing the networking manager below the file manager the networking manager becomes invisible (transparent) to the user. c)To access the network manager, a file path may now contain a non-existent directory name which represents a logical host name. d)When the file manager cannot find the directory name, it calls the network manager to see if it is a host name. e)The network manager then uses a peer-to-peer protocol to access the remote host, complete the file lookup, and return the file contents to the file manager which, in turn, passes the file contents back to the user program. Omit)By rearranging the OS components, explain how to make the memory hierarchy transparent. a)To make memory transparent, malloc() and other memory allocation services would be replaced with file access services such as open(), read(), write(), and close(). b)By placing the memory manager below the file manager the memory manager becomes invisible (transparent) to the user. c)This removes the notion of "memory" to the OS by only offering file access to the user. When a user creates a new file or accesses an existing file, its contents are stored in main memory. d)As the number of accessed files grow and exceed main memory capacity, file blocks are swapped out to the hard disk and that page marked "not present" for the file owner. e)When a user request access to file that is not present, it causes a page fault, another page is swapped, and the old page brought back into memory and the user process restarted. Lecture 1)Explain how parent-child communication can be deadlocked using the pipe() service. 2)Explain the six basic protocol steps in the pipe service and contrast pipe I/O versus file I/O. a)The pipe service is implemented from a finite buffer whose size is determined by the host OS. (In Linux, it's 65,536 bytes.) b)Reading an empty pipe (buffer) blocks the reading program. (File I/O only blocks waiting for hard drive, not the data.) c)Reading more data than there is in from the pipe (buffer) returns only the data that is available. (An error condition in file I/O.) d)EOF can only be read from a pipe after all writers have closed their end of the pipe. (This usually means that parents must close pipes.) e)Writing more bytes than the buffer will hold causes the writer to block until the reader drains the pipe (buffer). (If a writer attempts to write beyond the end of the disk, it is an I/O error.) f)Writing into a pipe (buffer) after all readers have closed the pipe file descriptor, generates the SIGPIPE signal. If the signal is not caught, it will terminate the writing process. 3)Describe the limitation to the pipe() service and an alternative service that offers more functionality. The Linux Kernel Primer by Rodriguez, et. al. Chapter 3 - Processes: The Principle Model of Execution. 1)Contrast a program versus a process. a)A program is the code created by the application programmer and the program performs a sequence of actions directed by its instructions. b)A process is the behavior of a program augmented by the linker- loader added run-time environment, dynamic shared libraries routines called by the user program, the behavior of invoked kernel service calls, and interaction with the environment through the assistance of device drivers. c)The program describes the high-level operation of the application while the process describes how the application gets the job done. In operating systems, we are more concerned with the how rather than the why, thus we focus on processes rather than programs. 2)List the four states of a process and the events that cause transitions into each state. a)Ready-to-Run - State entered by process creation, process preemption, and process wakeup. Process preemption occurs when time quantum expires and another process is selected for running. b)Running - State entered by selection for execution by process management (the scheduler). c)Waiting/Blocked - Self-entered suspension state primarily through a kernel device driver (waiting for a I/O completion), or interprocess communication routines (waiting for a signal). Other event-driven routines will resume the process by placing it on the Ready-to-Run queue. d)Zombie - Unix process concept. Instead of having the run time environment release system resources upon exit, enter the Zombie state and wait for the process' parent to do it. 3)Describe five or six areas of a process image. 4)Contrast user/kernel space versus user/kernel mode. a)User/kernel SPACE refers to the current state of the memory management unit (MMU) registers and how they provide a logical view of physical memory. b)User/kernel MODE refers to the processor status register (Intel Flags register) and how it enables/disables instructions that access the MMU registers and physical devices. c)The privilege mode is on by default at power up, but once the kernel executes its first user space program (great, great grandaddy init) the privilege mode is turned off. In this way no user program can gain direct access to physical memory or devices. (This concept was widely employed in computers in the 1960s & 70s, but somehow it escaped the attention of the EEs that developed the early microcomputers and led to virus/spyware crisis we have today.) 5)Explain the concept of a process descriptor. a)The key role of a single-CPU operating system is to provide an illusion of concurrency by quickly switching among user processes once the running process begins to wait for I/O, IPC, or runs too long. b)The same is true for multi-core CPUs, but there is also the possibility of true concurrency among user processes. c)Thus, every operating system maintains a list of processes and their respective states (Ready, Running, etc.). d)This list has various names: the proc array, the process control block (PCB), and the Linux task list just to name a few. e)In Linux, a list element, or structure record, is called a process descriptor and it is a member of the linked Task_list structure. 6)List and define the eight categories of information held in a Linux process descriptor. a)Process attributes - Swapped, threads, debug mode, binary format, profile mode, floating point processor used/unused. b)Process relationships - PIDs of parents, siblings, and group members. c)Process memory space - Saved MMU register values. d)File management - Currently open files, abstractions, and devices. e)Signal management - A list of signals which can be received or ignored and pending signals to be processed the next time the process is executed. f)Process credentials - Real owner/group, effective owner/group g)Resource limits - Maximum open files, max memory, max CPU time allowed, max child processes, max file locks, etc. h)Scheduling related fields - PID, priority, state, sleep average. 7)Explain how Linux has only one process task list yet many lists of process attributes. Give the design tradeoff. a)Process descriptor records are not continuous, but rather each process record is dynamically allocated and linked via pointers into a linked list. Additional process descriptor fields also contain pointers which point to other process descriptor records. b)This allows the formation of arbitrary "clusters of process descriptor records" which may be examined in various ways depending upon which linked list path is traversed through a given cluster. Some paths are exhaustive (they include all records) while others are a subset of process descriptors. c)Since linked lists must be search sequentially, it takes much longer to find and complete an action than it would for a simple array of records where array pointers can stay in CPU registers. But in exchange for relatively long list access intervals, linked lists allow for simple and unconstrained list growth, record shuffling with copy delete operations, and the ability to create multiple lists (paths) within the same set of records. 8)Define "context switch" and voluntary versus involuntary context switches. a)As a process migrates between user and kernel space, it changes from a user process to a kernel process with privileges. This multi-step process begins with a call to a user library which executes a software interrupt or trap instruction into the kernel. The kernel entry routine performs "state saving" by storing the CPU and MMU registers in the user's process descriptor and loading the saved kernel CPU and MMU registers. b)A process voluntarily performs a context switch when requesting a kernel service. c)A context switch is involuntary (preemptive) when a peripheral asserts a hardware interrupt or a fixed interval timing source interrupts the currently running process. 9)Contrast context switching for a timesharing versus real-time OS. And explain how context switches set the standard for an OS. a)If a process is already in kernel space when a hardware interrupt occurs, one of two things happen depending on the type of operating system. b)If it's a timesharing operating system, then there is no context switch per se. Instead, the CPU registers are saved and a device driver is run within the context of the suspended user process. The device driver processes the hardware data and sets flags for later use. Upon return from the device driver the suspended process is resumed. c)If it's a real-time operating system, then a true context switch takes place and eventually the interrupted user will be restarted where it left off in kernel space. However, the device driver can modify processes priority and upon exit from the device driver, the process scheduler is called to pick the next highest priority process. In this way the operating system can schedule user processes so they respond to interrupts in "real time." d)The number of context switches possible per second determines the "bandwidth" of the OS. Or said another way, determines the number of processes the OS can manage and still perform productive work. e)The reason that object oriented OSs run slower than monolithic OSs is that each message exchanged between two objects requires a context switch. Depending on the number of objects in the kernel, tens to hundreds of context switches may be required for each system service call. 10)Describe, and give the tradeoffs of, the Linux services fork(), vfork(), and clone(). a)The fork() kernel service allocates new process descriptor, memory, and copies the current process image to a new memory area. The kernel then schedules the new process and returns from the fork() service call for both processes. The initial process, the parent, receives the PID of the child process upon return from fork() while the child process receives a zero as the return value. Although the programs are identical, neither can see or modify the other's variables. b)The vfork() kernel service has a similar outcome, but does nothing except create a new process descriptor entry. Thus, both processes use the same memory image (that is the same MMU registers) until the child executes a new program; however, the system does not return to the parent until after the child executes the new program. c)Fork() and vfork() are implemented with a kernel service called "clone()." Clone() takes various arguments that can create a simple kernel-context thread or create two processes that use the same memory image (that is the same MMU registers) until one process writes to memory (copy on write). Writing causes the MMU to interrupt the process with a page fault. It's then that the kernel will allocate a new page (4096 bytes) and adjust the MMU registers for the writing process so that variables remain separated. d)Bad: The Linux design slows duplicating programs which create cooperating processes since each memory write to a new page must sustain the delay of page-fault processing. However, the vast majority of Unix fork() service calls are immediately followed with an execl() service call (i.e., shell programming). This means that in traditional Unix implementations time is wasted allocating and deallocating child process images. Good: In Linux, all process creation begins as a thread regardless of which process creation service call is made. Based upon the arguments to do_fork() and the behavior of the parent/ child processes, Linux incrementally adds to the process context complexity. In this way Linux provides the high performance of thread programming but still retains the advantages of process granularity. 11)Describe the Linux process states TASK_RUNNING, TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE, TASK_ZOMBIE, and TASK_STOPPED. And explain why these real states are disconnected from the Ready, Run, and Blocked states. a)The process may either be ready-to-run or it may be the currently running process. b)The process' saved state is intact and kernel-level events may act upon this process. Process is waiting for an event on its "wakeup channel." c)The process is not completely saved and the kernel needs a few more microseconds before it can process a kernel-level event on behalf of the task. d)The process has terminated and the kernel is waiting for the parent to execute the exit() service on behalf of the child. e)The process has received, or the kernel is processing, a software interrupt (signal) on behalf of the process. f)Ready, Run, Blocked are generalizations of process management and do not have a one-to-one correspondence with moment-to-moment needs of process management. For example, Linux makes no distinction between Ready and Running states since it is the process' priority which determines which process is scheduled to execute. Skip details of exit() and wait(). 12)Describe the role of an operating system scheduler, the Linux scheduler implementation, and give its tradeoff. a)The scheduler scans process descriptors searching for ready-to- run processes and the highest priority process within the group. b)Process priority can be any arbitrary numbering scheme, but in real-time systems priority is explictly set while in time-sharing systems priority is implicitly set based upon the amount of time remaining in its quantum and the relative amount of CPU time consumed over a series of quanta. c)As the number of processes increase, the scheduler incurs more overhead searching process descriptors upon process suspension. d)Linux limits this overhead by using two fixed-sized bit maps where the index into each bit map represents the process ID. As each ready-to-run process is preempted, it is removed from one bit map and noted in the twin bit map. When there are no more ready-to-run processes, the scheduler switches between bit maps. Thus, regardless of the number of processes, the Linux scheduler can search the process list in O(1) time. e)Bad side: The Linux scheduler is overly complex for the vast majority of its applications. Usually, a typical Linux box may not execute more than 100 or so processes and a simpler array data structure would be more efficient. Good side: The Linux scheduler scales from simple embedded appliance applications to large mainframe servers running thousands of process without any increase in overhead. 13)Describe four ways a process gives up the CPU. And explain what they all have in common. a)Preemption. A device or network interrupt activates a device driver and it changes the process' TASK_RUNNING state. b)I/O. The process requests information from the hard disk or network and its TASK_RUNNING state is changed. c)Time. Each clock tick decreases the amount of time remaining in the process' quantum. When it reaches zero, the TASK_RUNNING state is removed. d)Exceptions. CPU components stop a process such as the FPP divide-by-zero error, a MMU page fault, or I/O bus error. e)In each case the suspending code calls schedule() to have the scheduler select another process to run. 14)Contrast the traditional PIC versus the APIC circuits. a)The old style Peripheral Interrupt Controllers were centralized and stacked 8259 interrupt controllers and subsequently integrated into the south bridge. But more advanced features were needed with the new CPUs b)The new Advance Peripheral Interrupt Controllers allowed for a direct to CPU inter-processor (multi-core) interrupt in addition to system interrupts. The APIC also monitored CPU performance, temperature, fan speed, and APIC error conditions. 15)Describe the steps of an Interrupt Request (IRQ) bus cycle. a)Upon completion of the current instruction, test the CPU interrupt line(s). b)If true, request interrupting device to provide interrupt vector and fetch the vector from the device (double bus cycle). c)Multiply the vector byte by a constant (shift so many bits to the right) and use it as an index into the Interrupt Descriptor Table (IDT) for Intel 32-bit protected mode interrupt processing. d)Save CPU registers & PSR (Intel Flags register) of the interrupted process on the stack. e)Fetch new Program Counter (IP), and PSR from the IDT entry and jump to the Interrupt Service Routine (ISR). f)Upon completion of the ISR, execute the Interrupt Return (IRET) instruction to pop the saved process registers back into the CPU. 16)Contrast Linux top-half (fast) versus Linux bottom-half (slow) ISRs. a)If the ISR can quickly perform its job by setting/clearing I/O bits or OS semaphores, then the top-half ISR completes the job and returns to the interrupted process. All work is done in the so called "interrupt context." b)If the ISR must process data from its slow I/O device, then it schedules itself as a kernel thread (or tasklet) to complete the work at a later time when the system is idle. The initial action is done in the interrupt context while the remaining slow work is accomplished in the so called "process context" or kernel mode (also called work queues). c)If the machine is multi-core (Symmetrical Multi-Processing or SMP), then slow ISRs may run as parallel threads or "softirqs." The six time manager functions, for example, are run as parallel softirqs.