Data to Information Spring 2001
Operating System Architecture
Midterm Exam
Brook Hatch
Introduction
In the annals of history, no area of knowledge has changed as rapidly, nor has changed human civilization as dramatically, as computer technology. In the industrialized segment of the planet, nearly every human being has moved beyond remarking upon the novelty of ever-present computers to being nearly unconscious of them. The material computers are made of would be just so much inert junk if it were not for the instructions executed by the machines. The most important of these instructions is the Operating System (OS). The OS facilitates communication between different components, between processes, and between users. A brief survey of the history of the OS will provide, you, the reader an understanding of the some of the fundamental principles of current computer technology. This paper covers the era of plugboards, monoprogramming, multiprogramming, timesharing, and client server.
Plugboards
Computers have been with us since the abacus, but it wasn’t until recently that computers have become general purpose. Fundamental the architecture of most modern computers is a concept introduced by John von Neumann, a mathematician born in Budapest and instrumental in the development of the first atom bomb. Von Neumann's proposal consisted of two central elements: a Universal Computer and a Universal Constructor. The Universal Computer contains a program that directs the behavior of the Universal Constructor. The Universal Constructor, in turn, is used to manufacture both another Universal Computer and a Universal Constructor. Once finished, the newly manufactured Universal Computer was programmed by copying the program contained in the original Universal Computer, and program execution would then begin. This is also called a bootstrap technique. It is this technique to which we refer when we say that a computer it “booting up.” 
Plugboard systems used punch cards were fed into card readers. One program was executed at a time. The programmer loaded the program manually. All programs were written at this time in machine code. Programs grew in complexity and the need for storing these instruction sets in a quickly accessible format  arose. Magnetic memory core was invented to address this problem. Instructions that would be used repeatedly were stored in the machine for future use.
The computing machines of this era were made of vacuum tubes until circuitry was developed.

Batch systems – Monoprogramming

FORTRAN and COBOL were introduced. FORTRAN (formula translation) was developed to abstract the details of machine language, allowing the computer to do the dirty work. Human operators made many mistakes where computers made few. Programs were coded and executed faster. Yet when the CPU was executing, the I/O devices sat idle and vice versa.
A typical program running operation involved a programmer punching cards in both Job Control Language (JCL) and Fortran – JCL told the card reader what to expect, FORTRAN was the actual program intended to run. The card reader translated the punched patter into zeroes and ones, recording it onto tape. The tape was ten loaded onto a number cruncher, the result went on the tape. The tape mounted on another computer for printing. 
Application code must be assembled before is usable by the machine. Part of this process is linking and loading. Library functions are linked at compile time to produce an executable. Static linking and loading takes up a lot of room on disk. Common libraries are duplicated for many users.
Dynamic linking means that the executable doesn't actually contain the library code, but rather library calls are translated into instructions that jump to a linkage table. The entry causes a trap -- allowing the operating system to figure out where the library routine is and to replace that entry with the actual address. Next time the function is called, it doesn't cause a trap. This also allows library code to be shared. Microsoft popularized this technique in Windows using dynamic link libraries (DLLs), but that was much later.

