TECHNO INTERNATIONAL BATANAGAR

COMPUTER SCIENCE & ENGINEERING

SPECIAL ASSIGNMENT

SUBMITTED BY:-
NAME- Pankaj Roy
DEPT.- COMPUTER SCIENCE & ENGINEERING
ROLL NO.- 33200117024
SEMESTER-6th SEM(3RD YEAR)
SUBJECT- OPERATION RESEARCH
SUBJECT CODE- CS-(603)

1
 GROUP – A

1.

I. Which of the following page replacement algorithms suffers from Belady’s Anomaly?

a) Optimal replacement b) LRU

c) FIFO d) Both optimal replacement and FIFO

Ans:C)FIFO

II. FAT stands for :

a) File Attribute Transport b) File Allocation Table

c) File Attribute Table d) None of these

Ans:B)File Allocation Table

III. CPU generated address is :

a)Logical Address b) Physical Address

c) both A and B d) None of these.

Ans:A)Logical Address

2
 Group – B

2. What do you mean by Direct Memory Access (DMA).

Ans: DMA stands for “Direct Memory Access” and is a method of transferring data from the computer‘s RAM to another
part of the computer without processing it using the CPU. While most data that is input or output from your computer is
processed by the CPU, some data does not require processing, or can be processed by another device.

In these situations, DMA can save processing time and is a more efficient way to move data from the computer’s
memory to other devices. In order for devices to use direct memory access, they must be assigned to a DMA channel.
Each type of port on a computer has a set of DMA channels that can be assigned to each connected device. For example,
a PCI controller and a hard drive controller each have their own set of DMA channels.

DMA Transfer Types

Memory To Memory Transfer

In this mode block of data from one memory address is moved to another memory address. In this mode current
address register of channel 0 is used to point the source address and the current address register of channel is used to
point the destination address in the first transfer cycle, data byte from the source address is loaded in the temporary
register of the DMA controller and in the next transfer cycle the data from the temporary register is stored in the
memory pointed by destination address. After each data transfer current address registers are decremented or
incremented according to current settings. The channel 1 current word count register is also decremented by 1 after
each data transfer. When the word count of channel 1 goes to FFFFH, a TC is generated which activates EOP output
terminating the DMA service.

Auto initialize

In this mode, during the initialization the base address and word count registers are loaded simultaneously with the
current address and word count registers by the microprocessor. The address and the count in the base registers remain
unchanged throughout the DMA service.After the first block transfer i.e. after the activation of the EOP signal, the
original values of the current address and current word count registers are automatically restored from the base address
and base word count register of that channel. After auto initialization the channel is ready to perform another DMA
service, without CPU intervention.

3
3. What do you mean by Fragmentation? What are the types of Fragmentation?

And describe it.

Ans: In contiguous memory allocation whenever the processes come into RAM, space is allocated to them. These spaces
in RAM are divided either on the basis of fixed partitioning(the size of partitions are fixed before the process gets loaded
into RAM) or dynamic partitioning (the size of the partition is decided at the run time according to the size of the
process). As the process gets loaded and removed from the memory these spaces get broken into small pieces of
memory that it can’t be allocated to the coming processes. This problem is called fragmentation.Fragmentation is an
unwanted problem where the memory blocks cannot be allocated to the processes due to their small size and the blocks
remain unused. It can also be understood as when the processes are loaded and removed from the memory they create
free space or hole in the memory and these small blocks cannot be allocated to new upcoming processes and results in
inefficient use of memory. Basically, there are two types of fragmentation:

• Internal Fragmentation
• External Fragmentation

Internal Fragmentation

In this fragmentation, the process is allocated a memory block of size more than the size of that process. Due to this
some part of the memory is left unused and this cause internal fragmentation.

Example: Suppose there is fixed partitioning (i.e. the memory blocks are of fixed sizes) is used for memory allocation in
RAM. These sizes are 2MB, 4MB, 4MB, 8MB. Some part of this RAM is occupied by the Operating System (OS).

Now, suppose a process P1 of size 3MB comes and it gets memory block of size 4MB. So, the 1MB that is free in this
block is wasted and this space can’t be utilized for allocating memory to some other process. This is called internal
fragmentation.

External Fragmentation

In this fragmentation, although we have total space available that is needed by a process still we are not able to put that
process in the memory because that space is not contiguous. This is called external fragmentation.

Example: Suppose in the above example, if three new processes P2, P3, and P4 come of sizes 2MB, 3MB, and 6MB
respectively. Now, these processes get memory blocks of size 2MB, 4MB and 8MB respectively allocated.

So, now if we closely analyze this situation then process P3 (unused 1MB)and P4(unused 2MB) are again causing internal
fragmentation. So, a total of 4MB (1MB (due to process P1) + 1MB (due to process P3) + 2MB (due to process P4)) is
unused due to internal fragmentation.

4
 Group – C

4. Consider the following page reference string:

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1.

Calculate the number of page faults and page fault rate for the following algorithms.

Assuming 3 frames are available and all are initially empty.

i) FIFO Page Replacement.

ii) LRU Page Replacement.

Ans:

FIFO:

Input 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
F1 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
F2 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0
F3 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7
Faults F F F F F F F F F F F F F F F
No. of page faults: 15 &

Page fault Rate is:15/20=0.75

LRU:

Input 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
F1 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7
F2 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0
F3 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
Faults F F F F F F F F F F F F
No. of page faults:12 &

Page fault rate is:12/20=0.6

5. Suppose a disk drive has 200 cylinders numbered 0-199.The current position of the arm

is at 50.Consider a disk queue for request are

95 , 180, 34, 119, 11, 123, 62, 64.

Calculate the Total Head Movement for

i. FCFS Scheduling.

ii. SSTF Scheduling.

iii. SCAN Scheduling.

Ans:

1. First Come -First Serve (FCFS) All incoming requests are placed at the end of the queue. Whatever number that is
next in the queue will be the next number served. Using this algorithm doesn't provide the best results. To determine
the number of head movements we would simply find the number of tracks it took to move from one request to the
5
next. For this case it went from 50 to 95 to 180 and so on. From 50 to 95 it moved 45 tracks. If we tally up the total
number of tracks you will find how many tracks it had to go through before finishing the entire request. In this example,
it had a total head movement of 640 tracks. The disadvantage of this algorithm is noted by the oscillation from track 50
to track 180 and then back to track 11 to 123 then to 64. As we will soon see, this is the worse algorithm that one can
use.

Total Head Movement here is:640

2. Shortest Seek Time First (SSTF)

In this case request is serviced according to next shortest distance. Starting at 50, the next shortest distance would be 62
instead of 34 since it is only 12 tracks away from 62 and 16 tracks away from 34. The process would continue until all the
process are taken care of. For example the next case would be to move from 62 to 64 instead of 34 since there are only
2 tracks between them and not 18 if it were to go the other way. Although this seems to be a better service being that it
moved a total of 236 tracks, this is not an optimal one. There is a great chance that starvation would take place. The
reason for this is if there were a lot of requests close to eachother the other requests will never be handled since the
distance will always be greater.

Total Head Movement here is:236

3. Elevator (SCAN)
This approach works like an elevator does. It scans down towards the nearest end and then when it hits the bottom it
scans up servicing the requests that it didn't get going down. If a request comes in after it has been scanned it will not be
serviced until the process comes back down or moves back up. This process moved a total of 230 tracks. Once again this
is more optimal than the previous algorithm, but it is not the best.

6
Total Head Movement here is:230