Answer key for Exam 2 1. First set - Yes, deadlock is possible 1.1, 1.2, 2.1, 2.2, 3.1, 3.2 Second set - No, deadlock is not possible 2. Note, I cannot easily draw the graphs here Set 1 No deadlock P1 has all its resourses, it releases R10 P3 acquires R10, runs to completion, releases R10, R30 P2 acquires R10 Set 2 No deadlock P1 releases R10 P3 acquires R10, runs, releases R10, R30 P2 acquires R30 Set 3 Deadlock 3. The principle of locality states that programs access a relatively small portion of their address space at any point in time. There are two types of locality. Temporal locality An item that was recently referenced is likely to be referenced again soon Spatial locality A program that references a particular address is likely to reference nearby addresses soon. cache memory and paging work because of temporal locality Loading pages near a requested page, or loading a whole file when only part has been requested are examples of spatial locality 4. 1, 2, 5, 7, 3, 4, 8, 6 Here is the work! Request Time Queue Num Track Done at that time -------------------------------------------------------- 1 60 8 2(90), 3(30), 4(10) 2 90 13 3(30), 4(10), 5(50) 5 50 19 3(30), 4(10), 6(70), 7(40), 8(60) 7 40 22 3(30), 4(10), 6(70), 8(60) 3 30 25 4(10), 6(70), 8(60) 4 10 29 6(70), 8(60) 8 60 36 6(70) 6 70 39 5. The address displayed (133808) is a virutal address (logical address. However, since each process has its own page table, these point to different physical addresses. 6. Event driven programming - the kind of programming used in GUI systems, in which one or more windows are displayed, and the program then responds to events such as keystrokes, mouse moves, etc. Each event has a function associated with it (a callback in X windows terminology). Translation Lookaside Buffer - a cache of the page table that works with the MMU so that most memory references do not need to access the page table. A small number of recently accessed pages are stored along the the physical page ref. Searched with a hashing function. Inverted page table - a page table with an entry for each physical page table, in contrast to a regular page table which has an entry for each logical page. This solves the problem of trying to store a very large page table. Paging Daemon - a daemon which is a part of the Unix OS, which runs periodically (for example, once every 250 msec). If there are enough empty pages, it goes back to sleep, otherwise, it deletes some pages. The purpose of this is to assure that then a page fault occurs, there will always be empty pages available. ISO 9660 File System - the file system on CD-ROMs DMA - Direct Memory Access - an Input/Output mechanism in which devices (device drivers) can access memory directly without going through the kernel. It does this by cycle stealing Widget - a windows class in the X windowing system. It has a standard appearance and predefined actions to which it responds. Examples include pushbuttons, listboxes, or menus Journaling file system - a file system in which metadata about files (i.e. where blocks of the file are located on the disk) are stored in a log. Updates are not committed until all actions are complete. This makes it easier to restore the integrity of a file system in the event of a crash. 7. 2^22 2^12 8. First Program Parent reads ABCDE Child reads FGHIJ Parent reads KLMNO Second Program Parent Reads ABCDE Child Reads ABCDE Parent Reads FGHIJ Third Program Parent Reads ABCDE Child Reads ABCDE Parent Reads FGHIJ Fourth Program Parent Reads ABCDE Child Reads ABCDE Parent Reads FGHIJ 9. See Figure 4-23 on page 228 of the text 10. mv Read inode of / directory Read data of / directory Read inode of /usr directory Read data of /usr directory Read inode of /usr/bin directory Read data of /usr/bin directory Write data of /usr/bin to include the new file Write data of . directory to delete the file cp Read inode of / directory Read data of / directory Read inode of /usr directory Read data of /usr directory Read inode of /usr/bin directory Read data of /usr/bin directory Read inode of a.out Read data of a.out Create a new inode for the new file (this would involve accessing the freelist, but points were not taken off if this was not included) Write the new data (also would require accessing the freelist) Write the data of the /usr/bin directory 11. Contiguous - store the file in contiguous blocks on the disk, moving to a larger hole if the file grows. Not used because moving is very time consuming, and this can result in large holes. The size of the file is not known when it is created Linked List - each block contains a pointer to the next block. Not used because random access of large files is very time consuming FAT - all of the pointers to the blocks of a file are stored in on place. - an efficient system, used by early Microsoft operating systems (and still used) Unix Inodes - the inode contains a pointer to the first 12 blocks, a single indirect block (which points to the next 1K blocks, a double indirect block and a triple indirect block NTFS - stores blocks in runs. Each run consists of the the start address and the number of blocks. Very efficient