Q1. Write detailed notes on process
control and file manipulation.
Ans-Multiprogramming systems explicitly
allow multiple processes to exist at any given time, where only one is using
the CPU at any given moment, while the remaining processes are performing I/O
or are waiting.
The process manager is of the four
major parts of the operating system. It implements the process abstraction. It
does this by creating a model for the way the process uses CPU and any system
resources. Much of the complexity of the operating system stems from the need
for multiple processes to share the hardware at the same time. As a conseuence
of this goal, the process manager implements CPU sharing ( called scheduling ),
process synchronization mechanisms, and a deadlock strategy. In addition, the
process manager implements part of the operating system's protection and
security.
Process States
During the lifespan of a process, its
execution status may be in one of four states: (associated with each state is
usually a queue on which the process resides)
Executing: the process is currently
running and has control of a CPU
Waiting: the process is currently able
to run, but must wait until a CPU becomes available
Blocked: the process is currently
waiting on I/O, either for input to arrive or output to be sent
Suspended: the process is currently
able to run, but for some reason the OS has not placed the process on the ready
queue
Ready: the process is in memory, will
execute given CPU time
FILE MANIPULATION-
An operating system (OS) is basically a
collection of software that manages computer hardware resources and provides
common services for computer programs. Operating system is a crucial component
of the system software in a computer system.
These are some few common services
provided by an operating system −
- Program
execution
- I/O
operations
- File
System manipulation
- Communication
- Error
Detection
- Resource
Allocation
- Protection
A file represents a collection of
related information. Computers may store files on the disk (secondary storage),
for long-term storage purpose. Some Examples: magnetic tape, magnetic disk and
optical disk drives like CD, DVD. They have its own properties like speed, capacity,
data transfer rate and data access methods.
A file system is generally organized
into directories for easy navigation and usage. These directories can contain
files and other directions. Some of the major activities of an operating system
with respect to file management are −
- Program
requires to read a file or write a file.
- Operating
system gives the permission to the program for operation on file.
- This
permission varies from read-only, read-write, denied and so on.
- The
Operating System provides an interface to the user to create/delete files
and directories.
- The
Operating System provides an interface to create the backup of file
system.
Q2. Explain in detail about any two CPU
scheduling algorithms with suitable examples.
ANS- CPU Scheduling is a process
of determining which process will own CPU for execution while another process
is on hold. The main task of CPU scheduling is to make sure that whenever the
CPU remains idle, the OS at least select one of the processes available in the
ready queue for execution. The selection process will be carried out by the CPU
scheduler. It selects one of the processes in memory that are ready for
execution.
a)
First
Come First Serve (FCFS)
First Come First Serve is the full form of FCFS. It is the
easiest and most simple CPU scheduling algorithm. In this type of algorithm,
the process which requests the CPU gets the CPU allocation first. This
scheduling method can be managed with a FIFO queue.
As the process enters the ready queue, its PCB (Process Control
Block) is linked with the tail of the queue. So, when CPU becomes free, it
should be assigned to the process at the beginning of the queue.
Characteristics of FCFS
method:
- It
offers non-preemptive and pre-emptive scheduling algorithm.
- Jobs
are always executed on a first-come, first-serve basis
- It
is easy to implement and use.
- However,
this method is poor in performance, and the general wait time is quite
high.
b)Priority Based
Scheduling
Priority scheduling is a method of scheduling processes based on
priority. In this method, the scheduler selects the tasks to work as per the
priority.
Priority scheduling also helps OS to involve priority
assignments. The processes with higher priority should be carried out first,
whereas jobs with equal priorities are carried out on a round-robin or FCFS
basis. Priority can be decided based on memory requirements, time requirements,
etc.
Q3. (i) What is a deadlock? What are
the necessary conditions for a deadlock to occur?
Deadlock is a
situation where two or more processes are waiting for each other. For example,
let us assume, we have two processes P1 and P2. Now, process P1 is holding the
resource R1 and is waiting for the resource R2. At the same time, the process
P2 is having the resource R2 and is waiting for the resource R1. So, the
process P1 is waiting for process P2 to release its resource and at the same
time, the process P2 is waiting for process P1 to release its resource. And no
one is releasing any resource. So, both are waiting for each other to release
the resource. This leads to infinite waiting and no work is done here. This is
called Deadlock.
If a process is in the waiting state and is unable to
change its state because the resources required by the process is held by some
other waiting process, then the system is said to be in Deadlock.
Let's take one
real-life example to understand the concept of Deadlock in a better way.
Suppose, you are studying in a school and you are using the bus service also.
So, you have to pay two fees i.e. bus fee and tuition fee. Now, think of a
situation, when you go for submitting the bus fee and the accountant says that
you have to submit the tuition fee first and then the bus fee. So, you go to
submit the tuition fees on the other counter and the accountant there said that
you have to first submit the bus fees and then the tuition fees. So, what will
you do here? You are in a situation of deadlock here. You don't know what to
submit first, bus fees or tuition fees?
Necessary Conditions of Deadlock
There are four
different conditions that result in Deadlock. These four conditions are also
known as Coffman conditions and these conditions are not mutually exclusive.
Let's look at them one by one.
- Mutual Exclusion: A
resource can be held by only one process at a time. In other words, if a
process P1 is using some resource R at a particular instant of time, then
some other process P2 can't hold or use the same resource R at that
particular instant of time. The process P2 can make a request for that
resource R but it can't use that resource simultaneously with process P1.
- Hold and Wait: A
process can hold a number of resources at a time and at the same time, it
can request for other resources that are being held by some other process.
For example, a process P1 can hold two resources R1 and R2 and at the same
time, it can request some resource R3 that is currently held by process
P2.
- No preemption: A
resource can't be preempted from the process by another process,
forcefully. For example, if a process P1 is using some resource R, then
some other process P2 can't forcefully take that resource. If it is so,
then what's the need for various scheduling algorithm. The process P2 can
request for the resource R and can wait for that resource to be freed by
the process P1.
- Circular Wait: Circular
wait is a condition when the first process is waiting for the resource
held by the second process, the second process is waiting for the resource
held by the third process, and so on. At last, the last process is waiting
for the resource held by the first process. So, every process is waiting
for each other to release the resource and no one is releasing their own
resource. Everyone is waiting here for getting the resource. This is
called a circular wait.
(ii) How can a system recover from deadlock?
Deadlock Recovery
A traditional operating system such as Windows doesn’t deal with deadlock
recovery as it is time and space consuming process. Real-time operating systems
use Deadlock recovery.
Recovery method
1.
Killing the process: killing
all the process involved in the deadlock. Killing process one by one. After
killing each process check for deadlock again keep repeating the process till
system recover from deadlock.
2.
Resource Preemption: Resources
are preempted from the processes involved in the deadlock, preempted resources
are allocated to other processes so that there is a possibility of recovering
the system from deadlock. In this case, the system goes into starvation.
Q4. Describe the important concepts of
application I/O interface.
Application I/O Interface represents the structuring techniques
and interfaces for the operating system to enable I/O devices to be treated in
a standard, uniform way. The actual differences lies kernel level modules
called device drivers which are custom tailored to corresponding devices but
show one of the standard interfaces to applications. The purpose of the
device-driver layer is to hide the differences among device controllers from
the I/O subsystem of the kernel, such as the I/O system calls.
Following are the characteristics of I/O interfaces with
respected to devices:
• Character-stream / block - A character-stream device transfers
bytes in one by one fashion, whereas a block device transfers a complete unit
of bytes.
• Sequential / random-access - A sequential device transfers
data in a fixed order determined by the device, random access device can be
instructed to seek position to any of the available data storage locations.
• Synchronous / asynchronous - A synchronous device performs
data transfers with known response time where as an asynchronous device shows
irregular or unpredictable response time.
• Sharable / dedicated - A sharable device can be used
concurrently by several processes or threads but a dedicated device cannot be
used.
• Speed of operation - Device speeds may range from a few bytes
per second to a few gigabytes per second.
• Read-write, read only, or write only - Some devices perform
both input and output, but others support only one data direction that is read
only.
Q5. Discuss how scheduling algorithms
are selected for a system. What are the criteria considered?
- There
are several different criteria to consider when trying to select the
"best" scheduling algorithm for a particular situation and
environment, including:
- CPU
utilization -
Ideally the CPU would be busy 100% of the time, so as to waste 0 CPU
cycles. On a real system CPU usage should range from 40% ( lightly
loaded ) to 90% ( heavily loaded. )
- Throughput -
Number of processes completed per unit time. May range from 10 / second
to 1 / hour depending on the specific processes.
- Turnaround
time -
Time required for a particular process to complete, from submission time
to completion. ( Wall clock time. )
- Waiting
time -
How much time processes spend in the ready queue waiting their turn to
get on the CPU.
- ( Load
average - The average number of processes sitting in the ready
queue waiting their turn to get into the CPU. Reported in 1-minute,
5-minute, and 15-minute averages by "uptime" and
"who". )
- Response
time -
The time taken in an interactive program from the issuance of a command
to the commence of a response to that command.
- In
general one wants to optimize the average value of a criteria
( Maximize CPU utilization and throughput, and minimize all the
others. ) However some times one wants to do something different,
such as to minimize the maximum response time.
- Sometimes
it is most desirable to minimize the variance of a
criteria than the actual value. I.e. users are more accepting of a
consistent predictable system than an inconsistent one, even if it is a
little bit slower.
Q6. i) List out the
various process states and briefly explain with a state diagram
Process and Process
State:
§ In this article, we are going to discuss about
process, process state diagram and process control block (PCB).
§ A process is a program which is currently in
execution. A program by itself is not a process but it is a passive entity just
like content of a file stored on disk, while a process is an active entity.
§ A process also includes the process stack, which
contains temporary data (such as local variables, function parameters, return
address), and a data section, which contains
global variables and a heap-memory allocated to a
process to run and process state that defines its
current state.
§ A process changes its state during its execution. Each
process may be in one of the following states:
1.
New: when a new process is being created.
2.
Running: A process is said to be in running state when instructions
are being executed.
3.
Waiting: The process is waiting for some event to occur (such as an
I/O operation).
4.
Ready: The
process is waiting for processor.
5.
Terminated: The process has finished execution.
Process State Diagram
Only one process can be in
running state on any processor at a time while multiple processes may be in
ready and waiting state. The process state diagram shown below describes
different process states during its lifetime.
Process Control Block (PCB):
§ Operating system maintains one special data structure
called Process Control Block (PCB).
§ All the information about each process is stored in the process
control block (PCB) which is maintained by operating system.
It contains following information associated with a specific process.
§ Process state: It represents current status of the process. It may be
new, ready, running or waiting.
§ Program counter: It indicates the address of the next instruction
to be executed for this process.
§ CPU Registers: They include index registers, stack pointer and
general purpose registers. It is used to save process state when an interrupt
occurs, so that it can resume from that state.
§ CPU-scheduling information: it includes process priority, pointer to
scheduling queue.
§ Memory management information: value of the base and limit registers, page
tables depending on the memory system.
§ Accounting information: it contains an amount of CPU and real time
used, time limits process number and so on.
§ I/O status information: It includes a list of I/O devices allocated to the
process, a list of open files and so on.
§ Normally, operating system stores PCBs of processes into
the ready queue for the
process scheduling instead of the process itself .
ii) Define thread, it benefits and
the models of multithreading
A thread is a flow of execution through
the process code, with its own program counter that keeps track of which
instruction to execute next, system registers which hold its current working
variables, and a stack which contains the execution history.
A thread shares with its peer threads
few information like code segment, data segment and open files. When one thread
alters a code segment memory item, all other threads see that.
A thread is also called a lightweight
process. Threads provide a way to improve application performance through
parallelism. Threads represent a software approach to improving performance of
operating system by reducing the overhead thread is equivalent to a classical
process.
Advantages
of Thread
- Threads minimize the context switching time.
- Use of threads provides concurrency within a
process.
- Efficient communication.
- It is more economical to create and context
switch threads.
- Threads allow utilization of multiprocessor
architectures to a greater scale and efficiency.
Multithreading
Models
Some operating system provide a
combined user level thread and Kernel level thread facility. Solaris is a good
example of this combined approach. In a combined system, multiple threads
within the same application can run in parallel on multiple processors and a
blocking system call need not block the entire process. Multithreading models
are three types
- Many to many relationship.
- Many to one relationship.
- One to one relationship.
Many
to Many Model
The many-to-many model multiplexes any
number of user threads onto an equal or smaller number of kernel threads.
The following diagram shows the
many-to-many threading model where 6 user level threads are multiplexing with 6
kernel level threads. In this model, developers can create as many user threads
as necessary and the corresponding Kernel threads can run in parallel on a
multiprocessor machine. This model provides the best accuracy on concurrency
and when a thread performs a blocking system call, the kernel can schedule
another thread for execution.
Many
to One Model
Many-to-one model maps many user level
threads to one Kernel-level thread. Thread management is done in user space by
the thread library. When thread makes a blocking system call, the entire
process will be blocked. Only one thread can access the Kernel at a time, so
multiple threads are unable to run in parallel on multiprocessors.
If the user-level thread libraries are
implemented in the operating system in such a way that the system does not
support them, then the Kernel threads use the many-to-one relationship modes.
One to
One Model
There is one-to-one relationship of
user-level thread to the kernel-level thread. This model provides more
concurrency than the many-to-one model. It also allows another thread to run
when a thread makes a blocking system call. It supports multiple threads to
execute in parallel on microprocessors.
Disadvantage of this model is that
creating user thread requires the corresponding Kernel thread. OS/2, windows NT
and windows 2000 use one to one relationship model.
Q7. Discuss various system threats to
Operating System. What is access control and authentication?
Operating system's processes and kernel
do the designated task as instructed. If a user program made these process do
malicious tasks, then it is known as Program Threats. One of the
common example of program threat is a program installed in a computer which can
store and send user credentials via network to some hacker. Following is the
list of some well-known program threats.
·
Trojan
Horse − Such program traps user login
credentials and stores them to send to malicious user who can later on login to
computer and can access system resources.
·
Trap Door − If a program which is designed to work as required,
have a security hole in its code and perform illegal action without knowledge
of user then it is called to have a trap door.
·
Logic Bomb − Logic bomb is a situation when a program misbehaves
only when certain conditions met otherwise it works as a genuine program. It is
harder to detect.
·
Virus − Virus as name suggest can replicate themselves on
computer system. They are highly dangerous and can modify/delete user files,
crash systems. A virus is generatlly a small code embedded in a program. As
user accesses the program, the virus starts getting embedded in other files/
programs and can make system unusable for user
System
Threats
System threats refers to misuse of
system services and network connections to put user in trouble. System threats
can be used to launch program threats on a complete network called as program
attack. System threats creates such an environment that operating system
resources/ user files are misused. Following is the list of some well-known
system threats.
·
Worm − Worm is a process which can choked down a system
performance by using system resources to extreme levels. A Worm process
generates its multiple copies where each copy uses system resources, prevents
all other processes to get required resources. Worms processes can even shut
down an entire network.
·
Port
Scanning − Port scanning is a mechanism or
means by which a hacker can detects system vulnerabilities to make an attack on
the system.
·
Denial of
Service − Denial of service attacks
normally prevents user to make legitimate use of the system. For example, a
user may not be able to use internet if denial of service attacks browser's
content settings.
Access control is a security technique that
regulates who or what can view or use resources in a computing environment. It
is a fundamental concept in security that minimizes risk to the
business or organization. ... Logical access control limits
connections to computer networks, system files and data.
Authentication
Authentication refers to identifying
each user of the system and associating the executing programs with those
users. It is the responsibility of the Operating System to create a protection
system which ensures that a user who is running a particular program is
authentic. Operating Systems generally identifies/authenticates users using
following three ways −
·
Username /
Password − User need to enter a registered
username and password with Operating system to login into the system.
·
User
card/key − User need to punch card in card
slot, or enter key generated by key generator in option provided by operating
system to login into the system.
·
User
attribute - fingerprint/ eye retina pattern/ signature − User need to pass his/her attribute via designated
input device used by operating system to login into the system.
Q8. Consider the following snapshot of
a system:
P0 – P4 are 5 processes present and A,
B, C, D are the resources. The maximum need of a process and the allocated
resources details are given in the table :
Answer the following based on Banker’s
algorithm
i)
What is the content of NEED
matrix
ii)
Is this system in a safe
state?
iii)
Which process may cause deadlock
if the system is not safe.
iv)
If a request from process
P1 arrives for (0,4,3,1) can the request be granted immediately? Justify.
ANS-
Need matrix is calculated by subtracting Allocation Matrix from
the Max matrix
To check if system is in a safe state
- The
Available matrix is [1520][1520].
- A
process after it has finished execution is supposed to free up all the
resources it hold.
- We
need to find a safety sequence such that it satisfies the criteria
need Need≤AvailableNeed≤Available.
- Since Need(P0)≤AvailableNeed(P0)≤Available ,
we select P0.[Available]=[Available]+[Allocation(P0)]P0.[Available]=[Available]+[Allocation(P0)]
Available=[1520]+[0012]=[1532]Available=[1520]+[0012]=[1532]
- Need(P2)
≤ Available →→Available=[1
5 3 2]+[1 3 5 4]=[2 8 8 6]
- Need(P3)
≤ Available→→ Available=[
2 8 8 6 ]+[ 0 6 3 2 ]=[2 14 11 8 ]
- Need(P4)
≤ Available→→Available=[
2 14 11 8 ]+[0 0 1 4 ]=[ 2 14 12 12 ]
- Need(P1)
≤ Available→→Available=[
2 14 12 12 ]+[ 1 0 0 0 ]=[ 3 14 12 12]
- Safe
Sequence is <p0,p2,p3,p4,p1>
A request from process P1 arrives for (0,4,2,0)
- System
receives a request for P1 for Req(P1)[0420]Req(P1)[0420]
- First
we check if Req(P1) is less than Need(P1)Need(P1)→[0420]<[0750]istrue[0420]<[0750]istrue
- Now
we check if Req(P1) is less than AvailableAvailable→[0420]<[1520]istrue[0420]<[1520]istrue.
- So
we update the values as:
- Available=Available−Request=[1520]−[0420]=[1100]Available=Available−Request=[1520]−[0420]=[1100]
- Allocation=allocation(P1)+Request=[1000]+[0420]=[1420]Allocation=allocation(P1)+Request=[1000]+[0420]=[1420]
- Need=Need(P1)−Request=[0750]−[0420]=[0330]Need=Need(P1)−Request=[0750]−[0420]=[0330]
- This
is the modified table
- On
verifying, we see that the safe sequence still remains the same .The
system continues to remain in a safe state.
Q9. Explain in detail about PCB. What
are the contents of PCB?
For each process, the operating
system maintains the data structure, which keeps the
complete information about that process. This record or data structure is
called Process Control Block (PCB).
Whenever a user creates a process,
the operating system creates the corresponding PCB for that process. These PCBs
of the processes are stored in the memory that is reserved for the operating
system.
The process control block has many
fields that store the relative information about that process as you can see in
the above figure. PCB contains Process-Id, Process State, Process Priority, Accounting
Information, Program Counter, and also some other information which helps in
controlling the operations of the process.
Here we will discuss the Process
Control Block and its fields. So let us start.
Process-id
Whenever a new process is created by
the user, the operating system allots a number to that process. This number
becomes the unique identification of that process and it also helps in
distinguishing that process from all other processes existing in the system.
This number is also called as process-id of the process.
As we know, the operating system sets
a limit on the maximum number of the processes it can deal with at a time. So,
let us suppose that there are n number of the processes in
the system. Now, the process-id will take on the values between 0 to n-1.
The operating system will allocate
the value 0 to the first process that
arrives in the system, number 1 to the next process and
continues till n-1. At this point when the n-1
value is allocated to some process, and a new process arrives, the operating
system wraps around and allocates value 0 to
the newly arrived process. Considering that the process with process-id 0,
would have terminated.
Process-ids are not necessarily
allocated in the ascending fashion. There is also another scheme to generated
process-ids. Let us suppose, a PCB of a process requires x number
of bytes and there are n number of processes in the
system.
So, the operating system will
reserve nx number of bytes for all the
PCBs. And number the PCBs from 0 to n-1. Now, when a process
is created a fee PCB slot is allocated to that process and the PCB number
itself becomes the process-id of the process.
In this case, the operating system
has to maintain the chain of free PCBs. If the chain is empty no new process will
get created.
Process State
A process in its lifetime undergoes
different states. Like, a process may be in waiting
state, running state, ready state, blocked state, halted state,
and so on.
The PCBs field, process
state holds the current state of the respective process.
For example, if the process is currently executing. So, the process state will
hold the running state for that
process.
The information in the process state
field is kept in the codified fashion.
Process Priority
The priority of the process is
a numeric value, lesser the
value, greater is the priority of that process. The priority of the process can
be assigned externally by the user or by the operating system itself.
The process is assigned the priority
at the time of its creation. The priority of the process may get changed over
its lifetime depending on the various parameter. The parameters for changing
the priority of the process can be the age of that process, the resources it
consumed and so on.
Process Accounting Information
This field of PCB gives the
account/description of the resources used by that process. Like, the amount of
CPU time, real-time used, connect time.
Program Counter
The program counter is the pointer to
an instruction in the program or code that is to be executed next. This field
contains the address of the instruction that will be executed next in the
process.
List of Open Files
As you can see, this field is
self-explanatory. It contains the information of all the files that is required
by the program during its execution.
This information is also useful for
the operating system. Because it helps the operating system to close the all
opened files which are not closed explicitly at the termination of the program.
Process I/O status Information
Sometimes the process executing in
the system require I/o devices. So, this field of PCB contains the list of all
the I/O devices allocated to the process during its execution.
CPU Registers
Whenever an interrupt occurs and
there is a context switch between the processes, the temporary information is
stored in the registers. So, that when the process resumes the execution it
correctly gains from where it leaves. CPU registers are used to hold those
temporary values or information.
PCB Pointer
In this field, the pointer has an address
of the next PCB, whose process state is ready.
In this way, the operating system maintains the hierarchy of all the processes
so that a parent process could locate all the child processes it creates
easily.
Event Information
This field contains the information
of the event for which the certain process is in block state.
Whenever that event occurs the operating system identifies the process awaiting
for this event using this field. If the event occurred match with this field
the process changes its state from blocked to ready.
So these are the fields of PCBs which
contains much information that is associated with the specific process.
Q10. Explain in detail about process state
transition in operating system with suitable diagrams.
States of a process
are as following:
·
New (Create) – In
this step, the process is about to be created but not yet created, it is the
program which is present in secondary memory that will be picked up by OS to
create the process.
·
Ready – New
-> Ready to run. After the creation of a process, the process enters the
ready state i.e. the process is loaded into the main memory. The process here
is ready to run and is waiting to get the CPU time for its execution. Processes
that are ready for execution by the CPU are maintained in a queue for ready
processes.
·
Run – The
process is chosen by CPU for execution and the instructions within the process
are executed by any one of the available CPU cores.
·
Blocked or wait – Whenever
the process requests access to I/O or needs input from the user or needs access
to a critical region(the lock for which is already acquired) it enters the
blocked or wait state. The process continues to wait in the main memory and
does not require CPU. Once the I/O operation is completed the process goes to
the ready state.
·
Terminated or completed – Process
is killed as well as PCB is deleted.
·
Suspend ready – Process
that was initially in the ready state but were swapped out of main memory(refer
Virtual Memory topic) and placed onto external storage by scheduler are said to
be in suspend ready state. The process will transition back to ready state
whenever the process is again brought onto the main memory.
·
Suspend wait or suspend blocked
– Similar to suspend ready but uses
the process which was performing I/O operation and lack of main memory caused
them to move to secondary memory.
When work is finished it may go to suspend ready.
CPU and IO Bound Processes:
If the process is intensive in terms of CPU operations then it is called CPU
bound process. Similarly, If the process is intensive in terms of I/O
operations then it is called IO bound process.
Types of schedulers:
1.
Long term – performance – Makes
a decision about how many processes should be made to stay in the ready state,
this decides the degree of multiprogramming. Once a decision is taken it lasts
for a long time hence called long term scheduler.
2.
Short term – Context switching
time – Short term scheduler will decide
which process to be executed next and then it will call dispatcher. A
dispatcher is a software that moves process from ready to run and vice versa.
In other words, it is context switching.
3.
Medium term – Swapping time – Suspension
decision is taken by medium term scheduler. Medium term scheduler is used for
swapping that is moving the process from main memory to secondary and vice
versa.
Comments
Post a Comment