answer.f21.midterm.cs149

pdf

School

University of Southern California *

*We aren’t endorsed by this school

Course

317

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by CountSwan3693

ANSWER KEYS CS149 Operating Systems Midterm Exam I, Written Fall 2021 Q#1 (6pt) (Chapter 16: Segmentation) You could answer the questions with and without the help of the running the simulator program as follows: • ARG seed 1617 • ARG address space size 1k • ARG phys mem size 16k Base-and-Bounds register information: Base : 0x00002b72 (decimal 11122) Limit : 471 1. (2pt) VA 0: 0x000000fb (decimal: 251) --> o ____ valid ______ [fill in valid or invalid), o if valid, fill in the translated address in hexadecimal and decimal format) hexadecimal address 0x____ 00002c6d ______ (in the format of NNNNNNNN, where N is a hex digits 0-9 or A-F) decimal address __ 11373 ___ (in the format of NNNNN, where N is a decimal digits 0- 9) 2. (2pt) VA 1: 0x00000331 (decimal: 817) --> o ______ invalid ____ [fill in valid or invalid), o if valid, fill in the translated address in hexadecimal and decimal format) hexadecimal address 0x__________ decimal address __________ 3. (2pt) VA 9: 0x000000a5 (decimal: 165) --> o ___ valid _______ [fill in valid or invalid), o if valid, fill in the translated address in hexadecimal and decimal format) hexadecimal address 0x. 00002c17 decimal address 11287

Q#2 (24pt) (Chapter 10: Multiprocessor Scheduling) 1. (2pt) To start things off, let’s learn how to use the simulator to study how to build an effective multi-processor scheduler. The first simulation will run just one job, which has a run-time of 30, and a working-set size of 200. Run this job (called job ’a’ here) on one simulated CPU as follows: ./multi.py -n 1 -L a:30:200 How long will it take to complete? ______________ Turn on the -c flag to see a final answer, and the -t flag to see a tick-by-tick trace of the job and how it is scheduled. 2. (2pt) Now increase the cache size so as to make the job’s working set (size=200) fit into the cache (which, by default, is size=100); for example, run ./multi.py -n 1 -L a:x:200 -M 300 -r y, where x = 30, 50, 70, 90, and y = 2,3,4,5 Give the formulation of how fast the job will run once it fits in cache, as follows. The run time will be ___________________ in the format of A + ( B – C)/D • A = ____10__________ • B = _____x_________ • C = ______10________ • D = y (hint: remember the key parameter of the warm rate, which is set by the -r flag) Check your answer by running with • -C, --trace_cache o trace cache status (warm/cold) too • -c, --compute o compute answers for me • -T, --trace_time_left o trace time left for each job

3. (2pt) At this point, you should have a good idea of how the simulator works for a single job running on a single CPU. But hey, isn’t this a multi - processor CPU scheduling chapter? Oh yeah! So let’s start working with multiple jobs. Specifically, let’s run the followi ng three jobs on a two-CPU system, i.e., type ./multi.py -n 2 -L a:100:100,b:100:50,c:100:50 • How long this will take, given a round-robin centralized scheduler? o _______150_______ • (y/n) Does any job ever run the processor who cache is fully loaded with job's working set (warmed up for the job)? o ________n ______ Use -c to see if you were right, and then dive down into details with -t to see a step-by-step and then -C to see whether caches got warmed effectively for these jobs. 4. (6pt) Now we’ll apply some explicit controls to study cache affinity, as described in the chapter. To do this, you’ll need the -A flag. This flag can be used to limit which CPUs the scheduler can place a particular job upon. In this case, let’s use it to place jobs ’b’ and ’c’ on CPU 1, while restricting ’a’ to CPU 0. This magic is accomplished by typing this ./multi.py -n 2 -L a:100:100,b:100:50,c:100:50 -A a:0,b:1,c:1 don’t forget to turn on various tracing options to see what is really happening! • How fast this version will run? o Finished time = _____ 110 ________ • Give the CPU 0 utilization ___P___ % o P = ____50_________ • Give the CPU 1 utilization ___Q___% o Q = ____ 100 _________ • (y/n) Will any other combinations of ’a’, ’b’, and ’c’ onto the two processors run any faster? o ______n_______ • Give the other combination -A a:___X___,b:___Y___,c:___C___ that will also run as fast as -A a:0,b:1,c:1 o X = ____0_________ o Y = _____1________ o Z = _____1________

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

