Silbershatz/Galvin: Central Points Please use the class slides as the starting point. Here I give a rough set of related points. The fact that I have not outlined a set of points for a given subsection DOES NOT mean that the section is irrelevant. It only indicates lesser importance. Chap 1-4. All sections. ======================= Chap 1: ====== 1.1 - An operating system manages system resources and provides an environment, much like the government does for the economy - goals: efficiency, convenience, abstractions (multiprogramming etc) 1.2 - Simple batch systems read jobs in sequence from the card reader and output to printers - Using the disk as a buffer for both input and output improves efficiency since disk is faster. This is called spooling, and the disk data structure is called the job pool which can be accessed in a non-FIFO order, enabling basic multiprogramming. - Multiprogramming gives the user an illusion of multiple processes running simultaneously on a single CPU. - Using memory in addition to disk allows multiple processes to be loaded into memory, and the CPU can be held by single process for shorter time-slices. This allows greater efficiency in multiprogramming. - Choosing jobs to swap in/out of memory is called "job scheduling". Choosing jobs in/out of CPU is called CPU-scheduling (or short-term scheduling). 1.3 - Timesharing or multi-tasking means allowing "interactivity" in addition to multiprogramming. the primary issue is providing adequate reponse time while maintaining high system throughput. - Multi-user environment allows multiple users in the system. Primary issues include protection and sharing of resources among multiple users. Chap 2: ====== 2.1 - Modern computer systems consist of CPU, memory, I/O controllers connected by a system bus. This is the model used by an OS. - Operating systems are "interrupt-driven". An interrupt results in a call to an interrupt handler, which is like any other procedure except that the entire context of the current process must be saved. - System calls, which are interfaces between user processes and the kernel, are also implemented as hardware traps. In a hardware trap, the hardware provides support for saving a default subset of the state. - Interrupts can be disabled and enabled. - "process" is a program in execution 2.3.2 Disks - Important components of performance are seek time (huge), latency time(can be huge), and transfer time 2.5 Protection - Problem when multiple processes share resources or when multiple users exist in the system - Most errors detected by hardware and control passed to OS through interrupts, traps (which are synchronous with the currently running process) or OS signals (software interrupts) - Dual mode operation, base and limit registers (dual mode protection of memory), privileged instructions, CPU time-slices are all examples of support for protection. Chap 3: ====== 3.1.1 Process management - process is a program in execution, an active entity. - Process management tasks include creation, deletion, suspension, resumption of processes, and providing mechanisms for sychronization, communication and deadlock handling 3.1.2 Memory management - Involves OS management of virtual memory (software placement and replacement schemes), locking of pages and sharing the available physical memory pages among multiple processes. 3.1.2 File management - Logical storage unit - Operations: creation, deletion, manipulating files/directories, mapping files to secondary storage ... System structure: MS-DOS, UNIX, virtual machines, see class slides Chap 4: Processes 4.1-4.4 - "Job": batch processing term - "Task": interactive processing term - "Process": common term for programs in execution - Process state: new, ready, waiting, running and terminated (fig 4.1) - "Context switch": switching the CPU from one process to another (or the kernel). - Process control block: set of information which needs to be saved/restored upon a context-switch. Includes process state, hardware state (registers, program counter), OS resources (scheduling, memory management, files etc) - Scheduling: short-term (CPU-scheduling): which process in memory accesses the CPU long-term (job scheduling): which process gets into memory from disk - Process creation: fork() creates a duplicate of the process - execve(): loads another program into memory image of process - Termination: exit(): voluntary exit. May result in a wakeup of the parent (eg shell) abort(): kill another process. Only parents can kill children. - Cooperating processes: eg: the producer-consumer problem (p 101, sec 4.4) 4.5 Threads - Goal: to reduce context switch overhead. - Thread: share the code, data and several OS resources. Only own a program counter, reguster set and stack space... - Threads together form a "task" - User-level threads can be implemented as a bunch of library routines. - Several kernels are single-threaded (to avoid synchronization overhead/complexity) at the cost of inefficiency. - Solaris 2 offers an interesting implementation (sec 4.5.2) 4.6 Interprocess communication - Basic operations: Send/Receive - But need to deal with several other issues: - Naming: - direct: straightforward and does not involve creation of intermediaries -indirect: communication through "mailboxes". Can simply communication when parties dont necessarily know each other, or are dealing with large groups - Buffering & exceptions. - Zero buffering implies the need for a rendezvous and "synchronous" communications such as RPC (Remote procedure calls). - Bounded buffers implies delaying sender only if the buffer is full. If the sender is not delayed, one has to worry about buffer overflow, loss-recovery mechanisms like timeout/retransmission etc. - Unbounded buffers allow complete asynchronous communication Chap 5: Sections 5.1 to 5.3 5.1-5.2 - Process alternates between CPU bursts and I/O bursts - Operating system has to keep both the CPU and I/O channels busy - Short-term (CPU) and long-term (job) schedulers - Preemptive scheduling: process can be switched from the running state to the ready state. Has implications on synchronization esp in the kernel where several preemptible kernel threads may share sensitive data structures. - Nonpreemptive: process can only move from running state to the "waiting" state. Problem: Can be unfair in allocation, and does not control the worst case latency etc experienced. - Throughput and waiting time are key metrics in evaluating scheduling schemes 5.3 Schemes - The slides in class give a good summary of various schemes. - Work out some of the quantitative problems too Chap 8: Sections: 8.4 to 8.6 8.4: Memory allocation methods - Allocation is important as it determines what share of memory each process will get. Also it is important from the point of view of utilizing memory well itself. - Contiguous allocation can run into the problem of "external fragmentation" where there are gaps between allocated spaces which are wasted. - SOlution to external fragmentation is to do compaction, or go for fixed sized blocks/pages. - When a process outgrows its allocation, further overhead has to be incurred in relocating it. - "Internal fragmentation" refers to the space allocated but unused. Dynamic allocation (eg: the heap in the OS) can minimize it. In paged memory, the internal fragmentation can be as much as 1/2 of a page size. Smaller page sizes are desireable to minimize internal fragmentation. But larger page sizes are usually preferred to maximize spatial locality exploitation and minimizing overhead of loading/unloading pages. - Use base and limit registers to delimit user and kernel spaces. - A first fit allocation: find the first hole that is big enough - Best-fit: find the smallest hole that is big enough - worst-fit: find the largest hole that is big enough. - most operating systems implement first-fit allocation. First fit and best fit are known to be better than worst fit 8.5 Paging - Some of the same concepts we learnt in chap 7 in Patterson and Hennessey - Additional issues: multi-level page tables or inverted page tables to reduce the size of per-process table in memory. - multi-level page tables necessitate the efficient use of hardware support of TLB. - inverted page tables have entries per-physical page. But this structure makes sharing of pages among multiple processes tedious. - Examine the implementation of both inverted page tables and multi-level page tables given in this section... 8.6 Segmentation - Provides a convenient user-view of memory - In modern architectures segmentation is implemented on top of paging (the latter has hardware support) - In older architectures there was only segmentation (supported in hardware, eg the Intel architectures) or implemented paging on top of segmentation. - Implementation of segmentation: use of a base and limit values for each segment. Segmentation can be implemented over paging with hardware support (eg base and limit registers) or purely in software (eg in BSD Unix). - Protection etc is associated on a per-segment basis rather than on a per-page basis - Segmentation originally led to the problems of internal/external fragmentation and to the development of paging... Chap 9: Sections: 9.1, 9.2, 9.4, 9.5 (except 9.5.4.1 onwards), 9.6.3, and 9.7 9.1: - Overlays: load another program over parts of memory image of running programs. Used in MS-DOS due to limited memory. Usually controlled by programmer. - Virtual memory: removes memory management burden from programmer and also provides an illusion of a very large contiguous per-process memory. 9.2 Demand paging - Pages brought into memory only upon demand ("lazy swapping") 9.4 Page replacement - Use a dirty bit to optimize write-back ("copy-back") - UNIX even copies dirty, replaceable pages to other pages and allows the process to proceed while it writes-back asynchronously - Bringing in a working set of pages when a process is swapped in reduces overhead in demand paging 9.5 Page replacement algorithms - Reference string: string of actual memory references - FIFO algorithm: may exhibit belady's anamoly i.e. increasing the number of physical pages ("frames") does not necessarily lead to reduced page fault rate - Optimal algorithm: "replace the page that will not be used for the longest period of time". - LRU: approximates optimal algorithm due to locality of reference - LRU approximations can be implemented given a reference bit per page. 9.6.3 - Frame allocation can be global or local. Most operating systems use a global allocation strategy to optimize usage of memory resources. 9.7 Thrashing - Problem where the CPU spends more time on paging rather than doing productive work (i.e. executing processes) - Fig 9.14 shows the thrashing zone which gets created when degree of multiprogramming increases and CPU utilization plummets - A locality model can help identify which pages to keep in physical memory to avoid thrashing. - Example of a locality model is the "working set model". In the working set model, the operating system tracks the set of pages per process accessed in the last "delta" references ("delta" is a parameter). - If there is not enough space for the working set of current processes, then swap some process out & reduce the degree of multiprogramming - The page fault frequency method (keeping bounds on the page fault rate by increasing or decreasing the degree of multiprogramming) is a more direct way to deal with thrashing than the working set model. Chap 10: All sections except 10.5 ================================= - Files define logical storage units on non-volatile (secondary) devices. For a user, it is a collection of related information. - File may have several types based upon its structure. Some operating systems provide support for multiple file types while others (like UNIX) provide only a single file type (a stream of bytes) - File may have attributes (name, type, location, size, protection) and this "meta" information is usually stored in directories. - File operations: create, write, read, reposition, delete, truncate - other operations can be defined in terms of these primitive operations - The system usually maintains an open file table and passes an index (caled a "descriptor") to this table (or a per-process file table) to the process. - Files may be mapped to memory - A file may be accessed in two ways: sequential access and random (direct) access. In the latter mode, a block or a "record" in a file is directly accessed. 10.3 Directory structure - Simplest: Single level directory: cant support multiple users - Two-level directory: too monolithic even for a single user. New problem: how to share files among multiple users. - Tree structured directories: allows files of any user to be logically placed. Sharing of a single file in multiple directories or across users still a problem. Relative and absolute path names to be supported for convenience - Acyclic Graph: Allows sharing, logical placement and multi-user environment. Problem: what if some references to a file deleted -- possible dangling pointers 10.4 Protection - Controlled access operations: read, write, execute, list, append, delete - Best: access control lists. List set of user ids allowed for each file operation. Problem: too much information. UNIX approximation: user, group & universe permissions for read/write/execute - Other approaches: passwords for subtrees in the hierarchy Chap 11: all sections except 11.6 ================================= 11.2 Allocation methods - Contiguous allocation: very similar issues to contigous memory allocation for segments. Advantage: quick sequential access. problem: External and internal fragmentation. Down time required for compaction. - Linked allocation: File is a linked list of disk blocks Good: solves external and internal fragmentation problems Problem: Random access requires multiple disk accesses. Overhead per block for pointer. If any pointer gets corrupted, the file cannot be completely accessed. - MS-DOS implements a linked-list in a table known as the FAT - The index in the table refers to a block address, and the table entry refers to the next index in the table. Since the FAT is stored in memory, random access is speeded up. - Indexed allocation: Store block pointers in an index block (or set of index blocks). Eg: UNIX uses an "inode" which has both direct, single-indirect, double-indirect amd triple-indirect blocks.