Practical – 8.

1
OBJECTIVE: - Write a C program to Implement file storage allocation technique: Contiguous
(using array), Linked –list (using linked-list), Indirect allocation (indexing)

Problem Statement: Implement file storage allocation technique: Contiguous (using array), Linked
–list (using linked-list), Indirect allocation (indexing)

PROGRAM: - Contiguous (using array)

#include <stdio.h>
#include <conio.h>
int main()
{
int n, i, j, b[20], sb[20], t[20], x, c[20][20];
printf("Enter no.of files:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
printf("Enter no. of blocks occupied by file%d", i + 1);
scanf("%d", &b[i]);
printf("Enter the starting block of file%d", i + 1);
scanf("%d", &sb[i]);
t[i] = sb[i];
for (j = 0; j < b[i]; j++)
c[i][j] = sb[i]++;
}
printf("Filename\tStart block\tlength\n");
for (i = 0; i < n; i++)
printf("%d\t %d \t%d\n", i + 1, t[i], b[i]);
printf("Enter file name:");
scanf("%d", &x);
printf("File name is:%d", x);
printf("length is:%d", b[x - 1]);
printf("blocks occupied:");
for (i = 0; i < b[x - 1]; i++)
printf("%4d", c[x - 1][i]);
getch();
}

OUTPUT: -
 Practical – 8.2
OBJECTIVE: - Write a C program to Implement file storage allocation technique: Contiguous
(using array), Linked –list (using linked-list), Indirect allocation (indexing)

Problem Statement: Implement file storage allocation technique: Contiguous (using array), Linked
–list (using linked-list), Indirect allocation (indexing)

PROGRAM: - Contiguous (using linked list)

#include <stdio.h>
#include <conio.h>
struct file{
char fname[10];
int start, size, block[10];
} f[10];
main(){
int i, j, n;
printf("Enter no. of files:");
scanf("%d", &n);
for (i = 0; i < n; i++){
printf("Enter file name:");
scanf("%s", &f[i].fname);
printf("Enter starting block:");
scanf("%d", &f[i].start);
f[i].block[0] = f[i].start;
printf("Enter no.of blocks:");
scanf("%d", &f[i].size);
printf("Enter block numbers:");
for (j = 1; j <= f[i].size; j++)
{
scanf("%d", &f[i].block[j]);
}
}
printf("File\tstart\tsize\tblock\n");
for (i = 0; i < n; i++){
printf("%s\t%d\t%d\t", f[i].fname, f[i].start, f[i].size);
for (j = 1; j <= f[i].size - 1; j++)
printf("%d--->", f[i].block[j]);
printf("%d", f[i].block[j]);
printf("\n");
}
getch();
}
OUTPUT: -
 Practical – 8.3
OBJECTIVE: - Write a C program to Implement file storage allocation technique: Contiguous
(using array), Linked –list (using linked-list), Indirect allocation (indexing)

Problem Statement: Implement file storage allocation technique: Contiguous (using array), Linked
–list (using linked-list), Indirect allocation (indexing)

PROGRAM: - Contiguous (using indexing)

#include <stdio.h>
#include <conio.h>
main(){
int n, m[20], i, j, sb[20], s[20], b[20][20], x;
printf("Enter no. of files:");
scanf("%d", &n);
for (i = 0; i < n; i++){
printf("Enter starting block and size of file%d:", i + 1);
scanf("%d%d", &sb[i], &s[i]);
printf("Enter blocks occupied by file%d:", i + 1);
scanf("%d", &m[i]);
printf("enter blocks of file%d:", i + 1);
for (j = 0; j < m[i]; j++)
scanf("%d", &b[i][j]);
}
printf("\nFile\t index\tlength\n");
for (i = 0; i < n; i++){
printf("%d\t%d\t%d\n", i + 1, sb[i], m[i]);
}
printf("\nEnter file name:");
scanf("%d", &x);
printf("file name is:%d\n", x);
i = x - 1;
printf("Index is:%d", sb[i]);
printf("Block occupied are:");
for (j = 0; j < m[i]; j++)
printf("%3d", b[i][j]);
getch();
}
OUTPUT: -
 Practical – 9
