PARUL UNIVERSITY

PIET/PIT - CSE/IT
Operating System (203105203)

UNIT- 2 ASSIGNMENT - 2
---------------------------------------------------------------------------------------------------------

1) Threads of a process share

a. Global Variables but not heap

b. Heap but not Global Variables
c. Neither Global Variable nor heap
d. Both global variable and heap

⮚ Solution: Answer is option ( d )

● Note: Threads of a process share everything (Code, Data and Heap)
except the stack and registers.

---------------------------------------------------------------------------------------------------------

2) Consider the following CPU processes with arrival times (in milliseconds)
and length of CPU bursts (in milliseconds) as given below:

If the pre-emptive shortest remaining time first scheduling algorithm is used

to schedule the processes, then the average waiting time across all processes
is _______ millisecond.
 a. 1
b. 2
c. 3
d. 4
⮚ Solution: Answer is option ( c )
● Note: Please Check Below

Turn Around Time:

P1 = 12-0 = 12
P2 = 6-3 = 3
P3 = 17-5 = 12
P4 = 8 - 6 = 2

Waiting Time
P1 = 12-7 = 5
P2 = 3-3 = 0
P3 = 12-5 = 7
P4 = 2 - 2 = 0

Average Waiting time = (7+0+5+0)/4 = 3.0

Therefore, option C is correct

---------------------------------------------------------------------------------------------------------
3) Consider the set of processes with arrival time(in milliseconds), CPU burst
time (in milliseconds), and priority(0 is the highest priority) shown below.
None of the processes have I/O burst time.

The average waiting time (in milliseconds) of all the processes using
preemptive priority scheduling algorithm is _____.

a. 29
b. 30
c. 31
d. 32

⮚ Solution: Answer is option ( a )

● Note: Please Check Solution Below
4) Consider an arbitrary set of CPU-bound processes with unequal CPU burst
lengths submitted at the same time to a computer system. Which one of the
following process scheduling algorithms would minimize the average waiting
time in the ready queue?

a. Shortest remaining time first

b. Round-robin with time quantum less than the shortest CPU burst
c. Uniform random
d. Highest priority first with priority proportional to CPU burst length

⮚ Solution: Answer is option ( a )

● Note :Please check Explanation Below

Explanation: Turnaround time is the total time taken by the process between
starting and the completion and waiting time is the time for which process is
ready to run but not executed by CPU scheduler. As we know, in all CPU
Scheduling algorithms, shortest job first is optimal i.ie. it gives minimum turn
round time, minimum average waiting time and high throughput and the most
important thing is that shortest remaining time first is the pre-emptive version
of shortest job first. shortest remaining time first scheduling algorithm may
lead to starvation because If the short processes are added to the cpu
scheduler continuously then the currently running process will never be able to
execute as they will get pre-empted but here all the processes are arrived at
same time so there will be no issue such as starvation.
So, the answer is Shortest remaining time first, which is answer (a).

--------------------------------------------------------------------------------------------------------

5) Consider the following processes, with the arrival time and the length of
the CPU burst given in milliseconds. The scheduling algorithm used is
preemptive shortest remaining-time first.

The average turn around time of these processes is ___________

milliseconds.

a. 8.25
b. 10.25
c. 6.35
d. 4.25

⮚ Solution: Answer is option (A)

 ● Explanation: Pre Emptive Shortest Remaining time first scheduling, i.e.
that processes will be scheduled on the CPU which will be having least
remaining burst time (required time at the CPU).

The processes are scheduled and executed as given in the below Gantt chart.

Turn Around Time (TAT) = Completion Time(CT) – Arrival Time(AT)

TAT for P1 = 20 – 0 = 20

TAT for P2 = 10 – 3 = 7

TAT for P3 = 8- 7 = 1

TAT for P4 = 13 – 8 = 5

Hence, Average TAT = Total TAT of all the processes / no of processes

=( 20 + 7 + 1 + 5 ) / 4 = 33 / 4 = 8.25

