2021/4/27 ²âÑé: Sample Final Exam Sample Final Exam
ÒÑ¿ªÊ¼: 4ÔÂ27ÈÕ 0:22 ²âÑé˵Ã÷
Please read the following instructions carefully before you start working on your exam.
ONLY FOR THE SAMPLE EXAM: This is a sample exam whose purpose is to help you prepare for the final exam. It is comparable in scope, format, and complexity to the final exam. We will NOT be providing readymade solutions or offering answers over Piazza or email so PLEASE REFRAIN from making such requests. You are welcome to post your questions and ideas on Piazza in order to get inputs from your peer students. If you are unable to solve a problem on your own, the proper/scalable way of seeking help is through our office hours (there are 7 of us so it is unlikely that none of the OHs work for you).
This is an OPEN-BOOK/NOTES/SLIDES exam. This means you are allowed to access the following on your computer: (i) our textbooks (OSTEP, LBS); (ii) your own notes (if any); and (iii) our lecture slides. You may not make use of the Internet for any purpose other than accessing these resources or Canvas and Zoom.
This exam has questions worth a total of 41 points.
For multiple answer problems, you must choose ALL correct choices to get any points.
ONLY FOR THE FINAL EXAM: Please be aware that, unlike in the sample exam, you will only get
one attempt. We had to choose this because the Canvas design “leaks” answers when multiple attempts are allowed.
For the essay-type questions, you may type your solution in your favorite editor and upload the file (doc or txt or pdf). Alternatively, you may take a picture of your handwritten solution and upload the image.
ONLY FOR THE FINAL EXAM: Make sure you submit the exam on time, else you will get a 0.
ONLY FOR THE FINAL EXAM: If you need extra time (SDR or technical difficulties), seek help from your proctor. If you are seeking extra time due to SDR, you must email the proper form to your proctor in order to get the requested extra time.
ONLY FOR THE FINAL EXAM: Please keep yourself on mute at all times. Please make sure your video feed is on at all times and the proctor can see your work. If the proctor asks you to move your camera around, you must be prepared to do so.
ONLY FOR THE FINAL EXAM: Make sure to sign the honesty statement to ensure that your exam is graded.
ONLY FOR THE FINAL EXAM: If you are unclear about a problem, you may seek clarification from your proctor. Please use chat and be patient as the proctor will be helping about 40 students.
ÎÊÌâ 1 2 ·Ö
https://psu.instructure.com/courses/2109277/quizzes/4199967/take 1/8
2021/4/27 ²âÑé: Sample Final Exam
ÎÊÌâ 2 2 ·Ö
Consider a DRAM with 4 pages which is initially empty. Pick the number of page faults for the following reference string (each letter denotes a unique virtual page): AAABACAADCEDBAACEEAB.
8 10 7 9
Consider a concurrent program wherein all threads only read shared data. Select all that are true.
There are no data races but we cannot be sure of race conditions just with the information provided here.
There are no data races or race conditons.
There are no race conditions but we cannot be sure of data races just with the information provided here.
There are no race conditions but there are data races (by definition).
ÎÊÌâ 3 2 ·Ö
Consider a 48-bit virtual memory system using 3-level page tables with the parameters n1=n2=n3=p=12. What is the maximum size of memory occupied by the second-level tables? Assume each second-level page table entry is 4 Bytes large.
https://psu.instructure.com/courses/2109277/quizzes/4199967/take
2/8
2021/4/27 ²âÑé: Sample Final Exam
ÎÊÌâ 4 3 ·Ö
Consider a magnetic disk drive consisting of 100 tracks numbered 0, …, 99 whose scheduler employs the Elevator (SCAN) algorithm. Consider a set of 10 requests that arrive at the same time to this drive’s scheduler. We will denote each request by the track number on which its requested disk block resides. Assume the disk head to be on track 53 and the last request it serviced to have been on track 52. Calculate the average number of tracks that the disk head needs to traverse to service these 10 requests.
12, 92, 31, 54, 5, 0, 67, 32, 67, 99.
32 MB 64 MB 128 MB 1 GB
ÎÊÌâ 5 2 ·Ö
Select all that are true about the indirect overheads of context switching.
Larger quanta will tend to worsen the indirect overheads.
Multi-threaded realizations of a concurrent program will tend to be hurt less by cache and
https://psu.instructure.com/courses/2109277/quizzes/4199967/take
3/8
2021/4/27 ²âÑé: Sample Final Exam
https://psu.instr
4/8
TLB pollution than their multi-process realizations.
Multi-process realizations of a concurrent program will tend to be hurt less by cache and TLB pollution than their multi-threaded realizations.
Larger quanta will tend to reduce the indirect overheads.
ÎÊÌâ 6 10 ·Ö
Penn State is considering a new policy whereby the same bathroom may be used by both men and women. However, at any given time either only women or only men may be using the bathroom. Assume the bathroom has infinite capacity, write these functions:
Woman_wants_to_enter Man_wants_to_enter Woman_leaves Man_leaves
Your solution must satisfy the desired invariant stated above and be deadlock-free. It is acceptable for your solution to starve someone. You may use any combination of mutex locks, condition variable, and semaphores. You will get 0 points if your solution makes someone wait when they need not. You may use pseudo-code similar to that used in class; you do not need to use exact data type and function names from the pthreads API. You will win/lose points based on the following components/properties of your solution:
Choice of synchronization-related variables, how you initialize them, and a succinct comment next to each describing its purpose
Your use of synchronization-related variables with comments describing the purpose/effect of key statements and conditions
Your intent indicated in your comments must match what your pseudo-code accomplishes
±à¼ ÊÓͼ ²åÈë ¸ñʽ ¹¤¾ß ±í¸ñ 12pt ¶ÎÂä
ucture.com/courses/2109277/quizzes/4199967/take
2021/4/27 ²âÑé: Sample Final Exam
p 0 ¸ö×Ö
ÎÊÌâ 7 10 ·Ö
Suppose you know that your workload contains 20% memory instructions. Suppose you also know that it virtual memory access behavior corresponds to a fraction of memory refs vs. LRU queue position curve that is a line segment with the following end points:
(LRU QPos=1, fracMemRef=0.8), (LRU QPos=1000, fracMemRef=0),
You go to Best Buy (again!) and you find two laptop models that have the same price. Both have operating systems that use the LRU page replacement policy.
1. CPU = 2GHz, DRAM = 400pages 2. CPU = 1GHz, DRAM = 500pages
Assume non-memory instructions take 1 cycle each as does TLB access. Assume TLB hit rate of 99% for both laptops. Assume DRAM latency of 100 cycles and swap access time of 100,000 cycles on both laptops. Assume memory needed to store page tables doesn’t count towards the number of pages indicated above, ignore any hardware caches, ignore OS trap/interrupt handling and context switching time.
Calculate the average CPI offered by each laptop and state which one you would choose.
±à¼ ÊÓͼ ²åÈë ¸ñʽ ¹¤¾ß ±í¸ñ
https://psu.instructure.com/courses/2109277/quizzes/4199967/take
5/8
2021/4/27 ²âÑé: Sample Final Exam
ÎÊÌâ 8 1 ·Ö
For what kind of an IO device might polling be preferable over interrupts?
A character device
A slow device such as a keyboard A relatively fast IO device
A block device
12pt ¶ÎÂä
p
0 ¸ö×Ö
ÎÊÌâ 9 2 ·Ö
https://psu.instructure.com/courses/2109277/quizzes/4199967/take
6/8
2021/4/27 ²âÑé: Sample Final Exam
ÎÊÌâ 10 2 ·Ö
Select all resources whose “wastage” DMA helps reduce.
Bandwidth of busses TLB capacity
CPU cycles
Hardware cache capacity
Of the various examples of operating system functionality listed below, select all that tend to be hardware/architecture-independent.
Process control block Process identifiers (PIDs) Interrupt handlers
List of ready processes
ÎÊÌâ 11 2 ·Ö
Consider a program whose two threads use two locks L1 and L2 as shown below. Does this program have a deadlock? If yes, choose “True,” else choose “False.”
Thread1: Thread2: ———— ————
https://psu.instructure.com/courses/2109277/quizzes/4199967/take
7/8
2021/4/27 ²âÑé: Sample Final Exam
ÎÊÌâ 12 3 ·Ö
Consider using the wordcount application from Project 3 on a large input file. Which of the following will help improve completion time?
Increasing the CPU scheduling priority of only the reducer thread. Increasing the size of the shared buffer.
Decreasing the CPU scheduling priorities of only the mapper threads. Increasing the CPU scheduling priorities of only the mapper threads. Decreasing the CPU scheduling priority of only the reducer thread
… mutex_lock(L1); mutex_lock(L2);
critical section 1 mutex_unlock(L1); mutex_unlock(L2);
…
True False
… mutex_lock(L1);
mutex_lock(L2); critical section 2
mutex_unlock(L2); mutex_unlock(L1);
…
δ±£´æ Ìá½»²âÑé
https://psu.instructure.com/courses/2109277/quizzes/4199967/take
8/8