Basically, the operating system is the interface between the computer and the user. It is machine-dependent, and it can be implemented with any of number of features. This lecture talks about its fundamental components.
To me, this slide makes the most sense when included with the slides in lecture 18. A compiler is not an operating system, but it can be considered part of the operating system. When you're working on a UNIX operating system, you expect to be able to compile C programs. That expectation is met, because the system includes several C compilers. On the other hand, if you have a Macintosh, you need to find a C compiler and install it on your system.
When a compiler produces an object module, all the addresses in the code are relative to the beginning of the module. Some addresses may be 'external.' For example, if you've used library functions in your code, the addresses of those functions won't be known at this point.
The linker concatenates all the object modules into a single file. The addresses must be 'relocated' to reflect a new start address. At this point, external addresses are 'resolved.' At this point, you have all the code in one file for your program. All the addresses are relative to the beginning.
The loader executes the final step in the preparation of the program. All the addresses get actual numbers (like TOY code.) At this point, you can run the program.
An interrupt is a signal from the computer to the operating system. One type of interrupt is the clock interrupt, which helps the operating system keep track of time. There are also interrupts related to I/O (input/output). For example, if you want to read a file from a floppy disk, the operating system will communicate with the disk drive to start the operation. Then, the operating system waits for an interrupt from the disk driver, signalling that the operation is complete. While it waits, the operating system can do other useful work, instead of just idly waiting.
While only one program at a time is actually running, the operating system can simulate many different programs running at the same time by switching between them. The operating system is one of the programs running on your computer. When it's running, no other programs can run. Clock interrupts are useful for switching. After a specified amount of time, the interrupt signals the OS. The 'context' of the current running program (program counter, register values, stack pointer, etc.) is saved, control switches to the OS. The OS 'handles' the interrupt: in the case of a clock interrupt, which signals 'time-up' for the running process, the OS will choose which process to run next, load its context, and start the process running. (A process is basically a running program: it has 'state' information associated with it, such as the PC, registers, and a process stack.)
Relocatable and Reentrant programs are a special type: the OS must support them if they are to operate as expected.
A disk (floppy or hard disk) is storage for information. In order to access this information efficiently, the operating system can provide an abstraction. This abstraction makes the user think that he/she is accessing files, instead of just a stream of bytes. The operating system keeps track of which bytes on the disk correspond to a particular file or directory.
The UNIX operating system divides disks into the following sections:
Superblock: The first block (a block is just a fixed number of bytes) contains layout information about the rest of the disk. Since different disks will have different sizes, this superblock helps the operating system keep track of the location of data on the disk.
I-nodes: I talked about these in precept. Basically, an i-node is a list of pointers to the data of a file. The first part of an i-node is a fixed-sized chunk of information about the size of the file, modification/ creation dates, protection flags, etc. The rest of the i-node is just a series of pointers to data blocks. For larger files, indirect pointers are also necessary. Indirect pointers point to other i-nodes instead of to data blocks. To access these blocks of data, two pointers must be followed. Really big files may have several levels of indirection.
Data blocks: This is where the content of the files and directories is stored. Directory data consists of a table of file names and their corresponding i-node addresses. The data in a file may be one of many types, depending on what kind of file it is.
The total structure of i-nodes, pointers, and data blocks has a tree-like structure. The data blocks are the leaves. The superblock is the root of the tree.
Like many things we've learned this semester, drawing pictures can help you visualize the layout of the files and what the numbers refer to.
Here's what you need to keep track of when you're solving file-size problems. You need to know how big a data block is and how many there are. You could be given the total size and then have to figure out how many there are. (With any of these problems, you will be given some of the information, enough to figure out the missing information, just like any simple word problem.) Also, you need to know how much space is used for 'accounting info' in each i-node. Subtract this amount from the size of a data block. The remaining space is the amount you have available for pointers to data blocks or other i-nodes. Now, you also need to know whether all the pointers are 'direct' (pointing to data blocks), or whether some of the pointers are 'indirect' (pointing to another i-node.) In either case, you can figure out the number of pointers by dividing the space available for them by the size of the pointers. How do you know the size of the pointers? If you know how many data blocks there are, you know how big the addresses must be. For example, if you have 2^16 data blocks, an address referencing a data block needs to be 16 bits, or 2 bytes long. (Be careful about the units: 8 bits = 1 byte.) Divide the address space in the i-node by the size of the address to figure out how many pointers the i-node can hold. If all the pointers are direct, simply multiply the number of pointers by the size of a data block to find the maximum file size. For indirect pointers, more multiplication is necessary.
Another question you could ask, with the same given information, is which pointer in the i-node points to the 300th byte of the file, for instance. Again, drawing a picture will help you figure out this type of thing.
Also notice the block-size dilemma. Since the blocks are fixed size, you need to determine what the best fixed size is. This is a problem that comes up whenever you decide to use a system based on fixed-size blocks of memory (or time...) For example, in multi-processing, we talked about each process getting a fixed size 'turn' running. If this turn is too long, processes have to wait longer to get their time. If it's too short, too much time is spent switching back and forth between processes. These types of decisions are important in the study of operating systems.
Virtual memory is used by many operating systems now. Since reading and writing from/to disks is slow in comparison to reading/writing from main memory, operating systems require that running programs be in memory. When programs are all small, main memory can be split among them (problem 1.) However, sometimes a program needs more than its share or even more than is available in all of memory. Unless several programs are in main memory, we lose the advantages of multiprogramming.
A system of overlays was developed. The whole program was divided into a number of pieces, called overlays, which were stored on disk until needed. Each overlay could fit in memory and was brought in to memory as needed. When the program portion on the current overlay finished running, it called the next overlay. This technique is a solution to our problem; however, the programmer is given the responsibility of memory management, which is certainly not convenient.
Virtual memory is a system that gives the operating system the responsibility of managing the memory. It is based on the overlay system. The next slide describes the details of the system.
Physical address space is the actual main memory. Programs must be in physical memory in order to run.
Virtual address space is where programs 'think' they are. Addresses in programs use virtual addresses. Since virtual address space is larger than physical address space, more than one virtual address maps to the same physical address. The operating system keeps track of whether the data referenced by the virutal address is valid for that program.
Memory is divided into fixed size units called pages. A memory map (page table) relates virtual addresses to physical pages. With this system, pages can be allocated to processes as needed or according to some memory allocation algorithm. When there are no available pages in physical memory, one of the pages must be evicted: copied back (if it was changed) to secondary storage (disk, usually.) The strategy used by the operating system is referred to as its 'page replacement strategy.'
Memory hierarchy refers to the levels of storage. The slowest, cheapest memory is secondary storage, like CDs and disks. Main memory is more expensive and usually volatile: when you turn the computer off, the data is lost.
A cache is a small portion of memory that has extremely fast access time. Storing frequently accessed data here can greatly improve performance. As a slight digression, let me briefly discuss web browser cache. If you have a web browser like Netscape or Internet Explorer, one of your preference options is the cache size. The browser 'caches' the most recently or most frequently accessed pages. Normally, a web browser sends a request to a server for a particular page. If that page is in the cache, the web browser just loads the page from your computer's memory, which is much faster than sending a request over a network for the page. You can adjust the cache size according to your usage patterns. How to use a cache for memory management is a decision made by the operating system designer.
This issue relates closely to data block size decisions for file system management. There are always trade-offs. If you take the Operating Systems course later on in this department, you'll look more closely at these issues. The page of illustrations that follows this slide is a great illustration of the file system and virtual memory system in the lecture. Make sure you understand it!
We talked about the client-server model when we were working on the Rational Numbers programming assignment. Basically, a server is a system which 'infinitely loops,' waiting for requests. At review sessions, a TA acts like a server. I just stand up at the board waiting for 'requests.' I then process the requests in the order I receive them and return to the initial 'waiting' state. In this example, all the students who attend the review session are clients. They want to 'use' the server to accomplish some job for them. In this case, the 'job' the client wants done is an explanation of a particular topic. In this slide, the idea of the server being an interface between the client program and the display hardware is mentioned. You can think of the chalkboard as being the display hardware in our review session example. This is a model you will see over and over again in computer science.
A distributed system is one which is spread out over many computers. Ideally, the computing power of all the computers is combined, and a user of the system is unaware of which computer is actually doing the work. A client-server system is a good model for a distributed system because of its simplicity.