Q155: About processor pipeline

Question #155: Which of the following is not true about processor pipelines?

Options:

1. Pipeline increases throughput of the system.
2. If the wrong branch is predicted, then pipeline has to be flushed and stalls need to be added.
3. Pipeline decreases the latency of the first instruction to be executed.

Solution: The correct answer is option 3. Increasing the number of stages in the pipeline might increase the total time of one instruction, because the tasks are to be split into multiple sub-tasks. First instruction here not only refers to the first instruction after computer starts, but is also relevant to the first instruction after pipeline flush (which may happen due to several reasons). A simplest pipeline is as follows (ARM7 architecture):

Here, the first instruction takes 3 cycles to complete. However, the total throughput of the system would most likely increase because first instruction onwards, every instruction would take just one cycle. Hence, option 1 is true.

ARM7 doesn’t use branch prediction, but ARM9 does and there are 5 stages of pipeline in case of ARM9. Now, if a wrong branch is predicted, then whole pipeline needs to be flushed because the wrong instruction would have been fetched. Hence, option 2 is also true.

Q152: CPU Idle time in SRTF scheduling

Question 152: Consider 3 processes, all arriving at time zero with total execution time of 10, 20, and 30 units respective each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation and last 10% of time doing I/O again. OS uses SRTF scheduling algorithm. Assuming I/O of processes can be overlapped, what percentage of CPU time will remain idle?

Options:

1. 0%
2. 30%
3. 6%
4. 4%

Solution: The correct answer is the third one. Processes will run as follows:

0-2: Idle

2-9: P1

9-23: P2

23-44: P3

44-47: Idle

Idle time = 5 / 47 * 100 = 10.6%

Q150: Priority Scheduling

Question #150: Priority Scheduling is an algorithm where scheduler assigns priority to the processes, and the highest priority process is the next one to get CPU attention. Priority scheduling can be preemptive (such that if a higher priority process enters the queue while a lower priority process is running, the lower priority process gets preempted) or it can be non-preemptive.

Which of the following is true?

Options:

1. Starvation of a low priority process may occur if preemption is used but will not happen when processes are non-preemptive.
2. Starvation of a low priority process may occur if non preemption is used but will not happen when processes are preemptive.
3. If static priorities are assigned (meaning, once assigned, priority of a process will not be changed) then starvation can happen with or without preemption. Starvation can be avoided if priorities are dynamically adjusted.
4. Priority scheduling will always suffer from starvation.

Solution: 3rd option is the correct one. Priority scheduling can prevent starvation by using aging which dynamically changes process’s priority.

Q148: Shortest job first without pre-emption

Question 148: If shortest job first policy is used without pre-emption, what would be the average waiting time?

Options:

• 2
• 3
• 4
• 5

Solution: The correct answer is the third one. Average waiting time is (0 + 6 + 3 + 7)/4 = 4

Q142: Block allocation for files using linked list.

This is in continuation with Question 141

Question 142: Which of the following is true when the files will be allocated as per the linked list?

1. Dynamic allocation of the blocks is easy.
2. Moving to any offset in the file is easy.
3. Difficult to grow the size of the file.
4. None of the above

Solution: The correct answer is option 1 as any block can be allocated anywhere in the disk and can be joined via linked list.

Q103: Equivalent prefix expression

Question #103: What is the equivalent prefix expression for ((A + B) * (F + G))?

Options:

1. +*AB+FG
2. *++ABFG
3. *AB+FG+
4. *+AB+FG

Solution: * should be performed as the last operation and both + should be performed before multiplication. Hence, correct option is the 4th one.

Q74: Interval Scheduling: Another greedy approach

This question is in continuation of previous question of interval scheduling. Please visit Q7 & Q8 before attempting this question.

Question #74: In another greedy approach, consider the following rule for selecting requests to produce optimal set in interval scheduling problem:

For all requests, find the number of other requests which conflict with it. Then, choose the request with least number of conflicts. Then, eliminate the conflicting requests, and again from the remaining requests, choose the one with least number of conflicts & so on.

Options:

1. The above algorithm produces optimal set always as it is able to select maximum requests since requests with more conflicts can be avoided.
2. This algorithm only fails when all requests conflict with equal number of other requests, but such an example cannot be constructed.
3. This algorithm may not produce optimal set in every case, and counter examples can be constructed.
4. This algorithm doesn’t work as greedy algorithms are unsuccessful in solving problems like this.

Solution: Below is the counter example of the above proposed algorithm:

Here 4 is the optimal number of requests that can be scheduled, but they have maximum conflicts. Hence, the correct answer is 3rd one.

Q54: Linear search’s recursive equation

Question #54: Which of the following recursive equation holds true for the linear search algorithm?

Options:

1. T(n) = T(n-1) + 1
2. T(n) = T(n/2) + 1
3. T(n) = 2T(n/2) + 1
4. T(n) = T(log(n)) + 1

Solution: In every step while searching linearly, we eliminate one element from the list. Hence the problem T(n) reduces to T(n-1). Therefore, option 1 is correct.

Q51: Best case of Quick Sort

This is in continuation of Question #50

Question #51: What is the best case complexity of the quick sort?

1. O(n)
2. O(n³)
3. O(n²)
4. O(n log(n))

Solution: In the best case, we will always have the pivot element as the median, and it will divide the two sub-arrays into two equal parts. Hence, the recursive equation will be:

• T(n) = T(n/2) + T(n/2) + n
• T(n) = 2T(n/2) + n
• T(n) = 2( 2*T(n/4) + n/2) + n
• T(n) = 4T(n/4) + 2n
• T(n) = 8T(n/8) + 3n
• …
• T(n) = n*T(n/n) + log(n) * n
• T(n) = O(nlog(n))

Hence, the correct answer is D

Q25: Recursion vs. Iteration

Recursive solutions arise when there’s a scope of expressing the solution of a problem in terms of simpler versions of the same problem. Iterative solutions on the other hand simply keep repeating a same task until it’s “done”.

Question #25: Which of the following statements is false in relation to recursion & iterative solutions?

Options:

A) Recursion may provide a nice elegant mathematical solution to a particular problem, but it might not be the most efficient approach to solving the problem on a computer.

B) It is always possible to convert a recursion into an iterative solution.

C) Some recursive solutions can’t be expressed iteratively.

D) Some data structures like trees are easier to explore using recursion.

Solution: In some cases, recursive solutions have a higher time & space complexity than iterative ones, so statement A is correct. It is also true that all recursive solutions can be expressed as iterative ones.  Trees are an example of data structures which are more intuitively explored using recursion. Tree traversal, lookup algorithms are neatly expressed recursively. Hence, option C is the correct choice.