|
|
|
|
The Operating System Machine (OSM) level is is a complete set of instructions available to application programmers. This includes all Instruction Set Architecture level instructions and a new set of instructions that the operating system adds called system calls. The OSM level is always interpreted. For instance, if reading data from file, the operating system carries it out step by step, in the same manner a microprogram would carry out an ADD instruction.
VIRTUAL MEMORY
Virtual memory is a technique provided by many operating systems to
make the machine appear to have more memory than it really does.
In the early days, memory was small and expensive. Some had just
1024 words. Additional memory was secondary, on disks. The
program was broken up into a number of overlays, each of which could
fit into memory. Programmers had to organize overlays sequentially
without any help from the computer. In 1961, in Manchester, England,
a method of processing overlays automatically was introduced. This
procedure is now called virtual
memory.
The Manchester group separated the address space and the memory locations. For example, suppose a computer has a 16-bit address field in its instructions and 4096 words of memory. A program can address 216 (65536) words of memory. The address space consists of the numbers 0, 1, 2, ..., 65535. At any instant, 4096 words of memory can be directly accessed, but they need not correspond to memory addresses 0 to 4095. So address 4096 could correspond to 0 and 8191 to 4095. Address space can be mapped into actual memory addresses.
If a 4K machine has to branch to an address between 8192 and 12287. Without virtual memory, an error ("Nonexistent memory referenced") would be caused. But with virtual memory, the contents of main memory would be saved on disk, words 8192 to 12287 located on disk would be loaded into main memory as memory locations 0 to 4095 and execution would continue. This technique of automatic overlaying is called paging and the chunks of program read in from disk are called pages.
Implementation of Paging
One essential requirement for a virtual memory is a disk to keep the whole program and all the data. The original should be kept up to date. The virtual address space is broken up into a number of equal-sized power of 2 pages ranging from 64K to 4M bytes. Each piece of main memory can also hold exactly one page. These pieces of main memory into which the pages go are called page frames.
The only thing a memory understands are main memory addresses, not virtual addresses, so that is what it must be given. Every computer with virtual memory has a device for doing the virtual-to-physical mapping, called MMU (Memory Management Unit). It may be on the CPU chip or on a separate chip that works closely with the CPU chip.
Demand Paging and the Working Set Model
There may not be enough room in main memory for all the virtual pages. When a reference is made to an address on a page not present in main memory, it is called a page fault. After a page fault has occurred, the operating system must read in the required page from the disk, enter its new physical memory location in the page table, and then repeat the instruction that caused the fault. If a program runs on a machine with virtual memory and not in main memory, then the page table must indicate that each and every virtual page is in secondary memory and not in main memory. When the CPU tries to fetch the first instruction, it gets a page fault causing the page to be loaded into memory and entered in the page table. This method of operating a virtual memory is called demand paging. (when the baby cries, feed it rather than on a precise schedule). In demand paging, pages are brought in only when an actual request for a page occurs, not in advance. But once it has been running, the needed pages would already have been collected in main memory.
Page replacement Policy
The set of pages that a program is actively and heavily using,
called the working set, can be kept in memory to reduce page faults.
But since programmers do not know the pages, this must be done dynamically.
When a program references a page that is not in main memory, the needed
page must be fetched from the disk. To make room for it, some other
page must be sent back to the disk. Choosing a page at random is
not a good idea. If that page is required next, another page fault
will occur. Operating systems try to predict which of the pages in
memory is the least useful. (Its absence will have the smallest adverse
effect in running the program). It must be able to predict
when the next reference to each page will occur, and remove the page whose
predicted next reference lies furthest in the future. Select one
that will not be needed for a long time.
Two methods of doing so are LRU (Least Recently Used) and FIFO
(First In First Out). If the working set is larger than the number
of available page frames, page faults will be frequent. This is called
thrashing.
Page Size and Fragmentation
If the program and data fill an integral number of pages, there will be no wasted space in memory. Otherwise there will be some unused space on the last page. If the program and data need 26,000 bytes with 4096 bytes per page, then six pages will account for 24,576 bytes ( 6 x 4096) and the seventh page will contain only 1424 bytes (26000 - 24576) wasting 2672 bytes (4096 - 1424) of space. Since the wasted space is internal to some pages, this is known as internal fragmentation. If the page size is n bytes, the average amount of space wasted on the last page is n/2 bytes. A small page size will reduce the wasted space but will increase the number of pages and lead to a large page table.
If the mean segment size is s words and the page size is p words. In addition to wastage on the last page of average p/2, s/p words are wasted as they form the page table (one word per entry). Total waste w = p/2 + s/p. To minimize it differentiate with respect to p and set it 0. dw/dp = 1/2 - s/p2 = 0. So pmin = square root of 2s.
VIRTUAL INSTRUCTIONS FOR PARALLEL PROCESSING
Some computations are programmed for two or more cooperating processes running in parallel (i.e., simultaneously, on different processors) rather than for a single process. Other computations can be divided into pieces, which can then be carried out in parallel to decrease the elapsed time required for total computation. For several processes to work together, certain virtual instructions are needed. Nothing can travel faster than light 186,000 miles per second or approximately 1 foot per nano second. If CPU needs data from main memory 1 foot away, it will take 2 nsec (1 for request to arrive at memory and 1 for reply to return to CPU). Rather than making smaller computers with cycle time of 0.001 nsec, it is easier to build a thousand 1-nsec CPUs and have the same capacity.
Race Conditions
Multithreading
Parallel processes have to communicate and synchronize to do their
work. Suppose two processes communicate via a shared buffer in main
memory. Process 1, the producer, computes prime numbers and
puts them in a buffer one at a time. Process 2, the consumer,
removes
them from the buffer one at a time and prints them. They run in parallel
at different rates. If the buffer is full, the producer goes to sleep
(temporarily suspend operations) while waiting for a signal from the consumer.
When the consumer removes a number, and the buffer is no longer full, it
sends a wakeup call to restart the producer. Similarly, if the buffer
is empty, the consumer goes to sleep woken by the producer when a number
is put into the buffer.
The buffer is circular. The pointer in points to the next free word (where the producer will put the next prime) and out points to the next number to be removed by the consumer. When in = out, the buffer is empty. The consumer goes to sleep. When the producer puts in a word, in - out = 1. The producer knows that the consumer is sleeping and so sends a wake up message. When out - in = 1, the buffer is full. The last word is not used. The producer goes to sleep. When the consumer takes out a word, out - in = 2. The consumer knows that the producer was sleeping and sends a wake up call.
The two processes run asynchronously and at different speeds. This could cause a serious problem. Suppose the consumer takes out the last number and increments out, causing both in and out to have the same value. After printing the number it checks the values of in and out. But before it can compare them, the producer puts a number in, increments in making in - out =1. Thinking that the consumer is sleeping, it sends a wake up call. The consumer not being asleep, ignores it. Now the consumer compares the number and finding them to be equal, goes to sleep. The producer puts in the next number, increments in so that in - out = 2. Producer assumes incorrectly that the consumer is up. Producer continues until the buffer is full and goes to sleep. Both are now sleeping. This problem is a race condition, as its success depends on who wins the race to test in and out after out is incremented. It is so serious after Java was introduced, Sun changed the Thread class and deprecated the suspend and resume calls because they led to race conditions so often.
Process Synchronization Using Semaphores
There are two ways to solve the race condition.
1. Each process has a "wakeup waiting bit." Whenever the process goes to sleep when the wakeup waiting bit is set, it is immediately restarted and the wakeup waiting bit is cleared. The wakeup waiting bit stores the superfluous wakeup signal for future use. This solves the race condition when there are only two processes, but fails in the general case of n communicating processes as n - 1 wakeups have to be saved.
| 2. Dijkstra proposed a more general solution using two nonnegative integer variables called semaphores. Two system calls that operate on semaphores up and down. Up adds 1 to a semaphore, and down subtracts 1 from a semaphore. If a down operation is performed on a semaphore that is greater than 0, the semaphore is decremented by 1 and the process doing the down continues. If the semaphore is 0, the down cannot complete; the process doing the down is put to sleep and remains asleep until the other process performs an up on that semaphore. The up instruction checks to see if the semaphore is 0. If it is and the other process is sleeping, the semaphore is increased by 1. The sleeping process then completes the down operation that suspended it, resetting the semaphore to 0, and both the processes continue. An up instruction on a nonzero semaphore increases it by 1. Semaphores store wakeups for future use, so that they will not be lost. Once a process has initiated an instruction on a semaphore, no other process may access the semaphore until the first one has either completed its instruction, or has been suspended trying to perform a down n a 0. Dijkstra |  |
|
|
|
|
| Up | Semaphore = semaphore + 1
if the other process was halted attempting to complete a down instruction on this semaphore, it may complete the down and continue running. |
Semaphore = semaphore + 1 |
| Down | Process halts until the other process ups this semaphore | Semaphore = semaphore - 1 |
|
|
|
|
|
|