Shanto Mariam University of Creative Technology

Department of Computer Science and Engineering

Course Name: Operating system

Course Code: CSE 3167
Submitted to: Pelob Chakraborti

Submitted by: Rakibul Hasan Rakib

Department: CSE
ID: 181071019
Batch: 17th
Semester: 7th
Date of Submission: 11June 2020.
 Operating System Final Assignment
Deadlock :

Deadlock detection is the process of actually determining that a deadlock exists and
identifying the processes and resources involved in the deadlock.
The basic idea is to check allocation against resource availability for all possible
allocation sequences to determine if the system is in deadlocked state a. Of course, the
deadlock detection algorithm is only half of this strategy. Once a deadlock is detected,
there needs to be a way to recover several alternatives exists:

 Temporarily prevent resources from deadlocked processes.

 Back off a process to some check point allowing preemption of a needed
resource and restarting the process at the checkpoint later.
 Successively kill processes until the system is deadlock free.

These methods are expensive in the sense that each iteration calls the detection
algorithm until the system proves to be deadlock free. The complexity of algorithm
is O(N2) where N is the number of proceeds. Another potential problem is starvation;
same process killed repeatedly.

Coffman (1971) identified four (4) conditions that must hold simultaneously for there
to be a deadlock.

1. Mutual Exclusion Condition

The resources involved are non-shareable.
Explanation: At least one resource (thread) must be held in a non-shareable mode,
that 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.

2. Hold and Wait Condition

Requesting process hold already, resources while waiting for requested
resources.
Explanation: There must exist a process that is holding a resource already allocated
to it while waiting for additional resource that are currently being held by other
processes.
3. No-Preemptive Condition
Resources already allocated to a process cannot be preempted.
Explanation: Resources cannot be removed from the processes are used to
completion or released voluntarily by the process holding it.
 
4. 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.

As an example, consider the traffic deadlock in the following figure

Consider each section of the street as a resource.

1. Mutual exclusion condition applies, since only one vehicle can be on a section

of the street at a time.
2. Hold-and-wait condition applies, since each vehicle is occupying a section of
the street, and waiting to move on to the next section of the street.
3. No-preemptive condition applies, since a section of the street that is a section of
the street that is occupied by a vehicle cannot be taken away from it.
 4. Circular wait condition applies, since each vehicle is waiting on the next
vehicle to move. That is, each vehicle in the traffic is waiting for a section of
street held by the next vehicle in the traffic.

The simple rule to avoid traffic deadlock is that a vehicle should only enter an
intersection if it is assured that it will not have to stop inside the intersection.

It is not possible to have a deadlock involving only one single process. The deadlock
involves a circular “hold-and-wait” condition between two or more processes, so
“one” process cannot hold a resource, yet be waiting for another resource that it is
holding. In addition, deadlock is not possible between two threads in a process,
because it is the process that holds resources, not the thread that is, each thread has
access to the resources held by the process.

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

File Allocation Table (FAT) 

A file allocation table (FAT) is a file system developed for hard drives that originally
used 12 or 16 bits for each cluster entry into the file allocation table. It is used by the
operating system (OS) to manage files on hard drives and other computer systems. It is
often also found on in flash memory, digital cameras and portable devices. It is used to
store file information and extend the life of a hard drive.
Most hard drives require a process known as seeking; this is the actual physical
searching and positioning of the read/write head of the drive. The FAT file system was
designed to reduce the amount of seeking and thus minimize the wear and tear on the
hard disc.
FAT was designed to support hard drives and subdirectories. The earlier FAT12 had a
cluster addresses to 12-bit values with up to 4078 clusters; it allowed up to 4084
clusters with UNIX. The more efficient FAT16 increased to 16-bit cluster address
allowing up to 65,517 clusters per volume, 512-byte clusters with 32MB of space, and
had a larger file system; with the four sectors it was 2,048 bytes.

Virtual memory:

Virtual memory is a memory management capability of an operating system (OS)

-- which uses hardware and software to allow a computer to compensate for
physical memory shortages, by temporarily transferring data from random access
memory (RAM) to disk storage. virtual address space is increased using active
memory in RAM and inactive memory in hard disk drives (HDDs), to form
contiguous addresses that hold both the application and its data.

4. Explain various directory structured

used in os for storing files give its merits
and demerits.

Answer: A directory is a container that is used to contain folders and file. It

organizes files and folders into a hierarchical manner. The various directory
structure are given below with their merits and demerits.

 Single-level directory,

Single level directory is simplest directory structure in it all files are

contained in same directory which make it easy to support and
understand.

 A single level directory has a significant limitation, however,

when the number of files increases or when the system has
more than one user. Since all the files are in the same directory,
they must have the unique name . if two users call there dataset
test, then the unique name rule violated.

Advantages:

 Since it is a single directory, so its implementation is very easy.

 If files are smaller in size, searching will faster.

 The operations like file creation, searching, deletion, updating
are very easy in such a directory structure.

Disadvantages:

 There may chance of name collision because two files can not
have the same name.

 Searching will become time taking if directory will large.

 In this can not group the same type of files together.

 Two-level directory –

As we have seen, a single level directory often leads to

confusion of files names among different users. the solution to
this problem is to create a separate directory for each user.

 In the two-level directory structure, each user has there own

