CS109 HW3 - Homework 3; 7.5% of overall grade in the course. Answers are provided with explanations. PDF

Preview

Summary

Homework 3; 7.5% of overall grade in the course. Answers are provided with explanations....

Description

Homework 3 Problem 1: Programming a. The program will print 9 for the given inputs, which is given by the following: N = 1000 b=2 a=0 n=N while n >= b n=n/b a=a+1 print a So, it does this: while n >= 2 //condition is met here n = 1000 / 2 //n=500 a=1 while n >=2 //condition still met n = 500 / 2 //n=250 a=2 while n >=2 //condition still met n = 250 / 2 //n=125 a=3 while n >=2 //condition still met n = 125 / 2 //n=62 a=4 while n >=2 //condition still met n = 62 / 2 //n=31 a=5 while n >=2 //condition still met n = 31 / 2 //n=15 a=6 while n >=15 //condition still met n = 31 / 2 //n=7 a=7 while n >=2 //condition still met n=7/2 //n=3 a=8 while n >=2 //condition still met n = 31 / 2 //n=1 a=9 /* loop terminates after this iteration condition is no longer met */ Page 1! of 5!

b. If N were initialized to 1024 ⋅ 1024 ⋅ 1024, the program would print 30.

⋅ 1024 ⋅ 1024 = 230 A. 1024 ! B. We get this by doing the same thing as we did above, or analyzing the problem and seeing that it really is working out the function from part c. c. As a function that is being computed in terms of N, we are looking at log2 (N ) Problem 2: Programming a. Calling func(0): func(x): i = 0; print x; while i < x: i =i +1 func(x-1)

func(0): i = 0; print x; //at this step we print 0 while i < x: //while not executed, 0 not < than 0 i =i +1 func(x-1)

So, when calling func(0), the program prints once. The output is 0. Calling func(1) func(x): i = 0; print x; while i < x: i =i +1 func(x-1)

func(1): i = 0; print x; //at this step we print 1 while 0 < 1: //while executed i = i + 1 // i = 1 func(x-1). //call func(0), (in part a)

So, when calling func(1), the program prints twice. The outputs are 1 & 0. Part B is on the following page. !

Page 2! of 5!

b. We know the following: !T (0) = 1 an d T (1) = 2 We also know that: !T (n) = 1 + nT (n − 1) Using this, we get !T (n − 1) = 1 + nT (n − 2) Given this info, we come up with an expanded and general solution for ! T (n) with ! n > 1.

T! (n) = 1 + n ⋅ (1 + (n − 1) ⋅ T (n − 2)) T! (n) = 1 + n + n(n − 1)[1 + (n − 2)T (n − 3)] We can keep doing this expansion further, but if we multiply it out, we get an expanded version that resembles an ! n!, found below.

T! (n) = n ⋅ (n − 1) ⋅ (n − 2) ⋅ (n − 3) ⋅ . . . a nd T (0) + n Knowing this, we can state that the algorithm does not run in polynomial time, since the

T (n) = n! + n , the Big O of which would likely be O(n!). Problem 3: Operating Systems

a.

P1 (26)

0

P2

26

P3 (12)

29

P4 (6)

41

P5(18)

47

65

b. The wait time is indicated in the chart below. P1

Waits 0, first process

P2

Waits 26 units

P3

Waits 29 units

P4

Waits 41 units

P5

Waits 47 units

The average wait time for the above processes is

0 + 26 + 29 + 41 + 47 = 28.6 5

c. To minimize the amount of waiting for the processes we have been given, we can order the processes based on the time they take to complete, with the fastest processes coming first. This gives us the following:

Page 3! of 5!

P 2 ⟹ P4 ⟹ P 3 ⟹ P5 ⟹ P1 ! 2 ⟹ 6 ⟹ 12 ⟹ 18 ⟹ 26

Process Order : Burst Time:

d. The graph of the process described above is shown below. The time required to complete the process is shown in the parentheses. P2

0

P4 (6)

3

P3 (12)

9

P5(18)

P1 (26)

21

39

65

e. The average wait time is computed as follows:

0 + 3 + 9 + 21 + 39 = 14.4 5 f. Given order of processes is:

⟹ P4 ⟹ 6. P2

P3

P4

P5

P3

P5

P1

21 ve a borde time at each point is specified. At the end, process P1 runs for ! 26 − 6 ⋅ 3 = 26 − 18 = 8 units of time, until it is completed. Let’s compute the average wait time. The wait time for P1 is: ! 0 + (27 − 6) + (45 − 33) + (57 − 51) = 39 The wait time for P2 is: ! 6 The wait time for P3 is: ! 9 + (33 − 15) = 27 The wait time for P4 is: ! 15 The wait time for P5 is: ! 21 + (39 − 27) + (51 − 45) = 39 The Average Wait time comes out to:

39 + 6 + 27 + 15 + 39 126 = 25.2 = 5 5

Page 4! of 5!

g. The maximum wait time for a process would be shown by (n − 1) ⋅ q. (! n − 1) represents the processes before the last one ! q represents the time quantum h. Advantage: A short term quantum allows many processes to quickly circulate through the CPU, and each of them gets a chance to run. Due to this, the interactive performance is improved. Starvation is not likely to take place, since each process will get a chance to run and use the CPU. Disadvantage: Every time we switch to another process, the CPU has to perform a context switch. This, in turn, means that the CPU is not performing useful work at that time, but spends time switching processes, which is overhead. i. System calls have an important purpose. Essentially, when a program requests a service from the OS’s kernel, a system call occurs. This makes it a way for programs to interact with the OS. System calls allow the OS to provide its services to the user-programs, and, in general, if a program needs resources, it must use a system call. There are also different types of system calls (divided into five categories). These include: file management, device management, information maintenance, communication, and process control. System calls are necessary because they really are the only way for a user-level program to interact with the OS and use its resources; in many cases, without system calls, a program would not be able to execute its intended actions.

Page 5! of 5!...