OBJECTIVE: - Calculation of external and internal fragmentation, free space list of blocks from
system, List process file from the system

Problem Statement: Calculation of external and internal fragmentation, free space list of blocks
from system, List process file from the system

PROGRAM: -
#include<stdio.h>
#include<conio.h>

void main(){
printf("Internal and Enternal Fragmentation\n");
int ms, bs, nob, ef, n, mp[10], tif=0;
int i, p =0;
printf("Enter the total memory available (in Bytes)");
scanf("%d", &ms);
printf("Enter the block size (in Bytes)");
scanf("%d", &bs);
nob=ms/bs;
ef=ms-nob*bs;
printf("Enter the number of processes");
scanf("%d", &n);
for(i=0;i<n;i++){
printf("Enter memory required for process %d (in Bytes)", i+1 );
scanf("%d", &mp[i]);
}
printf("\nNo. of Blocks available in memory -- %d", nob);
printf("\n\nPROCESS\TMEMORY REQUIRED\TALLOCATED\TINTERNAL
FRAGMENTATION");

for(i=0;i<n && p<nob;i++){

printf("\n%d\t\t%d", i+1, mp[i]);
if(mp[i]>bs)
printf("\t\tNO\t\t---");
else{
printf("\t\tYES\t%d", bs-mp[i]);
tif=tif+bs;

}
}

printf("\nMemory is Full, Remaining Processes cannot be accomodate");

printf("\nTotal Enternal Fragmentation is %d",tif);
printf("\nTotal Internal Fragmentation is %d",ef);

getch();

}
OUTPUT: -
 Practical – 10
OBJECTIVE: - Implementation of resource allocation graph (RAG)

THEORY: -
As Banker’s algorithm using some kind of table like allocation, request, available all that thing to
understand what is the state of the system. Similarly, if you want to understand the state of the
system instead of using those table, actually tables are very easy to represent and understand it, but
then still you could even represent the same information in the graph. That graph is called Resource
Allocation Graph (RAG).
We know that any graph contains vertices and edges. So RAG also contains vertices and edges. In
RAG vertices are two type –
1. Process vertex – Every process will be represented as a process vertex.Generally, the process
will be represented with a circle.
2. Resource vertex – Every resource will be represented as a resource vertex. It is also two type –
• Single instance type resource – It represents as a box, inside the box, there will be one
dot.So the number of dots indicate how many instances are present of each resource type.
• Multi-resource instance type resource – It also represents as a box, inside the box, there
will be many dots present.
Now coming to the edges of RAG.There are two types of edges in RAG –
1. Assign Edge – If you already assign a resource to a process then it is called Assign edge.
2. Request Edge – It means in future the process might want some resource to complete the
execution, that is called request edge.
So, if a process is using a resource, an arrow is drawn from the resource node to the process node. If
a process is requesting a resource, an arrow is drawn from the process node to the resource node

PROGRAM: -
#include <stdio.h>
#include <conio.h>
int proc, res, i, j, row = 0, flag = 0;
static int pro[3][3], req[3][3], st_req[3][3], st_pro[3][3];
int main(){
printf("\nEnter the number of Processes:");
scanf("%d", &proc);
printf("\nEnter the number of Resources:");
scanf("%d", &res);
printf("\nEnter the Process Matrix:");
for (i = 0; i < proc; i++)
for (j = 0; j < res; j++)
scanf("%d", &pro[i][j]);
printf("\nEnter the Request Matrix:");
for (i = 0; i < res; i++)
for (j = 0; j < proc; j++)
scanf("%d", &req[i][j]);
row = 0;
while (!kbhit()){
for (i = 0; i < res; i++){
if (pro[row][i] == 1){
if (st_pro[row][i] > 1 && flag == 1){
 printf("\nDeadlock Occured");
getch();
}
st_pro[row][i]++;
row = i;
break;
}}
for (i = 0; i < proc; i++){
if (req[row][i] == 1){
if (st_req[row][i] > 1){
printf("\nDeadlock Occured");
getch();
}
st_req[row][i]++;
row = i;
flag = 1;
break;
}}}
printf("\nNo Deadlock Detected");
getch();
getch();
}

OUTPUT: -
 Practical – 11

OBJECTIVE: - Write a C program to Implement the solution for Bounded Buffer (producer-
consumer) problem using inter process communication techniques-Semaphores

PROBLEM STATEMENT: -
The producer-consumer problem illustrates the need for synchronization in systems where many
processes share a resource. In the problem, two processes share a fixed-size buffer. One process
produces information and puts it in the buffer, while the other process consumes information from
the buffer. These processes do not take turns accessing the buffer, they both work concurrently.
Herein lies the problem. What happens if the producer tries to put an item into a full buffer? What
happens if the consumer tries to take an item from an empty buffer?

OBJECTIVE
Producers produce items to be stored in the buffer. Consumers remove and consume items which
have been stored. Mutual exclusion must be enforced on the buffer itself. Moreover, producers can
store only when there is an empty slot, and consumers can remove only when there is a full slot.
Three semaphores are used. The binary semaphore mutex controlls access to the buffer itself. The
counting semaphore empty keeps track of empty slots, and the counting semaphore full keeps track
of full slots.
In this example, the buffer is implemented as an array of size MAX treated as a circular (ring)
buffer. Variables in and out give the index of the next position for putting in and taking out (if any).
Variable count gives the number of items in the buffer.

ALGORITHM: -
Step 1: The Semaphore mutex, full & empty are initialized.
Step 2: In the case of producer process
i) Produce an item in to temporary variable.
ii) If there is empty space in the buffer check the mutex value for enter into the critical
section.
iii) If the mutex value is 0, allow the producer to add value in the temporary variable to the
buffer.
Step 3: In the case of consumer process
i) It should wait if the buffer is empty
ii) If there is any item in the buffer check for mutex value, if the mutex==0, remove item
from buffer
iii) Signal the mutex value and reduce the empty value by 1.
iv) Consume the item.
Step 4: Print the result

