# Introduction An operating system (OS) is a collection of software that provides an abstract machine on top of a physical machine. The OS provides resource management. An OS makes a computer easier to use for end users and programmers. Typical services provided by an OS includes storage/file systems, process/thread management, security and communications. # Processes A process is an instance of a computer program that is being executed. It contains the progam code and its current memory state. A CPU can execute a single process at a time. Multiprogramming is a way for CPUs to fake concurrency by switching between different processes, often quickly. The Scheduler, using a schelduling algorithm, decides which process gets to use a CPU at any given time. ## Scheduling Scheduling algorithms should be fair and balanced. For batch systems, the goal is to maximize process throughput, minimize turnaround time, and maximize CPU utilization. For interactive systems, the goal is to minimize response time, and ensure proportionality in latency (meeting the user's expectations). For real time systems, the goal is to meet deadlines and behave predictably. A scheduling algorithm can either be preemptive or non-preemptive. A non-preemptive lets active processes decide when they are done using the CPU, while a preemptive algorithm can decide to switch processes at any time. ### Scheduling Algorithms in Batch Systems || First-Come First-Served || Non-preemptive. Active processes are run to completion or blockage. New or unblocked processes are put in the ready queue. Maximizes CPU usage. || || Shortest Job First || Non-preemptive. Uses statistics to make educated guesses about run-time of processes. The ready queue is a priority queue prioritizing the shortest jobs first. Minimizes turnaround. || || Shortest Remaining Time Next || Preemptive. Like Shortest Job First, except a new process may take the place of the active process if its remaining time is lower than that of the active process. || ### Scheduling Algorithms in Interactive Systems ||Round-Robin Scheduling||Preemptive. Each process is assigned a time interval, or quantum. Processes that run longer than quantum are switched. Switching also occurs when the actuve process becomes blocked, or terminates. The quantum time must be tweaked to allow the best balance of response time and CPU utilization.|| ||Priority Scheduling||Preemptive. Processes are given a priority score, assigned statically or dynamically. The ready queue is a prority queue on process priority. May use quantums.|| ||Shortest Process Next||Preemptive. Estimates which process is shortest, and prioritizes accordingly.|| ||Guaranteed Scheduling||Preemptive. When there are n processes, each process gets 1/n CPU cycles.|| ||Lottery Scheduling||Preemptive. Prioritize processes at (optionally weighted) random.|| ### Scheduling Algorithms in Real Time Systems TBD. # Memory Management The essential requirement of memory management is to provide a memory abstraction which allows dynamically allocating portions of memory to a process. This section details different memory management strategies. ## No Memory Abstraction The entire memory is addressable by every process. Usually a complete disaster when multiprogramming is involved. ## Address Spaces A process is given a private address space, which is a private area of memory denoted by a base address and a size limit. Processes use relative addresses which are translated to absolute addresses by the OS. ## Swapping Swapping dumps a non-running process' address space to disk to free up memory when the system runs out of space. Swapping takes time. ## Virtual Memory To decrease swaping times, address spaces are split into chunks called pages. Each page can then be swapped independantly, even while the process is running. When a page which is not in memory is requested, it gets loaded in on-the fly. This is called a page fault. ## Physical Representation Physically, memory structures are usually stored in a tree-like hierarchy, with pointers to the next nodes. ## Page Replacement Algorithms ### Not Recently Used (NRU) Pages are given two flags: referenced and modified. Each time a page is read from, the referenced flag is set. Each time a page is written to, the modified flag is set. Every now and then (e.g. every 20 msec), a clock signal triggers the resetting of the referenced flag. Based on these flags, we can classify the pages at any given time in one of four classes: ||Class 0 || Not referenced, not modified.|| ||Class 1 || Not referenced, modified.|| ||Class 2 || Referenced, not modified.|| ||Class 3 || Referenced, modified.|| NRU swaps out a random page from the lowest-numbered non-empty class. ### First-In, First-Out (FIFO) Oldest page gets swapped out first. ### Least Recently Used (LRU) Swaps out the page which has remained unused for the longest time. ### WSClock Combination of the Working Set and Clock algorithms. We regard the memory as an initially-empty cirular list of frames, and maintain a pointer to a single frame ("current page"). Each page has a referenced flag and a modified flag, as well as a time of last use field. Again, eventual clock ticks reset the referenced flag. The algorithm: t = some constant, e.g. 120 msec On page fault: if current page is referenced: set current page as not referened set current page to next page restart procedure else:

if current page is modified: schedule disk write for current page set current page to next page restart procedure else: swap out current page Additionally, we must consider the case where the current page pointer completes one entire circle in the circular list of frames. In the case where at least one write has been scheduled, the algorithm simply continues until the write is complete, at which point the newly-written page will be ready for eviction. On the other hand, if no writes have been scheduled, the first non-modified page will be swapped out. If there are no non-modified pages, the current page gets swapped out. # File systems A file system is an abstraction to store, retrieve and update a set of files. A file is a logical unit of information created by a process. Information stored in a file is persistent, and can be accessed by different processes. ## File Structure There are many different ways to logically structure a file. Here is a list of three common structures: || Byte sequence || Maximum flexibility. The OS does not help, and does not get in the way. UNIX, MS-DOS and Windows uses this. || || Record sequence || Crap. Reads and writes entire fixed-size records at once. Old, punch card-based systems used this, but it is really unpopular now. || || Tree || Tree of variable size records, allows quick lookup on a specific key. Some mainframes use this. File Types || Operating systems often support different file types. Here are some common file types: || Regular files || Good ol' regular binary files. || || Directories || System files for maintaining the structure of the file system. || || Character special files || IO-devices masquerading as byte-sequenced files to abstract writing and reading to and from IO devices. || || Block special files || IO-devices masquerading as record-sequenced files to abstract writing and reading to and from IO devices. || ## Directories A file system usually organizes its files in some sort of directory organization. Here are some different ways to organize files: || Single-Level Directory Systems || Every file is in one large root directory. Often used on simple embedded devices. || || Hierarchical Directory Systems || Allows directories to contain other directories, creating a directory tree. Tree directory systems allow for sane organization of files. || ## File System Layout A file system is typically stored on a partition on a disk. Every partition starts with a boot block, but other than that, layout on disk can vary wildly from file system to file system. Boot block File allocation table Root directory File data area Figure 1: layout of the FAT-16 file system As an example, figure 1 shows the layout of the FAT-16 file system, a basic hierarchical file system. Here, the boot block contains administrative data about the file system, in addition to the bootstrapping program which is run if an operating system attempts to boot the partition. The file allocation table (FAT) contains a list of all the clusters/chunks in the file data area, together with a pointer to the next cluster for each cluster. The root directory is the statically allocated logical root of the file system, containing files and subdirectories. The file data area contains the rest of the data, organized in clusters as referenced from the file allocation table. # IO # Deadlocks A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. Four conditions must hold for there to be a deadlock: || Mutual exclusion || A resource can only be assigned to one or no process at once. || || Hold and wait || Processes currently holding resources can request more resources. || || No preemption || Processes cannot lose a resource against its will. || || Circular wait || There must be a circular chain of two or more processes, each waiting for a resource held by the next member of the chain. || Deadlock prevention can be done by preventing one or more of the four conditions above. Removing a deadlock after it has occurred usually entails killing processes, or doing resource rollbacks.