OPERATING SYSTEMS ANSWERS

UNIT - 2

1. Consider a logical address space of 8 pages of 1024 words each, mapped on to a

physical memory of 32 frames. (i) How many bits are there in the logical address? (ii)
How many bits are there in the physical address?

A) Logical address space has 8 pages, size of each page, offset = 1024 words
Number if bits in page# field of the logical address = log28 bits = 3 bits
Offset bits = log21024 = 10 bits
So, Logical address = 3 + 10 = 13 bits
Physical memory has 32 frames, offset = 1024 words
Number of bits in frame# field of the Physical address = log232 bits = 5 bits
Physical address = 5 + 10 = 15 bits

2. What is fragmentation? List its types with disadvantages

A) Fragmentation is an unwanted problem in the operating system in which the processes

are loaded and unloaded from memory, and free memory space is fragmented. Processes
can't be assigned to memory blocks due to their small size, and the memory blocks stay
unused.

Disadvantages

There are various disadvantages of fragmentation. Some of them are as follows:

 Need for regular defragmentation

A more fragmented storage device's performance will degrade with time, necessitating the
requirement for time-consuming defragmentation operations.

 Slower Read Times

The time it takes to read a non-sequential file might increase as a storage device becomes
more fragmented.

3. What actions are taken by the operating system when a page fault occurs?

A) A page fault occurs when an access to a page that has not been brought into main
memory takes place. The operating system verifies the memory access, aborting the
program if it is invalid. If it is valid a free frame is located and I/O requested to read the
needed page into the free frame. Upon completion of I/O, the process table and page table
are updated and the instruction is restarted.
 4. What is segmentation? Explain demand segmentation

A) Segmentation is a memory management technique in which the memory is divided into

the variable size parts. Each part is known as a segment which can be allocated to a
process.

There are types of segmentation:

I. Virtual memory segmentation – Each process is divided into a number of segments,
not all of which are resident at any one point in time.
II. Simple segmentation – Each process is divided into a number of segments, all of
which are loaded into memory at run time, though not necessarily contiguously.

Demand segmentation is the process of dividing demand data into smaller chunks
(segments) to help measure performance or improve service quality. A demand
segmentation analysis can be performed on a pre - defined company segment, such as a
product or location.

5. Explain the difference between Physical and logical address

Physical address : The physical address identifies the physical location of required data in
memory. The user never directly deals with the physical address but can access it by its
corresponding logical address.

Logical address : A logical address is an address that is generated by the CPU during
program execution. The logical address is a virtual address as it does not exist physically,
and therefore, it is also known as a Virtual Address.

Terms Logical Address Physical Address

Definition the CPU generates the logical address while The physical address is a location in
the program is running memory.
Location The logical address does not exist physically The physical address is a location in
in the memory, and therefore it is sometimes the memory unit.
known as a virtual address.
Access The logical address is used as a reference to The physical address cannot be
access the physical address. accessed directly.
Address The set of all the logical addresses generated Whereas all the physical addresses
space about a program by the CPU is called mapped to the logical address is called
Logical Address Space. Physical Address Space.
 6. Differentiate between the following a) Paging and Segmentation b) Page table and
segment table

Sr Paging Segmentation
No.

1 Non-Contiguous memory allocation Non-contiguous memory allocation

2 Paging divides program into fixed size Segmentation divides program into variable
pages. size segments.
3 OS is responsible Compiler is responsible.
4 Paging is faster than segmentation Segmentation is slower than paging
5 Paging is closer to Operating System Segmentation is closer to User
6 It suffers from internal fragmentation It suffers from external fragmentation
7 There is no external fragmentation There is no external fragmentation
8 Logical address is divided into page Logical address is divided into segment
number and page offset number and segment offset
9 Page table is used to maintain the page Segment Table maintains the segment
information. information
10 Page table entry has the frame number and Segment table entry has the base address of the
some flag bits to represent details about segment and some protection bits for the
pages. segments.

7. What is disk scheduling? Explain FCFS and SCAN disk scheduling algorithms

A) Disk scheduling is done by operating systems to schedule I/O requests arriving for the
disk. Disk scheduling is also known as I/O scheduling.

The main purpose of disk scheduling algorithm is to select a disk request from the queue
of IO requests and decide the schedule when this request will be processed.

FCFS Scheduling Algorithm processes requests in the sequential order in which they
arrive in the disk queue. Even if a higher priority request arrives in the schedule later,
FCFS will process the request in the order that they have arrived and hence we can say
that FCFS has a fair policy.

