HW08 Operating System ================================================================================ 2. A machine has a 32-bit byte-addressable virtual address space. The page size is 4 KB. How many pages of virtual address space exist? 3. Is it necessary to have the page size be a power of 2? Could a page of size, say, 4000 bytes be implemented in theory? If so, would it be practical? 5. A computer has 16 pages of virtual address space but only four page frames. Initially, the memory is empty. A program references the virtual pages in the order 0, 7, 2, 7, 5, 8, 9, 2, 4 a. Which references cause a page fault with LRU? b. Which references cause a page fault with FIFO? 10. Some computers allow I/O directly to user space. For example, a program could start up a disk transfer to a buffer inside a user process. Does this cause any problems if compaction is used to implement the virtual memory? Discuss. 16. Supermarkets are constantly faced with a problem similar to page replacement in virtual memory systems. They have a fixed amount of shelf space to display an everincreasing number of products. If an important new product comes along, say, 100% efficient dog food, some existing product must be dropped from the inventory to make room for it. The obvious replacement algorithms are LRU and FIFO. Which of these would you prefer? 17. In some ways, caching and paging are very similar. In both cases there are two levels of memory (the cache and main memory in the former and main memory and disk in the latter). In this chapter we looked at some of the arguments in favor of large disk pages and small disk pages. Do the same arguments hold for cache line sizes? 18. Why do many file systems require that a file be explicitly opened with an open system call before being read? 23. On a certain computer, a program can create as many files as it needs, and all files may grow dynamically during execution without giving the operating system any advance information about their ultimate size. Do you think that files are stored in consecutive sectors? Explain. 24. Studies of different file systems have shown that more than half the files are a few KB or smaller, with the vast majority of files less than something like 8 KB. On the other hand, the largest 10 percent of all files usually occupies about 95 percent of the entire disk space in use. From this data, what conclusion can you draw about disk block size? 25. Consider the following method by which an operating system might implement semaphore instructions. Whenever the CPU is about to do an up or down on a semaphore (an integer variable in memory), it first sets the CPU priority or mask bits in such a way as to disable all interrupts. Then it fetches the semaphore, modifies it, and branches accordingly. Finally, it enables interrupts again. Does this method work if a. There is a single CPU that switches between processes every 100 msec? b. Two CPUs share a common memory in which the semaphore is located? 28. Make a table showing which of the processes P1, P2, and P3 are running and which are blocked as a function of time from 0 to 1000 msec. All three processes perform up and down instructions on the same semaphore. When two processes are blocked and an up is done, the process with the lower number is restarted, that is, P1 gets preference over P2 and P3, and so on. Initially, all three are running and the semaphore is 1. At t = 100 P1 does a down At t = 200 P1 does a down At t = 300 P2 does an up At t = 400 P3 does a down At t = 500 P1 does a down At t = 600 P2 does an up At t = 700 P2 does a down At t = 800 P1 does an up At t = 900 P1 does an up 31. Show the values of in and out for a circular buffer of length 65 words after each of the following operations. Both start at 0. a. 22 words are put in b. 9 words are removed c. 40 words are put in d. 17 words are removed e. 12 words are put in f. 45 words are removed g. 8 words are put in h. 11 words are removed