Thus, A is the correct choice.

---------------------------------------------------------------------------------------------------------

6) The maximum number of processes that can be in Ready state for a

computer system with n CPUs is

a. N
b. n2
c. 2n
 d. Independent of n

⮚ Solution: Answer is option ( a )

● Explanation: The size of ready queue doesn’t depend on number of

processes. A single processor system may have a large number of
processes waiting in ready queue.

---------------------------------------------------------------------------------------------------------

7) A thread is usually defined as a “light weight process” because an

operating system (OS) maintains smaller data structures for a thread than for
a process. In relation to this, which of the following is TRUE?

a. On per-thread basis, the OS maintains only CPU register state

b. The OS does not maintain a separate stack for each thread
c. On per-thread basis, the OS does not maintain virtual memory
state
d. On per-thread basis, the OS maintains only scheduling and
accounting information

⮚ Solution: Answer is option ( c )

● Note: Threads share address space of Process. Virtually memory is
concerned with processes not with Threads.

---------------------------------------------------------------------------------------------------------

8) Multithreading is also called as ____________

a. Concurrency
b. Simultaneity
c. Crosscurrent
d. Recurrent
 ⮚ Solution: Answer is option ( a )

---------------------------------------------------------------------------------------------------------

9) We wish to schedule three processes P1, P2 and P3 on a uniprocessor

system. The priorities, CPU time requirements and arrival times of the
processes are as shown below.

Arrival
time
Process Priority CPU time required (hh:mm:ss)

P1 10(highest) 20 sec 00:00:05

P2 9 10 sec 00:00:03

P3 8 (lowest) 15 sec 00:00:00

We have a choice of preemptive or non-preemptive scheduling. In

preemptive scheduling, a late-arriving higher priority process can preempt a
currently running process with lower priority. In non-preemptive scheduling,
a late-arriving higher priority process must wait for the currently executing
process to complete before it can be scheduled on the processor.
What are the turnaround times (time from arrival till completion) of P2 using
preemptive and non-preemptive scheduling respectively.

a. 30 sec, 30 sec
b. 30 sec, 10 sec
c. 42 sec, 42 sec
 d. 30 sec, 42 sec

⮚ Solution: Answer is option (D)

● Explanation: For Non preemptive scheduling

P3(AT=0) P1(AT=5) P2(AT=3)

0 15 35
45
Turn Around Time= Completion Time – Arrival Time = 45 -3 = 42

For Preemptive scheduling

P3 P3 P3 P2 P2 P1 P2 P3
0 1 2 3 4 5 25
33 45
Turn Around Time= Completion Time – Arrival Time = 33 – 3 = 30
---------------------------------------------------------------------------------------------------------
10) In the following process state transition diagram for a uniprocessor
system, assume that there are always some processes in the ready state:
Now consider the following statements:

I. If a process makes a transition D, it would result in another process making

transition A immediately.
II. A process P2 in blocked state can make transition E while another process
P1 is in running state.
III. The OS uses preemptive scheduling.
IV. The OS uses non-preemptive scheduling.
Which of the above statements are TRUE?
 a. I and II
b. I and III
c. II and III
d. II and IV

⮚ Solution: Answer is option (C)

● Explanation : Please Check Below Details
I is false. If a process makes a transition D, it would result in another process
making transition B, not A.
II is true. A process can move to ready state when I/O completes irrespective of
other process being in running state or not.
III is true because there is a transition from running to ready state.
IV is false as the OS uses preemptive scheduling.
--------------------------------------------------------------------------------------------------------
10) A scheduling algorithm assigns priority proportional to the waiting time
of a process. Every process starts with priority zero (the lowest priority). The
scheduler re-evaluates the process priorities every T time units and decides
the next process to schedule. Which one of the following is TRUE if the
processes have no I/O operations and all arrive at time zero?

a. This algorithm is equivalent to the first-come-first-serve algorithm.