5. (2pt) One interesting aspect of caching multiprocessors is the opportunity for better-than- expected speed up of jobs when using multi- ple CPUs (and their caches) as compared to running jobs on a single processor. Specifically, when you run on N CPUs, sometimes you can speed up by more than a factor of N, a situation entitled super-linear speedup. To experiment with this, use the job description (-L a:100:100,b:100:100,c:100:100) with a small cache (-M 50) to create three jobs. Run this on systems with 1, 2, and 3 CPUs (-n 1,-n 2,-n 3). Use -c to confirm your guesses, and other tracing flags to dive even deeper. • ./multi.py -L a:100:100,b:100:100,c:100:100 -C -t -c -M 50 -n 1 o Finished time ______ 300 ___________ • ./multi.py -L a:100:100,b:100:100,c:100:100 -C -t -c -M 50 -n 2 o Finished time _______150__________ • ./multi.py -L a:100:100,b:100:100,c:100:100 -C -t -c -M 50 -n 3 o Finished time _______100__________ 6. (2pt) Now, do the same, but with a larger per-CPU cache of size 100. What do you notice about performance as the number of CPUs scales? • ./multi.py -L a:100:100,b:100:100,c:100:100 -C -t -c -M 100 -n 1 o Finished time : ____300_________ • ./multi.py -L a:100:100,b:100:100,c:100:100 -C -t -c -M 100 -n 2 o Finished time : _____150________ o (y/n) Is there a super-linear speedup against the above run : _____n________ • ./multi.py -L a:100:100,b:100:100,c:100:100 -C -t -c -M 100 -n 3 o Finished time : _______55______ o (y/n) Is there a super-linear speedup against the above run = _______y__________ 7. (8pt) One other aspect of the simulator worth studying is the per-CPU scheduling option, the - p flag. Run with two CPUs again, and this three job configuration (-L a:100:100,b:100:50,c:100:50). In particular, do the following experiments and fill in the answers, where x is an integer that means for per-cpu scheduling, how often to peek at other schedule queue; 0 turns this off • ./multi.py -L a:100:100,b:100:50,c:100:50 -C -t -p -n 1 -c -P x o -P 0: Finished time = _____300__________ • ./multi.py -L a:100:100,b:100:50,c:100:50 -C -t -p -n 2 -c -P x o -P 1: Finished time = ______90_______ (y/n) The finished time is better than that in Q#4 ________y_________

o -P 7: Finished time = ______100___________ (y/n) The finished time is better than that in Q#4 ______y___________ o -P 190: Finished time = _____200____________ (y/n) The finished time is better than that in Q#4 _______3__________ • ./multi.py -L a:100:100,b:100:50,c:100:50 -C -t -p -n 3 -c -P x o -P 0: Finished time = _____55____________ • How does this option do, as opposed to the hand-controlled affinity limits you put in place above? o _________________ • How does performance change as you alter the ’peek interval’ ( -P) to lower or higher values? o _________________ • How does this per-CPU approach work as the number of CPUs scales? o _________________

