ENEE350H - Fall, 2004

Homework 6

(Due in class on Tuesday, November 23)

1.   You are using a 1 GHz system with paged virtual memory for doing a real-time application.  No other application is running on the system. A real time application is one where each task must be finished within a guaranteed time bound.  In this particular real-time application, there are many tasks; each runs the exact same code but with different data each time.   Each real-time task reads 100 bytes from an I/O device, performs some processing on it, and writes the data back to the I/O device.  I/O reads or writes are performed at 20 MB/sec.  Processing 100 bytes takes 10,000 cycles, which includes a total of 10 loads and stores.  These loads and stores can access anywhere in virtual memory.  The system transfers control to another task with an overhead of 1000 cycles.

Every memory access takes 25 ns and every disk page transfer from the virtual memory swap space takes up to 2 ms.  In the worst case a load or store could require 4 memory accesses and 2 disk transfers.  How many real-time tasks can be guaranteed to run on this system per second in the worst case?  (Assume the worst-case virtual memory behavior)

2.  Suppose you have a operating system that uses segmentation on a computer with 1M of physical memory.  A series of programs are executed on this computer, performing the following series of allocations and deallocations:


            allocate Block A: 512k

            allocate Block B: 256k

            allocate Block C: 64k

            free      Block B

            allocate Block D: 186k

            allocate Block E: 190k


(a)  What is the biggest hole size in physical memory at the end of the above sequence if first-fit is used?


(b)  What is the biggest hole size in physical memory at the end of the above sequence if best-fit is used?


(c)  What type of fragmentation does this computer suffer from: external or internal?


For parts (d) and (e), suppose that the operating system pages the segments so that each segment is comprised of 4k pages.  The allocations and deallocations work as before.


(d)  In total, how much memory is being wasted by external fragmentation?


(e)  In total, how much memory is being wasted by internal fragmentation?


3.   A 32-bit byte-addressed DLX processor has a physically addressed direct-mapped data cache of size 16Kbytes and cache lines of size 16 bytes.  It also implements paging with a page size of 4Kbytes.  Assume the bit positions in memory addresses are numbered 0 (least significant) to 31 (most significant).

(a)    What range of address bits is used as the index into the cache?

(b)    Can the cache be accessed in parallel with the TLB?  If not, give the correct order of access.

(c)    Repeat part (b), but assuming a page size of 16 Kbytes.

(d)    Suppose we want a cache in which lines from more than one process can co-exist at the same time.  Does the cache tag need to include the process ID # in addition to the high-order bits of the address?  Give a reason. (1-2 sentences) [Hint: Page size does not affect the answer here.]


4.   In the MS-DOS file system, a disk is prefaced with an array of values called the File Allocation Table (FAT).  Each FAT entry corresponds to a sector on the disk.  The operating system uses the FAT as a linked list to keep track of where files are on the disk, with each FAT entry pointing to another FAT entry corresponding to the file’s next sector.  The directory, a list of all files on the disk, holds the initial FAT entry of each file and a record of the file size.


For example, suppose a disk has two files:

            AUTOEXEC.BAT       First sector: 12

            CONFIG.SYS             First sector:  7


The FAT (of a very messy disk) might look like:

Index                FAT value

5                      empty

6                      End of File

7                      8

8                      10

9                      empty

10                    11

11                    14

12                    13

13                    6

14                    End of File


(a)  If a sector is 512 bytes, how big is AUTOEXEC.BAT?  How big is CONFIG.SYS?


The remaining parts (b) to (d) are about file deletion.  When a file is deleted in MS-DOS, the FAT entries corresponding to that file are all set to empty.  The directory entry is not deleted, however, but simply marked as deleted.  The actual sectors comprising the file are likewise not erased, but are liable to be overwritten.


(b)  How might you design a simple Undelete utility that resurrects a mistakenly deleted file?  (Hint:  MS-DOS tries to write files to sequential sectors whenever possible).


(c)  When will your Undelete utility fail? 


(d)  How can you detect if Undelete will fail?  Under what circumstances can Undelete fail without your detecting it?