b. This algorithm is equivalent to the round-robin algorithm.
c. This algorithm is equivalent to the shortest-job-first algorithm.
d. This algorithm is equivalent to the shortest-remaining-time-first
algorithm

● Solution: Answer is option ( b )

---------------------------------------------------------------------------------------------------------
11) Which of the following statements are true?
I. Shortest remaining time first scheduling may cause starvation
II. Preemptive scheduling may cause starvation
III. Round robin is better than FCFS in terms of response time

a. I only
b. I and III only
 c. II and III only
d. I, II and III

● Solution: Answer is option ( d )

---------------------------------------------------------------------------------------------------------

12) Which of the following scheduling algorithms is non-preemptive?

a. Round Robin
b. First-In First-Out
c. Multilevel Queue Scheduling
d. Multilevel Queue Scheduling With feedback

● Solution: Answer is option ( b )

---------------------------------------------------------------------------------------------------------
13) Consider a set of n tasks with known runtimes r1, r2, … rn to be run on a
uniprocessor machine. Which of the following processor scheduling
algorithms will result in the maximum throughput?

a. Round-Robin
b. Shortest-Job-First
c. Highest-Response-Ratio-Next
d. First-Come-First-Served

⮚ Ans: Option (b)

● Explanation:
Throughput means total number of tasks executed per unit time.
shortest Job First has maximum throughput because in this scheduling
technique shortest jobs are executed first hence maximum number of
tasks are completed.

---------------------------------------------------------------------------------------------------------

15) A thread is also called ___________

 a. Light Weight Process(LWP)
b. Heavy Weight Process(HWP)
c. Process
d. None of the mentioned
⮚ Solution : a

16) Which of the following statements is false about thread?

a. Thread is a lightweight process.

b. Thread takes more time to terminate a running thread than a process.
c. Thread takes less time for switching in between threads.
d. Thread consumes less system resources.
---------------------------------------------------------------------------------------------------------

17) Which of the following level of a thread is the fastest to create and
manage thread?

a. Many-to-Many
b. Kernel
c. Many-to-One
d. User

---------------------------------------------------------------------------------------------------------

18) Which of the following is/are shared by all the threads in a process?

I. Program counter

II. Stack

III. Address space

IV. Registers

a. I and II only
b. III only
c. IV only
d. III and IV only
 ⮚ Solution : b

---------------------------------------------------------------------------------------------------------

19) Consider an arbitrary set of CPU-bound processes with unequal CPU burst
lengths submitted at the same time to a computer system. Which one of the
following process scheduling algorithms would minimize the average waiting
time in the ready queue?

a. Shortest remaining time first

b. Round-robin with time quantum less than the shortest CPU burst
c. Uniform random
d. Highest priority first with priority proportional to CPU burst length

⮚ Solution : a

---------------------------------------------------------------------------------------------------------

20) Which one of the following is FALSE?

a. User level threads are not scheduled by the kernel.

b. When a user level thread is blocked, all other threads of its
process are blocked.
c. Context switching between user level threads is faster than
context switching between kernel level threads.
d. Kernel level threads cannot share the code segment

⮚ Solution : d

---------------------------------------------------------------------------------------------------------

21) Which of the following statements is FALSE?

a. The long term scheduler controls the degree of multiprogramming

b. Multiple process of a single program cannot exist
c. Ready queue of the processes resides in main memory
d. A process can have multiple sub processes
 ⮚ Solution : b

---------------------------------------------------------------------------------------------------------

22) A scheduler which selects processes from Primary memory is called

a. Long Term Scheduler

b. Medium Term Scheduler
c. Short Term Scheduler
d. Job Scheduler

⮚ Solution : c

---------------------------------------------------------------------------------------------------------

23) Interval between the time since submission of the job to the time its
results become available, is called

a. Response Time
b. Throughput
c. Waiting time
d. Turnaround Time

⮚ Solution : a

---------------------------------------------------------------------------------------------------------

24) Which one of the following is FALSE?

a. User level threads are not scheduled by the kernel.