11/15/21, 1 : 36 PM HW #10: Two-Level Page-Table Scheme: FA21: CS-149 Sec 02 - Operating Systems Page 1 of 8 https://sjsu.instructure.com/courses/1433630/quizzes/1512507 ? module_item_id=12489173 HW #10: Two-Level Page-Table Scheme Due Oct 14 at 11:59pm Points 10 Questions 1 Available after Oct 5 at 12am Time Limit None Allowed Attempts 3 Instructions Two-Level Page-Table Scheme Below are the program and its readme file for this experiments. README.md (https://sjsu.instructure.com/courses/1433630/files/64305157/download? download_frd=1) paging-multilevel-translate.py (https://sjsu.instructure.com/courses/1433630/files/64305155/download?download_frd=1) (Reference: lecture7-SmallerTables.pptx (https://sjsu.instructure.com/courses/1433630/files/65923319/download?download_frd=1) ) # Overview This fun little homework tests if you understand how a multi-level page table works. And yes, there is some debate over the use of the term fun in the previous sentence. Some basic assumptions: * The page size is an unrealistically small 32 bytes (5 bits for page offset) * The virtual address space for the process in question (assume there is only one) is 1024 pages, or 32 KB * physical memory consists of 128 pages (7 bits for PFN) Thus, a virtual address needs 15 bits (10 bits for the VPN, 5 bits for the page offset). a physical address requires 12 bits ( 7 bits for the PFN, 5 bits for the page offset). The system assumes a multi-level page table. Thus, the upper five bits of a virtual address are used to index into a page directory;

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

11/15/21, 1 : 36 PM HW #10: Two-Level Page-Table Scheme: FA21: CS-149 Sec 02 - Operating Systems Page 2 of 8 https://sjsu.instructure.com/courses/1433630/quizzes/1512507 ? module_item_id=12489173 the page directory entry (PDE), if valid, points to a page of the page table. Each page table page holds 32 page-table entries (PTEs). Each PTE, if valid, holds the desired translation (physical frame number, or PFN) of the virtual page in question. The format of a PTE is thus: VALID, PFN6, ... . PFN0. and is thus 8 bits or 1 byte. The format of a PDE is essentially identical: VALID, PT6, ... , PT0 You are given two pieces of information to begin with.

11/15/21, 1 : 36 PM HW #10: Two-Level Page-Table Scheme: FA21: CS-149 Sec 02 - Operating Systems Page 3 of 8 https://sjsu.instructure.com/courses/1433630/quizzes/1512507 ? module_item_id=12489173 First, you are given the value of the page directory base register (PDBR), which tells you which page the page directory is located upon. Second, you are given a complete dump of each page of memory. A page dump looks like this: page 0: 08 00 01 15 11 1d 1d 1c 01 17 15 14 16 1b 13 0b ... page 1: 19 05 1e 13 02 16 1e 0c 15 09 06 16 00 19 10 03 ... page 2: 1d 07 11 1b 12 05 07 1e 09 1a 18 17 16 18 1a 01 ... ... which shows the 32 bytes found on pages 0, 1, 2, and so forth. The first byte (0th byte) on page 0 has the value 0x08, the second is 0x00, the third 0x01, and so forth. You are then given a list of virtual addresses to translate. Use the PDBR to find the relevant page table entries for this virtual page. Then find if it is valid. If so, use the translation to form a final physical address. Using this address, you can find the VALUE that the memory reference is looking for. Of course, the virtual address may not be valid and thus generate a fault. Below is an example: Memory Specifications: Read the memory contents in 2level.page.table.txt (https://sjsu.instructure.com/courses/1433630/files/64304977/download?download_frd=1) PDBR: 108 (decimal) [This means the page directory is held in this page] Virtual Address 611c: Translates To What Physical Address (And Fetches what Value)? Or Fault? Virtual Address 3da8: Translates To What Physical Address (And Fetches what Value)? Or Fault? Virtual Address 17f5: Translates To What Physical Address (And Fetches what Value)? Or Fault? Virtual Address 7f6c: Translates To What Physical Address (And Fetches what Value)? Or Fault? Virtual Address 0bad: Translates To What Physical Address (And Fetches what Value)? Or Fault? Virtual Address 6d60: Translates To What Physical Address (And Fetches what Value)? Or Fault?

