NAME________________________________________ e-mail
(netid)_________________
Prelim 2, 1:30
hours, Nov 30, 2000. Please write
e-mail address without “cornell.edu” on exam to receive your grade (exam and
potential final grade) by e-mail.
Memory subsystem and virtual memory:
Half of the
size of a page frame
In essence LRU
always replaces the page referenced furthest in the past. This scheme works well if the program
adheres to the locality of reference i.e., the accesses tend to be more from
the spatially and temporally nearby pages.
This algorithm is also the optimal strategy in reverse and if the past
is a good indication of the future this algorithm should work well. Further, the LRU algorithm does not suffer
from Belady’s anamoly.
The key disadvantage of LRU algorithm is that it needs a lot of book keeping on each memory access to be implemented exactly. After each access the time of the least recently used page must be tracked either using timestamps or counters. This is highly inefficient and requires sophisticated hardware support.
If FIFO is used there will be 11 pagefaults. The accesses would go like this. 3 page faults initially to have 5, 6, 9 in memory. Then 5 is replaced by 3, 6 by 5, 9 by 6. No page faults on 3 and 6. 3 is replaced by 9, 5 by 4, and 6 by 3. No page fault on 9. 9 is replaced by 6. No page fault on 4. 4 is replaced by 9. Total 11 pagefaults.
If LRU is used there will be 11 pagefaults. 3 pagefaults initially to have 5, 6, 9 in memory. Then 5 is replaced by 3, 6 by 5, 9 by 6. No page faults on 3 and 6. 5 is replaced by 9, 3 by 4, and 6 by 3. No page fault on 9. 4 is replaced by 6, 3 by 4 and no page fault on 9. Total 11 page faults.
If OPT is used there will be 7 pagefaults. 3 pagefaults initially to have 5, 6, 9 in memory. 9 is replaced by 3. No page faults on 5, 6, 3, and 6. 5 is replaced by 9, 6 by 4. No page faults on 3 and 9. 3 is replaced by 6. No page faults on 4 and 9. Total 7 page faults.
The working set of a process, W(D, t) is the set of pages accessed by the process from the current time t to D time units back. Where D is a pre-defined amount of time usually measured in terms of virtual time (actual CPU time of the process, number of instructions etc…)
Since the working set denotes the current locality of reference of the process, if we have a good estimate of D then it suffices to have the pages in the working set alone in the memory. This way we can minimize page faults. However, the difficulty comes in estimating the window D, which would give the correct locality of reference. Further this window is dynamic and could vary through the execution of the process. Alternate schemes such as page fault frequency manages the number of frames allocated to each process more efficiently.
IO systems
All memory
accesses of the CPU goes through a cache.
In this case, all the cache needs to do is to pre-fetch 1K words of data
upon the first memory access to that block of data. Once the cache completes its pre-fetch operation, the bus can be
granted to the DMA to complete its operation.
User does system call à
operating system à device controller and device à
interrupt handler à operating system à user
In questions 9-11, mark (a) TRUE (b) FALSE
Disk allocation/management and file systems:
In questions 13-17, mark (a) TRUE (b) FALSE
In questions 19-22, let there be 2 sectors in a track
and 4 tracks and a single surface in a disk.
Assume the following blocks are accessed by the file system; the notation
is 1-digit for block number, and 1 digit for operation (Read, Write,
or Append): 1A, 2A, 3A, 4A, 5A, 1R, 1W, 1R. Assume that all these blocks are accessed for the same file,
and that the file’s I-node is initially stored in track 0. Assume also that all operations immediately
go to disk (i.e., there is no buffering/cache in the system), that the head is
at track 0, and that the disk is initially empty. Also assume that the inode occupies the entire track 0 and that
each block consists of one sector.
(Remember that for small files, the LFS rewrites the entire file
contiguously upon each write (not append) to the disk.)
25, 5
3, 3
operations |
1a |
2a |
3a |
4a |
5a |
1r |
1w |
1r |
total |
|
|
LFS |
1 |
|
1 |
|
1 |
2 |
18 |
2 |
25 |
18
because to write out the entire file, each block has to be read individually
(since there is no buffering/cache) |
|
In-place |
1 |
|
1 |
|
1 |
2 |
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
LFS |
1 |
|
1 |
|
1 |
|
|
|
3 |
Note
that to write out the entire file, only 3 tracks are moved. All ops are done in memory before writing
the file. |
|
In-place |
1 |
|
1 |
|
1 |
|
|
|
3 |
|
The key operations in this case are appends and then a few random access reads and writes. We know that the indexed file system is pretty good for this case. The linked system is OK as long as we assume that only block 1 is going to be accessed but if any other block is read or written, the linked system is futile. The contiguous system is not good because of many append operations. The best data placement would be organ pipe placement with the index block closest to the disk head in the middle and block 1 as close to the disk head as possible.
Networking:
Physical layer: Consists of the actual communication medium such as optic fibres, cable, etc…
Data Link Layer: Takes care of getting the packets through
the physical medium. Also does error
correction, flow control and manages media access or channel access.
Network Layer: This layer is responsible for getting
messages from one end machine to another end machine. It has addresses associated with machines. Does routing, and fragmentation (in case it
has to split packets to go through
section of the route.)
The lower three layers usually
are implemented on a hardware called the network interface controller. Having the NIC to have a processor in it
makes it real smart and a number of operations such as error correction (CRC
check), calculating routes, processing headers, etc… can be done in hardware. Having a big cache to store the frequently
used routing information also helps a lot.
Having DMA access between the memory and the NIC is very useful. Physical media that can provide multicast
abilities is also very useful.
In questions 22-25, mark (a)
TRUE or (b) FALSE [2 pts each for questions 22-25]
|
Advantages |
Disadvantages |
Fully connected network |
22. Most reliable TRUE |
23. Highest communication costs FALSE |
Bus-based network |
24. Highest delays FALSE |
25. One failure will cripple the network TRUE |