b. When a user level thread is blocked, all other threads of its
process are blocked.
c. Context switching between user level threads is faster than
context switching between kernel level threads.
d. Kernel level threads cannot share the code segment.

⮚ Solution : d
One liner Questions:
1. Process is ________ Activity and Program ____________ Activity.
2. When does a process terminate?
3. List out the name of the section in which process memory can be
divided?
4. What is context Switch?
5. What is Thread?
6. Define Process Scheduling.
7. What is Non Pre-emptive Scheduling and Pre-emptive Scheduling?
Define Throughput, Turnaround time, waiting time, Load Average and
Response Time.
8. Which system call is used for Process Termination?
9. What is Non Pre-emptive Scheduling and Pre-emptive Scheduling?
10. What is Convoy Effect ?

Subjective Questions:
1. Write Difference Between Program and Process.
2. Explain Process States with Diagram.
3. Explain Process Control Block.
4. Write Difference Between Thread and Process.
5. Differentiate between User Level Thread and Kernel Level Thread.
6. Advantages and disadvantages of User Level and Kernel Level Threads.
 7. Define Throughput, Turnaround time, waiting time, Response Time,
Load Average.
8. Difference between Long Term, Short Term, Medium Term Schedulers.

Examples :
(1) Consider the following Processes with CPU execution time.Calculate the
average Waiting time and average turnaround time .

Process id Average Time Burst Time

P1 0 2

P2 1 3

P3 2 5

P4 3 4

P5 4 6

Solution:
(2) We have 4 processes with process ID P0, P1, P2, and P3. The arrival time of
P0 is 0, P1 is 1, P2 is 2, and P3 is 3. The arrival time and burst time of the
processes are given in the following table. Calculate the average Waiting time
and average turnaround time .

Process id Average Time Burst Time

P0 0 6

P1 1 8

P2 2 10

P3 3 12

Solution :
 Process Arrival Burst Completion Turnaround
Waiting Time
ID Time Time Time Time

P0 0 6 6 6 0

P1 1 8 14 13 5

P2 2 10 24 22 12

P3 3 12 36 33 21

Average Waiting Time = 0+5+12+21/4

Average Waiting Time = 0+5+12+21/4

= 38/4
= 9.5 ms

Average Turnaround Time = 6+13+22+33/4

=74/4
= 18.5 ms

(2) Consider the set of 6 processes whose arrival time and burst time are given
below.

Process id Average Time Burst Time

P1 0 3

P2 1 2

P3 2 1

P4 3 5
 P5 4 4

P6 5 2

If the CPU scheduling policy is FCFS and there is 1 unit of overhead in

scheduling the processes, find the efficiency of the algorithm.

Gantt Chart-

Here, δ denotes the context switching overhead.

● Useless time / Wasted time = 6 x δ = 6 x 1 = 6 unit

● Total time = 23 unit
● Useful time = 23 unit – 6 unit = 17 unit

Efficiency (η) = Useful time / Total Total

= 17 unit / 23 unit

= 0.7391 = 73.91%

(3) Consider the set of 5 processes whose arrival time and burst time are given
below-

Process id Average Time Burst Time

P1 3 1

P2 1 4
 P3 4 2

P4 0 6

P5 2 3

If the CPU scheduling policy is SJF non-preemptive, calculate the average

waiting time and average turn around time.

Solution-
Gantt Chart-

Process Id Exit time Turn Around time Waiting time

P1 7 7–3=4 4–1=3

P2 16 16 – 1 = 15 15 – 4 = 11

P3 9 9–4=5 5–2=3

P4 6 6–0=6 6–6=0

P5 12 12 – 2 = 10 10 – 3 = 7

Now,
● Average Turn Around time = (4 + 15 + 5 + 6 + 10) / 5 = 40 / 5 = 8 unit
● Average waiting time = (3 + 11 + 3 + 0 + 7) / 5 = 24 / 5 = 4.8 unit
(4) Consider the set of 5 processes whose arrival time and burst time are given
below-

Process id Average Time Burst Time