11/15/21, 1 : 36 PM HW #10: Two-Level Page-Table Scheme: FA21: CS-149 Sec 02 - Operating Systems Page 4 of 8 https://sjsu.instructure.com/courses/1433630/quizzes/1512507 ? module_item_id=12489173 Virtual Address 2a5b: Translates To What Physical Address (And Fetches what Value)? Or Fault? Virtual Address 4c5e: Translates To What Physical Address (And Fetches what Value)? Or Fault? Virtual Address 2592: Translates To What Physical Address (And Fetches what Value)? Or Fault? Virtual Address 3e99: Translates To What Physical Address (And Fetches what Value)? Or Fault? Then, after you have computed the translations in the virtual address trace, use the following answer keys (not including the redundant information) to verify your computations. Hence you can check if you understand how a system using paging multilevel translates addresses. PDBR: 108 (decimal) [This means the page directory is held in this page] Virtual Address 611c: --> pde index:0x18 [decimal 24] pde contents:0xa1 (valid 1, pfn 0x21 [decimal 33]) --> pte index:0x8 [decimal 8] pte contents:0xb5 (valid 1, pfn 0x35 [decimal 53]) --> Translates to Physical Address 0x6bc --> Value: 08 Virtual Address 3da8: --> pde index:0xf [decimal 15] pde contents:0xd6 (valid 1, pfn 0x56 [decimal 86]) --> pte index:0xd [decimal 13] pte contents:0x7f (valid 0, pfn 0x7f [decimal 127]) --> Fault (page table entry not valid) Virtual Address 17f5: --> pde index:0x5 [decimal 5] pde contents:0xd4 (valid 1, pfn 0x54 [decimal 84]) --> pte index:0x1f [decimal 31] pte contents:0xce (valid 1, pfn 0x4e [decimal 78]) --> Translates to Physical Address 0x9d5 --> Value: 1c Virtual Address 7f6c: --> pde index:0x1f [decimal 31] pde contents:0xff (valid 1, pfn 0x7f [decimal 127]) --> pte index:0x1b [decimal 27] pte contents:0x7f (valid 0, pfn 0x7f [decimal 127]) --> Fault (page table entry not valid) Virtual Address 0bad: --> pde index:0x2 [decimal 2] pde contents:0xe0 (valid 1, pfn 0x60 [decimal 96]) --> pte index:0x1d [decimal 29] pte contents:0x7f (valid 0, pfn 0x7f [decimal 127]) --> Fault (page table entry not valid) Virtual Address 6d60:

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

11/15/21, 1 : 36 PM HW #10: Two-Level Page-Table Scheme: FA21: CS-149 Sec 02 - Operating Systems Page 5 of 8 https://sjsu.instructure.com/courses/1433630/quizzes/1512507 ? module_item_id=12489173 Attempt History Attempt Time Score KEPT Attempt 3 5 minutes 10 out of 10 LATEST Attempt 3 5 minutes 10 out of 10 Attempt 2 17 minutes 8 out of 10 Attempt 1 29 minutes 6 out of 10 Score for this attempt: 10 out of 10 Submitted Oct 14 at 8:59pm --> pde index:0x1b [decimal 27] pde contents:0xc2 (valid 1, pfn 0x42 [decimal 66]) --> pte index:0xb [decimal 11] pte contents:0x7f (valid 0, pfn 0x7f [decimal 127]) --> Fault (page table entry not valid) Virtual Address 2a5b: --> pde index:0xa [decimal 10] pde contents:0xd5 (valid 1, pfn 0x55 [decimal 85]) --> pte index:0x12 [decimal 18] pte contents:0x7f (valid 0, pfn 0x7f [decimal 127]) --> Fault (page table entry not valid) Virtual Address 4c5e: --> pde index:0x13 [decimal 19] pde contents:0xf8 (valid 1, pfn 0x78 [decimal 120]) --> pte index:0x2 [decimal 2] pte contents:0x7f (valid 0, pfn 0x7f [decimal 127]) --> Fault (page table entry not valid) Virtual Address 2592: --> pde index:0x9 [decimal 9] pde contents:0x9e (valid 1, pfn 0x1e [decimal 30]) --> pte index:0xc [decimal 12] pte contents:0xbd (valid 1, pfn 0x3d [decimal 61]) --> Translates to Physical Address 0x7b2 --> Value: 1b Virtual Address 3e99: --> pde index:0xf [decimal 15] pde contents:0xd6 (valid 1, pfn 0x56 [decimal 86]) --> pte index:0x14 [decimal 20] pte contents:0xca (valid 1, pfn 0x4a [decimal 74]) --> Translates to Physical Address 0x959 --> Value: 1e

