1. 10.2 Given m frames, p references, n distinct page numbers
   
   
1. What is the lower bound on the number of page faults
   n – these are compulsory misses. This could occur if page replacement is perfect, or there is more memory than needed (m > n)
   
   
2. What is the upper bound on the number of page faults
   p – you could potentially miss on every page. This could occur if there is very little memory (m = 1) or if page replacement is particularly bad.
   
   
2. 10.3 Explain how the system establishes the physical location of a virtual address in the given computer system. Distinguish between hardware and software operations
   
   The virtual address in binary form is
   0001 0001 0001 0010 0011 0100 0101 0110
   Since the page size is 2¹², the page table size is 2²⁰. Therefore the low-order 12 bits “0100
   0101 0110” are used as the displacement into the page, while the remaining 20 bits “0001
   0001 0001 0010 0011” are used as the displacement in the page table. This displacement is looked up in hardware in the TLB. If there is a miss in the TLB, than either the hardware may walk the page table for the entry, or it may raise an exception, and the operating system can check the page table.
   
   If the entry in the page table is valid, then either hardware or the OS puts it in the TLB and the process continues executing.
   
   If the entry is invalid, the OS decides what to do next – either signal the process that it accessed an invalid address, or bring in the page from somewhere else. If it brings in the page, it must find a free frame (which may cause paging out another page), and then read in the missing page from the disk. Once the page is in, the OS marks the page table entry as valid, possibly sticks the entry in the TLB, and lets the process continue.
   
   
3. 10.7 List the costs and benefits of virtual memory. What measures can you take to ensure the costs don’t exceed the benefits?
   
   The costs are additional hardware, additional complexity in the OS, additional memory usage for virtual memory data structures, and slower access time. The benefits are good utilization of memory, protection, and larger logical address space than physical address space.
   
   You can make sure for that programs that fit in memory, there are no unnecessary overheads –e.g. extra accesses to memory, page faults. Also, you can use good page replacement algorithms, to minimize the number of page faults.
   
   
4. 10.11 How many page faults are generated using LRU replacement with 5 frames?
   
   LRU: 8
   FIFO: 10
   Optimal: 7
   
   
5. 10.12 How can you simulate a reference bit if it is not provided by hardware? Calculate the cost of doing so.
   
   You can use the valid/invalid bit supported in hardware to simulate the reference bit. Initially set the bit to invalid. On first reference a trap to the operating system is generated. The operating system will set a software bit to 1 and reset the valid/invalid bit to valid.
   
   The cost is that of doing a page fault (e.g. 100s of cycles) to set the reference bit.
   
   
6. 11.3 Why do some systems keep track of the type of file, while others leave it to the user? Which system is better?
   
   Some systems allow different file operations based on the type of the file (for instance, an ASCII file can be read as a stream while a database file can be read via a index to a block). Other systems leave such interpretation of a file’s data to the process and provide no help in accessing the data. The method that is “better” depends on the needs of the processes on the system, and the demands the users place on the operating system. If a system runs mostly database applications, it may be more efficient for the operating system to implement a database-type file and provide operations, rather than making each program implement the same thing (possibly in different ways). For general-purpose systems it may be better to only implement basic file types to keep the operating system size smaller and allow maximum freedom to the processes on the system.
   
   
7. 11.5 What are the advantages / disadvantages of recording the name of the creating program with the file’s attributes?
   
   By recording the name of the creating program, the operating system is able to implement features (such as automatic program invocation when the file is accessed) based on this information. It does add overhead in the operating system and require space in the file descriptor, however.
   
   
8. 11.11 Subdirectories as files

a. Describe protection problems that could arise
One piece of information kept in a directory entry is file location. If a user could modify this location, then he could access other files defeating the access-protection scheme.

b. Suggest a scheme for dealing with each of the protection problems
Do not allow the user to directly write onto the subdirectory. Rather, provide system operations to do so.

9. 11.12 Sharing a file among 4990 of 5000 users

a. Unix
Create a group with 4990 users and give the group access to the file
Put 4990 users on the file with the appropriate access

b. What other scheme could be more effective?
Create a group with the 10 users that cannot access the file. Set the ACL on the file to deny access to the group of 10 users.
Put the 10 users on the file with no access, and grant everyone access.