P1 3 1

P2 1 4

P3 4 2

P4 0 6

P5 2 3

If the CPU scheduling policy is SJF preemptive, calculate the average waiting
time and average turn around time.

Solution-
Gantt Chart-

Process
Exit time Turn Around time Waiting time
Id

P1 4 4–3=1 1–1=0

P2 6 6–1=5 5–4=1

P3 8 8–4=4 4–2=2
 P4 16 16 – 0 = 16 16 – 6 = 10

P5 11 11 – 2 = 9 9–3=6

Average Turn Around time = (1 + 5 + 4 + 16 + 9) / 5 = 35 / 5 = 7 unit

Average waiting time = (0 + 1 + 2 + 10 + 6) / 5 = 19 / 5 = 3.8 unit

(5) Consider the set of 3 processes whose arrival time and burst time are given
below- If the CPU scheduling policy is SRTF, calculate the average waiting time
and average turn around time.

Process id Average Time Burst Time

P1 0 9

P2 1 4

P3 2 9

Solution-
Gantt Chart-

Process Id Exit time Turn Around time Waiting time

P1 13 13 – 0 = 13 13 – 9 = 4

P2 5 5–1=4 4–4=0
 P3 22 22- 2 = 20 20 – 9 = 11

Now,
● Average Turn Around time = (13 + 4 + 20) / 3 = 37 / 3 = 12.33 unit
● Average waiting time = (4 + 0 + 11) / 3 = 15 / 3 = 5 unit

(6) Consider the set of 5 processes whose arrival time and burst time are given
below-

Process id Average Time Burst Time

P1 0 5

P2 1 3

P3 2 1

P4 3 2

P5 4 3

If the CPU scheduling policy is Round Robin with time quantum = 2 unit,
calculate the average waiting time and average turn around time.
Problem-01:

Consider the set of 5 processes whose arrival time and burst time are given
below-

Process Id Arrival time Burst time

P1 0 5

P2 1 3

P3 2 1

P4 3 2
 P5 4 3

If the CPU scheduling policy is Round Robin with time quantum = 2 unit, calculate
the average waiting time and average turn around time.

Solution-

Gantt Chart-

Ready Queue-
P5, P1, P2, P5, P4, P1, P3, P2, P1

Process Id Exit time Turn Around time Waiting time

P1 13 13 – 0 = 13 13 – 5 = 8

P2 12 12 – 1 = 11 11 – 3 = 8

P3 5 5–2=3 3–1=2

P4 9 9–3=6 6–2=4

P5 14 14 – 4 = 10 10 – 3 = 7

● Average Turn Around time = (13 + 11 + 3 + 6 + 10) / 5 = 43 / 5 = 8.6 unit

Average waiting time = (8 + 8 + 2 + 4 + 7) / 5 = 29 / 5 = 5.8 unit
(7) Consider the set of 6 processes whose arrival time and burst time are given
below-

Process id Average Time Burst Time

P1 5 5

P2 4 6

P3 3 7

P4 1 9

P5 2 2

P6 6 3

If the CPU scheduling policy is Round Robin with time quantum = 3, calculate
the average waiting time and average turn around time.

Solution-

Gantt chart-

Ready Queue-
P3, P1, P4, P2, P3, P6, P1, P4, P2, P3, P5, P4
 Process Id Exit time Turn Around time Waiting time

P1 32 32 – 5 = 27 27 – 5 = 22

P2 27 27 – 4 = 23 23 – 6 = 17

P3 33 33 – 3 = 30 30 – 7 = 23

P4 30 30 – 1 = 29 29 – 9 = 20

P5 6 6–2=4 4–2=2

P6 21 21 – 6 = 15 15 – 3 = 12

Now,
● Average Turn Around time = (27 + 23 + 30 + 29 + 4 + 15) / 6 = 128 / 6 = 21.33
unit
● Average waiting time = (22 + 17 + 23 + 20 + 2 + 12) / 6 = 96 / 6 = 16 unit