CS 416 Exam 2
Spring 2012
See the solutions (6 per page).
- 4 points
Under what conditions will you reach a point of diminishing returns where adding more memory may improve performance only a little? - 6 points
- One of the ways that Berkeley improved performance in their design of the Fast File System was to use larger clusters. Assume that an inode has a small number of direct blocks, 1 indirect block, 1 double indirect block, and 1 triple indirect block. Further, assume that each disk cluster holds b block (cluster) pointers. Approximately how much bigger a file can the file system support if the cluster size is doubled? Show your work and approximate your answer as a single number.
- You have the option of doubling the cluster size or adding two additional triple indirect blocks to the inode. Completely ignoring the performance implications of using triple indirect blocks, which file system will support a larger file size? Show your work and explain why.
- Dynamic linking:
(a) Brings in libraries as needed to create the final executable file that can then be loaded and run.
(b) Links libraries to create the final executable file without having the user identify them.
(c) Loads libraries when the executable file first references those libraries.
(d) Is a technique for re-linking an executable file with newer versions of libraries. - Running multiple processes in a single partition monoprogramming environment requires:
(a) Swapping the memory image of a process to disk at each context switch.
(b) Ensuring that each process uses the same amount of memory.
(c) Having each program compiled to start at the address of one of several partitions.
(d) That multiple processes can coexist within a single partition. - By adding base and limit addressing to multiple partitions, we can now use:
(a) Absolute code.
(b) Position independent code.
(c) Statically linked code.
(d) Dynamically relocatable code. - One advantage of multiple fixed partitions (MFP) over variable partitions is:
(a) MFP never leads to unusably small holes due to external fragmentation.
(b) There is no need to pre-allocate partitions.
(c) Sharing memory is much easier.
(d) MFP will usually result in much more efficient use of system memory. - In a conventional paging system, a page table entry (PTE) will not contain:
(a) A logical page number.
(b) A physical page frame number.
(c) A page residence bit.
(d) Page permissions. - A system with 32-bit addresses, 1 GB (230) main memory, and a
1 megabyte (20-bit) page size will have a page table that contains:
(a) 4,096 (4K, 212) entries.
(b) 4,294,967,296 (4G, 230) entries.
(c) 1,048,576 (1M, 220) entries.
(d) 1,024 (1K, 210) entries. - The Linux slab allocator is NOT designed to:
(a) Provide an interface for memory allocation for kernel structures.
(b) Avoid external fragmentation by allocating same-size objects per cache.
(c) Replace the buddy algorithm for allocating pages as well as objects.
(d) Be able to increase the amount of memory it uses by requesting more pages. - Segmentation is a form of:
(a) Base & limit addressing.
(b) Direct-mapped paging.
(c) Multi-level page tables.
(d) Base & limit addressing followed by a page table lookup. - Assume that a main memory access takes 100 ns. If we are using a two-level page table and have a 50% TLB hit ratio, the effective memory access time is (assume no memory cache and no page faults):
(a) 100 ns.
(b) 200 ns.
(c) 300 ns.
(d) 400 ns. - A system with 32-bit addresses, 1 GB (230) main memory, and a 1 megabyte (20-bit) page size will have an inverted page table that contains:
(a) 1,024 (1K, 210) entries
(b) 4,096 (4K, 212) entries.
(c) 1,048,576 (1M, 220) entries.
(d) 4,294,967,296 (4G, 230) entries. - You are using a buddy algorithm that allocates storage from 16-byte blocks up to 1024-byte blocks. What percentage of allocated memory is wasted due to internal fragmentation when satisfying requests for allocating 130-byte chunks?
(a) Approximately 0%.
(b) Approximately 25%.
(c) Approximately 50%.
(d) Approximately 100%. - You are using a buddy algorithm for allocating chunks of memory in the same configuration as in the previous question. You make a sequence of 256-byte allocations as follows:
a=alloc(256), b=alloc(256), c=alloc(256), d=alloc(256)
Which sequence of deallocations will result in having the largest chunk of memory available for a future allocation?
(a) free(a), free(d).
(b) free(c), free(d).
(c) free(b), free(c).
(d) free(b), free(d). - Memory compaction refers to:
(a) Moving regions of memory to get rid of external fragmentation.
(b) Compressing a region of memory to have it consume less space.
(c) Getting rid of large empty (zero) sections within a region of memory.
(d) Configuring a system to run in less memory than is actually available - The page number in the 24-bit address 0x123456 with an 256-byte page size is:
(a) 0x56
(b) 0x12
(c) 0x1234
(d) 0x3456 - Which cannot be a valid page size?
(a) 32 bytes.
(b) 1,024 bytes.
(c) 3,072 bytes.
(d) 1,048,576 bytes. - The reason for using a multilevel page table is to:
(a) Reduce the amount of memory used for storing page tables.
(b) Make table lookups more efficient than using a single-level table.
(c) Make it easier to find unused page frames in the system.
(d) Provide a hierarchy to manage different sections of a program. - Monitoring page fault frequency of a process allows us to:
(a) Manage page frame allocation per process.
(b) Adjust the size of the TLB for optimum performance.
(c) Determine if the process is I/O bound or CPU intensive.
(d) Identify the number of illegal instructions and invalid memory accesses within a program. - A buffer cache is useful only for:
(a) Block devices.
(b) Character devices.
(c) Network devices.
(d) Block and network devices. - The following is not an example of a character device:
(a) Mouse.
(b) Sound card.
(c) USB-connected printer.
(d) Flash memory. - The minor number of a device identifies:
(a) The version number of a device driver.
(b) Whether a device is a block, character, or network device.
(c) The specific driver used by a block, character, or network device.
(d) The instance of a specific device among devices sharing the same driver. - The top half of a device driver runs in:
(a) Driver context.
(b) User context.
(c) Kernel context.
(d) Interrupt context. - A disk drive using the Circular LOOK (C-LOOK) algorithm just wrote block 1203 and then read block 1204. The following blocks are queued for I/O: 900, 1200, 1800, 2500. In what order will they be scheduled?
(a) 1200, 900, 1800, 2500
(b) 1200, 900, 2500, 1800
(c) 1800, 2500, 1200, 900
(d) 1800, 2500, 900, 1200 - Which scheduling algorithm makes the most sense for flash memory?
(a) Shortest seek time first (SSTF).
(b) SCAN.
(c) LOOK.
(d) First come, first served (FCFS). - The VFS inode interface does NOT allow you to:
(a) Create a file.
(b) Read file data.
(c) Write a file's attributes.
(d) Delete a directory. - The use of clusters in a file system does NOT:
(a) Reduce internal fragmentation in a file.
(b) Increase the amount of contiguous blocks in a file.
(c) Reduce the number of blocks we need to keep track of per file.
(d) Improve file data access performance. - A File Allocation Table:
(a) Stores a list of blocks used by every single file in the file system.
(b) Stores file names and the blocks of data that each file in the file system uses.
(c) Is a table-driven way to store file data.
(d) Is a bitmap identifying unused blocks that can be used for file data. - The Berkeley Fast File System did NOT improve the Unix File System by adding:
(a) Cylinder groups.
(b) Bitmap allocation for keeping track of free and used blocks.
(c) Extent-based allocation.
(d) Prefetching of blocks. - Unlike full data journaling, ordered journaling:
(a) Improves performance by not writing file data into the journal.
(b) Makes sure that all that all journal entries are written in a consistent sequence.
(c) Provides improved consistency by writing the data before any metadata is written.
(d) Imposes no order between writing data blocks and writing metadata journal entries. - With NTFS:
(a) File data may be present within the file record along with file attributes.
(b) The main structure guiding the location of files is the File Allocation Table.
(c) Journals, free bitmaps, file records, and file data are kept in distinct sections of the disk.
(d) All data blocks are compressed to maximize available disk space. - Which structure of ext3 is least useful for a flash-based storage device?
(a) inode table.
(b) Block groups.
(c) Journal.
(d) Free block bitmap. - The Linux ext4 file system differs from ext3 in that it uses:
(a) Cluster-based allocation.
(b) Extent-based allocation.
(c) Block groups.
(d) Journaling. - A log structured file system is the same as an inode-based file system with journaling added.
True False - YAFFS uses a separate area in the file system for storing directories and metadata.
True False - Because of page-based virtual memory, operating systems never need to worry about allocating contiguous pages.
True False - Each page table needs to have within it a reference to each page frame in the system.
True False - A partial page table contains page table entries for all pages in the system but not all page frames.
True False - YAFFS2 implements dynamic wear leveling, not static.
True False - A clock page replacement algorithm tries to approximate a Least Recently Used (LRU) algorithm.
True False - The Shortest Seek Time First (SSTF) algorithm has a danger of starving some requests.
True False - The order that disk blocks are scheduled in flash memory is not critical.
True False - The loop device converts a regular file into a block device.
True False
Part I – 10 Points
PART II – 81 points – 27 questions – 3 points each
For each statement, select the most appropriate answer. You may omit one question per page.
PART III – 9 questions – 9 points – 1 point each
For each statement, specify whether it is true or false by circling the correct choice. You may omit one question.
