Unit One CSCI523 Operating Systems Lecture on General OS Structure Handout 1)Explain how the Basic Operating System Control Flow Figure shows five layers of functionality in an OS. a)The Figure is arranged to show how user requests flow from top to bottom or how environmental events flow from bottom to the top of the Figure. b)At the highest layer are programs which execute in user space. Some of these are system background program, system utility programs, or user application programs. c)The state saver sits at the second level. Although just a 100 or so lines of code, its job is to switch the logical view of memory from user space to kernel space. The state saver also enables or disables a privilege mode when it restores or saves the kernel-space control flow. d)At the third layer is made up of the main OS agents which accept user-space requests and execute in kernel mode. The sum of these requests make up the application program interface (API) of the operating system. e)The fourth layer consists of jump tables and common OS buffering. Jump tables create system abstractions by transferring flow control from a common source to one of many possible subroutines. Abstractions are created when the row of the jump table represents a logical entity (e.g, virtual device, status report, format converter, and so on) while the table columns represent operations or actions to be conducted on that logical entity. Common OS buffers hold logical OS blocks of data and are used to synchronize data movement among asynchronous environmental events below and the synchronous user space requests from above. f)The last, fifth, layer is made up of device drivers which translate logical OS blocks of data to/from physical device records. 2)Describe three levels of state saving and explain how they are employed in an OS. a)At the lowest level, a hardware interrupt saves the program counter (Intel instruction pointer) so that the new program may return to the previous program upon completion of interrupt processing. However, many architectures also save the stack pointer and some form of memory management data as well as the program counter. b)At the next level, subroutine linkage performs stack frame management. Before a subroutine is called, it's arguments are saved on the stack, then the return address, then a copy of the stack (frame) pointer is saved. Finally, the stack pointer is decremented to create space for local variables to be used in the called subroutine. c)The context switch represents the highest level of state saving. Here the calling routine CPU registers, memory management registers, and other volatile registers are saved in a reserved space, the process control block (PCB), for the process. Then, the new process' saved information is read from another PCB entry and copied into the various CPU registers. Upon copying the saved program counter, control is automatically passed to the new process. 3)Describe those programs that exist at the highest layer. 4)Name and describe the role of six mid-level agents. a)Network Protocol Stack allows program-to-program communication via the use of a protocol, local port number, local IP address, remote port number, and remote IP address. Example API calls are socket(), bind(), accept(), connect(), send(), receive(), and close(). b)File Manager provides two public functions: naming and protection for user-defined data units (files) as well as two private functions: a disk mapping scheme to describe the disk blocks that make up free blocks and allocated file blocks; and a buffering mechanism that maps any size user buffer to a series of sequential logical OS blocks and subsequently physical records. Example API calls are open(), read(), write(), lseek(), and close(). c)Memory Management routines allocate space for a process from a pool of free memory pages. Most of its allocation/deallocation actions are at the request of process management. The two user API calls are malloc() and mfree(). d)Process Management loads, sets read-to-run, executes, suspends, resumes, terminate, and reclaim user processes. Example API calls are fork(), exec(), exit(), wait(), and pause(). e)Time Manager is responsible for subtasks: i)Tally fixed-frequency interrupts or jiffies into seconds, minutes, hours, etc. ii)Evaluate interval time-outs for device drivers and threads and jumping (callback) to the kernel function requesting service upon interval completion. iii)If the fixed-frequency interrupt occurring during user mode, increment the jiffy count for user time. Otherwise increment the jiffy count for kernel time for the current process. iv)Adjust current process consumed quantum time and process priority. If process' priority has dropped below others, switch process back to "ready-to-run" state so the next highest priority process will execute. v)If profiling has been enabled for this process and we are in user mode, use the program counter value as an index into a histogram and increment a jiffy count for amount of time spent in the current user process function. f)Inter Process Communication provides four basic forms of communication among processes. i)Software Interrupts transfer control flow from the current user function to the signal function in the user's program. Upon completion, the signal function returns to the previously executing function. ii)Shared Memory or mail boxes allow processes to pass data or share data. It is possible for one process to erase or modify another process' data held in shared memory. iii)Messages are data copied from one process address space to another process address space. It is not possible for the one process to modify another process' data. iv)Semaphores control access to shared data. All process agree to use the semaphore to prevent one process from modifying another process' data. 5)Define device independence and explain how the logical unit table (LUT) is the key to device independence. a)Device independence means that any user data may be read from or written to any device simply by specifying a logical device number or name. b)First, arbitrary user-buffer sizes are translated to a uniform logical OS block size which all device drivers are programmed to use. c)Second, all device drivers have entry points which process all device commands, even if the command has no relevance to a particular device (e.g., write to a CD-ROM). d)Lastly, the logical unit table is constructed so that each row has a series of function addresses (pointers) for the various entry points into a given device driver. The row number is the logical device number. Also, each column of the table represents a driver command such as open(), read(), write(), close(), and so on. 6)Define system abstraction and explain how to implement it with the LUT. a)System abstractions are logical constructs within the OS such as the /dev/null rathole and /dev/ramdisk. b)Logical drivers occupy a row in the logical unit table and accept the common driver commands. c)A logical driver is programmed just like a physical driver except that it takes input from, or outputs to files. 7)Describe the Linux VFS and explain how it offers abstractions at a higher level than the LUT. Give the VFS design tradeoff. a)To mount a file system and access a file in Unix/Linux, the file manager must navigate the file system super block as well as three other data structures: the open file array, the file array, and the inode table. b)Linux VFS extends the Unix super block, file array, and inode by adding a LUT like jump table to the these data structures. c)Unlike the LUT, the VFS table has only one row, but many columns for all possible operations on a file system or file. d)In this way, Linux may call any function to handle any operation on any logical or physical file system or individual file. e)In exchange for this flexibility, Linux must carry many duplicate data structures for each file that resides on the same physical device. 8)Explain how the VFS has replaced the LUT and why it is still "hanging around." a)Since the VFS controls which functions are called for which file operation, then the VFS may also directly call a logical or physical device driver without going through the LUT. b)Not sure... Some application programs may depend upon the block or character device driver file type and use well known row numbers. Could also be something to do with loading a module device driver and registering the module with the kernel. 9)Describe the role of a device driver and give example of two basic types of device drivers. a)A device driver translates logical OS blocks of data to/from device specific physical records. b)A block driver maps a logical 4KiB logical OS block into 8,512 byte physical records based upon selecting a disk surface, track number, and sector number. c)A character driver maps a sequence of bytes to/from a sequential device (e.g., keyboard, magnetic tape). 10)Explain how rearranging OS components lead to transparent functionality. a)The six main agents: NPS, FM, MM, PM, TM, and IPC makeup the application program interface of the operating system. That is, the total operating system functionality is described by the sum of the services provided by each agent. b)If one of these agents is placed below another, then its respective API becomes invisible to application programs. Since the functionality remains behind another agent, the service is said to be transparent. 11)Explain how to use the concept of a logical driver simplify user interface programming. a)Although closely related to each other, the display, keyboard, and mouse must be controlled by one or more user space programs that share access to the devices. b)A logical driver such as screen manager could be placed between the LUT and drivers which would provide a single point for controlling user interaction in the kernel without the need for user space program management while updating the display. c)The screen manager could be configured to process multi-displays, and other devices such as biometric scanners. d)Furthermore, the screen manager actions would be done in response to device interrupts from the kernel providing faster response times compared to user space mediated interactions. 12)By rearranging the OS components, explain how to make IPC access transparent. a)With its open(), read/write(), and close() semantics across all logical and physical drivers, the file manager is the most flexible of the six OS agents. b)Thus the IPC shared memory, semaphores, messages, and signals can thought of as reading or writing to special files which provide direct access to another program. 13)By rearranging the OS components, explain how to make the memory hierarchy transparent. a)A typical program allocates a memory buffer, opens a file, reads the contents of the file into the buffer, manipulates the data, and writes the buffer contents back to a file. b)If the memory manager were subservient to the file manager, then there would not be a memory allocation API such as malloc(). c)Instead, the program would open a file and directly operate upon its contents. The file manager, in turn, would call malloc() and page the file contents into memory. d)If the file contents were too large for memory, then a page fault would initiate a page swap so that the required page may be brought into memory. 13)By rearranging the OS components, explain how to make the network access transparent. a)Here the file manager is used to access files on remote host computers. However, network-based communication requires logical to physical hosts name translation, host-to-host connectivity, as well as program-to- program connectivity. b)A communication manager is placed above the network device driver so it can manage host-to-host virtual circuit conversations. c)A resource manager provides logical to physical host name lookup primarily at the request of the communication manager. When a host boots up, it broadcasts its logical name to all other hosts and it receives a reply containing their logical to physical mapping. d)A network manager resides below the file manager, but above the communication manager, and provides program-to-program connectivity. In this way, it accepts file access requests that contain logical host names as a file name path component, and it initiates a conversation with its peer network manager at the destination host to read or write the requested file contents. e)The destination host network manager accepts the file access request and uses its local file manager to fetch or put the requested file contents. John Lyons' C Tutorial Omit)Contrast 10, 010, and 0x10. Omit)Contrast "int" and "char" and explain the effect of using "short," "long," "register," and "unsigned." 3)Explain the significance of: "long flag_pole; int i; flag_pole = i; flag_pole = (long) i;". 4)Explain why the char data type is always promoted to int internally, and define "sign extension." List the four steps in: "i = c & 0377;". 5)Contrast "int a[10];" "struct data1 {int i; char c;}" and "union {int i; char c;} u;". Omit)Contrast "int i, *pi, a[10], *b[10], **pi;". 7)Explain "register struct table *p;" and "p = &z[4];". Omit)Contrast "n = p->i;" and "n = z[4].i;". 9)Describe the action of statements like: "i = x < y ? 6 : K + 1;". Omit)Contrast "local" and "global" C variables. Describe two ways of creating local variables. Explain the difference between uninitialized local and uninitialized global variables. Omit)Give examples of file inclusion, macro definition, macro expansion, and conditional compilation. 12)Contrast "for(i=0; i operand) andl $255, %eax cmpl %eax, x sete %al andl $255, %eax # Logical AND constant to register movl %eax, z pushl y pushl x pushl z pushl $.LC0 call printf 14)Describe the four steps and final values where z = x = 1; and the statement "z = x++ - 1;" is executed. z = x = 1; z = x++ - 1; printf ("z = %d, x = %d\n", z,x); /* z = 0, x = 2 */ movl $1, x movl $1, z movl x, %eax decl %eax movl %eax, z incl x subl $4, %esp pushl x pushl z pushl $.LC1 call printf 15)Describe the five steps and final values where z = 0; x = 2; y = 1; and the statement "z += - x ++ + ++ y;" is executed. z = 0; x = 2; y = 1; z =+ - x ++ + ++ y; printf ("z = %d, x = %d, y = %d\n", z,x,y); /* z = 0, x = 3, y = 2 */ movl $0, z movl $2, x movl $1, y incl y movl x, %edx movl y, %eax subl %edx, %eax addl %eax, z incl x pushl y pushl x pushl z pushl $.LC0 call printf 16)Describe the five steps in; "while (n--) *p++ = *q++;" and explain why this control structure works for n or n+1. while (--n) printf ("%d\n", n); .L2: leal -4(%ebp), %eax decl (%eax) cmpl $0, -4(%ebp) jne .L4 jmp .L3 .L4: subl $8, %esp pushl -4(%ebp) pushl $.LC0 call printf addl $16, %esp jmp .L2 .L3: while (n--) printf ("%d\n", n); .L2: leal -4(%ebp), %eax decl (%eax) cmpl $-1, -4(%ebp) jne .L4 jmp .L3 .L4: subl $8, %esp pushl -4(%ebp) pushl $.LC0 call printf addl $16, %esp jmp .L2 .L3: Linux Kernel Development, 2nd ed. - Robert Love Chapter Two - Getting Started with the Kernel Omit)Define source tree (explaining why there are duplicated directory names) and describe the proper protocol of building a new kernel image. p. 12 2)Contrast our six OS model agents (NPS, FS, MM, PM, TM, & IPC) with the top level Linux directory names. Support or refute the idea of mapping the source tree tightly to an OS model. 3)Explain the kernel builders design decision with "tri-states." p. 13-14 Omit)Describe the following commands or files: make config, make menuconfig, make xconfig, make gconfig, make defconfig, .config, make oldconfig, make -j2 > /dev/null. P. 14-15 Omit)Describe distcc and ccache utilities and explain how these programs represent the "Unix philosophy" or something else. p.15 6)Describe the last two steps in kernel building. And explain why one adds a new kernel to the boot menu, but rarely deletes a kernel image. P. 16 7)Describe these special features of kernel development: No libc, in-line functions & assembly, & optimizer assistance. p. 16-19 8)Describe the physical versus logical memory layout of the kernel and user processes. Explain why kernel programming requires extra caution and explain how the kernel helps to overcome one of these difficulties. (oops, paging) p. 19 9)Give the tradeoff of using floating point arithmetic in the kernel. p. 19 10)Explain the role of context state saving, give two possible designs, and explain how the kernel stack is a scarce resource in the Unix design. p. 19-20 a)In a context switch the calling routine CPU registers, memory management registers, and other volatile registers are saved in the Per-Process Data Area (PPDA) pointed to by the process' entry in the Linux task array which has a record for each process. b)The PPDA is relatively large and the top portion is used as a kernel stack. Being fixed size, kernel programmers have to be careful that they do not push too many items on the stack, erasing the PPDA. c)Thus, a process can be suspended in the kernel and restarted, regardless of how many other processes execute, exactly where it left off by using its private kernel stack. d)Alternately, a kernel designer would have to manage a pool of stacks or manage one large stack with sections assigned to individual processes.