1. CPU Scheduling.
COMP 2432 Operating Systems Solution to Written Assignment 1
122244222111111155555555333333333
Pid Burst Arr Prior Wait TR 1 8 0 3 8 16 261428 3 9 2 2 22 31 424502 5 8 5 1 11 19
Copyright By PowCoder代写 加微信 powcoder
(b) Priority with Preemption (Linux)
113335555555533333311111122222244
Pid Burst Arr Prior Wait TR 1 8 0 3 17 25 2 6 1 4 24 30 3 9 2 2 8 17 4 2 4 5 27 29 585108
(c) Priority with Preemption (Windows)
122244222111111133333333355555555
Pid Burst Arr Prior Wait TR 1 8 0 3 8 16 261428 3 9 2 2 14 23 424502 5 8 5 1 20 28
(d) RR, q = 3
111222333111445552223331155533355
Pid Burst Arr Prior Wait TR
1 8 0 3 17 25
2 6 1 4 13 19
3 9 2 2 20 29
4 2 4 5 8 10
5 8 5 1 20 28
(e) RR, q = 2
112211332244551133225511335533553
Pid Burst Arr Prior Wait TR 1 8 0 3 16 24 2 6 1 4 13 19 3 9 2 2 22 31 424568 5 8 5 1 19 27
(f) RR, q = 1 (used for responsiveness)
112132143521435213521352135353535
(f) Algorithm
Average resp. (k = 3, w = 0.8) P1
Average resp. (k = 2, w = 0.8)
11.744 18.944 5.600 28.320 27.856 10.976 1.600 28.600 16.344 5.344 12.629 18.437 11.123 15.603 5.184 27.904 27.051 10.171 1.600 28.600 15.723 4.723 12.136 17.400
11.744 14.816 15.136 5.600 13.360 13.640 19.856 19.456 22.144 1.600 9.600 7.600 25.344 21.000 20.728 12.829 15.646 15.850 11.123 13.069 12.557 5.184 12.944 11.560 19.051 18.139 18.717 1.600 9.600 7.600 24.723 20.072 18.430 12.336 14.765 13.773
15.616 16.520 20.752
7.800 20.448 16.227 13.197 14.696 18.150
7.800 18.630 14.495
Here are some possible observations. SRT is proved to produce the best average waiting time. Therefore it is also likely that it also produces the best responsiveness. However, SRT is a biased algorithm that favors short processes at the expense of long processes. It can be seen that P3 suffers the most (worst performance across all other algorithms). Priority with preemption (Windows) produces better performance than Priority with preemption (Linux) for this specific input, but the performance is not stable, since the priority is independent of process arrival nor burst time. Similar trend can be observed for the average turnaround times for the two priority conventions, i.e. 21.8 vs 15.4, with Windows convention performing better by a margin of 6.4. It can be seen that the performance for RR algorithms is not stable when varying the time quantum. However, generally, the performance for k=2 is better than k=3. One major reason is that there are more responses generated per process with a smaller value of k, and that could help to amortize the relatively high “first” response time when each process is first allocated the CPU. As a comparison on the effect of time quantum, consider FCFS meaning an infinite time quantum for RR. The average responsiveness would be 16.093 (better than RR -1) and 15.600 (worse than RR -1/2/3) respectively.
2. Multi-level Scheduling. Fixed Priority Scheduling.
Summarizing
Q1: 11221 13322 44553 34455
Time Slicing Scheduling.
11122 23334 45551 12223 33555
Multi-level Feedback Queue: fixed priority
Processes on queue 1 can begin
11221 13322 44553 34455
Queue 1 becomes empty at time 20
Processes on queue 2 can now begin
11122 23334 45551 12223 33555
Queue 2 becomes empty at time 45
Processes on queue 3 can now begin
Queue 2 becomes empty at time 54
23333 3355
23333 3355
Pid Burst Arr Prior Wait TR 1 9 0 3 27 36 211 1 4 34 45 316 2 2 34 50 4 6 4 5 21 27 512 5 1 37 49
Multi-level Feedback Queue: time slicing
Pay attention to the moment when each queue uses up its allocated time
Processes on queue 1 can begin, P1 is there initially
Queue 1 uses up its time slice at time 8
Processes on queue 2 can now begin, only P1 is there
Queue 2 completes all its processes at time 13
Queue 3 is empty at time 13
Queue 1 continues to use its next time slice
22 44553 3
Queue 1 uses up its time slice at time 21
Processes on queue 2 can now begin, P2, P3 are there in that order
Queue 2 uses up its time slice at time 27
Queue 3 is empty at time 27
Queue 1 continues to use its next time slice
Queue 1 completes all its processes at time 31
Processes on queue 2 can now begin, P2, P3, P4, P5 are there in that order
Queue 2 uses up its time slice at time 37
Processes on queue 3 can now begin, P2, P3 are there in that order
Queue 3 uses up its time slice at time 43
Queue 1 is empty at time 43
Queue 2 continues to use its next time slice, P4, P5 are there in that order
Queue 2 uses up its time slice at time 49
Queue 3 continues to use its next time slice, only P3 is there
Queue 3 becomes empty at time 50
Queue 1 is empty at time 50
Queue 2 continues to use its next time slice, only P5 is there
Queue 2 becomes empty at time 52
Queue 3 continues to use its next time slice, only P5 is there
Queue 3 becomes empty at time 54
Summarizing
Q1: 11221 133
Q2: 11 111
22 44553 3
44 5555 55
233 333 3 55
Pid Burst Arr Prior Wait TR 1 9 0 3 4 13 211 1 4 26 37 316 2 2 32 48 4 6 4 5 35 41 512 5 1 37 49
3. Contiguous Memory Allocation.
The following indicates filling up of holes by the tasks. Note that holes do not occupy consecutive memory space and there is a boundary between them composed of occupied memory space. The holes left behind after the allocation and the unfilled requests are painted in yellow and pink respectively. There are 6 possible ways to fill up the holes in an optimal manner.
Alg. FF BF WF Opt1 Opt2 Opt3 Opt4 Opt5 Opt6
146 hole 234 hole 175 hole Unfilled 80 44 11 11 96 52 65 18 3 77 26 54 18 31 28 80 44 11 11 65 77 54 31 7 96 52 26 1 28 18
Util. 96.8% 98.1% 97.3% 99.9% 99.9% 99.9% 99.9% 99.9% 99.9%
521177 6 963118 1 652654 1
80 65 1 52 65 11 18 44 65 11 26
80 44 65 28 17 96 26 31
80 52 65 11 26 44 96 44 52 11 31 80 96 44 52 11 31 77
96 52 11 26 31 18 44 80 96 26 31 1 44 80 96 26 31 1 80
(e) If the size of one of medium-sized tasks is under-reported, both scenario (ii) and (iii) would not suffer from a reduced utilization, but scenario (i) would suffer. There are three possible ways to achieve the best utilization for (ii) and (iii). Actually, there is a slightly improved utilization for these cases.
Alg. 146 hole 234 hole 175 hole
Optii 44651126 96535431 80 77 Optiii1 44651126 96525531 80 77 Optiii2 65 26 55 9644521131 80 77
Unfilled Util. 18 28 100.0% 18 28 100.0% 18 28 100.0%
(f,g,h) The following table indicates the maximum usage of the hole of size S and the respective number of tasks used. There may be more than one possible answers, as long as your collection of tasks can lead to the usage of 551, 772 and 567 respectively, with at most 9 tasks of each type in (f). Note that you cannot achieve full usage for all the cases. Even if we relax the requirement that there can be unlimited number of tasks of each type as in (g), the holes still cannot be completely filled, but the unused space is smaller for one case. Finally, if we further strengthen the requirement that tasks of all sizes must be included in (h), the same utilizations as in (f) can be achieved for two cases and there is a reduction in utilization for two cases.
(f) At most 9 tasks 168 263/8
538 510/0 740 658/6 555 600
(g) Unlimited number of tasks
(h) Strictly 1 to 9 tasks
342/5 512/0 778/8 789 786
1628/30 532/0 740/1 555
263/8/13/18/23 510/0/0/0/0 658/6/4/2/0 600
342/5 512/0 778/8 789 786
162/4/6/8 537/5/3/1 742/3/4/5 555
261/6 342 511/1 512 658/6 778
4. Segmentation.
Memory used: 0 to 999, 1002 to 1643, 1901 to 2221, 2432 to 2735, 3131 to 3661, 3911 to 4144, 4432 to 5218, 5678 to 6218, 6789 to 8191. So there are 8 holes (1000 to 1001, 1644 to 1900, 2222 to 2431, 2736 to 3130, 3662 to 3910, 4145 to 4431, 5219 to 5677, 6219 to 6788) to be allocated for 7 segments (you better draw three diagrams to show the memory allocation for the three segments with FF, BF, WF algorithms as in Tutorial 8, either horizontally or vertically).
First-fit allocates S0, S6 to 2nd hole, S2 to 4th hole, and S4 to 6th hole, S1 to 7th hole, and S3 to 8th hole. S5 is shared with S2 of P1.
Best-fit allocates S4 to 2nd hole, S0 to 3rd hole, S3, S6 to 4th hole, S2 to 5th hole, and S1 to 7th hole. S5 is shared with S2 of P1.
Worst-fit allocates S6 to 2nd hole, S3 to 4th hole, S4 to 6th hole, S2 to 7th hole, and S0, S1 to 8th hole. S5 is shared with S2 of P1.
Base (b) BF 2222 5219 3662 2736 1644
(d) Translating logical addresses into physical addresses.
Segment table for P2
(a) FF 1644 5219 2736 6219 4145
Length / Limit
6219 99 6318 456 5219 222 2736 288 4145 256
Physical address for P2
5540 6639 3763 5320 2970 2970 1843 4344 2735 2735 3101 1721
Allocation algorithm for P2
Logical address
(0, 88) (1, 321) (2, 101) (3, 234) (4, 199) (5, 303) (6, 77)
Physical address for P1
3999 error/invalild 2533
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com