1. CPU Scheduling.
COMP 2432 Operating Systems Written Assignment Submission to BlackBoard Deadline: 21 March 2022
Draw Gantt charts for the following set of processes using different scheduling algorithms: (a) SRT, (b) Priority with preemption (Linux convention), (c) Priority with preemption (Windows convention),
(d) RR with quantum Q = 3, and (e) RR with quantum Q = 2. Let us assume the standard tie-breaking rules when multiple processes are eligible, i.e., the process with smaller ID will go first. Compute the waiting time and turnaround time for each process under the algorithms (a) to (e).
Copyright By PowCoder代写 加微信 powcoder
Process Burst Time Arrival Time Priority P1 8 0 3
P4 2 4 5 P5 8 5 1
(f) Response time measures the time taken for the first response of a process. However, response time does not always provide a good measure for the responsiveness of interactive processes since it only measures the time taken for the first response. Assume that each process generates a response when it starts, and then a response just before the completion of each k time units until it finishes execution. It will also give a final answer (final response) by the moment that it finishes. We know that the first response is normally more important. As execution continues, subsequent responses are less and less a concern. Let us define a metric called responsiveness, which measures the weighted average for all responses. Taking the second SJF example in the lecture with k = 3, P1 will execute from 0 to 8. The first response comes when P1 first gets the CPU. It will generate a response every 3 time units. The first response comes at 0, the second response at time 3, the third at time 6, and the final at time 8. Thus, the 4 response times are 0, 3 (3-0), 3 (6-3), and 2 (8-6). There is also a weighting factor w. The first response will take a weight of 1, the second response a weight of w, the third a weight of w2, the fourth a weight of w3, and so on. The weighted sum will be the responsiveness. Let w = 0.9. The responsiveness for P1 will be 01 + 30.9 + 30.92 + 20.93 = 6.588. P2 will execute from 8 to 12. The first response comes at 8, the second at 11, the final at 12. The response times for P2 are 7, 3, and 1. The responsiveness for P2 will be 71 + 30.9 + 10.92 = 10.51. Likewise, responsiveness for P3 and P4 are 22.317 and 13.32. The responsiveness of the processes for the SRT example with k = 3 and w = 0.9 would be 14.688, 3.51, 22.317, and 6.32. Compute the responsiveness for the algorithms in (a) to (e) for each process, as well as the average value for the 5 processes, assuming that k = 3 and w = 0.8. Compute also the responsiveness for the extreme case of RR with quantum Q = 1. Now assume that k = 2 and w = 0.8, repeat the computation for responsiveness. Do you have any observation by comparing the responsiveness across the cases?
2. Multi-level Scheduling.
A multi-level feedback queue is adopted to schedule the following processes for execution. Processes first enter the high priority queue based on RR with quantum 2. A process that cannot complete its execution
after a service time of 4 will be demoted to the medium priority queue based on RR with quantum 3. A process that cannot complete its execution after a service time of 6 in this queue will be demoted to the low priority queue based on FCFS.
(a) Assume that Fixed Priority scheduling is adopted. Draw a Gantt chart for the process execution schedule. Compute the process waiting and turnaround time and their average.
(b) Assume that Time Slicing scheduling is adopted with a ratio of 4:3:3 in allocated time slices, in the format of 8 time units, 6 time units and 6 time units respectively on the three queues. Draw a Gantt chart for the process execution schedule. Compute the process waiting and turnaround time and their average.
Process Burst Time Arrival Time Priority P1 9 0 3
P4 6 4 5 P5 12 5 1
3. Contiguous Memory Allocation.
A memory system currently has three holes of size 146K, 234K, and 175K and the total memory is 1000K. You are given 12 requests: 80, 96, 44, 52, 65, 11, 77, 26, 54, 31, 28, and 18K, arriving in that order. Indicate how the requests are satisfied with (a) first-fit algorithm, (b) best-fit algorithm, (c) worst- fit algorithm, and (d) an optimal algorithm that makes a decision after seeing all requests using an oracle. There are multiple possible answers for the optimal algorithm. You are to give two possible answers to (d). What are the utilizations for the four algorithms?
(e) It is found that one medium-sized task has under-reported its size by 1K. The suspected task could be one of those with sizes 44K, 52K or 54K. There could be some effect on the best utilization if (i) 44K becomes 45K, (ii) 52K becomes 53K, (iii) 54K becomes 55K. Two of the three scenarios would not have affected the best utilization. Give any one of such request satisfaction scenarios with the new request.
(f) You are given some tasks of size xK, yK and zK respectively and there are at most 9 tasks each. Determine the best that you could achieve if you are to fill up a hole of size SK, for the following values of x, y, z and S, by minimizing the unused space left, if any. Show how many tasks of size x, how many of size y and how many of size z are used in each case. (g) Now if we relax the requirement so that there are no upper limit on the number of tasks for each type, determine the minimal unused space left and the task mix. (h) If we tighten the requirement so that there are still at most 9 tasks of each size, but we also require that each type of tasks must be used at least once, determine the minimal unused space left and the task mix.
x 16 26 34 y 53 51 51 z 74 65 77 S 555 600 789
4. Segmentation.
Consider the segment table for process P1 containing the following.
P1 Segment Base
Length / Limit 234
Suppose that segment 2 of P1 is a shared segment with segment 5 of P2, and P2 has 7 segments of size 99, 456, 222, 288, 256, 304 and 78 respectively, starting from segment 0 to segment 6. Note that segment 2 of P1 has the same size as segment 5 of P2, since it is shared. Assume that the computer has a memory of 8KB allocated for users, with physical address from 0 to 8191. Those bytes at the lowest end of the memory as well as those at the highest end of the memory, from 0 to 999, and from 6789 to the end, are reserved by the operating system. Segments for P2 are to be allocated from the free memory in the order of 0, 1, 2, 3, 4, 5, and 6, if necessary, using (a) first-fit algorithm, (b) best-fit algorithm, (c) worst-fit algorithm. Show the three segment tables for P2 for segments allocated under the three algorithms. Note that it is useful to draw diagrams showing the memory allocation to the used segments for clarity.
(d) Translate the following logical addresses for P1 and P2 by filling in the table below.
Allocation algorithm for P2
Physical address for P2
Logical address (0, 88)
Physical address for P1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com