CSCI 4210 — Operating SystemsSample Final Exam Questions and Prep (document version 1.0)OverviewˆThis exam is scheduled for the extended window that starts at 4:00PM EDT on Thursday8/20 and ends at 2:00AM EDT on Friday 8/21ˆThis exam is a 90-minute exam, but you will have a full three-hour window to complete andsubmit your exam solutions; if you have extra-time accommodations, then you have either a4.5-hour (50%) or six-hour (100%) window (and can go beyond the 2:00AM EDT end time)ˆSubmitty will start the three-hour “clock” for you when you first view the exam gradeable(nothing under course materials), so please plan accordingly by avoiding any distractionsor interruptions;and note that you must start your exam by 11:00PM EDT onThursday 8/20 to have the full three-hour windowˆThis exam is open book(s), open notes; given that you are working remotely, you may use anyand all of the posted course materials, including all previous questions and answers posted inthe Discussion Forum.ˆPlease do not search the Web for answers;please follow the instructions carefully andonly use the techniques taught in this courseˆFor the exam, be as concise as you can in your answers; long answers are difficult to gradeˆAll work on this exam must be your own; do not copy or communicate withanyone else about the exam during or for 24 hours after the examˆOnce we have graded your exam, solutions will be posted; the grade inquiry window for thisexam will be one weekˆAssume all code compiles without warnings or errors; also assume all library functions andsystem calls return successfullyˆThe Final Exam will becomprehensive, covering everything we have done this semester.ˆUse the sample questions from the previous two exams, all previous quizzes and programmingassignments, and the suggested most recent topics and questions below to prepare.ˆThe Final Exam and final course grades will be made available via Rainbow Grades onSubmitty.ˆThe Final Exam willnotbe handed back or available for review; however, exams will begraded multiple times to ensure correctness and consistency of grading. Additional Sample Final Exam Questions/Topics1. What is contiguous memory allocation? How does it differ from non-contiguous memoryallocation?2. What are the advantages of contiguous memory allocation? What are its disadvantages?3. What are the advantages of non-contiguous memory allocation? What are its disadvantages?4. What is the difference between a fixed partitioning scheme and a dynamic partitioningscheme? Do these apply to both contiguous and non-contiguous memory allocation?5. What are the four algorithms for placing processes in a contiguous memory allocation scheme?Which algorithm is the “best” algorithm (and why)?6. Describe how address translation works in a contiguous memory allocation scheme.7. Describe how address translation works in a non-contiguous memory allocation scheme.8. How does a virtual memory scheme differ from a non-contiguous memory allocation scheme?What are the benefits of using a virtual memory scheme?9. What is a page fault?10. What is a locality? What is the principle of locality?11. What are the various policies for describing a virtual memory scheme?12. Why is buffering important in an operating system?13. In a Linux filesystem with a block size ofQ= 4096 bytes and inodes with 15 direct blockpointers, what is the maximum file size? Assume that an indirect inode block has a maximumof 1024 pointers.14. Given the parameters described in Question 13 above, how many indirect blocks are requiredfor a file of size 33,333 bytes? How about for a file of size 307,200,000 bytes? And for a fileof size 307,200,000,000 bytes?Remember that indirect blocks do not contain data15. What is a File Allocation Table (FAT)? How does it differ from an inode based file system?2 16. Consider a contiguous memory allocation scheme with dynamic partitioning for a 64MBphysical memory with five pre-allocated processes (i.e.,A,R,C,H, andX) that just happen tohave memory requirements that are evenly divisible by 1MB.Given new processesF,U, andNthat arrive (almost) simultaneously in the order shown below,show how memory allocation occurs for each of the given placement algorithms.Arrival Order ProcessID Memory Requirements=======================================================1 F 2,987,642 bytes2 U 4,002,016 bytes3 N 6,202,454 bytes=======================================================Note that if a process cannot be placed, be sure to state that, then move on to the nextprocess. Donotperform defragmentation.ˆFor the memory allocation shown below, apply theFirst-Fitalgorithm:Memory:AAAAAAAAA......R (each character here represents 1MB)RRRRRR.....CCCCCCCCC...HHHHHHHHHHHHH.........XXXˆFor the memory allocation shown below, apply theBest-Fitalgorithm:Memory:AAAARRRRRRRRRRRRRRRRRRRR....CCCCCCCCC...HHHHHHHHHHHHHH.......XXXˆFor the memory allocation shown below, apply theNext-Fitalgorithm,with processHbeing the last-placed process:Memory:AAAAAAAAAA.....RRRRRRRRR.....CCCCCCCCC...HHHHHHHHHHH........XXXX17. For each of the above algorithms, how much space is unused after the processes are allocatedto memory?18. Perform defragmentation on the above memories (after all processes have been placed).3 19. Consider a non-contiguous memory allocation scheme in which a logical memory address isrepresented using 32 bits. Of these bits, the high-order 12 bits represent the page number;the remaining bits represent the page offset.ˆWhat is the total logical memory space (i.e., how many bytes are addressed)?ˆHow many pages are there?ˆWhat is the page size?ˆWhat is the frame size?ˆHow does logical memory address 23,942,519 (binary 1011011010101010101110111) mapto physical memory (i.e., what is the logical page number and page offset)?ˆIf a process requires 78,901,234 bytes of memory, how many pages will it require?ˆHow many bytes are unused due to fragmentation?ˆGiven that the page table is stored entirely in memory and a memory reference takes100 nanoseconds, how long does a paged memory reference take?ˆAdding a translation look-aside buffer (TLB) with a TLB access time of 15 nanoseconds,how long does a paged memory reference take if a TLB hit occurs?ˆGiven a TLB hit ratio of 94%, what is the effective memory access time (EMAT)?20. In a virtual memory scheme, given a page reference string and a 3-frame memory, how manypage faults occur for the following page replacement algorithms: FIFO; OPT; LRU; LFU.Repeat the above for a 4-frame memory.Page Reference Stream:1 8 4 8 4 3 8 3 4 7 1 7 2 3 2 4 2 7 821. Given a page reference string and a working set delta, identify the working set at the pointindicated below. Also show the working set at each step beyond the point indicated below.Page Reference Stream:1 9 4 8 4 3 8 3 4 7 1 7 2 3 2 4 2 7 8^|Use a ∆ of 3, 5, 8, then 10.4