SCAN Algorithm scans all the tracks of the disk in a back and forth manner such that it
will first process all the requests in one direction till it reaches the last track in that
direction then it reverses the direction and starts servicing the requests in it comes across.
8. Describe the LRU page replacement algorithm. Assume there are 3 frames and the
page reference string is 7, 0, 1, 2, 3, 3, 0, 4, 2, 3, 4, 3, 2, 1, 2, 0, 1, 7 Find the number of
page faults.

A) The LRU stands for the Least Recently Used. It keeps track of page usage in the
memory over a short period of time. It works on the concept that pages that have been
highly used in the past are likely to be significantly used again in the future. It removes the
page that has not been utilized in the memory for the longest time. LRU is the most widely
used algorithm because it provides fewer page faults than the other methods.

7 0 1 2 3 3 0 4 2 3 4 3 2 1 2 0 1 7
7 7 7 2 2 2 2 4 4 4 4 4 4 1 1 1 1 1
0 0 0 3 3 3 3 2 2 2 2 2 2 2 2 2 7
1 1 1 1 0 0 0 3 3 3 3 3 3 0 0 0
F F F F F H F F F F H H H F H F H F

The number of page faults : Total Numbers - Total Hits

= 18 - 6

= 12

9. What are the different principles which must be considered while selection of a
scheduling algorithm?

A) The objective/principle which should be kept in view while selecting a scheduling

policy are the following
a. Fairness − All processes should be treated the same. No process should suffer
indefinite postponement.
b. Maximize throughput − Attain maximum throughput. The largest possible number of
processes per unit time should be serviced.
c. Predictability − A given job should run in about the same predictable amount of time
and at about the same cost irrespective of the load on the system.
d. Maximum resource usage − The system resources should be kept busy. Indefinite
postponement should be avoided by enforcing priorities.
e. Controlled Time − There should be control over the different times −
Response time
Turnaround time
Waiting time
10. When does a page fault occur? Explain various page replacement
strategies/algorithms

A) In demand paging memory management technique, if a page demanded for execution is

not present in main memory, then a page fault occurs.

Various page replacement Strategies / Algorithms

a) The Optimal Page Replacement Algorithm − This algorithm replaces the page that
will not be used for the longest period of time. The moment the page fault occurs,
some set of pages are in memory.
b) FIFO (First in First out) Page Replacement Algorithm − It is one of the simplest
page replacement algorithm. The oldest page, which has spent the longest time in
memory is chosen and replaced.
c) LRU(Least Recently Used) Algorithm − The Least Recently used (LRU) algorithm
replaces the page that has not been used for the longest period of time.

11. What is Virtual Memory? Explain

A) Virtual Memory is a storage allocation scheme in which secondary memory can be

addressed as though it were part of the main memory.

whenever some pages needs to be loaded in the main memory for the execution and the
memory is not available for those many pages, then in that case, instead of stopping the
pages from entering in the main memory, the OS search for the RAM area that are least
used in the recent times or that are not referenced and copy that into the secondary
memory to make the space for the new pages in the main memory.

Advantages of Virtual Memory

 The degree of Multiprogramming will be increased.

 User can run large application with less real RAM.
 There is no need to buy more memory RAMs.

Disadvantages of Virtual Memory

 The system becomes slower since swapping takes time.

 It takes more time in switching between applications.
 The user will have the lesser hard disk space for its use.
 12. What are the differences between process and thread?

Process Thread

A process is an instance of a program that Thread is a segment of a process or a lightweight

is being executed or processed. process that is managed by the scheduler
independently.
Processes are independent of each other Threads are interdependent and share memory.
and hence don't share a memory or other
resources.
Each process is treated as a new process by The operating system takes all the user-level threads
the operating system. as a single process.
If one process gets blocked by the If any user-level thread gets blocked, all of its peer
operating system, then the other process threads also get blocked because OS takes all of
can continue the execution. them as a single process.
Context switching between two processes Context switching between the threads is fast
takes much time as they are heavy because they are very lightweight.
compared to thread.
The data segment and code segment of Threads share data segment and code segment with
each process are independent of the other. their peer threads; hence are the same for other
threads also.
The operating system takes more time to Threads can be terminated in very little time.
terminate a process.
New process creation is more time taking A thread needs less time for creation.
as each new process takes all the resources.

13. What is a process scheduler? State the characteristics of a good process scheduler.
 IMP
Scheduling can be defined as a set of policies and mechanisms which controls the order in
which the work to be done is completed. The scheduling program which is a system
software concerned with scheduling is called the scheduler and the algorithm it uses is
called the scheduling algorithm.
Various criteria or characteristics that help in designing a good scheduling algorithm are:
CPU Utilization − A scheduling algorithm should be designed so that CPU remains busy
as possible. It should make efficient use of CPU.