Multiprogramming
As the corporate sector jumped into data processing, a more complex operating system was necessary to meet new demands. IBM supplied two versions of operating systems: 
MFT, Multiprogramming with a Fixed number of Tasks for smaller computers. also known as Fixed Partition Multiprogramming. Main storage is divided into a number of fixed-size blocks, each of which may be of different size, in order to permit multiprogramming. Each partition holds a single job, and the CPU switches rapidly between users to create the illusion of simultaneity. Jobs are translated with absolute assemblers and compilers to run in specific partition. If a partition is occupied, the job has to wait even if other partitions are free. Two boundary registers for every partition permit operating system and interprocess protection.
MVT, Multiprogramming with a Variable number of Tasks theoretically allowed any number of tasks to be performed concurrently. Because of the added function, more real storage was required : 64KB for MFT and 128KB for MVT. Several jobs were able to be run concurrently. Control was passed from one job to another whenever the first became idle waiting for I/O. By balancing between I/O-bound jobs and CPU-bound jobs a greater efficiency was achieved. 
Efficiency came by the price of complexity. It was now necessary to implement a process table (process states – running and blocked). The record in a process table consisting of a process’s address space and its registers, among other things was called a core image after the large magnetic main memory cores in older model computers.
Spooling was the method designed to allow multiprogramming. By separating the number crunching and the I/O inside one machine, disk and tape data could be read into unused memory partitions while the CPU was busy performing calculations on the data in another partition.
It was necessary to build memory management systems. Caching and virtual memory were ways of maximizing the flow of data through the system. 
Cache Organization
There are at least three ways of organizing a cache memory, each with its own performance:cost tradeoff (i.e., direct-mapped, associative mapped and set associative mapped cache). 
Associative mapping appears to be insensitive or not so sensitive to whether the memory references follow the locality principle. In associative mapping, any memory block can be mapped to any cache line. Given a memory address the least significant bit is used to index the byte within a block, and the rest is used as the tag.
Cache memory provides system designers with a way of exploiting high-speed processors without incurring the cost of large high-speed memory systems. The word cache is derived from the French word meaning hidden. Cache memory is hidden from the programmer and appears as part of the system's memory space. There is nothing mysterious about cache memory. It is simply a quantity of very high-speed memory that can be accessed rapidly by the processor. The element of magic comes from the ability of systems with cache memory to employ a tiny amount of high-speed memory (e.g., 128K bytes of cache memory in a system with 8 Mbytes of DRAM) and expect the processor to make over 95% of its accesses to the cache rather than to the slower DRAM. 
Cache memory can be understood in everyday terms by its analogy with a diary or notebook used to record telephone numbers. A telephone directory contains hundreds of thousands of telephone numbers and nobody carries a telephone directory around with them. However most people have a diary or a note book with a hundred or so telephone numbers that they keep with them. Although the fraction of all possible telephone numbers in someone's notebook might be less than 0.01%, the probability that their next call will be to a number in the notebook is very high. Why? Because people tend to phone friends and colleagues very frequently.
Cache memory operates on exactly the same principle at the note book by locating frequently accessed information in the cache memory rather than in the much slower main memory. Unfortunately, unlike the personal notebook, the computer cannot know, a priori, what data is most likely to be accessed. Computer caches operate on a learning principle. By experience they learn what data is most frequently used and then transfer it to the cache.
The general structure of a cache memory is as follows. A block of cache memory sits on the processor's address and data buses in parallel with the much larger main memory. Note that the implication of parallel in the previous sentence is that data in the cache is also maintained in the main memory. To return to the analogy with the telephone notebook, writing a friend's number in the notebook does not delete their number in the directory.
Cache memory relies on the same principle as the notebook with telephone numbers. The probability of accessing the next item of data in memory is not simply a random function. Because of the nature of programs and their attendant data structures, the data required by a processor is often highly clustered throughout memory. This aspect of memories is called the locality of reference and makes the use of cache memory possible (it is of course the same principle that underlies virtual memory).
A cache memory requires a cache controller to determine whether or not the data currently being accessed by the CPU resides in the cache or whether it must be obtained from the main memory. When the current address is applied to the cache controller, the controller returns a signal called hit, which is asserted if the data is currently in the cache. Before we look at how cache memories are organized, we will demonstrate their effect on a system's performance.
The principal parameter of a cache system is its hit ratio, that defines the ratio of hits to all accesses. The hit ratio is determined by statistical observations of the operation of a real system and cannot readily be calculated. Furthermore, the hit ratio is dependent on the actual nature of the programs being executed. It is possible to have some programs with very high hit ratios and others with very low hit ratios. Fortunately, the effect of locality of reference usually means that the hit ratio is often in the region of 98%. Before calculating the effect of a cache memory on a processor's performance, we need to introduce some terms.
Direct-Mapped Cache
The simplest way of organizing a cache memory employs direct mapping which relies on a simple algorithm to map data block from the main memory into a data block in the cache. For the purpose of this section we will regard the smallest unit of data held in a cache as a slot (i.e., block) which is made up of typically two or four consecutive words.
The advantage of the directly mapped cache is almost self-evident. Both the cache memory and the cache tag RAM are widely available devices that, apart from their speed, are no more complex that any other mainstream integrated circuit. Moreover, the direct mapped cache requires no complex line replacement algorithm. If line x in set y is accessed and a miss takes place, line x from set y in the main store is loaded into the frame for line x in the cache memory. That is, there is no decision concerning which line from the cache is to be rejected when a new line is to be loaded.
Another important advantage of direct mapped cache is its inherent parallelism. Since the cache memory holding the data and the cache tag RAM are entirely independent, they can both be accessed simultaneously. Once the tag has been matched and a hit has occurred, the data from the cache will also be valid (assuming the two cache data and cache tag memories have approximately equal access times).
The disadvantage of direct mapped cache is almost a corollary of its advantage. A cache with n lines has one restriction—at any instant it can hold only one line numbered x. What it cannot do is hold a line x from set p and a line x from set q. This restriction exists because there is one page frame in the cache for each of the possible lines. 
Suppose a cache is almost empty and most of its frames have not yet been loaded with active data. However, lines may have to be swapped in and out of the cache frequently because several lines in the main store just happen to share the same line numbers. In spite of these objections to direct mapped cache, it is very popular because of its low cost of implementation and high speed. 
Associative Mapped Cache
An excellent way of organizing a cache memory that overcomes the limitations of direct mapped cache is described in Figure 4. Ideally, we would like a cache that places no restrictions on what data it can contain. The associative cache is such a memory.
An address from the processor is divided into three fields: the tag, the line and the word. Like the direct mapped cache, the smallest unit of data transferred into and out of the cache is the line. Unlike the direct-mapped cache, there is no predetermined relationship between the location of lines in the cache and lines in the main memory. Line p in the memory can be put in line q in the cache with no restrictions on the values of p and q. Consider a system with 1 Mbyte of main store and 64 Kbytes of associatively mapped cache. If the size of a line is four 32-bit words (i.e., 16 bytes), the main memory is composed of 220/16 = 64K lines and the cache is composed of 216/16 = 4096 lines. Because an associative cache permits any line in the main store to be loaded into one of its page frames, line i in the associative cache can be loaded with any one of the 64K possible lines in the main store. Therefore, line i requires a 16-bit tag to uniquely label it as being associated with line i from the main store.
When the processor generates an address, the word bits select a word location in both the main memory and the cache. The line address from the processor can't be used to address a line in the cache (unlike the direct-mapped cache memory). Why? Because the direct-mapped cache reserves each line in the cache for one of a set of possible lines in the main store (the tag resolves which of the lines is actually present). As the associative cache can store any of the 64K memory lines in one of its page frames, it requires a 16-bit tag (assuming that there are 216 possible lines in the main memory) for each of its page frames. More importantly, as the cache's page frames (i.e., lines) are not ordered, the tags are not ordered and cannot be stored in a simple look up table like the direct mapped cache. In other words, when the CPU accesses line i, it may be anywhere in the cache or it may not be in the cache.
Associative cache systems employ a special type of memory called associative memory. An associative memory has an n-bit input but not necessarily 2n unique internal locations. The n-bit address input is a tag that is matched with a tag field in each of its locations simultaneously. If the input tag matches a stored tag, the data associated with that location is output. Otherwise the associative memory produces a miss output. An associative memory is not addressed in the same way that a computer's main store is addressed. Conventional computer memory requires the explicit address of a location, whereas an associative memory is accessed by asking, "Do you have this item stored somewhere?"
Associative cache memories are efficient because they place no restriction on the data they hold. In figure 6 the tag that specifies the line currently being accessed is matched against the tag of each entry in the cache simultaneously. In other words, all locations are accessed at once. Unfortunately, small associative memories are very expensive and large associative memories don't exist. Moreover, once the associative cache is full, a new line can be brought in only by overwriting an existing line. As in the case of virtual memories, cache memories must use some page (i.e., line) replacement policy. 
Fully associative cache memories are not practical because of their high cost. However, most computers employ an arrangement that is a compromise between direct-mapped caches and fully associative caches. This compromise system is called a set associative cache.
A set associative cache memory nothing more than several direct-mapped caches operated in parallel. The simplest arrangement is called a 2-way set associative cache and consists of two direct-mapped cache memories. Each line in the cache system is duplicated; for example there are two line 5s in the cache. Consequently, it is now possible to store two line 5s, one line 5 from set x and one line 5 from set y. 
Relocation 
Different jobs will be run at different addresses. When a  program is linked, the linker must know at what address the program will begin in memory. Instructions must not overwrite each other, so protection is necessary. This happened initially in the form of two special hardware registers, called the base and limit registers. The start address was loaded into the base register and the length was stored in the limit register. These registers were protected from user programs.
Supervisor mode instructions were designed to address this need for protection. The portion of the instructions that make up the OS are said to run in kernel mode. Kernel mode is generally protected from the user. It is the core of the OS and provides an abstraction layer.
Timesharing – Multics to UNIX