11/15/21, 1 : 36 PM HW #10: Two-Level Page-Table Scheme: FA21: CS-149 Sec 02 - Operating Systems Page 6 of 8 https://sjsu.instructure.com/courses/1433630/quizzes/1512507 ? module_item_id=12489173 This attempt took 5 minutes. 10 / 10 pts Question 1 Read the following example and answer the questions below. Note use lowercase for the hexadecimal digits a-f in your answers. See the memory contents in 2level.page.table.Q1.txt (https://sjsu.instructure.com/courses/1433630/files/64304956//download? download_frd=1) PDBR: 17 (decimal) [This means the page directory is held in this page] Virtual Address 03df: (0x03df = 00000, 11110, 11111 ) --> pde index:0x0 [decimal 0] pde contents:0xda = 1,101 1010 (valid 1, pfn 0x5a [decimal 90]) --> pte index:0x1e [decimal 30] pte contents:0x85 = 1,000 0101 (valid 1, pfn 0x05 [decimal 5]) --> Translates to Physical Address 0x0bf (0000 101,1 1111 )--> Value: 0f Virtual Address 6b22: (6b22 = 0110 1011 0010 0010 = 0, 11010 , 11001 , 00010 ) --> pde index:0x1a [decimal 26] pde contents:0xd2 (valid 1, pfn 0x52 [decimal 82]) --> pte index:0x19 [decimal 25] pte contents:0xc7 (valid 1, pfn 0x47 [decimal 71]) --> Translates to Physical Address ___A1___ ---> Value: ___A2___ A1 = 0x 8e2 . (3-digit hexadecimal xxx, where x is 0-9 or a-f) hint: pfn 0x47 = 100 0111 (PFN) + 0 0010 (page offset 2 2 2 2 2 2 2 2

11/15/21, 1 : 36 PM HW #10: Two-Level Page-Table Scheme: FA21: CS-149 Sec 02 - Operating Systems Page 7 of 8 https://sjsu.instructure.com/courses/1433630/quizzes/1512507 ? module_item_id=12489173 Answer 1: hint: pfn 0x47 = 100 0111 (PFN) + 0 0010 (page offset ) A2 = 1a (2-digit hexadecimal xx) Virtual Address 6c74: --> pde index:0x1b [decimal 27] pde contents: ___B1___ (valid ___B2__, pfn ___B3___ [decimal ______]) --> pde index:0x3 [decimal 3] pde contents: ___B4___ (valid ___B5__, pfn ___B6___ [decimal ______]) --> Translates to Physical Address ___B7___ ---> Value: ___B8___ B1 = 0x a0 (2-digit hexadecimal xx) B2 = 1 (fill in 1 if valid otherwise 0) B3 = 0x 20 (2-digit hexadecimal xx) B4 = 0x e1 (2-digit hexadecimal xx) B5 = 1 (fill in 1 if valid otherwise 0) B6 = 0x 61 . (2-digit hexadecimal xx) B7 = 0x c34 (3-digit hexadecimal xxx) B8 = 06 . (2-digit hexadecimal xx) 2 2 8e2 Correct! Correct!

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

11/15/21, 1 : 36 PM HW #10: Two-Level Page-Table Scheme: FA21: CS-149 Sec 02 - Operating Systems Page 8 of 8 https://sjsu.instructure.com/courses/1433630/quizzes/1512507 ? module_item_id=12489173 Answer 2: Answer 3: Answer 4: Answer 5: Answer 6: Answer 7: Answer 8: Answer 9: Answer 10: 1a Correct! Correct! a0 Correct! Correct! 1 Correct! Correct! 20 Correct! Correct! e1 Correct! Correct! 1 Correct! Correct! 61 Correct! Correct! c34 Correct! Correct! 06 Correct! Correct! Quiz Score: 10 out of 10

answer.f21.midterm.cs149

Related Documents