SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
Haonan Wang
CMPE 142
Operating Systems
SJSU SAN JOSÉ STATEUNIVERSITY
Important Information
• For students with time conflict
– Time: Wednesday, May. 25, 09:45 - 12:00 @ Canvas with LockDown Browser + Webcam
• Review the first half with midterm review slides and recordings!
• Extra Office hour: 19:00 – 20:00 PM, Sunday, May. 22.
– I will also be available for questions via Email/Canvas/Slack.
• You do not have to know everything in the textbook. However, any content covered in the
lecture could appear in the exam. The review slides do not cover everything.
• Do not leave it blank!
• Good luck!
2
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
1. Consider a system with N bytes of physical RAM, and M bytes of virtual address space per process.
Pages and frames are K bytes in size. Every page table entry is P bytes in size, including the extra flags
required and such. What is the size of the page table of a process?
3
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
2. Consider a system with a 6-bit virtual address space, and 16-byte pages/frames. The mapping from
virtual page numbers to physical frame numbers of a process is (0,8), (1,3), (2,11), and (3,1). Translate the
following virtual addresses to physical addresses. Note that all addresses are in decimal. You may write
your answer in decimal or binary.
(a) 20
(b) 40
4
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
3. Consider a simple system running a single process. The size of physical frames and logical pages is 16
bytes. The DRAM can hold 3 physical frames. The virtual addresses of the process are 6 bits in size. The
program generates the following 20 virtual address references as it runs on the CPU: 0, 1, 20, 2, 20, 21, 32,
31, 0, 60, 0, 0, 16, 1, 17, 18, 32, 31, 0, 61. (Note: the 6-bit addresses are shown in decimal here.) Assume
that the physical frames in RAM are initially empty and do not map to any logical page.
(a) Translate the virtual addresses above to logical page numbers referenced by the process. That is, write
down the reference string of 20 page numbers corresponding to the virtual address accesses above.
0, 0, 1, 0, 1, 1, 2, 1, 0, 3, 0, 0, 1, 0, 1, 1, 2, 1, 0, 3
(b) Calculate the number of page faults generated by the accesses above, assuming a FIFO page
replacement algorithm. You must also correctly point out which page accesses in the reference string shown
by you in part (a) are responsible for the page faults.
5
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
3. Consider a simple system running a single process. The size of physical frames and logical pages is 16
bytes. The DRAM can hold 3 physical frames. The virtual addresses of the process are 6 bits in size. The
program generates the following 20 virtual address references as it runs on the CPU: 0, 1, 20, 2, 20, 21, 32,
31, 0, 60, 0, 0, 16, 1, 17, 18, 32, 31, 0, 61. (Note: the 6-bit addresses are shown in decimal here.) Assume
that the physical frames in RAM are initially empty and do not map to any logical page.
0, 0, 1, 0, 1, 1, 2, 1, 0, 3, 0, 0, 1, 0, 1, 1, 2, 1, 0, 3
(c) Repeat (b) above for the LRU page replacement algorithm.
(d) What would be the lowest number of page faults achievable in this example, assuming an optimal page
replacement algorithm were to be used? Repeat (b) above for the optimal algorithm.
6
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
4. Consider a system with several running processes. The system is running a modern OS that uses virtual
addresses and demand paging. It has been empirically observed that the memory access times in the system
under various conditions are: t1 when the logical memory address is found in TLB cache, t2 when the
address is not in TLB but does not cause a page fault, and t3 when the address results in a page fault. This
memory access time includes all overheads like page fault servicing and logical-to-physical address
translation. It has been observed that, on average, 10% of the logical address accesses result in a page fault.
Further, of the remaining virtual address accesses, two-thirds of them can be translated using the TLB
cache, while one-third require walking the page tables. Using the information provided above, calculate the
average expected memory access time in the system in terms of t1, t2, and t3.
7
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
5. Consider an operating system that uses 48-bit virtual addresses and 16KB pages. The system uses a
hierarchical page table design to store all the page table entries of a process, and each page table entry is 4
bytes in size. What is the total number of pages that are required to store the page table entries of a process,
across all levels of the hierarchical page table?
8
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
6. Assume that the DRAM can hold 3 physical frames and they are initially empty. Now, apply LRU
replacement to the following string of page number references: 3 2 4 5 4 1 2 4 3 4. Please show which
pages are in memory after each page reference.
9
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
7. Consider a secondary storage system of size 2 TB, with 512-byte sized blocks. Assume that the
filesystem uses a multilevel inode data structure to track data blocks of a file. The inode has 64 bytes of
space available to store pointers to data blocks, including a single indirect block, a double indirect block,
and several direct blocks. What is the maximum file size that can be stored in such a file system?
10
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
8. Assume a disk rotates at 5,000 RPM with an average rotation of 0.5 round. The average seek time is 5
ms. The data transfer rate is 200MB/sec. There is a controller overhead of 0.1 ms. What is the estimated
average latency to read or write a 512B sector?
11
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
9. Assume that the head pointer range of a disk is from 0 to 199 (cylinder). The head pointer is currently at 100. Now
we have a sequence of requests with the following cylinder index: 18, 123, 87, 192, 34, 114, 15, 76. What is the total
head movement for 1) SSTF and 2) C-LOOK Disk Scheduling?
12
SJSU SAN JOSÉ STATEUNIVERSITY
Final Review Questions
10. One way to implement the reader-writer problem is as follows:
Shared:
…
Sem_t rw_mutex = 1;
Sem_t mutex = 1;
Sem_t read_count = 0;
Writer:
while (true) {
wait(rw_mutex);
...
// writing is performed
...
signal(rw_mutex);
}
13
Reader:
while (true){
wait(mutex);
read_count++;
if (read_count == 1) // first reader
wait(rw_mutex);
signal(mutex);
...
// reading is performed
...
wait(mutex);
read count--;
if (read_count == 0) //last reader
signal(rw_mutex);
signal(mutex);
}
Please explain the functionality of each signal and wait function call in the code.
SJSU SAN JOSÉ STATEUNIVERSITY