BLOCK 1 UNIT 1
OPERATING SYSTEM: AN OVERVIEW
Q1. What is an operating system?
Ans: An operating system is a collection of programs that acts as an interface between a user of a computer and the computer hardware. Some of the operating system functions are: implementing the user interface, sharing hardware among users, allowing users to scheduling resources among users, facilitating input or output, recovering from errors, accounting for resources usage, facilitating parallel operations, organizing data for secure and rapid access and handling network communications.
Q2. What are the functions of operating system?
Ans: The functions of operating system are given below:
1) Should act as a command interpreter by providing a user friendly environment.
2) Should facilitate communication with other users.
3) Facilitate the directory or file creation along with the security option.
4) Provide routines that handle the intricate details of I/O programming.
5) Provide access to compilers to translate programs from high level language to machine language.
6) Provide a loader program to move the compiled program code to the computers memory for execution.
7) Assure that when there are several active processes in the computer, each will get fair and non-interfering access to the central processing unit for execution.
8) Take care of storage and devices allocation.
9) Provide for long term storage of user information in the form of files.
10) Permit system resources to be shared among users when appropriate, and be protected from unauthorized or mischievous intervention as necessary.
Q3. What are the goals of operating system?
Ans: The goals of operating system are given below:
(a) The primary goal of an operating system is to make the computer convenient to use.
(b) The secondary goal is to use the hardware in an efficient manner.
Q4. Explain the generations of operation systems.
Ans: The generations of operating system are given below:
(a) 0th Generation
Early programs were written in machine language and each contained code for initiating operation of the computer itself. The mode of operation was called “open-shop” and this meant that users signed up for computer time and when a user’s time arrived, the entire (in those days quite large) computer system was turned over to the user. This system was clearly inefficient and dependent on the varying competencies of the individual programmer as operators.
(b) First Generation (1951 – 1956)
The first generation marked the beginning of commercial computing. The first generation was characterized again by the vacuum tube as the active component technology. The mode was called closed shop and was characterized by the appearance of hired operators who would select the job to be run, initial program load the system, run the user’s program and then select another job and so forth. Programs began to be written in higher level, procedure oriented languages and thus the operator’s routine expanded.
(c) Second Generations (1956 – 1964)
The second generation of computer hardware was most notably characterized by transistors replacing vacuum tubes as the hardware components technology. Program processing was, for the most part, provided by large centralized computers operated under mono-programmed batch processing operating systems. Toward the end of this period, as random access devices became available, tape oriented operating system began to be replaced by disk oriented systems. The second generation was a period of intense operating system development.
(d) Third Generations (1964 – 1979)
The third generation officially began in April 1964 with IBM’s announcement of its System 360 family of computers. Hardware technology began to use integrated circuits which yielded significant advantages in both speed and economy. The third generation was an exciting time, indeed, for the development of both computer hardware and the accompanying operating system. During this period, the topic of operating system became in reality a major element of the discipline of computing.
(e) Fourth Generation (1979 – Present)
The fourth generation is characterized by the appearance of the personal computer and the workstation. Miniaturization of electronic circuits and components continued and large scale integration (LSI) the component technology of the third generation was replaced by very large scale integration (VLSI) which characterizes the fourth generation. VLSI with its capacity for containing thousands of transistors on a small chip, made possible the development of desktop computers with capabilities exceeding those that filled entire rooms and floors of building just twenty years earlier.
Q5. Explain the different types of operating system?
Ans: The different types of operating system are explained below:
(a) Bath Processing Operation System
In a batch processing operating system, environment users submit jobs to a central place where these jobs are collected into a batch, and subsequently placed on an input queue at the computer when they will be run.
(b) Time Sharing Operating System
Another mode for delivering computing services is provided by time sharing operating systems. In this environment a computer provides computing services to several or many users concurrently on-line.
(c) Real Time Operating System
Real time operating systems are designed to service those applications where response time is of the essence in order to prevent error, misrepresentation or even disaster. These real time operating systems are used to control machinery, scientific instruments and industrial systems.
(d) Multiprogramming Operating System
A multiprogramming operating system is a system that allows more than one active user program or part of user program to be stored in main memory simultaneously.
(e) Multiprocessing Operating System
A multiprocessing system is a computer hardware configuration that includes more than one independent processing unit. The term multiprocessing is generally used to refer to large computer hardware complexes found in major scientific or commercial applications.
(f) Networking Operating System
A networked computing system is a collection of physical interconnected computers. The operating system of each of the interconnected computers must contain in addition to its own stand alone functionality, provisions for handling communication and transfer of program and data among the other computers with which it is connected.
(g) Distributed Operating System
The networked and distributed computing environments and their respective operating systems are designed with more complex functional capabilities. In a network operating system, the users are aware of the existence of multiple computers, and can log in to remote machines and copy files from one machine to another. Each machine runs its own local operating system and has its own user or users.
(h) Distributed Operating System
A distributed operating system, in contrast, is one that appears to its users as a traditional uni-processor system, even though it is actually composed of multiple processors. In a true distributed system, users should not be aware of where their programs are being run or where their files are located; that should all be handled automatically and efficiently by the operating system.
Q6. What are the desirable qualities of operating system?
Ans: The desirable qualities of operating system are given below:
ð Usability – Robustness, Accept all valid inputs and can handle them, consistency, proportionality, convenience, powerful with high level facilities.
ð Facilities – Sufficient for intended use, complete, appropriate.
ð Costs – Want low cost and efficient services, good algorithms, make use of space or time tradeoffs, special hardware, low overhead, cost of doing nothing should be low, low maintenance cost; system should not require constant attention.
ð Adaptability – Tailored to the environment, support necessary activities. Do not impose necessary restrictions, changeable over time, extendible and extensible.
Q7. What are the functions of operating system related to process management?
Ans: The CPU executes a large number of programs. While its main concern is the execution of user programs, the CPU is also needed for other system activities. These activities are called processes. A process is a program in execution. Typically a batch job is a process. A time shared user program is a process. The operating system is responsible for the following activities in connection with processes management:
(a) The creation and deletion of both user and system processes.
(b) The suspension and resumption of processes.
(c) The provision of mechanisms for process synchronization.
(d) The provision of mechanisms for deadlock handling.
Q8. What are the functions of OS in connection with memory management?
Ans: Memory is the most expensive part in the computer system. Memory is a large array of words or bytes, each with its own address. The operating system is responsible for the following activities in connection with memory management:
(a) Keep track of which parts of memory are currently being used and by whom.
(b) Decide which processes are to be loaded into memory when memory space becomes available.
(c) Allocate and de-allocate memory space as needed.
Q9. What are the functions of OS related to I/O management?
Ans: The operating system is responsible for the following activities in connection to I/O management:
(a) A buffer caching system.
(b) To activate general device driver code.
(c) To run the driver software for specific hardware devices as and when required.
Q10. What are the functions of OS related to file management?
Ans: File management is one of the most visible services of an operating system. Computers can store information in several different physical forms: magnetic tape, disk and drum are the most common forms. Each of these devices has its own characteristics and physical organization. The operating system is responsible for the following activities in connection to the file management:
(a) The creation and deletion of files.
(b) The creation and deletion of directory.
(c) The support of primitives for manipulating files and directories.
(d) The mapping of files onto disk storage.
(e) Backup of files on stable (non-volatile) storage.
(f) Protection and security of the files.
Q11. Explain the functions of operation in connection the followings:
(a) Protection
The various processes in an operating system must be protected from each other activities. For that purpose, various mechanisms which can be used to ensure that the files, memory segment, CPU and other resources can be operated on only by those processes that have gained proper authorization from the operating system.
(b) Networking
A distributed system is a collection of processors that do not share memory or a clock. Instead, each processor has its own local memory and the processors communicate with each other through various communication lines, such a high speed buses or telephone lines.
(c) Command Interpretation
One of the most important components of an operating system is its command interpreter. The command interpreter is the primary interface between the user and the rest of the system.
BLOCK 1 UNIT 2
PROCESSES
Q1. Define process.
Ans: The term process was first used by the operating system designers of the MULTICS system way back in 1960s. A process is a program in execution. Typically, a batch job is a process. A time shared user program is a process. A system task, such as spooling, is also a process.
Q2. Differentiate between implicit tasking and explicit tasking.
Ans: Implicit tasking means that processes are defined by the system. It is commonly encountered in general purpose multiprogramming system. Explicit tasking means that programs explicitly defined each process and some of its attributes. Explicit tasking is used in situations where high performance is desired system program such as parts of the operating system and real time applications are common examples of programs defined processes.
Q3. What are the common reasons for the user of explicit tasking?
Ans: The common reasons for the user of explicit tasking include:
ð Speedup: Explicit tasking can result in faster execution of applications.
ð Driving I/O Devices that have latency: While one task is waiting for I/O to complete, another portion of the application can make progress towards completion if it contains order tasks that can do useful work in the interim.
ð User Convenience: By creating tasks to handle individual actions, a graphical interface can allow users to launch several operations concurrently by clicking on action icons before completion of previous commands.
ð Multiprocessing and Multi-computing: A program coded as a collection of tasks can be relatively easily posted to a multiprocessor system, where individual tasks may be executed on different processors in parallel.
Q4. Explain process relationship.
Ans: In the concurrent environment basically processes have two relationships, competition and cooperation. In the concurrent environment, processes compete with each other for allocation of system resources to execute their instructions. In addition, a collection of related processes that collectively represent a single logical application cooperate with each other.
A process is independent if it cannot affect or be affected by other processes executing in the system. The features of independent process are:
(1) Their state is not shared in any way by any other process.
(2) Their execution is deterministic, i.e. the result of execution depends only on the input values.
(3) Their execution is reproducible i.e. the result of execution will always be the same for the same input.
(4) Their execution can be stopped and restarted without any negative effect.
In contrast to independent processes, cooperating processes can affect or affect by other processes executing the system. They are characterized by:
(1) Their states are shared by other processes.
(2) Their execution is not deterministic i.e. the results of execution depend on relative execution sequence and cannot be predicted in advance.
Q5. What are the states of process?
Ans: The states of process are given below:
(1) New – The process is being created.
(2) Ready – The process is waiting to be assigned to a processor.
(3) Running – Instructions are being executed.
(4) Waiting / Suspended / Blocked – The process is waiting for some event to occur.
(5) Halted / Terminated – The process has finished execution.
Q6. What is Process Control Block (PCB)? What information is stored in PCB? How it differs from context switch?
Ans: To implement the processes model the operating system maintains a table, an array of structures, called the process table or process control block (PCB) or switch frame. The following are the information stored in a PCB:
ð Process state, which may be new, ready, running, waiting or halted.
ð Process number, each process is identified by its process number called process ID.
ð Program counter, which indicates the address of the next instruction to be executed for this process.
ð CPU registers, which vary in number and type, depending on the concrete microprocessor architecture.
ð Memory management information which includes base and bounds registers or page table.
ð I/O status information, composed I/O requests, I/O devices allocated to this process, a list of open files and so on.
ð Processor scheduling information, which includes process priority, pointers to scheduling queues and any other scheduling parameters.
ð List of open files.
A context switch (also sometimes referred as a process switch or a task switch) is the switching of the CPU from one process or to another. A context is the contents of a CPUs registers and program counter at any given point in time. A context switch is sometimes described as the kernel suspending execution of one process on the CPU and resuming execution of some other process that had previously been suspended.
Q7. Explain process hierarchy.
Ans: Modern general purpose operating systems permit a user to create and destroy processes. A process may create several new processes during its time of execution. The creating process is called parent process, while the new processes are called child processes. A parent process can terminate the execution of one of its children for one of these reasons:
ð The child process has exceeded its usage of the resources it has been allocated. In order to do this, a mechanism must be available to allow the parent process to inspect the state of its children processes.
ð The task assigned to the child process is no longer required.
In UNIX this is done by the fork system call, which creates a child process and the exit system call, which terminates the current process.
Q8. What are threads? Why use threads?
Ans: Threads, sometimes called lightweight process (LWPs) are independently scheduled parts of a single program. We say that a task is multithreaded if it is composed of several independent sub-processes which do work on common data, and if each of these pieces could (at least in principle) run in parallel. In a sense, threads are further level of object orientation for multi-tasking systems. They allow certain functions to be executed in parallel with others. The point is that threads are cheaper than normal processes, and they can be scheduled for execution in a user-dependent way, with less overhead. Threads are cheaper than a whole process because they do not have a full set of resources each.
We use threads because of the following reasons:
(1) Threads allow a programmer to switch between lightweight processes when it is best for the program.
(2) A process which uses threads does not get more CPU time than an ordinary process – but the CPU time it gets is used to do work on the threads. It is possible to write a more efficient program by making use of threads.
(3) Inside a heavyweight process, threads are scheduled on a FCFS basis, unless the program decides to force certain threads to wait for other threads. If there is only one CPU, then only one thread can be running at a time.
(4) Threads context switch without any need to involve the kernel the switching is performed by a user level library, so time is saved because the kernel does not need to know about the threads.
Q9. What is system calls? Explain fork/join method.
Ans: System calls provide the interface between a process and the operating system. These system calls are the routine services of the operating system. Fork/join is a method of process creation and termination which is originally introduced as primitive for multiprocessor system. The fork operations are used to split a sequence of instruction into two concurrently executable sequences. Join is used to merge the two sequences of code divided by the fork and it is available to a parent process for synchronization with a child.
Q10. Explain process scheduling. What are the scheduling objectives?
Ans: Scheduling refers to a set of policies and mechanisms supported by operating system that controls the order in which the work to be done is completed. A scheduler is an operating system program or module that selects the next job to be admitted for execution. The main objective of scheduling is to increase CPU utilization and higher throughput. Throughput is the amount of work accomplished in a given time interval.
Various objectives of scheduling are given below:
(1) Maximize throughput – Scheduling should attempt to service the largest possible number of process per unit time.
(2) Be Predictable – A given job should utilize the same amount of time and should cost the same regardless of the load on the system.
(3) Minimize Overhead – Scheduling should minimize the wasted resources overhead.
(4) Balance Resource use: The scheduling mechanisms should keep the resources of the system busy. Process that will use under utilized resources should be favored.
(5) Avoid Indefinite postponement – It would be fair if all processes are treated the same and no process can suffer indefinite postponement.
Q11. Explain the different types of schedulers.
Ans: The different types of schedulers are explained below:
(a) Short Term Scheduler
The short term scheduler selects the process for the processor among the processes which are already in queue in memory. The scheduler will execute quite frequently mostly at least once every 10 mili-seconds. It has to be very fast in order to achieve better processor utilization. The short term scheduler, like all other OS programs, has to execute on the processor.
(b) Long Term Scheduler
The long term scheduler select processes from the process pool and loads selected processes into memory for execution. The long term scheduler execute much less frequently when compared with the short term scheduler. It controls the degree of multiprogramming i.e. the number of processes in memory at a time.
(c) Medium Term Scheduler
Medium term scheduler is in between the short term scheduler and long term scheduler. Sometimes it is good to reduce the degree of multiprogramming by removing processes from memory and storing them on disk. These processes can then be re-introduced into memory by a medium term scheduler. This operation is also known as swapping. Swapping may be necessary to improve the process mix or to free memory.
Q12. Define the following terms:
(a) CPU Utilization
CPU utilization is the ratio of busy time of the processor to the total time passes for processes to finish.
(b) Throughput
It refers to the amount of work completed in a unit of time. One way to measure throughput is by means of number of processes that are completed in a unit of time.
(c) Waiting Time
This is the time spent in a ready queue. The waiting time may be expressed as turnaround time, less than the actual processing time.
(d) Throughput
It may be defined as interval from the time of submission of a process to the time of its completion. It is the sum of the periods spent waiting to get into memory, waiting in the ready queue, CPU time and I/O operations.
(e) Response Time
Response time may be defined as interval from the time the last character of a command line of a program or transaction is entered to the time the last result appears on the terminal. In real time system, it may be defined as interval from the time on internal or external event is signaled to the time the first instruction of the respective service routine is executed.
Q13. Explain the difference between pre-emptive scheduling and non-pre-emptive scheduling.
Ans: Preemptive means the operating system moves a process from running go ready without the process requesting it. An OS implementing this algorithm switches to the processing of a new request before completing the processing of the current request. Round Robin scheduling, priority based scheduling or event driven scheduling and SRTN are considered to be the preemptive scheduling algorithm.
A scheduling discipline is non-preemptive if once a process has been allotted to the CPU, the CPU cannot be taken away from the process. A non-preemptive discipline always processes a scheduled request to its completion. In non-preemptive systems, jobs are made to wait by longer jobs, but the treatment of all processes is fairer. First Come First Serve (FCFS), and Shortest Job First (SJF) are considered to be the non-preemptive scheduling algorithms.
Q14. Explain the different scheduling algorithms.
Ans: The different scheduling algorithms are explained below:
(1) First Come First Serve (FCFS)
The simplest scheduling algorithm is first come first serve. Jobs are scheduled in the order they are received. FCFS is non-preemptive. Implementation is easily accomplished by implementing a queue of the processes to be scheduled or by storing the time the process was received and selecting the process with the earliest time.
(2) Shortest Job First (SJF)
This algorithm is assigned to the process that has the smallest next CPU processing time, when the CPU is available. In case of a tie, FCFS scheduling algorithm can be used. It is originally implemented in a batch processing environment. SJF relied on a time estimate supplied with a batch job.
(3) Round Robin (RR)
Round robin scheduling is a preemptive algorithm that relates the process that has been waiting the longest. This is one of the oldest, simplest and widely used algorithms. The round robin scheduling algorithm is primarily used in time sharing and a multi-user system environment where the primary requirement is to provide reasonably good response times and in general to share the system fairly among all system users. Basically the CPU time is divided into time slices.
(4) Shortest Remaining Time Next (SRTN)
This is the preemptive version of the shortest job first. This permits a process that enters the ready list to preempt the running process if the time for the new process or for its next burst is less than the remaining time for the running process or for its current burst.
(5) Priority Based or Event Driven (ED)
A priority is associated with each process and the scheduler always picks up the highest priority process for execution from the ready queue. Equal priority processes are scheduled FCFS. The level of priority may be determined on the basis of resources requirements, processes characteristics and its run time behavior.
BLOCK 1 UNIT 3
INERPROCESS COMMUNICATION AND SYNCHRONIZATION
Q1. Define inter-process communication (IPC).
Ans: Inter-process communication (IPC) is a capability supported by operating system that allows one process to communicate with another process. The processes can be running on the same computer or on different computers connected through a network. IPC enables one application to control another application.
Q2. Explain the two complimentary inter-process communication types.
Ans: The two complimentary inter-process communication types are explained below:
(a) Shared Memory System
Shared memory systems require communication processes to share some variables. The processes are expected to exchange information through the use of these shared variables. In a shared memory system, the responsibility for providing communication rests with the application programmers. The operating system only needs to provide shared memory.
(b) Message Passing System
Message passing system allows communication processes to exchange messages. In this scheme, the responsibility rests with the operating system itself. The function of message passing system is to allow processes to communicate with each other without the need to resort to shared variable. An inter-process communication facility basically provides two operations: send (message) and receive (message).
Q3. Explain direct and indirect communication.
Ans: Direct and indirect communications are explained below:
(a) Direct Communication
In direct communication, each process that wants to send or received a message must explicitly name the recipient or sender of the communication. In this case, the send and receive primitives are defined as follows:
· Send(P, message) To send a message to process P
· Receive (Q, message) To receive a message from process P
This scheme shows the symmetry in addressing i.e. both the sender and the receiver have to name one another in order to communicate.
(b) Indirect Communication
With indirect communication, the messages are sent to and received from a mailbox. A mailbox can be abstractly viewed as a object into which messages may be place and from which messages bay be removed by processes. In order to distinguish one communicates with some other process by a number of different mailboxes. The send and receive primitives are defined as follows:
· Send (A, message) To send a message to the mailbox A
· Receive (A, message) To receive a message from the mailbox A
Q4. What is capacity link? Explain the different types of capacity link.
Ans: A link has some capacity that determines the number of messages that can temporarily reside in it. This is known as capacity link.
The different types of capacity link are explained below:
(a) Zero Capacity
This link has a message queue length of zero, i.e. no message can wait in it. The sender must wait until the recipient receives the message.
(b) Bounded Capacity
This link has a limited message queue length of n, i.e. at most n messages can reside in it. If a new message is sent, and the queue is not full, it is placed in the queue either by copying the message or by keeping a pointer to the message and the sender should continue execution without waiting. Otherwise, the sender must be delayed until space is available in the queue.
(c) Unbounded Capacity
This queue has potentially infinite length i.e. any number of messages can wait in it. This is why the sender is never delayed.
Q5. What is serialization? Explain the two strategies of serializing processes.
Ans: The key idea in process synchronization is serialization. This means that we have to go to some pains to undo the work we have put into making an operating system perform several tasks in parallel.
There are essentially two categories to serializing processes in a multitasking environment which are given below:
(a) The scheduler can be disabled for a short period of time, to prevent control being given to another process during a critical action like modifying shared data. This method is very inefficient on multiprocessor machines, since all other processors have to be halted every time one wishes to execute a critical section.
(b) A protocol can be introduced which all programs sharing data must obey. The protocol ensures that processes have to queue up to gain access to shared data. A process which ignores the protocol ignores it at their own peril. This method works on multiprocessor machines also, though it is more difficult to visualize.
Q6. Define mutexes. Give the characteristic properties of critical section of mutexes.
Ans: When two ore more processes must share the same object, an arbitration mechanism is needed so that they do not try to use it at the same time. The particular object being shared does not have a great impact on the choice of such mechanisms.
The characteristic properties of the code that form the critical section are:
(i) Codes that refer one or more variables in a read update write fashion while any of those variables is possibly being altered by another thread.
(ii) Codes that alter one or more variable that are possibly being referenced in need-update-write fashion by another thread.
(iii) Codes use a data structure while any part of it is possibly being altered by another thread.
(iv) Codes alter any part of a data structure while it possibly in use by another thread.
Q7. What are the drawbacks of switching off interrupts in mutexes solutions?
Ans: The drawbacks of switching of interrupts are given below:
(a) Masking interrupts can be dangerous – there is always the possibility that important interrupts will be missed.
(b) It is not general enough in a multi-processor environment, since interrupts will continue to be serviced by other processors – so all processors would have to be switched off.
(c) It is too harsh. We only need to prevent two programs from being in their critical sections simultaneously if they share the same data. Programs A and B might share different data to programs C and D so why should they wait for C and D?
Q8. Give the different algorithms for solving mutual exclusion problem.
Ans: The different algorithms for solving mutual exclusion problem are given below:
(a) GL Peterson Solution
In 1981 G.L. Peterson discovered a simple algorithm for achieving mutual exclusion between two processes with PID equal to 0 and 1. The code is given below:
int turn;
int interested[2];
void Get_Mutex(int pid)
{
int other;
other = 1 – pid;
interested[process] = true;
turn = pid;
while(turn==pid && interested[other])
{
//Loop until no one else is interested
}
}
Release_Mutex(int pid)
{
Interested[pid]=false;
}
(b) Dekker Solution
Dekker’s algorithm uses busy waiting and works for only two processes. The basic idea is that processes record their interest in entering a critical section and they take turns when both need entry at the same time. Dekker’s solution is shown below:
type processed = 0.1;
var need:array[processed] of Boolean { initially false};
turn:processed { initially either 0 or 1};
procedure dekkerwait(me:processed);
var other:processed;
begin
other := 1 – me;
need[me] := true;
while need[other] do begin {there is contention}
if turn = other then begin
need[me] := false {let other take a turn};
while turn = other do {nothing};
need[me] :=true {re-assert my interest};
end;
end;
end {dekkerwait};
procedure dekkersignal{me:processed};
begin
need[me] : false;
turn := 1 – me {now it is the other’s turn};
end {dekkarsignal};
(c) Bakery’s Algorithm
Bakery algorithm can handles critical section problem for n processes. The algorithm is given below:
do
{
choosing[i] = true;
number[i] = max(number[0], number[1]…number[n-1]) + 1;
choosing[i] = false;
for (int j = 0; j<n; j++)
{
while (choosing[j] == true
{
/* do nothing */
}
while((number[j]!=0) && (number[j].j) < (number[i].i))
// see reference point
{
/* do nothing */
}
}
do critical section
number[i] = 0;
do remainder section
}
while(true)
Q9. What are semaphores?
Ans: The effective synchronization tools often used to realize mutual exclusion in more complex system are called semaphores. A semaphore S is an integer variable which can be accessed only through two standard atomic operations: wait and signal. The definition of the wait and signal operations are:
Wait(S): while S <= 0 do skip;
S:= S – 1;
Signal(S): S:=S+1;
Q10. Explain the producers or consumers problem with algorithm.
Ans: In a producer or consumers problem, a producer (process) produces the information that is consumed by a consumer (process). For example, a compiler may produce assembly code, which is consumed by an assembler. A producer can produce one item while the consumer is consuming another item. The producer and consumer must be synchronized. This problem can be solved either through unbound buffer or bounded buffer. The algorithm for producer consumer problem is given below:
Shared Data
char item;
char buffer[n];
semaphore full = 0;
semaphore empty = n;
semaphore mutex = 1;
char nextp, nextc;
Producer Process
do
{
produce an item in nextp
wait(empty);
wait(mutex);
add nextp to buffer
signal(mutex);
signal(full);
}
while(true)
Consumer Process
do
{
wait(full);
wait(mutex);
remove an item from buffer to nextc
signal(mutex);
signal(empty);
consume the item in nextc;
}
Q11. Explain readers and writers problem by giving algorithm.
Ans: The readers/writers problem is one of the classic synchronization problems. It is often used to compare and contrast synchronization mechanisms. It is also an eminently used practical problem. A common paradigm in concurrent application is isolation of shared data such as a variable, buffer, or document and the control of access to that data. This problem has two types of clients accessing the shared data. The first type, referred to as readers, only wants to read the shared data. The second type, referred to as the writers may want to modify the shared data. There is also a designed central data server or controller. It enforces exclusive writer semantics; if a writer is active then no other writer or reader can be active. The service can support clients that wish to both read and write. The algorithm for the solution of readers and writers problem is given below:
semaphore mutex = 1;
semaphore db = 1;
int reader_count;
reader()
{
while(TRUE)
{
down(&mutex);
reade_count= reader_count + 1;
if(reader_count==1)
down(&db);
up(&mutex);
read_db();
down(&mutex);
reader_count = reader_count – 1;
if(reader_count ==0;
up(&db);
up(&mutex);
reader_countuse_data();
}
writer()
{
while(TRUE)
{
create_data();
down(&db);
write_db();
up(&db);
}
Q12. Explain the Dinning Philosophers problem.
Ans: Five philosophers sit around a circular table. Each philosopher spends his life alternatively thinking and eating. In the centre of the table is a large bowl of rice. A philosopher needs two chopsticks to eat. Only 5 chopsticks are available and a chopstick is placed between each pair of philosophers. They agree that each will only use the chopstick to his immediate right and left. From time to time, a philosopher gets hungry and tries to grab the two chopsticks that are immediate left and right to him. When a hungry philosopher has both his chopsticks at the same time, he eats without releasing his chopsticks. When he finished eating, he puts down both his chopsticks and start thinking again. The algorithm for dinning philosophers is given below:
#define N5
#define RIGHT(i) (((i) + 1) % N)
#define LEFT(i) (((i)==N? 0: (i) + 1)
typedef enum {THINKING, HUNGRY, EATING} phil_state;
phil_state sate[N];
semaphore mutex = 1;
semaphore s[N];
/*one per philosopher, all0 */
void get_forks(int i) {
state[i] = HUNGRY;
while(state[i] == HUNGRY) {
P(mutex);
If(state[i] == HUNGRY &&
state[LEFT] != EATING &&
state[RIGHT(i) != EATING) {
state[i] = EATING;
V(s[i]);
}
V(mutex);
P(s[i]);
}
}
void put_forks(int i) {
P(mutex);
state[i] = THINKING;
if(state[LEFT(i)]==HUNGRY) V(s[LEFT(i)]);
if(state[RIGHT(i)]==HUNGRY)V(s[RIGHT(i)]);
V(mutex);
}
void philosopher (int process) {
while(1) {
think();
get_forks(process);
eat();
put_forks();
}
}
Q13. Explain the sleeping barber problem.
Ans: A barber shop consists of a waiting room with chairs, and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barber shop and all chairs are occupied, then the customer leaves the shop. If the barber is busy, but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. The algorithm for sleeping barber problem is given below:
#define CHAIRS 5
typedef int semaphore;
semaphore customers = 0;
semaphore barbers – 0;
semaphore mutex = 1;
int waiting = 0;
void barber(void)
{
While(TRUE) {
down(&customers);
down(&mutex);
waiting = waiting – 1;
up(&barbers);
up(&mutex);
cut_hair();
}
}
void customer(void)
{
down(&mutex);
if(waiting < CHAIRS)
{
waiting = waiting + 1;
up(&customers);
up(&mutex)
down(&barbers);
get_haircut();
}
else
{
up(&mutex);
}
}
Q14. What are locks?
Ans: Locks are another synchronization mechanism. A lock has got two atomic operations to provide mutual exclusion. These two operations are Acquire and Release. A process will acquire a lock before accessing a shared variable and later it will be released. A process locking a variable will run the following code: Lock-Acquire(); critical section and Lock-Release();. The difference between a lock and a semaphore is that a lock is released only by the process that has acquired it earlier.
BLOCK 1 UNIT 4
DEADLOCKS
Q1. What is deadlock?
Ans: A deadlock is a situation where a group of processes is permanently blocked as a result of each process having acquired a set of resources needed for its completion and having to wait for the release of the remaining resources held by other thus making it impossible for any of the deadlocked processes to proceed.
Q2. What are the two types of resources?
Ans: The two types of resources are given below:
(a) Pre-emptive resources: This resource can be taken away from the process with no ill effects. Memory is an example of a pre-emptable resource.
(b) Non-Preemptive Resources: This resource cannot be taken away from the process without causing ill effect. Form example, CD resources are not preemptable at an arbitrary moment.
Q3. What are the characteristics of a deadlock or four necessary conditions for deadlock?
Ans: The four necessary conditions that must hold simultaneously for a deadlock to occur are explained below:
(i) Mutual Exclusion Condition
The resources involved are non-shareable. At least one resource must be held in a non-shareable mode, which is only one process at a time claims exclusive control of the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.
(ii) Hold and Wait Condition
In this condition, a requesting process already holds resources and waiting for the requested resources. A process, holding a resource allocated to it waits for an additional resources(s) that is/are currently being held by other processes.
(iii) Non-Preemptive Condition
Resources already allocated to a process cannot be preempted. Resources cannot be removed forcibly from the processes. After completion, they will be released voluntarily by the process holding it.
(iv) Circular Wait Condition
The processes in the system form a circular list or chain where each process in the list is waiting for a resource held by the next process in the list.
Q4. Explain the deadlock prevention mechanism.
Ans: Havender gives algorithm for deadlock prevention. The Havender’s algorithm for deadlock prevention is explained below:
(a) Elimination of Mutual Exclusion Condition
The mutual exclusion condition must hold for non-shareable resources. That is, several processes cannot simultaneously share a single resource. This condition is difficult to eliminate because some resources such as the tap drive and printer, are inherently non-shareable. Note that shareable resources like read-only file do not require mutually exclusive access and thus cannot be involved in deadlock.
(b) Elimination of Hold and Wait Condition
There are two possibilities for the elimination of hold and wait condition. The first alternative is that a process request be granted all the resources it needs at once, prior to execution. The second alternative is to disallow a process from requesting resources whenever it has previously allocated resources. This strategy requires that all the resources a process will need must be requested at once.
(c) Elimination of No-Preemption Condition
The non-preemption condition can be alleviated by forcing a process waiting for a resource that cannot immediately be allocated, to relinquish all of its currently held resources, so that other processes may use them to finish their needs.
(d) Elimination of Circular Wait Condition
The last condition, the circular wait, can be denied by imposing a total ordering on all of the resource types and than forcing all processes to request the resources in order of increasing or decreasing. This strategy imposes a total ordering of all resources types, and requires that each process request resources in a numerical order of enumeration.
Q5. Explain how to avoid deadlock?
Ans: The most famous deadlock avoidance algorithm from Dijkstra is the Banker’s Algorithm. The Banker algorithm is based on the banking system, which never allocates its available cash in such a manner that it can no longer satisfy the needs of all its customers. The Banker’s algorithm is based on the banking system, which never allocates its available cash in such a manner that it can no longer satisfy the needs of all its customers. The following are the features that are to be considered for avoidance of the deadlock per the Banker’s Algorithms:
(1) Each process declares maximum number of resources of each type that it may need.
(2) Keep the system in a safe state in which we can allocate resources to each process in some order and avoid deadlock.
(3) Check for the safe state by finding a safe sequence: <P1, P2…Pn> where resources that Pi needs can be satisfied by available resources plus resources held by Pj where j < i.
(4) Resource allocation graph algorithm uses claim edges to check for safe state.
Q6. What are the limitations of the Banker’s algorithm?
Ans: The limitations of the Banker’s algorithm are given below:
(1) It is time consuming to execute on the operation of every resource.
(2) If the claim information is not accurate, system resources may be underutilized.
(3) Another difficulty can occur when a system is heavily loaded.
(4) New processes arriving may cause a problem.
(5) A resource becoming unavailable can result in an unsafe state.
Q7. Explain deadlock detection.
Ans: Detection of deadlocks is the most practical policy, which being both liberal and cost efficient, most operating system deploys. To detect a deadlock, we must go about in a recursive manner and simulate the most favored execution of each unblocked process.
(i) An unblocked process may require all the needed resources and will execute.
(ii) It will then release all the required resources and remain dormant thereafter.
(iii) The now released resources may wake up some previously blocked process.
(iv) Continue the above steps as long as possible.
(v) If any blocked processes remain, they are deadlocked.
Q8. What are the methods of recovery from deadlock?
Ans: The methods of recovery from deadlock are explained below:
(a) Recovery from process termination
In this approach, we terminate deadlocked processes in a systematic way taking into account their priorities. The moment, enough processes are terminated to recover from deadlock, we stop the process termination.
(b) Recovery by check pointing and rollback.
Check pointing is saving enough state of a process so that the process can be restarted at the point in the computation where the checkpoint was taken. If a deadlock is detected, one or more processes are restarted from their last checkpoint. Restarting a process from a checkpoint is called rollback. It is done with the expectation that the resource requests will not interleave again to produce deadlock.
BLOCK-2 UNIT-1
MEMORY MANAGEMENT
Q1. What is memory? What the activities of OS into memory?
Ans: Memory is central to the operation of a modern computer system. Memory is large array of words or bytes, each location with its own address. The CPU fetches from the program from the hard disk and stores in memory. If a program is to be executed, it must be mapped to absolute addresses and loaded into memory.
The operating system is responsible for the following activities in connection with memory management:
(i) Keep track of which parts of memory are currently being used and by whom.
(ii) Decide which processes are to be loaded into memory when memory space becomes available.
(iii) Allocate and de-allocate memory space as needed.
Q2. Explain contiguous and non-contiguous memory allocation.
Ans: In contiguous memory allocation, each program data and instruction are allocated a single contiguous space in memory. In non contiguous memory allocation, each programs data and instructions are allocated memory space that is not continuous. This unit focuses on contiguous memory allocation scheme.
Q3. What is overlay? What are its limitations?
Ans: An overlay is a part of an application, which has been loaded at same origin where previously some other parts of the program were residing. A program based on overlay scheme mainly consists of following:
· A root piece which is always memory resident.
· Set of overlays.
The limitations of overlays are given below:
(i) Require careful and time consuming planning.
(ii) Programmer is responsible for organizing overlay scheme of the program with the help of files structures etc. and also to ensure that piece of code is already loaded when it is called.
(iii) Operating system provides the facility to load files into overlay region.
Q4. What is swapping? List the benefits of swapping.
Ans: Swapping is an approach for memory management by bringing each process in entirely, running it and then putting it back on the disk, so that another program may be loaded into that space. Swapping is a technique that lets you use a disk file as an extension of memory. Lower priority user processes are swapped to backing store when they are waiting for I/O or some other event like arrival of higher priority processes. This is rollout swapping. Swapping the process back into store when some event occurs, or when needed is known as roll in swapping.
The major benefits of using swapping are:
(i) Allows higher degree of multi-programming.
(ii) Allows dynamic relocation i.e. if address binding at execution time is being used we can swap in different location else in case of compile and load time bindings processes have to be moved to same location only.
(iii) Better memory utilization.
(iv) Less wastage of CPU time on compaction and
(v) Can easily be applied on priority based scheduling algorithms to improve performance.
Q5. What is memory management unit?
Ans: Memory management unit is a hardware device that maps logical address to the physical address. It maps the virtual address to the real store location. The simple MMU scheme adds the relocation register contents to the base address of the program that is generated at the time it is sent to memory.
Q6. Explain the different partition systems.
Ans: The different partitions systems are given below:
(a) Single Partition System
This approach keeps the operating system in the lower part of the memory and other user processes in the upper part. With this scheme, operating system can be protected from updating in user processes. Relocation register scheme known as dynamic relocation is useful for this purpose. It not only protects user processes from each other but also from changing OS code and data.
(b) Multiple Partition System
This is also known as static partitioning scheme. Simple memory management scheme is to divide memory into n possibly unequal fixed sized partitions, each of which can hold exactly one process. The degree of multiprogramming is dependent on the number of partitions. IBM used this scheme for systems 360. The partition boundaries are not moveable.
(c) Variable Sized Partition System
This scheme is also known as dynamic partitioning. In this scheme, boundaries are not fixed. Processes accommodate memory according to their requirement. There is no wastage as partition size is exactly same as the size of the user process. Initially when processes start this wastage can be avoided but later on when they terminate them leave holds in the main storage.
Q7. What is paging? What are its advantages and disadvantages of paging?
Ans: Logical memory is divided into a number of fixed sizes chunks called pages. The physical memory is also pre-divided into same fixed sized blocks as is the size of the page called page frames. The page sizes also the frame sizes are always powers of 2 and vary between 512 bytes to 8192 bytes per page. The reason behind this is implementation of paging mechanism u sing page number and page offset.
There are different page allocation policies which are explained below:
1) Best Fit Policy – Allocating the hole in which the process fits most tightly i.e. the difference between the hole size and the process size is the minimum one.
2) First Fit Policy – Allocating the first available hole according to memory order which is big enough to accommodate the new process.
3) Worst Fit Policy – Allocating the largest hole that will leave maximum amount of unused space i.e. leftover space is maximum after allocation.
The advantages of paging are given below:
(a) Virtual address space must be greater than main memory size i.e. can execute program with large logical address space as compared with physical address space.
(b) Avoid external fragmentation and hence storage compaction.
(c) Full utilization of available main storage.
Disadvantages of paging include internal fragmentation problem i.e. wastage within allocated page when process is smaller than page boundary. Also extra resource consumption and overheads for paging hardware and virtual address to physical address translation takes place.
Q8. Explain segmentation.
Ans: Segmentation is a memory management scheme that view system memory as a collection of variable sized segments rather than as a linear array of words. Segmentation presents an alternative scheme for memory management. This scheme divides the logical address space into variable length chunks called segments with no proper ordering among them.
The mapping between two is done by segment table, which contains segment based and its limit. The segment base has starting physical address of segment and segment limit provides the length of segment. This scheme is similar to variable partition allocation method with improvement that the process is divided into parts. For fast retrieval we can use registers as in page scheme. This is known as segment table length register. The segments in a segmentation scheme correspond to logical divisions of the process and are defined by program names.
Protection and sharing method also allows segment that are read only to be shared so that two processes can use shared code for better memory efficiency. The implementation is such that no program can read from or write to segments belonging to another program, except the segments that have been set up to be shared.
BLOCK 2 UNIT 2
VIRTUAL MEMORY
Q1. Explain the concept of virtual memory.
Ans: The virtual memory scheme divides physical memory into blocks and allocates blocks to different processes. The advantage of using virtual memory is that it reduces the time taken to launch a program, since not all the program code and data needed to be in physical memory before the program execution can be started. Virtual memory automatically manages two levels of the memory hierarchy representing the main memory and the secondary storage, in a manner that is invisible to the program that is running. The program itself never has to bother with the physical location of any fragment of the virtual address space. A mechanism called relocation allows for the same program to run in any location in physical memory as well. Virtual memory enables a program to ignore the physical location of any desired block of its address space; a process can simply seek to access any block of its address space without concern for where that block might be located. The purpose of virtual memory is to enlarge the address space, the set of address a program can utilize.
Q2. What are the functions of virtual memory management?
Ans: The functions of virtual memory management are given below:
1. Make portions of the logical address space resident in physical RAM.
2. Make portions of the logical address space immovable in physical RAM.
3. Map logical to physical addresses.
4. Defer execution of application defined interrupt code until a safe time.
Q3. What are the steps that are followed by the operating system in handling a page fault?
Ans: The steps that are followed in handling a page fault are:
1. If a process refers to a page which is not in the physical memory then an internal table kept with a process control block is checked to verify whether a memory reference to a page was valid or invalid.
2. If the memory reference to a page was valid, but the page is missing, the process of bringing a page into the physical memory starts.
3. Free memory location is identified to bring a missing page.
4. By reading a disk, the desired page is brought back into the free memory location.
5. Once the page is in the physical memory, the internal table kept with the process and page map table is updated to indicate that the page is now in memory.
6. Restart the instruction that was interrupted due to the missing page.
Q4. What is demand paging?
Ans: In demand paging pages are loaded only on demand, not in advance. It is similar to paging system with swapping feature. Rather than swapping the entire program in memory, only those pages are swapped which are required currently by the system.
Q5. How do you implement the virtual memory?
Ans: Virtual memory can be implemented as an extension of paged or segmented memory management scheme, also called demand paging or demand segmentation respectively.
Q6. When do a page fault and thrashing occur?
Ans: A page fault occurs when a process accesses an address in a page which is not currently resident in memory. Thrashing occurs when the incidence of page faults becomes so high that the system spends all its time swapping pages rather than doing useful work. This happens if the number of process either because there is inadequate physical memory or because the program is very badly organized.
Q7. What are the features of page swap algorithm?
Ans: The features of page swap algorithm are given below:
(a) Impose the minimum overhead in operation.
(b) Not assume any particular hardware assistance.
(c) Try to prevent swapping out pages which are currently referenced.
(d) Try to avoid swapping modified pages.
BLOCK 2
UNIT 3
INPUT OUTPUT AND FILE MANAGEMENT
Q1. What are the activities of operating system in concerned with file management?
Ans: The operating system is responsible for the following activities in connection with file management:
(a) The creation and deletion of files
(b) The creation and deletion of directory.
(c) The support of primitives for manipulating files and directories.
(d) The mapping of files onto disk storage.
(e) Backup of files on stable storage.
Q2. What is I/O buffering?
Ans: A buffer is an intermediate memory area under operating system control that stores data in transit between two devices or between users work area and device. It allows computation to proceed in parallel with I/O. There are two I/O buffering; single and double buffering. In case of single buffered transfer, blocks are first read into a buffer and then moved to the user’s work area. When the move is complete, the next block is read into the buffer and proceeds in parallel with the first block. Double buffering is an improvement over single buffering. A pair of buffer is used; blocks/records generated by running process are initially stored in the first buffer until it is full. Then from this buffer it is transferred in the second buffer and when this second buffer is also full and first buffer transfer is complete.
Q3. Explain the concept of RAID.
Ans: Redundant Array of Inexpensive Disks is the technique employed for the improvement of disk usage. Its organization is based on disk striping or interleaving which uses a group of disks as one storage unit. Disk striping is a way of increasing the disk transfer rate up to a factor of N, by splitting files across N different disks. Instead of saving all the data from a given file on one disk, it is split across many. Since the N heads can now search independently, the speed of transfer is in principle increased manifold. Logical disks data blocks can be written on two or more separate physical disks which can further transfer their sub-blocks can be written on two or more separate physical disks which an further transfer their sub-blocks in parallel. The total transfer rate system is directly proportional to the number of disks. The larger the number of physical disk strips together, the larger the total transfer rate of the system. Hence, the overall performance and disk accessing speed is also enhanced.
Q4. What is disk cache?
Ans: Disk caching is an extension of buffering. A cache is a collection of blocks that logically belong on the disk, but are kept in memory for performance reasons. It is used in multiprogramming environment or in disk file servers which maintain a separate section of main memory called disk cache.
Q5. What is virtual device?
Ans: A virtual device is a simulation of an actual device by the operating system. It responds to the system calls and helps in achieving device independence. Example, Print Spooler.
BLOCK 2 UNIT – 4
SECURITY AND PROTECTION
Q1. Explain the difference between security policy and security model.
Ans: The security policy outlines several high level points: how the data is accessed, the amount of security required and what the steps are when these requirements are to met. The security model is more in depth and supports the security policy. Security models are important concept in the design of any security system. They all have different security policies applying to the system.
Q2. Explain the different types of security models.
Ans: The different types of security models are explained below:
(a) Access Matrix Model
The access matrix model for computer protection is based on abstraction of operating system structures. Because of its simplicity and generality, it allows a variety of implementation techniques as has been widely used. There are three principal components in the access matrix model:
· A set of passive objects
· A set of active subjects, which may manipulate the objects
· A set of rules governing the manipulation of objects by subjects.
(b) Mandatory Access Control
In a mandatory access control environment, all requests for access to resources are automatically subject to access controls. In such environments, all users and resources are classified and receive one or more security labels. When a user request a resource, the associated security labels are examined and access is permitted only if the user label is greater than or equal to that of the resource.
(c) Discretionary Access Control
In a discretionary access control environment, resource owners and administrators jointly control access to resources. This model allows for much greater flexibility and drastically reduces the administrative burdens of security implementation.
(d) Rule Based Access Control
In general, rule based access control systems associate explicit access controls with specified system resources such as files or printers. In such environment, administrators typically establish access rules on a per resource basis and the underlying operating system or directory services employ those rules to grant or deny access to users who request access to such resources. Rule based access control may use a MAC or DAC scheme, depending on the management role of resource owners.
(e) Role Based Access Control
Role based access control enforces access controls depending upon a user roles. Roles represent specific organizational duties and are commonly mapped to job titles such as administrators, developers, system analyst, etc.
(f) Take Grant Model
Take grant models use graphs to model access control. They have been well researched. These fundamentally access matrix models. The graph structure can be represented as an adjacency matrix and labels on the arcs can be coded as different values in the matrix.
(g) Multilevel Models
This type of models corresponds to the multilevel policies where data is classified into sensitivity levels and users have access according to their clearance. Because of the way they control security they have also been called data flow models, they control the allowed flow of data between levels.
(h) Biba Integrity Model
This model is a modification of the Bell La Padula mode, with emphasis on integrity. There are two properties of Biba Model.
Ø Simple Integrity Property – It is a subject may have write access to an object only if the security level of the subject is either higher or equal to the level of object.
Ø Integrity Property – A subject has the read only access to an object o, then it can also have the write access to another object p only if the security level of p is either lower or equals to the level of o.