School of Computing and Information Systems
COMP30023: Computer Systems
Tutorial Week 4
Process scheduling and memory management
Copyright By PowCoder代写 加微信 powcoder
1. Five batch jobs, A through E, arrive at a computer centre at almost the same time. They have estimated running times of 10, 6, 2, 4, and 8 minutes. Their (externally determined) priorities are 3, 5, 2, 1, and 4, respectively, with 5 being the highest priority. For each of the follow- ing scheduling algorithms, determine the mean process turnaround time. Ignore process switching overhead. (a) Round robin with quantum of 6 minutes. (b) Priority scheduling. (c) First-come, first-served (run in order 10, 6, 2, 4, 8). (d) Shortest job first. For (b) through (d), assume that only one job at a time runs, until it finishes. All jobs are completely CPU bound.
2. Give an arithmetic expression connecting a given virtual address with the corresponding page number and offset. What does this tell you about page sizes that are not powers of two?
3. How much physical memory do you need to store a page table which describes 512 KB of memory given a page size of 512 bytes? Assume that Page Table Entries (PTEs) are 4 bytes.
(a) What if 4 GB of memory need to be described? (b) What if the page size is increased to 8 KB?
4. You are given the following data about a virtual memory system:
(a) The TLB can hold 1024 entries and can be accessed in 1 clock cycle (1 nsec).
(b) A page table entry can be found in 100 clock cycles or 100 nsec. (c) The average page replacement time is 6 msec.
If page references are handled by the TLB 99% of the time, and only 0.01% lead to a page fault, what is the effective address-translation time?
5. Working set page replacement algorithm will first try to evict pages that are not in the working set before evicting pages in the working set. Under what type of access locality does a working set algorithm perform best (i.e., minimise number of page faults) and why?
Continued on the next page
Weekly tutorial participation activity
To obtain a weekly tutorial mark (1% of your overall mark for the subject, totalling to 10% over the semester), please answer the following questions in Canvas Quiz (called Week 4 Tutorial Activity). You can have multiple attempts but need to submit the quiz by 11:59 pm AEDT on the day of your tutorial. Only answering all questions correctly will give you the week¡¯s mark.
During the tutorial, your tutor will provide you with the access code that will unlock the quiz for the corresponding week. The access code is valid only for students in this tutorial. As a result, we expect you to attend your tutorial class as otherwise the access code you obtain in another tutorial will not work for you.
If you have a valid reason for not being able to attend your tutorial, please fill in the form accessible via Canvas by Friday 8pm AEDT of the corresponding week. You will be given an access code during the next business day. The code will not be provided otherwise, hence, please do not email the subject coordinator or other staff members including your tutor asking for the code. We will monitor such requests and may limit the number of times an access code is given to the same student throughout the semester to encourage participation and attendance of the tutorials.
1. Four batch jobs, W, X, Y and Z arrive at a computer centre at almost the same time. They have estimated running times of 10, 6, 2, and 5 minutes. Their (externally determined) priorities are 3, 4, 2, 1, respectively, with 4 being the highest priority. In which order will these jobs run if round robin with quantum of 4 minutes is used to completion of all jobs. Use process names to break ties giving priority according to alphabetical order (e.g., W runs before Z).
(a) W,X,Y,Z,W,X,Z,W (b) W,X,Y,Z,W,X,W
(c) Y,Z,X,W,X,W
(d) W,X,Y,W,Z,X,Z,W
2. Given the page table in Figure 2, what is the physical address of the virtual address 128?
(a) 8320 (b) 128
(c) 8328 (d) 4096 (e) 9328
Figure 1: Page table from Fig 3.9 Tanenbaum & Bos, Modern Operating Sys- tems: 4th ed.
3. Consider a swapping system in which memory consists of the following hole sizes in memory order: 10 MB, 4 MB, 20 MB, 18 MB, 7 MB, 9 MB,12 MB, and 15 MB. Which hole is taken for successive segment requests of (1) 12 MB (2) 10 MB (3) 9 MB for first fit; best fit and worst fit algorithms?
(a) 20,10,9; 20,18,15; 12,10,18 (b) 15,12,10; 12,10,9; 20,18,9
(c) 20,10,18; 12,10,9; 20,18,15 (d) 15,10,18; 12,10,9; 20,18,15
4. A computer has four page frames. The time of loading, time of last access, and the R and M bits for each page are as shown below in Table 1 (the times are in clock ticks). Which algorithm among NRU, FIFO, LRU or second chance would choose page 1 for replacement?
Loaded Last ref. R M 126 280 1 0 230 265 0 1 140 270 0 0 110 285 1 1
(b) LRU (c) NRU
(d) second chance
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com