Beyond third generation - maybe fourth generation - the IBM system 370 with its virtual storage: The program is loaded onto a direct-access storage device, usually a disk, and divided into small segments called pages. Each page is loaded as needed into internal memory (real storage) onto "page frames" (paging in). When it finishes executing, the program is paged back out to the disk (virtual storage). In this way, programs may be larger than the internal memory. Many more programs can be executed simultaneously with very little of real storage wasted.
Paging is also called swapping and it brought with it the problem of fragmentation. As a system runs, its large blocks of free memory are inexorably filled up and what remains are small, fragmented memory areas insufficiently large to hold a large program. Free space management approaches are as follows.
•	Working set  - when a process loaded from disk to main memory, the process causes page faults. The working set model is designed to reduce the page fault rate by loading pages before letting processes run. This is also called prepaging. 
•	Demand paging – Pages are loaded only on demand, not in advance
•	Least Recently Used Page Replacement Algorithm(LRU) – Pages that have not been used for a long time will probably remain unused. When a page fault occurs, throw out the page that has been unused for the longest time.
Page table – page table contains indexed page numbers – it links up page frames to virtual pages.
Networking & client/server
The mass production of cheap, powerful personal computers has brought forth a new generation of computing. One of the byproducts is the Load Module – in UNIX, the kernel contains the drivers for I/O devices, but with PCs, a great plethora of possible drivers emerged. A modular peripheral driver system was developed. Modules can be loaded into the kernel while the system is running.  
 Summary
In the annals of history, no area of knowledge has changed as rapidly, nor has changed human civilization as dramatically, as computer technology. In the industrialized segment of the planet, nearly every human being has moved beyond remarking upon the novelty of ever-present computers to being nearly unconscious of them. The material computers are made of would be just so much inert junk if it were not for the instructions executed by the machines. The most important of these instructions is the Operating System (OS). The OS facilitates communication between different components, between processes, and between users. OS architecture has moved from plugboards, monoprogramming, multiprogramming, timesharing, and finally to client/server.