Throughput − Throughput is the amount of work completed in a unit of time. In other

words throughput is the processes executed to number of jobs completed in a unit of time.
The scheduling algorithm must look to maximize the number of jobs processed per time
unit.
Response time − Response time is the time taken to start responding to the request. A
scheduler must aim to minimize response time for interactive users.
Turnaround time − Turnaround time refers to the time between the moment of
submission of a job/ process and the time of its completion. Thus how long it takes to
execute a process is also an important factor.
Waiting time − It is the time a job waits for resource allocation when several jobs are
competing in multiprogramming system. The aim is to minimize the waiting time.
Fairness − A good scheduler should make sure that each process gets its fair share of the
CPU.

14. Describe the SSTF disk scheduling algorithm.

SSTF Scheduling Algorithm

Shortest seek time first (SSTF) algorithm selects the disk I/O request which requires the
least disk arm movement from its current position regardless of the direction. It reduces
the total seek time as compared to FCFS. It allows the head to move to the closest track in
the service queue.
 UNIT - 1
1. What do you understand by dead lock avoidance? Explain Banker’s Algorithm
with suitable example.

A) In deadlock avoidance, the request for any resource will be granted if the resulting state
of the system doesn't cause deadlock in the system. The state of the system will
continuously be checked for safe and unsafe states.

In order to avoid deadlocks, the process must tell OS, the maximum number of resources a
process can request to complete its execution.

The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that
tests for safety by simulating the allocation for predetermined maximum possible amounts
of all resources, then makes an “s-state” check to test for possible activities, before
deciding whether allocation should be allowed to continue.

EXAMPLE :

Consider a system that contains five processes P1, P2, P3, P4, P5 and the three resource
types A, B and C. Following are the resources types: A has 10, B has 5 and the resource
type C has 7 instances.

Process Allocation Max Available

A B C A B C A B C

P1 0 1 0 7 5 3 3 3 2
P2 2 0 0 3 2 2
P3 3 0 2 9 0 2
P4 2 1 1 2 2 2
P5 0 0 2 4 3 3

Context of the need matrix is as follows:

Need [i] = Max [i] - Allocation [i]

Need for P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3
Need for P2: (3, 2, 2) - (2, 0, 0) = 1, 2, 2
Need for P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0
Need for P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1
Need for P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1
Process Need
A B C

P1 7 4 3

P2 1 2 2

P3 6 0 0

P4 0 1 1

P5 4 3 1

Hence, we created the context of need matrix.

Apply the Banker's Algorithm:

Available Resources of A, B and C are 3, 3, and 2.

Now we check if each type of resource request is available for each process.

Step 1: For Process P1:

Need <= Available

7, 4, 3 <= 3, 3, 2 condition is false.

So, we examine another process, P2.

Step 2: For Process P2:

Need <= Available

1, 2, 2 <= 3, 3, 2 condition true

New available = available + Allocation

(3, 3, 2) + (2, 0, 0) => 5, 3, 2

Similarly, we examine another process P3.

Step 3: For Process P3:

P3 Need <= Available

6, 0, 0 < = 5, 3, 2 condition is false.

Similarly, we examine another process, P4.

Step 4: For Process P4:

P4 Need <= Available

0, 1, 1 <= 5, 3, 2 condition is true

New Available resource = Available + Allocation

5, 3, 2 + 2, 1, 1 => 7, 4, 3

Similarly, we examine another process P5.

Step 5: For Process P5:

P5 Need <= Available

4, 3, 1 <= 7, 4, 3 condition is true

New available resource = Available + Allocation

7, 4, 3 + 0, 0, 2 => 7, 4, 5

Now, we again examine each type of resource request for processes P1 and P3.

Step 6: For Process P1:

P1 Need <= Available

7, 4, 3 <= 7, 4, 5 condition is true

New Available Resource = Available + Allocation

7, 4, 5 + 0, 1, 0 => 7, 5, 5

So, we examine another process P2.

Step 7: For Process P3:

P3 Need <= Available

6, 0, 0 <= 7, 5, 5 condition is true

New Available Resource = Available + Allocation

7, 5, 5 + 3, 0, 2 => 10, 5, 7

Hence, we execute the banker's algorithm to find the safe state and the safe sequence
like P2, P4, P5, P1 and P3.
2. What are the five major activities of an operating system in regard to process
management?

A) A Program does nothing unless its instructions are executed by a CPU. A program in
execution is called a process. In order to accomplish its task, process needs the computer
resources.

There may exist more than one process in the system which may require the same resource
at the same time. Therefore, the operating system has to manage all the processes and the
resources in a convenient and efficient way.