Advantages:

 We can give full path like /User-name/directory-name/.

 Diffrent users can have same directory as well as file name.

 Searching of files become more easy due to path name and

user-grouping.

Disadvantages:

 A user is not allowed to share files with other users.

 Still it not very scalable, two files of the same type cannot be
grouped together in the same user.

 Tree-structured directory –

 Once we have seen a two-level directory as a tree of height 2,

the natural generalization is to extend the directory structure to
a tree of arbitrary height.

 This generalization allows the user to create there own

subdirectories and to organise on their files accordingly.

 A tree structure is the most common directory structure. The

tree has a root directory, and every file in the system have a
unique path.

Advantages:

 Very generalize, since full path name can be given.

 Very scalable, the probability of name collision is less.

 Searching becomes very easy, we can use both absolute path

as well as relative.

Disadvantages:

 Every file does not fit into the hierarchical model, files may be
saved into multiple directories.

 We can not share files.

 It is inefficient, because accessing a file may go under multiple

directories.

 Acyclic graph directory –

 An acyclic graph is a graph with no cycle and allows to share

subdirectories and files. The same file or subdirectories may be
in two different directories. It is a natural generalization of the
tree-structured directory.

 It is used in the situation like when two programmers are

working on a joint project and they need to access files.
 It is the point to note that shared file is not the same as copy
file if any programmer makes some changes in the subdirectory
it will reflect in both subdirectories.

Advantages:

 We can share files.

 Searching is easy due to different-different paths.

Disadvantages:

 We share the files via linking, in case of deleting it may create

the problem,

 If the link is softlink then after deleting the file we left with a
dangling pointer.

 In case of hardlink, to delete a file we have to delete all the

reference associated with it.

 General graph directory structure –

 In general graph directory structure, cycles are allowed within a
directory structure where multiple directories can be derived
from more than one parent directory.

 The main problem with this kind of directory structure is to

calculate total size or space that have been taken by the files
and directories.

Advantages:

 It allows cycles.

 It is more flexible than other directories structure.

Disadvantages:

 It is more costly than others.

 It needs garbage collection.

5. A variable portion memory system has at

some point in time the following box sizes in
the order 20k,15k,40k,60k,10k,25k, a new
process is to be loaded which block will be
filled using best fit, first fit, worst fit
respectively.
Answer: First feat,

allocate the 1st hole that is big enough for a first feat 40K is
preferred.

Best feet,

allocate the smallest hole that is a big enough must search

entire list an with ordered by size produces the smallest leftover
hole. For 25 K using best fit the whole of 25 K is preferred.

Worst feet,

allocate the largest whole must also search entire list.

Produces the largest leftover whole for worst feet 60 K
preferred.

So, first feet and best fit bit turned them was then worst feat in
terms of speed and storage utilization.

6. Describe the dining-philosopher’s problem

and provide its solution. How will you handle
synchronization problem using hardware? Discuss.

Answer: In computer science, the dining philosophers

problem is an example Problem hello used in concurrent
algorithm design to illustrate synchronization Issues and
techniques for resolving them.
Solution for dining philosophers problem is to use a semaphore
to represent a chopstick. A chopstick can be picked up by
executing a wait operation on the semaphore and released by
executing a signal semaphore.The critical section problem could
be solved easily in a single-processor environment if we could
disallow interrupts to occur while a shared variable or resource is
being modified.

7.What are the various free space

management technique? Discuss it
Answer: Bitmap or Bit vector – A Bitmap or Bit Vector is series
or collection of bits where each bit corresponds to a disk block.

Linked List – In this approach, the Free disk blocks are linked

together i.e. a free block contains a pointer to the next free
block.

Grouping,

Counting.

8.What is the critical section problems?

what are its various solutions?
Answer: The critical section is a code segment where the
shared variables can be accessed. An atomic action is required
in a critical section i.e. only one process can execute in its
critical section at a time. All the other processes have to wait to
execute in their critical sections.

Solutions,
 Mutual Exclusion
Mutual exclusion implies that only one process can be inside the
critical section at any time. If any other processes require the critical
section, they must wait until it is free.

 Progress
Progress means that if a process is not using the critical section, then
it should not stop any other process from accessing it. In other words,
any process can enter a critical section if it is free.

 Bounded Waiting
Bounded waiting means that each process must have a limited
waiting time. It should not wait endlessly to access the critical section.

9.What is paging? Explain the structure inverted

page table.
Answer: Paging is a method of writing data to, and reading it from,
secondary storage for use in primary storage, also known as main
memory. Paging plays a role in memory.
Inverted page table is the global page table which is maintained by
the Operating System for all the processes. In inverted page table, the
number of entries is equal to the number of frames in the main
memory. It can be used to overcome the drawbacks of page table.

10. Explain the concept of thrashing?

Answer: In a virtual storage system thrashing is a condition in which
excessive paging operations are taking place. A system that
is thrashing can be perceived as either a very slow system or one that
has come to a halt.
 11.Explain how buffering is used with respect to
storage devices.
Answer: In computer science, a data buffer is a region of a physical
memory storage used to temporarily store data while it is being
moved from one place to another.However, a buffer may be used
when moving data between processes within a computer.

12.Discuss banker’s algorithm in detail also

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

 2 Printers.

 4 Scanners.

 3 Hard disks.