PSEUDO CODE:
shared binary semaphore mutex = 1;
shared counting semaphore empty = MAX;
shared counting semaphore full = 0;
shared anytype buffer[MAX];
shared int in, out, count;
PRODUCER :
 anytype item;

repeat {
/* produce something */
item = produce();

/* wait for an empty space */

P(empty);

/* store the item */

P(mutex);
buffer[in] = item;
in = in + 1 mod MAX;
count = count + 1;
V(mutex);

/* report the new full slot */

V(full);

} until done;

CONSUMER:
anytype item;
repeat {

/* wait for a stored item */

P(full);

/* remove the item */

P(mutex);
item = buffer[out];
out = out + 1 mod MAX;
count = count - 1;
V(mutex);

/* report the new empty slot */

V(empty);

/* consume it */
consume(item);
} until done;

PROGRAM: -
#include <stdio.h>
#include <stdlib.h>
int mutex = 1, full = 0, empty = 3, x = 0;
int main(){
int n;
void producer();
void consumer();
int wait(int);
 int signal(int);
printf("\n1.Producer\n2.Consumer\n3.Exit");
while (1){
printf("\nEnter your choice:");
scanf("%d", &n);
switch (n){
case 1:
if ((mutex == 1) && (empty != 0))
producer();
else
printf("Buffer is full!!");
break;
case 2:
if ((mutex == 1) && (full != 0))
consumer();
else
printf("Buffer is empty!!");
break;
case 3:
exit(0);
break;
}}
return 0;
}
int wait(int s){
return (--s);
}
int signal(int s){
return (++s);
}
void producer(){
mutex = wait(mutex);
full = signal(full);
empty = wait(empty);
x++;
printf("\nProducer produces the item %d", x);
mutex = signal(mutex);
}
void consumer(){
mutex = wait(mutex);
full = wait(full);
empty = signal(empty);
printf("\nConsumer \

item %d", x);

x--;
mutex = signal(mutex);
}
OUTPUT: -
 Practical – 12
OBJECTIVE: - Write a C program to Implement the solutions for Readers-Writers problem using
inter process communication technique –Semaphore

ALGORITHM: -
• The writer just waits on the w semaphore until it gets a chance to write to the resource.
• After performing the write operation, it increments w so that the next writer can access the
resource.
• On the other hand, in the code for the reader, the lock is acquired whenever the read_count
is updated by a process.
• When a reader wants to access the resource, first it increments the read_count value, then
accesses the resource and then decrements the read_count value.
• The semaphore w is used by the first reader which enters the critical section and the last
reader which exits the critical section.
• The reason for this is, when the first readers enters the critical section, the writer is blocked
from the resource. Only new readers can access the resource now.
• Similarly, when the last reader exits the critical section, it signals the writer using the w
semaphore because there are zero readers now and a writer can have the chance to access the
resource.

PROGRAM: -
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

sem_t mutex, writeblock;

int data = 0, rcount = 0;

void *reader(void *arg){

int f;
f = ((int)arg);
sem_wait(&mutex);
rcount = rcount + 1;
if (rcount == 1)
sem_wait(&writeblock);
sem_post(&mutex);
printf("Data read by the reader%d is %d\n", f, data);
sleep(1);
sem_wait(&mutex);
rcount = rcount - 1;
if (rcount == 0)
sem_post(&writeblock);
sem_post(&mutex);
}
void *writer(void *arg){
int f;
f = ((int)arg);
sem_wait(&writeblock);
data++;
printf("Data writen by the writer%d is %d\n", f, data);
sleep(1);
sem_post(&writeblock);
}

main(){
int i, b;
pthread_t rtid[5], wtid[5];
sem_init(&mutex, 0, 1);
sem_init(&writeblock, 0, 1);
for (i = 0; i <= 2; i++){
pthread_create(&wtid[i], NULL, writer, (void *)i);
pthread_create(&rtid[i], NULL, reader, (void *)i);
}
for (i = 0; i <= 2; i++){
pthread_join(wtid[i], NULL);
pthread_join(rtid[i], NULL);
}}

OUTPUT: -
 Practical – 13
OBJECTIVE: - Write a C program to implementation of Compaction for the continually changing
memory layout and calculate total movement of data.

PROBLEM STATEMENT: -
Compaction is a technique used to remove internal fragmentation. Assumption that has to be taken
into consideration is that the files must be inserted and deleted continuously. User must provide
memory image at different instances of time.

OBJECTIVE
Compaction is a process in which the free space is collected in a large memory chunk to make some
space available for processes.
In memory management, swapping creates multiple fragments in the memory because of the
processes moving in and out.
Compaction refers to combining all the empty spaces together and processes.
Compaction helps to solve the problem of fragmentation, but it requires too much of CPU time.
It moves all the occupied areas of store to one end and leaves one large free space for incoming
jobs, instead of numerous small ones.
In compaction, the system also maintains relocation information and it must be performed on each
new allocation of job to the memory or completion of job from memory.

ALGORITHM: -
Compaction is a method to overcome the external fragmentation problem.
All free blocks are brought together as one large block of free space.
Compaction requires dynamic relocation. Certainly, compaction has a cost and selection of an
optimal compaction strategy is difficult.
One method for compaction is swapping out those processes that are to be moved within the
memory, and swapping them into different memory locations.

PROGRAM: -
#include <stdio.h>
#include <conio.h>

void create(int, int);

void del(int);
void compaction();
void display();

int fname[10], fsize[10], fstart[10], freest[10], freesize[10], m = 0, n = 0, start;

int main(){
 int name, size, ch, i;
int *ptr;
// clrscr();
ptr = (int *)malloc(sizeof(int) * 100);
start = freest[0] = (int)ptr;
freesize[0] = 500;

printf("\n\n");
printf(" Free start address Free Size \n\n");

for (i = 0; i <= m; i++)

printf(" %d %d\n", freest[i], freesize[i]);
printf("\n\n");
while (1){

printf("1.Create.\n");
printf("2.Delete.\n");
printf("3.Compaction.\n");
printf("4.Exit.\n");
printf("Enter your choice: ");
scanf("%d", &ch);
switch (ch){
case 1:
printf("\nEnter the name of file: ");
scanf("%d", &name);
printf("\nEnter the size of the file: ");
scanf("%d", &size);
create(name, size);
break;
case 2:
printf("\nEnter the file name which u want to delete: ");
scanf("%d", &name);
del(name);
break;
case 3:
compaction();
printf("\nAfter compaction the tables will be:\n");
display();
break;
case 4:
exit(1);
default:
printf("\nYou have entered a wrong choice.\n");
}}}

void create(int name, int size){

int i, flag = 1, j, a;

for (i = 0; i <= m; i++)

if (freesize[i] >= size)
a = i, flag = 0;
if (!flag){
 for (j = 0; j < n; j++)
;
n++;
fname[j] = name;
fsize[j] = size;
fstart[j] = freest[a];
freest[a] = freest[a] + size;
freesize[a] = freesize[a] - size;

printf("\n The memory map will now be: \n\n");

display();
}
else{
printf("\nNo enough space is available.System compaction......");

flag = 1;

compaction();
display();

for (i = 0; i <= m; i++)

if (freesize[i] >= size)
a = i, flag = 0;
if (!flag){
for (j = 0; j < n; j++)
n++;
fname[j] = name;
fsize[j] = size;
fstart[j] = freest[a];
freest[a] += size;
freesize[a] -= size;
printf("\n The memory map will now be: \n\n");
display();
}
else
printf("\nNo enough space.\n");
}}

void del(int name){

int i, j, k, flag = 1;
for (i = 0; i < n; i++)
if (fname[i] == name)
break;
if (i == n){
flag = 0;
printf("\nNo such process exists......\n");
}
else{
m++;
freest[m] = fstart[i];
freesize[m] = fsize[i];
for (k = i; k < n; k++){
 fname[k] = fname[k + 1];
fsize[k] = fsize[k + 1];
fstart[k] = fstart[k + 1];
}
n--;
}
if (flag){
printf("\n\n After deletion of this process the memory map will be : \n\n");
display();
}}

void compaction(){
int i, j, size1 = 0, f_size = 0;
if (fstart[0] != start){
fstart[0] = start;
for (i = 1; i < n; i++)
fstart[i] = fstart[i - 1] + fsize[i - 1];
}
else{
for (i = 1; i < n; i++)
fstart[i] = fstart[i - 1] + fsize[i - 1];
}
f_size = freesize[0];

for (j = 0; j <= m; j++)

size1 += freesize[j];
freest[0] = freest[0] - (size1 - f_size);
freesize[0] = size1;
m = 0;
}

void display(){
int i;
printf("\n *** MEMORY MAP TABLE *** \n");
printf("\n\nNAME SIZE STARTING ADDRESS \n\n");
for (i = 0; i < n; i++)
printf(" %d%10d%10d\n", fname[i], fsize[i], fstart[i]);
printf("\n\n");
printf("\n\n*** FREE SPACE TABLE ***\n\n");
printf("FREE START ADDRESS FREE SIZE \n\n");
for (i = 0; i <= m; i++)
printf(" %d %d\n", freest[i], freesize[i]);
}
OUTPUT: -