Five major activities

i. The creation and deletion of both user and system processes

ii. The suspension and resumption of processes
iii. The provision of mechanisms for process synchronization
iv. The provision of mechanisms for process communication
v. The provision of mechanisms for deadlock handling

3. List out and explain briefly the various services that the operating system provides
to programs and users

A) The operating system provides the programming environment in which a programmer

works on a computer system. The user program requests various resources through the
operating system.

Following are the services provided by an operating system -

o Program execution
o Control Input/output devices
o Program creation
o Error Detection and Response
o Accounting
o Security and Protection
o File Management
o Communication

Program execution - To execute a program, several tasks need to be performed. Both the
instructions and data must be loaded into the main memory.

Control Input/output devices - As there are numerous types of I/O devices within the
computer system, and each I/O device calls for its own precise set of instructions for the
operation.
Program Creation - The Operating system offers the structures and tools, including
editors and debuggers, to help the programmer create, modify, and debugging programs.

Error Detection and Response - An Error in a device may also cause malfunctioning of
the entire device. These include hardware and software errors such as device failure,
memory error, division by zero, attempts to access forbidden memory locations, etc.

Accounting - An Operating device collects utilization records for numerous assets and
tracks the overall performance parameters and responsive time to enhance overall
performance.

Security and Protection - Operating device affords safety to the statistics and packages of
a person and protects any interference from unauthorized users

File management - Computers keep data and information on secondary storage devices
like magnetic tape, magnetic disk, optical disk, etc. Each storage media has its capabilities
like speed, capacity, data transfer rate, and data access methods.

Communication - The operating system manages the exchange of data and programs
among different computers connected over a network. This communication is
accomplished using message passing and shared memory.

4. Differentiate between a process and a program. Describe the life cycle of a process

Features Process Program

Definition A program has a collection of instructions A process is an example of an execution program.

designed to accomplish a certain task.

Nature It is an active entity. It is a passive entity.

Lifespan It has a limited lifespan. It has a much higher lifespan.

Resources It has a high resources requirement, and it It doesn't have any resources requirements; it only
requires including CPU, memory address, disk, needs memory space to store the instructions.
Input/output during its lifetime.

Creation The new process needs duplication of the No much duplication is needed.
parent process.

Computation The process takes a long time to access and It has no computation time and cost.
Time compute a single fact.

Required It holds resources including CPU, disk, The program is stored on a disk in a file and doesn't
Process memory address, Input/Output etc. need any additional resources.

Overhead It has considerable overhead. It has no significant overhead cost.

Cache Data It may use the cache to store the retrieve the It has the instruction to use cache for its data.
data as it uses OS paging scheme and cache
replacement policy like FCFS, LRU, RR,
LIFO.
S.N. State & Description

1 Start
This is the initial state when a process is first started/created.

2 Ready
The process is waiting to be assigned to a processor. Ready processes are waiting
to have the processor allocated to them by the operating system so that they can
run. Process may come into this state after Start state or while running it by but
interrupted by the scheduler to assign CPU to some other process.

3 Running
Once the process has been assigned to a processor by the OS scheduler, the
process state is set to running and the processor executes its instructions.

4 Waiting
Process moves into the waiting state if it needs to wait for a resource, such as
waiting for user input, or waiting for a file to become available.

5 Terminated or Exit
Once the process finishes its execution, or it is terminated by the operating system,
it is moved to the terminated state where it waits to be removed from main
memory.
5. Explain the different types of scheduling algorithms.

The Purpose of a Scheduling algorithm

1. Maximum CPU utilization

2. Fare allocation of CPU
3. Maximum throughput
4. Minimum turnaround time
5. Minimum waiting time
6. Minimum response time

There are the following algorithms which can be used to schedule the jobs.

First Come First Serve

It is the simplest algorithm to implement. The process with the minimal arrival time will
get the CPU first. The lesser the arrival time, the sooner will the process gets the CPU. It is
the non-preemptive type of scheduling.

Round Robin

In the Round Robin scheduling algorithm, the OS defines a time quantum (slice). All the
processes will get executed in the cyclic way. Each of the process will get the CPU for a
small amount of time (called time quantum) and then get back to the ready queue to wait
for its next turn. It is a preemptive type of scheduling.

Shortest Job First

The job with the shortest burst time will get the CPU first. The lesser the burst time, the
sooner will the process get the CPU. It is the non-preemptive type of scheduling.

Priority based scheduling

In this algorithm, the priority will be assigned to each of the processes. The higher the
priority, the sooner will the process get the CPU. If the priority of the two processes is
same then they will be scheduled according to their arrival time.