[Approved by AICTE, Govt. of India & Affiliated to Dr.

APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

OPERATING SYSTEM

List of Experiments
Minimum Ten / Eight experiments to be performed (As per syllabus)

S. Experiments
No
1 Study of hardware and software requirements of different operating systems
(UNIX,LINUX,WINDOWS XP, WINDOWS7/8
Execute various UNIX system calls for
2 i.​ Process management
ii.​ File management
iii.​ Input/output Systems calls
Implement CPU Scheduling Policies:
i.​ SJF
3 ii.​ Priority
iii.​ FCFS
iv.​ Multi-level Queue
Implement file storage allocation technique:
4 i.​ Contiguous(using array)
ii.​ Linked –list(using linked-list)
iii.​ Indirect allocation (indexing)
Implementation of contiguous allocation techniques:
i.​ Worst-Fit
5
ii.​ Best- Fit
iii.​ First- Fit
Calculation of external and internal fragmentation​
6 i.​ Free space list of blocks from system
ii.​ List process file from the system

7 Implementation of compaction for the continually changing memory layout and

calculate total movement of data
8 Implementation of resource allocation graph RAG)

9 Implementation of Banker‟s algorithm

 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Conversion of resource allocation graph (RAG) to wait for graph (WFG) for each
10
type of method used for storing graph.

11 Implement the solution for Bounded Buffer (producer-consumer) problem using

inter process communication techniques-Semaphores.
12 Implement the solutions for Readers-Writers problem using inter process
communication technique –Semaphore.
Beyond Syllabus

Implement disk scheduling algorithms:

1 ​ ​ ​ (i) FCFS
​ ​ ​ (ii) SCAN
​ ​ ​ (iii) C-SCAN
Implement page replacement algorithm
2 ​ ​ ​ (i) FIFO
​ ​ ​ (ii) LRU
​ ​ ​ (iii) LFU
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Experiment 1

Study of Hardware and Software requirements of different Operating Systems

(UNIX, LINUX, WINDOWS XP and Windows 7/8)

1. UNIX Operating System:

Hardware Requirements:

UNIX-like operating systems have varying hardware requirements depending on the

distribution
Typically, UNIX systems can run on a wide range of hardware, from older systems to modern
servers and workstations.

Minimum requirements may include

1) 256 MB recommended
128 MB minimum
2) 250 MB available Hard drive space
3) CD-ROM drive
4) TCP/IP Network Interface

. Software:

UNIX systems often require specific system libraries and utilities. Depending on the distribution,
additional software packages may be needed for specific functionalities (e.g., development
tools, graphical environment).

1) Hewlett-Packard HP-UX
2) IBM AIX
3) Sun Solaris

Linux Operating System:

Hardware Requirements:
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Linux distributions have diverse hardware support, from embedded systems to high-end
servers.
Minimum hardware specifications generally include a compatible CPU (x86, ARM, etc.),
recommended RAM (varies by distribution), and disk space (typically a few gigabytes for
installation).

Software

1) Red Hat Enterprise Linux(RHEL)

2) SE Linux container installed as a Pocker dependency
3) Debian
4) Ubuntu

3. Windows XP:

Hardware Requirements:

Windows XP, although outdated, typically required a Pentium processor (233 MHz or higher), at
least 64 MB of RAM (128 MB recommended), and around 1.5 GB of available hard disk space.
Additional hardware for specific features (e.g., DirectX for gaming).

Software Requirements:

DirectX for multimedia and gaming support.

Various device drivers for hardware components.

4. Windows 7/8:

Hardware Requirements

Windows 7/8 requires more modern hardware compared to XP. Typically, a 1 GHz processor
(32-bit or 64-bit), 1 GB (32-bit) or 2 GB (64-bit) of RAM, and around 16-20 GB of hard disk space
are recommended.

Graphics card compatible with DirectX 9 with WDDM driver

Software Requirements:
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Compatibility with newer software applications and drivers compared to XP

Additional software like NET Framework for application support

 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Experiment 2 (i)
Objective: Execute various UNIX system calls for: Process Management
Solution:
Process management uses certain system calls. They are explained below.
1. To create a new process – fork () is used.
2. To run a new program = exec () is used.
3. To make the process to wait = wait () is used.
4. To terminate the process – exit () is used.
5. To find the unique process id – getpid () is used.
6. To find the parent process id – getppid () is used.
7. To bias the currently running process property – nice () is used.

2(i).a. Example program for example of fork()

Figure: Flow of fork () system call

#include<stdio.h>
#include<unistd.h>​ ​ ​
int main()
{
int i =10;
int pid;
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

pid=fork();
if(pid==0)
{
for(i=0; i < 999999; i++)
{
sleep(2);
printf(" from Child process %d\n", i);
}
}
else
{
for(i=0; i < 999999; i=i+2)
{
sleep(2);
printf(" from Parent process %d\n", i);
}
}

return 0;
}
Output 2.(i).a
user@node1:~/oslab$ ./chp
from Parent process 0
from Child process 0
from Parent process 2
from Child process 1
from Parent process 4
from Child process 2
…………………..
……………………

2(i).b. Example program for example of exec()

 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Figure: flow of exec () system call

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
int main()
{
int i =10;
char *p[]={"./hello", NULL};
int pid;

pid=fork();
if(pid==0)
{
for(i=0; i < 999999; i++)
{
sleep(2);
printf(" from Child process %d\n", i);
}
}
else
{
for(i=0; i < 999999; i=i+2)
{
sleep(2);
printf(" from parent process %d\n", i);
execv(p[0], p);
}
}
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

return 0;
}
Output 2.(i).b
user@node1:~/oslab$ ./chp2
from parent process 0
hello world
from Child process 0
from Child process 1
from Child process 2
from Child process 3
………
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Experiment 2 (ii)
Objective: Execute various UNIX system calls for:
File Management
Solution:
There are four system calls for file management,
1.​ open (): system call is used to know the file descriptor of user-created files. Since read and
write use file descriptor as their 1st parameter so to know the file descriptor open() system
call is used.
2.​ read ()system call is used to read the content from the file. It can also be used to read the
input from the keyboard by specifying the 0 as file descriptor.
3.​ write (): system call is used to write the content to the file.
4.​ close ():system call is used to close the opened file, it tells the operating system that you are
done with the file and close the file.

2(ii). Example program for file management

#include<unistd.h>​ // for read and write functions for input from keyboard
#include<fcntl.h>​ // for open function and O_CREAT and O_RDWR flags
#include<stdio.h>​

int main()
{
​ int n,fd;
​ char buff[50];​
​ printf("Enter text to write in the file:\n");
​ n= read(0, buff, 50);
​ fd=open("file",O_CREAT | O_RDWR, 0777);
​ write(fd, buff, n);
​ write(1, buff, n);
​ int close(int fd);
​ return 0;​
}
Output 2.(ii)
Enter text to write in the file:
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Hello world, welcome @ IncludeHelp

Hello world, welcome @ IncludeHelp

Experiment 2 (iii)
Objective: Execute various UNIX system calls for: Input / output system calls
Solution:
Standard File Descriptors: When any process starts, then that process file descriptors table’s
fd(file descriptor) 0, 1, 2 open automatically, (By default) each of these 3 fd references file table
entry for a file named /dev/tty
Read from stdin => read from fd 0: Whenever we write any character from keyboard, it read
from stdin through fd 0 and save to file named /dev/tty
Write to stdout => write to fd 1: Whenever we see any output to the video screen, it’s from the
file named /dev/tty and written to stdout in screen through fd 1

Figure: Input /output file descriptors

Basically, there are total 5 types of I/O system calls:

●​ Create: Used to Create a new empty file.
●​ open: Used to Open the file for reading, writing or both.
●​ close: Tells the operating system you are done with a file descriptor and Close the file which
pointed by fd.
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

●​ read: From the file indicated by the file descriptor fd, the read() function reads cnt bytes of
input into the memory area indicated by buf. A successful read() updates the access time
for the file.
●​ write: Writes cnt bytes from buf to the file or socket associated with fd. cnt should not be
greater than INT_MAX (defined in the limits.h header file). If cnt is zero, write() simply
returns 0 without attempting any other action.

2(iii). Example program for Input/output System Calls

main()
{
​ char c;
​ int a=1, i;
​ while (a != 0)
​ {​
​ ​ read(0, &a, 3);​
​ ​ i=a;
​ ​ write(1, &i, 3);
​ ​ write(1, "\n", 1);
​ }
}
Output 2.(iii)
tarun@node1:~/oslab$ ./io
2
2
33
33
44
44
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Experiment 3 (i)
Objective: Implement CPU Scheduling Policies:
SJF (Shortest Job First)
Solution:
Algorithm:
Step 1.​ Sort all the process according to the arrival time.
Step 2.​ Then select that process which has minimum arrival time and minimum Burst time.
Step 3.​ After completion of process make a pool of process which after till the completion of
previous process and select that process among the pool which is having minimum
Burst time.
Example: Sorting the process according to brust time. (Array sorting flowchart can be used for
logic understanding)

3(i). Example program for SJF scheduling implementation

#include<stdio.h>
struct process
{
int id;
int brust;
};
typedef struct process proc;
int main()
{
int n;
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

printf("enter the number of processs: ");

scanf("%d", &n);
proc p[n], temp;
int i,j;
for(i=0;i<n;i++)
{
p[i].id=i;
printf("enter the brust time of process P %d :", i);
scanf("%d", &p[i].brust);
}
for(i=0;i<n-1;i++)
{
​ ​ for(j=i+1;j<n;j++)
​ ​ {
​ ​ ​ if(p[j].brust < p[i].brust)
​ ​ ​ {
​ ​ ​ ​ temp.id = p[j].id;
​ ​ ​ ​ temp.brust = p[j].brust;
​ ​ ​ ​ p[j].id = p[i].id;
​ ​ ​ ​ p[j].brust = p[i].brust;
​ ​ ​ ​ p[i].id = temp.id;
​ ​ ​ ​ p[i].brust = temp.brust;
​ ​ ​ }
​ ​ }
​
}
int wt=0;
int twt=0;
printf("\n scheduling information \n");
for(i=0;i<n;i++)
{
​ ​ twt = twt+wt;
​ ​ printf("process id: %d \t wating time: %d \n",p[i].id, wt );
​ ​ wt=wt+p[i].brust;
}
printf("\n avg waiting time: %1.2f :", ((float)twt/n));
return 0;
}
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Input: Program 3(i):

Process Brust Time
P0 5
P1 3
P2 6
P3 4

Output:
scheduling information
process id: 1 ​ waiting time: 0
process id: 3 ​ waiting time: 3
process id: 0 ​ waiting time: 7
process id: 2 ​ waiting time: 12
avg waiting time: 5.50 :
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Experiment 3 (ii)
Objective: Implement CPU Scheduling Policies: Priority Scheduling
Solution:
Algorithm:
Step 1.​ First input the processes with their arrival time, burst time and priority.
Step 2.​ Sort the processes, according to arrival time if two process arrival times are the same
then sort according process priority if two process priority are same then sort
according to process number.
Step 3.​ Now simply apply the FCFS algorithm.

Example: Sorting the process according to priority. (Array sorting flowchart can be used for logic
understanding)

3(ii). Example program for Priority scheduling implementation

#include<stdio.h>
struct process
{
int id;
int brust;
int pr;
};
typedef struct process proc;
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

int main()
{
int n;
printf("enter the number of processs: ");
scanf("%d", &n);
proc p[n], temp;
int i,j;
for(i=0;i<n;i++)
{
p[i].id=i;
printf("enter the burst time of process P %d :", i);
scanf("%d", &p[i].brust);
printf("enter the priority of process P %d :", i);
scanf("%d", &p[i].pr);
}
for(i=0;i<n-1;i++)
{
​ ​ for(j=i+1;j<n;j++)
​ ​ {
​ ​ ​ if(p[j].pr < p[i].pr)
​ ​ ​ {
​ ​ ​ ​ temp.id = p[j].id;
​ ​ ​ ​ temp.brust = p[j].brust;
​ ​ ​ ​ temp.pr = p[j].pr;
​ ​ ​ ​ p[j].id = p[i].id;
​ ​ ​ ​ p[j].brust = p[i].brust;
​ ​ ​ ​ p[j].pr = p[i].pr;
​ ​ ​ ​ p[i].id = temp.id;
​ ​ ​ ​ p[i].brust = temp.brust;
​ ​ ​ ​ p[i].pr = temp.pr;
​ ​ ​ }
​ ​ }
​
}
int wt=0;
int twt=0;
printf("\n scheduling information \n");
for(i=0;i<n;i++)
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

{
​ ​ twt = twt+wt;
​ ​ printf("process id: %d priority %d \t waiting time: %d \n",p[i].id,p[i].pr, wt );
​ ​ wt=wt+p[i].brust;
​
​

}
printf("\n avg waiting time: %1.2f :", ((float)twt/n));
return 0;
}
Input: Program 3(ii):
Process Brust Time Priority
P0 5 3
P1 3 1
P2 6 2
P3 4 4
Output:
Scheduling information
process id: 1 priority 1 ​ waiting time: 0
process id: 2 priority 2 ​ waiting time: 3
process id: 0 priority 3 ​ waiting time: 9
process id: 3 priority 4 ​ waiting time: 14
avg waiting time: 6.50
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Experiment 3 (iii)
Objective: Implement CPU Scheduling Policies: FCFS (First come first serve) Scheduling
Solution:
Algorithm:
Step 1. First input the processes with their arrival time, burst time.
Step 2. Queue them in their arrival order i.e. the process that comes first then process it first.
Example:

3(iii). Example program for FCFS scheduling implementation

#include<stdio.h>
struct process
{
int id;
int brust;
int at;
};
typedef struct process proc;
int main()
{
int n;
printf("enter the number of processes: ");
scanf("%d", &n);
proc p[n], temp;
int i,j;
for(i=0;i<n;i++)
{
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

p[i].id=i;
printf("enter the burst time of process P %d :", i);
scanf("%d", &p[i].burst);
printf("enter the arrival time of process P %d :", i);
scanf("%d", &p[i].at);
}
for(i=0;i<n-1;i++)
{
​ ​ for(j=i+1;j<n;j++)
​ ​ {
​ ​ ​ if(p[j].at < p[i].at)
​ ​ ​ {
​ ​ ​ ​ temp.id = p[j].id;
​ ​ ​ ​ temp.brust = p[j].brust;
​ ​ ​ ​ temp.at = p[j].at;
​ ​ ​ ​ p[j].id = p[i].id;
​ ​ ​ ​ p[j].brust = p[i].brust;
​ ​ ​ ​ p[j].at = p[i].at;
​ ​ ​ ​ p[i].id = temp.id;
​ ​ ​ ​ p[i].brust = temp.brust;
​ ​ ​ ​ p[i].at = temp.at;
​ ​ ​ }​
​ ​ }
​
}
int wt=0;
int twt=0;
printf("\n scheduling information \n");
for(i=0;i<n;i++)
{
​ ​ twt = twt+wt;
​ ​ printf("process id: %d arrival-time %d \t waiting time: %d \n",p[i].id,p[i].at, wt );
​ ​ wt=wt+p[i].brust;
​ }
printf("\n avg waiting time: %1.2f :", ((float)twt/n));

return 0;
}
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Input: Program 3(iii):

Process Brust Time Arrival time
P0 5 3
P1 3 1
P2 6 2
P3 4 4
Output:
Scheduling information
process id: 1 arrival-time 1 ​ waiting time: 0
process id: 2 arrival-time 2 ​ waiting time: 3
process id: 0 arrival-time 3 ​ waiting time: 9
process id: 3 arrival-time 4 ​ waiting time: 14
avg waiting time: 6.50
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Experiment 3 (iv)
Objective: Implement CPU Scheduling Policies: Multilevel Queue Scheduling
Solution:
Algorithm:
Let, us suppose we have three level queue such that queue 1, 2 and 3. Queue 1 for system
process, queue 2 for interactive process and queue 3 for batch process. Input process
parameters from user
Step 1.​ If process is system process then insert this process in queue 1.
Step 2.​ If process is interactive process the insert this process in queue 2.
Step 3.​ If process is batch process then insert this process in queue 3.
Step 4.​ Sort all queues using FCFS.
Step 5.​ Process Queue 1
Step 6.​ Process Queue 2
Step 7.​ Process Queue 3
Step 8.​ Repeat from step 1 for further processing.

Example:

Figure: Multilevel Queue Scheduling of Process (3 queues example)

3(iv). Example program for multilevel queue scheduling implementation

#include<stdio.h>
#include<stdlib.h>
typedef struct process
{​
​ int num;
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

​ int arrive;
​ int brust;
​ int pt;
​ int f;
​ int cpu;
​ int wait;
} process;
typedef struct queue
{
​ process p[10];
​ int front;
​ int rear;
} queue;
void insert(queue *q,process t)
{
​ q->p[q->rear]=t;
​ q->rear++;
}
void pstack(queue *que)
{
​ int i,j;
​ for(i=0;i<3;i++)
​ {
​ ​ printf("\n queue %d is \n",i+1);
​ ​ printf("Process\tarrive\tbrust\t type\t I/O\t cpu \twait\n");​​
​ ​ for(j=0;j<que[i].rear;j++)
​ ​ {
​ ​printf(" %d \t %d \t %d \t %d \t %d \t %d \t
%d\n",que[i].p[j].num,que[i].p[j].arrive,que[i].p[j].brust,que[i].p[j].
pt,que[i].p[j].f,que[i].p[j].cpu,que[i].p[j].wait);
​ ​ }
​ }
}
void fcfs_sort(queue *que)
{
​ process *temp;
​ int i,j,k,n;
​ for(k=0;k<3;k++)
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

​ {
​ ​ n=que[k].rear;​​
​ ​ for(i=1;i<n;i++)
​ ​ {
​ ​ ​ for(j=0;j<n-i;j++)
​ ​ ​ {
​ ​ ​ ​ if(que[k].p[j].arrive > que[k].p[j+1].arrive)
​ ​ ​ ​ {
​ ​ ​ ​ ​ temp=&que[k].p[j];
​ ​ ​ ​ ​ que[k].p[j]=que[k].p[j+1];
​ ​ ​ ​ ​ que[k].p[j+1]=*temp;
​ ​ ​ ​
​ ​ ​ ​ }
​ ​ ​ }​
​ ​ }
​ }
}
void pque(queue *que)
{
​ int c=0,cp=0;
​ int w=0;
​ int j=0,k=0,l=0,t=0,i;
​ process *temp;
​ int max=0;
​ for(i=0;i<3;i++)
​ {
​ ​
​ ​ max=max+que[i].rear;
​ }​
​ for(i=0;i<max;i++)
​ {
​ ​ if(que[0].p[j].arrive <= cp && j< que[0].rear)
​ ​ {
​ ​ ​ que[0].p[j].cpu=c;​ ​ ​
​ ​ ​ que[0].p[j].wait=c-que[0].p[j].arrive;​
​ ​ ​ if(que[0].p[j].wait < 1)
​ ​ ​ que[0].p[j].wait=0;​ ​
​ ​ ​ c=c+que[0].p[j].brust;
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

​ ​ ​ j++;
​ ​ ​ cp=c;
​ ​ ​ continue;
​ ​ }
​ ​ else if(que[1].p[k].arrive < cp && k < que[1].rear )
​ ​ {
​ ​ ​ que[1].p[k].cpu=c;​ ​ ​
​ ​ ​ que[1].p[k].wait=c-que[1].p[k].arrive;​ ​ ​
​ ​ ​ if(que[1].p[k].wait < 1)
​ ​ ​ que[1].p[k].wait=0;​
​ ​ ​ c=c+que[1].p[k].brust;
​ ​ ​ k++;
​ ​ ​ cp=c;
​ ​ ​ continue;
​ ​ }
​ ​ else if(que[2].p[l].arrive < cp && l < que[2].rear)
​ ​ {
​ ​ ​ que[2].p[l].cpu=c;
​ ​ ​ que[2].p[l].wait=c-que[2].p[l].arrive;​​ ​
​ ​ ​ if(que[2].p[l].wait < 1)
​ ​ ​ que[2].p[l].wait=0;​ ​ ​
​ ​ ​ c=c+que[2].p[l].brust;
​ ​ ​ l++;​
​ ​ }
​ ​ else
​ ​ c=0;
​ }
}
int main()
{
​ queue que[3];
​ int j;
​ for(j=0;j<3;j++)
​ {
​ ​ que[j].front=-1;
​ ​ que[j].rear=0;
​ }​ ​
​ process temp;​
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

​ int n;
​ printf("enter the number of process");
​ scanf("%d",&n);
​ int i;
​ for(i=0;i<n;i++)
​ {
​ ​ temp.num=i+1;
​ ​ temp.cpu=0;
​ ​ temp.wait=0;​
​ ​ printf("\n enter the arrival time of process %d =",i+1);
​ ​ scanf("%d",&temp.arrive);
​ ​ printf("\n enter the brust time of process %d =",i+1);
​ ​ scanf("%d",&temp.brust);
​ ​ printf("\n enter the type of(1-back,2-forground,3-other) process %d =",i+1);
​ ​ scanf("%d",&temp.pt);
​ ​ printf("\n enter the feedback of process(0-for normal,1-I/O) %d =",i+1);
​ ​ scanf("%d",&temp.f);
​ ​ if(temp.pt>=2 && temp.f==1)
​ ​ insert(&que[temp.pt-2],temp);
​ ​ else if(temp.f==0)
​ ​ insert(&que[temp.pt-1],temp);
​ ​ else
​ ​ insert(&que[temp.pt-1],temp);
​ }
​ pstack(que);​ ​ ​
​ fcfs_sort(que);
​ printf("\n\nafter sorting of process list is \n\n");
​ pstack(que);
​ pque(que);
​ printf("\n\nafter processing cpu and wait is \n\n");
​ pstack(que);​
​ return 0;​ ​
}
Input: Program 3(iv):
Process Arival Time Brust Time Process_Type I/O
P1 0 2 1 0
P2 2 5 1 0
P3 1 3 1 0
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

P4 1 3 2 0
P5 0 4 2 0
P6 2 4 2 0
P7 1 3 3 0
P8 3 4 3 0
P9 2 6 3 0
Output:
queue 1 is
Process​ arive​ brust​ type​ I/O​ cpu ​ wait
1 ​ ​ 0 ​ 2 ​ 1​ 0​ 0​ 0
2 ​ ​ 2 ​ 5 ​ 1​ 0​ 0​ 0
3 ​ ​ 1 ​ 3 ​ 1​ 0​ 0​ 0

queue 2 is
Process​ arive​ brust​ type​ I/O​ cpu ​ wait
4 ​ ​ 1 ​ 3 ​ 2​ 0​ 0​ 0
5 ​ ​ 0 ​ 4 ​ 2​ 0​ 0​ 0
6 ​ ​ 2 ​ 4 ​ 2​ 0​ 0​ 0

queue 3 is
Process​ arive​ brust​ type​ I/O​ cpu ​ wait
7 ​ ​ 1 ​ 3 ​ 3​ 0​ 0​ 0
8 ​ ​ 3 ​ 4 ​ 3​ 0​ 0​ 0
9 ​ ​ 2 ​ 6 ​ 3​ 0​ 0​ 0

after sorting of process list is

queue 1 is
Process​ arive​ brust​ type​ I/O​ cpu ​ wait
1 ​ ​ 0 ​ 2 ​ 1​ 0​ 0​ 0
3 ​ ​ 1 ​ 3 ​ 1​ 0​ 0​ 0
3 ​ ​ 1 ​ 3 ​ 1​ 0​ 0​ 0

queue 2 is
Process​ arive​ brust​ type​ I/O​ cpu ​ wait
5 ​ ​ 0 ​ 4 ​ 2​ 0​ 0​ 0
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

5 ​ ​ 0 ​ 4 ​ 2​ 0​ 0​ 0
6 ​ ​ 2 ​ 4 ​ 2​ 0​ 0​ 0

queue 3 is
Process​ arive​ brust​ type​ I/O​ cpu ​ wait
7 ​ ​ 1 ​ 3 ​ 3​ 0​ 0​ 0
9 ​ ​ 2 ​ 6 ​ 3​ 0​ 0​ 0
9 ​ ​ 2 ​ 6 ​ 3​ 0​ 0​ 0

after processing cpu and wait is

queue 1 is
Process​ arive​ brust​ type​ I/O​ cpu ​ wait
1 ​ ​ 0 ​ 2 ​ 1​ 0​ 0​ 0
3 ​ ​ 1 ​ 3 ​ 1​ 0​ 2​ 1
3 ​ ​ 1 ​ 3 ​ 1​ 0​ 5​ 4

queue 2 is
Process​ arive​ brust​ type​ I/O​ cpu ​ wait
5 ​ ​ 0 ​ 4 ​ 2​ 0​ 8​ 8
5 ​ ​ 0 ​ 4 ​ 2​ 0​ 12 ​ 12
6 ​ ​ 2 ​ 4 ​ 2​ 0​ 16 ​ 14

queue 3 is
Process​ arive​ brust​ type​ I/O​ cpu ​ wait
7 ​ ​ 1 ​ 3 ​ 3​ 0​ 20 ​ 19
9 ​ ​ 2 ​ 6 ​ 3​ 0​ 23 ​ 21
9 ​ ​ 2 ​ 6 ​ 3​ 0​ 29 ​ 27
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Experiment 4 (i)
Objective: Implement file storage allocation technique: Contiguous (using array)
Theory –
1.Contiguous Allocation
About Contiguous allocation technique:
In this scheme, each file occupies a contiguous set of blocks on the disk. For example, if a file
requires n blocks and is given a block b as the starting location, then the blocks assigned to the
file will be: b, b+1, b+2,……b+n-1. This means that given the starting block address and the
length of the file (in terms of blocks required), we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains Address of starting block
Length of the allocated portion.

4(i). Example program for Contiguous(using array)file storage allocation technique

#include<stdio.h>
struct filep {
int id; int start;
int count;
};
typedef struct filep files;
int main() {
int disk[100];
int i,j,k;
for(i=0;i<100;i++)
disk[i]=-1;
files f[3];
for(i=0;i < 3;i++) {
f[i].id=i;
printf("enter the number of blocks for file : %d", i);
scanf("%d", &f[i].count);
}
int flag = 0;
for(i=0;i<3;i++) {
flag=0;
for(j=0;j<100;j++){
if(disk[j] == -1) {
for(k=j;k< j+f[i].count && disk[k] == -1;k++)
{
flag++;
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

printf("\n flag for file %d : %d\n", i, flag);

}
if(flag == f[i].count) {
for(k=j;k< j+f[i].count;k++) {
f[i].start = j; disk[k]=f[i].id;
}

}
else {

}}

j=j+f[i].count;
break;
j=j+flag;
flag=0;
if(j==99 && flag == 0)
printf("\n disk is full \n");
}}
printf("\n here is the disk allocation details \n");
for(i=0;i<100;i++)
printf("%d ", disk[i]);
return 0;
}
Input: Program 4(i):
Disk Size = 100 (Block (all of equal size))

File ID​ Block_Count

File 0​ 5
File 1​ 3
File 2​ 2

Output:
here is the disk allocation details
0 0 0 0 0 1 1 1 2 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

2.Linked List
Linked List Allocation technique:
In this scheme, each file is a linked list of disk blocks which need not be contiguous. The disk
blocks can be scattered anywhere on the disk.
The directory entry contains a pointer to the starting and the ending file block. Each block
contains a pointer to the next block occupied by the file.

Example program for file storage allocation technique (Linked List Allocation)
#include <stdio.h>
#include <stdlib.h>

struct file {
int id;
int block;
struct file *next_block;
};
typedef struct file f;

int main() {
f *file1 = NULL, *temp = NULL, *temp2 = NULL;
int i = 1, j, count;

printf("Enter the number of blocks for file %d: ", i);

scanf("%d", &count);

for (j = 0; j < count; j++) {

temp2 = (f*)malloc(sizeof(f));
if (temp2 == NULL) {
printf("Memory allocation failed\n");
return 1;
}
temp2->id = i;
temp2->block = j;
temp2->next_block = NULL;
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

if (j == 0) {

file1 = temp2;
} else {

temp = file1;
while (temp->next_block != NULL) {
temp = temp->next_block;
}
temp->next_block = temp2;
}

printf("%d\t", i);
}

printf("\nHere is the disk allocation for file:\n");

temp = file1;
while (temp != NULL) {
printf("file id: %d\t block number: %d\t block address %d\n", temp->id, temp-
>block,(int)temp); temp=temp->next_block;

temp = file1;
while (temp != NULL) {
temp2 = temp->next_block;
free(temp);
temp = temp2;
}

return 0;
}
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Input:

}
return 0;}

File ID​ Block_Count

File 1​ 5

Output:
Here is the disk allocation for file :
file id: 1​ block number: 0​ block address 38287408
file id: 1​ block number: 1​ block address 38287440
file id: 1​ block number: 2​ block address 38287472
file id: 1​ block number: 3​ block address 38287504
file id: 1​ block number: 4​ block address 38287536
file id: 1​ block number: 5​ block address 38287568

3.Indirect Allocation
About Indirect allocation (indexing) technique:
In this scheme, a special block known as the Index block contains the pointers to all the blocks
occupied by a file. Each file has its own index block. The ith entry in the index block contains the
disk address of the ith file block. The directory entry contains the address of the index block as
shown in the image:

Figure: Indirect (index) file allocation technique

Example program for file storage allocation technique (Indirect (index))
#include<stdio.h> #include<stdlib.h> struct file{
int id;
int block;
struct file *next_block;
};
typedef struct file f;
int main(){
f *files[3], *temp, *temp2; int count, i, j, id;
for(i=0;i<3;i++){
printf("enter the number of blocks for file : %d", i);
scanf("%d", &count);
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

for(j=0;j<count;j++)​ { if(j==0){
temp=(f*)malloc(sizeof(f));
temp->id=i;
temp->block=j;
temp->next_block=NULL;
files[i]=temp;
printf("%d\t", i);

}
else{
temp=files[i];
while ( temp->next_block != NULL)

}}}
temp=files[id];
while(temp!=NULL){
temp=temp->next_block;
temp2=(f*)malloc(sizeof(f));
temp2->id=i;
temp2->block=j;
temp2->next_block=NULL;
temp->next_block = temp2;
printf("%d\t", i);

printf("file id:​ %d\t​ block​ number: %d\t​ block​ address %d\n", temp->id, temp-
>block,(int)temp);
temp=temp->next_block;
}
return 0;
}
Input: Program 4(iii):

File ID​ Block_Count

File 0​ 5
File 1​ 4
File 2​ 6
Output:
disk allocation using index as file id
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

file id: 0​ block number: 0​ block address 35997744

file id: 0​ block number: 1​ block address 35997776
file id: 0​ block number: 2​ block address 3599780
file id: 0​ block number: 3​ block address 35997840
file id: 0​ block number: 4​ block address 35997872
file id: 1​ block number: 0​ block address 35997904
file id: 1​ block number: 1​ block address 35997936
file id: 1​ block number: 2​ block address 35997968
file id: 1​ block number: 3​ block address 35998000
file id: 2​ block number: 0​ block address 35998032
file id: 2​ block number: 1​ block address 35998064
file id: 2​ block number: 2​ block address 35998096
file id: 2​ block number: 3​ block address 35998128
file id: 2​ block number: 4​ block address 35998160
file id: 2​ block number: 5​ block address 35998192
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

EXPERIMENT – 5
Objective - Implementation of contiguous allocation techniques:
i.Worst-Fit
ii.Best-Fit
iii.First-Fit

Theory –
1.Worst Fit
Worst Fit Allocate the process to the partition which is the largest sufficient among the freely
available partitions available in the main memory.
Algorithm
Step 1. Input the total number of blocks and their size. Step 2. Input the total number of
processes and their size. Step 3. For each process in list
Find free block having max size and greater than process size Allocate block to process

Example program for implementation of contiguous allocation techniques: Worst-Fit

#include<stdio.h>
#include<stdlib.h>
int disk[20];
struct blocks{
int bid;
int size;
int index;
}block;
struct processs{
int pid;
int size;
int flag;
struct blocks b;
int fragment;
}process;
int main(){
int nb, np, i , j; int disk_index=0;
printf(" Total disk size is 50 \n");
printf(" enter number of blocks: ");
scanf("%d", &nb);
struct blocks bls[nb], temp;
for(i=0;i<nb;i++)​ {
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

bls[i].bid=i;
printf("enter the size of block %d ", i);
scanf("%d", &bls[i].size);
bls[i].index=disk_index; disk_index=disk_index+bls[i].size;

}
printf(" enter number of process: ");
scanf("%d",&np);

struct process ps[np];

for(i=0;i<np;i++){
ps[i].pid=i;
printf("enter the size of process %d ", i);
scanf("%d", &ps[i].size);
ps[i].flag=-1;

}
for(i=0;i<nb-1;i++){
for(j=i+1;j<nb;j++){
if(bls[j].size > bls[i].size){
temp.bid = bls[j].bid;
temp.size = bls[j].size;
temp.index = bls[j].index;
bls[j].bid = bls[i].bid;
bls[j].size = bls[i].size;
bls[j].index = bls[i].index;
bls[i].bid = temp.bid;
bls[i].size = temp.size;
bls[i].index = temp.index;
}}}
for(i=0;i<np;i++){
if(i >= nb || bls[i].size < ps[i].size)
printf("\n no block is available for the process \n");

else

}
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

ps[i].b=bls[i];

printf(" \n now process block allocation list is \n");

for(i=0;i<np;i++){
printf(" process id: %d process size %d block id %d free space %d\n", ps[i].pid, ps[i].size,
ps[i].b.bid, ps[i].b.size-ps[i].size);
}
return 0;
}

Input: Program 5(i):

Block ID​ Block_size
Block 0​ 5
Block 1​ 4
Block 2​ 8
Block 3​ 3

Process ID​ Process_size

Process 0​ 3
Process 1​ 2
Process 2​ 4

Output:
now process block allocation list is
process id: 0 process size 3 block id 2 free space 5
process id: 1 process size 2 block id 0 free space 3
process id: 2 process size 4 block id 1 free space 0

2.Best-Fit
Best Fit Allocate the process to the partition which is the first smallest sufficient partition among
the free available partition.
Algorithm
Step 1. Input the total number of blocks and their size.
Step 2. Input the total number of processes and their size.
Step 3. For each process in list
Find free block where, block_size - process _size = minimum Allocate block to process

Example program for implementation of contiguous allocation techniques: Best-Fit

#include<stdio.h>
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

#include<stdlib.h>
int disk[20];
struct blocks{
int bid; int size; int index;
}block;
struct process{
int pid; int size;
int flag;
struct blocks b;
int fragment;
}process; int main(){
int nb, np, i , j;
int disk_index=0;
printf(" Total disk size is 20 \n");
printf(" enter number of blocks: ");
scanf("%d", &nb);
struct blocks bls[nb];
for(i=0;i<nb;i++){
bls[i].bid=i;
printf("enter the size of block %d ", i);
scanf("%d", &bls[i].size);
bls[i].index=disk_index; disk_index=disk_index+bls[i].size;
}
printf(" enter number of process: ");
scanf("%d",&np);
struct process ps[np]; for(i=0;i<np;i++){
ps[i].pid=i;
printf("enter the size of process %d ", i);
scanf("%d", &ps[i].size);
ps[i].flag=-1;
}
int temp,temp2=20, bindex, pindex;
for(i=0; i<nb;i++){
for(j=0;j<np;j++){
temp = bls[i].size - ps[j].size; if(temp < 0){
continue;
}
else if(temp < temp2) {
if(ps[j].flag == -1){
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

pindex=j; temp2=temp;
}}}
ps[pindex].b = bls[i]; ps[pindex].flag = 1; temp2=20;
}
printf(" \n now process block allocation list is \n");
for(i=0;i<np;i++){
printf(" process id: %d process size %d block id %d free space %d\n", ps[i].pid, ps[i].size,
ps[i].b.bid, ps[i].b.size-ps[i].size);
}
return 0;
}

Input: Program 5(ii):

Block ID​ Blocksize

Block 0​ 5
Block 1​ 4
Block 2​ 8
Block 3​ 3

Process ID​ Process size

Process 0​ 3
Process 1​ 2
Process 2​ 4

Output:
now process block allocation list is
process id: 0 process size 3 block id 1 free space 1
process id: 1 process size 2 block id 3 free space 1
process id: 2 process size 4 block id 0 free space 1

3.First Fit
First Fit: In the first fit, the partition is allocated which is first sufficient block from the top of Main
Memory.
Algorithm
Step 1. Input the total number of blocks and their size. Step 2. Input the total number of
processes and their size. Step 3. For each process in list
Find free block where, block size > process _size
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Allocate block to process

Example program for implementation of contiguous allocation techniques: First-Fit

#include<stdio.h>
#include<stdlib.h>
int disk[20];
struct blocks{
int bid;
int size;
int index;
int status;
}block;
struct process{
int pid; int size; int flag;
struct blocks b; int fragment;
}process; int main(){
int nb, np, i , j;
int disk_index=0;
printf(" Total disk size is 50 \n");
printf(" enter number of blocks: ");
scanf("%d", &nb);
struct blocks bls[nb], temp; f
or(i=0;i<nb;i++){
bls[i].bid=i;
printf("enter the size of block %d ", i);
scanf("%d", &bls[i].size); b
ls[i].index=disk_index; disk_index=disk_index+bls[i].size; bls[i].status = -1;
}
printf(" enter number of process: ");
scanf("%d",&np);
struct process ps[np];
for(i=0;i<np;i++)​ {
ps[i].pid=i;
printf("enter the size of process %d ", i);
scanf("%d", &ps[i].size);
ps[i].flag=-1;
}
for(i=0;i<np;i++){
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

for(j=0;j<nb;j++)​ {
if(bls[j].size > ps[i].size && bls[j].status ==-1)​{ ps[i].b=bls[j];
bls[j].status = 1; break;
}}}
printf(" \n now process block allocation list is \n");
for(i=0;i<np;i++){

printf(" process id: %d process size %d block id %d free space %d\n", ps[i].pid, ps[i].size,
ps[i].b.bid, ps[i].b.size-ps[i].size);
}
return 0;
}

Input: Program 5(iii):

Block ID​ Block_size

Block 0​ 5
Block 1​ 4
Block 2​ 8
Block 3​ 3

Process ID​ Process_size

Process 0​ 3
Process 1​ 2
Process 2​ 4

Output:
now process block allocation list is
process id: 0 process size 4 block id 0 free space 1
process id: 1 process size 2 block id 1 free space 2
process id: 2 process size 3 block id 2 free space 5
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

EXPERIMENT – 6
Objective – Calculation of Internal and External fragmentation
i.Free space list of blocks from system
ii.List process file from the system
Theory –
1.Fres space list of blocks from system
External Fragmentation:
External fragmentation happens when there’s a sufficient quantity of area within the memory to
satisfy the memory request of a method. However, the process’s memory request cannot be
fulfilled because the memory offered is during a non-contiguous manner. Either you apply first-fit
or best-fit memory allocation strategy and it'll cause external fragmentation.

Figure. External Fragmentation in System Example program for Free space list of blocks from
system
#include<stdio.h>
#include<stdlib.h>
int disk[20];
struct blocks{
int bid; int size; int index; int status;
}block;
struct process{
int pid; int size;
int flag;
struct blocks b;
int fragment;
}process;
int main(){
int nb, np, i , j; int disk_index=0;
printf(" Total disk size is 50 \n");
printf(" enter number of blocks: ");
scanf("%d", &nb);
struct blocks bls[nb], temp;
for(i=0;i<nb;i++){

bls[i].bid=i;
printf("enter the size of block %d ", i);
scanf("%d", &bls[i].size);
bls[i].index=disk_index; disk_index=disk_index+bls[i].size; bls[i].status = -1;
}
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

printf(" enter number of process: ");

scanf("%d",&np);
struct process ps[np];
for(i=0;i<np;i++){
ps[i].pid=i;
printf("enter the size of process %d ", i);
scanf("%d", &ps[i].size);
ps[i].flag=-1;
}
for(i=0;i<np;i++){
for(j=0;j<nb;j++){
if(bls[j].size > ps[i].size && bls[j].status ==-1){
ps[i].b=bls[j];
bls[j].status = 1;
break;
}}}
printf(" \n now Free space list of blocks is \n");
int free=0;
for(i=0;i<nb;i++)
if(bls[i].status == -1){
printf(" Block id: %d Block size %d block index %d \n", bls[i].bid, bls[i].size, bls[i].index);
free= free + bls[i].size;
}}
printf(" \n Total external free space is: %d \n", free);
return 0;
}
Input: Program 6:
Disk size = 20

Block ID​ Blocksize

Block 0​ 5
Block 1​ 4
Block 2​ 8
Block 3​ 3

Process ID​ Process size

Process 0​ 4
Process 1​ 6
Process 2​ 2
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Output:
now Free space list of blocks is
Block id: 2 Block size 3 block index 9 Total external free space is: 3

2.List process file from the system

Internal Fragmentation:
Internal fragmentation happens when the memory is split into mounted sized blocks. Whenever
a- method request for the memory, the mounted sized block is allotted to the method. Just in
case, the memory allotted to the method is somewhat larger than the memory requested, then
the distinction between allotted and requested memory is that the internal fragmentation.
Figure. Internal Fragmentation Example program for List process file from the system
#include<stdio.h>
#include<stdlib.h>
int disk[20];
struct blocks{
int bid; int size; int index; int status;
}block;
struct process{
int pid; int size; int flag;
struct blocks b; int fragment;
}process; int main(){
int nb, np, i , j;
int disk_index=0;
printf(" Total disk size is 50 \n");
printf(" enter number of blocks: ");
scanf("%d", &nb);
struct blocks bls[nb], temp;
for(i=0;i<nb;i++){
bls[i].bid=i;
printf("enter the size of block %d ", i);
scanf("%d", &bls[i].size); bls[i].index=disk_index; disk_index=disk_index+bls[i].size; bls[i].status
= -1;

}
printf(" enter number of process: ");
scanf("%d",&np);
struct processs ps[np];
for(i=0;i<np;i++){
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

ps[i].pid=i;
printf("enter the size of process %d ", i);
scanf("%d", &ps[i].size);
ps[i].flag=-1;
}
for(i=0;i<np;i++){
for(j=0;j<nb;j++){
if(bls[j].size > ps[i].size && bls[j].status ==-1){
ps[i].b=bls[j];
bls[j].status = 1; break;
}}}
printf(" \n now process block allocation list is \n");
int t_free=0;
for(i=0;i<np;i++){
printf(" process id: %d process size %d block id %d free space %d\n", ps[i].pid, ps[i].size,
ps[i].b.bid, ps[i].b.size-ps[i].size);
t_free = t_free + (ps[i].b.size-ps[i].size);
}
printf(" \n Total internal fragmentation space is: %d \n", t_free); return 0;
}

Input: Program 6(ii):

Block ID​ Block_size

Block 0​ 5
Block 1​ 4
Block 2​ 8
Block 3​ 3

Process ID​ Process_size

Process 0​ 3
Process 1​ 2
Process 2​ 4

Output:
now process block allocation list is
process id: 0 process size 4 block id 0 free space 1
process id: 1 process size 2 block id 1 free space 2
process id: 2 process size 3 block id 2 free space 5 Total internal fragmentation space is: 8
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

EXPERIMENT – 7
Objective – Implementation of compaction for the continually changing memory layout and
calculate total movement of data

Theory –
Memory compaction
The longstanding memory fragmentation problem has been covered many times in these pages.
In short: as the system runs, pages tend to be scattered between users, making it hard to find
groups of physically-contiguous pages when they are needed. Much work has gone into
avoiding the need for higher-order (multi-page) memory allocations whenever possible, with the
result that most kernel functionality is not hurt by page fragmentation. But there are still
situations where higher-order allocations are needed; code which needs such allocations can
fail on a fragmented system.

Example:

Program for Implementation of compaction for the continually changing memory layout and
calculate total movement of data
#include<stdio.h>
#include<stdlib.h>
int disk[20];
struct blocks{
int bid; int size; int index;
int status;
}block;
struct process{
int pid; int size; int flag;
struct blocks b;
int fragment;
}process;
int main(){
int nb, np, i , j;
int disk_index=0;
printf(" Total disk size is 50 \n");
printf(" enter number of blocks: ");
scanf("%d", &nb);
struct blocks bls[nb], temp;
for(i=0;i<nb;i++)​ {
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

bls[i].bid=i;
printf("enter the size of block %d ", i);
scanf("%d", &bls[i].size);
bls[i].index=disk_index; disk_index=disk_index+bls[i].size; bls[i].status = -1;
}
printf(" enter number of process: ");
scanf("%d",&np);
struct process ps[np];
for(i=0;i<np;i++){
ps[i].pid=i;
printf("enter the size of process %d ", i);
scanf("%d", &ps[i].size);
ps[i].flag=-1;
}
for(i=0;i<np;i++){
for(j=0;j<nb;j++)​ {
if(bls[j].size > ps[i].size && bls[j].status ==-1){
ps[i].b=bls[j];
}}}
bls[j].status = 1; break;
printf(" \n now process block allocation list is \n"); for(i=0;i<np;i++){
printf(" process id: %d process size %d block id %d free space %d\n", ps[i].pid, ps[i].size,
ps[i].b.bid, ps[i].b.size-ps[i].size);
}
printf(" \n now Free space list of blocks is \n"); int free=0;
for(i=0;i<nb;i++){
printf(" Block id: %d Block size %d block index %d \n", bls[i].bid, bls[i].size,
bls[i].index);
}
int sid, count=0; for(i=0;i<nb-1;i++){
count = 0;
for(j=1; j<nb;j++){
if(bls[i].status == -1 && bls[j].status !=-1){ sid = bls[j].index;
bls[j].index= bls[i].index; bls[i].index = sid;
}
else{
count = count +1; i=i+count;

}
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

}
i=i-count;
}
printf(" \n now After compaction list of blocks is \n"); free=0;
for(i=0;i<nb;i++){
if(bls[i].status == -1){
printf(" Block id: %d Block size %d New block index %d \n", bls[i].bid, bls[i].size, bls[i].index);
free= free + bls[i].size;
}
}
printf(" \n Total external free space is: %d \n", free); return 0;
}

Input: Program 7:

Block ID​ Block_size

Block 0​ 3
Block 1​ 8
Block 2​ 5
Block 3​ 4

Process ID​ Process_size

Process 0​ 4
Process 1​ 2

Output:
now process block allocation list is

process id: 0 process size 4 block id 1 free space 4

process id: 1 process size 4 block id 2 free space 1

now Free space list of blocks is

Block id: 0 Block size 3 block index 0
Block id: 1 Block size 8 block index 3
Block id: 2 Block size 5 block index 11
Block id: 3 Block size 4 block index 16 now After compaction list of blocks is
Block id: 0 Block size 3 New block index 11 Block id: 3 Block size 4 New block index 16 Total
external free space is: 7
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

EXPERIMENT – 8
Objective – Implementation of Resource Allocating Graph (RAG).

Theory –
Resource Allocation Graph (RAG)
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).
So, resource allocation graph is explained to us what is the state of the system in terms of
processes and resources. Like how many resources are available, how many are allocated and
what is the request of each process. Everything can be represented in terms of the diagram.
One of the advantages of having a diagram is, sometimes it is possible to see a deadlock
directly by using RAG, but then you might not be able to know that by looking at the table. But
the tables are better if the system contains lots of process and resource and Graph is better if
the system contains less number of process and resource.
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.

Figure: Resource Allocation Graph

8. Example program for Implementation of resource allocation graph RAG)
#include<stdio.h>
int main(){
int np, nr, temp, temp1;
printf("enter number of resources: ");
scanf("%d", &nr);
printf("enter number of processs: ");
scanf("%d", &np);
int rag[nr+np][nr+np]; int i, j; for(i=0;i<np+nr;i++) {
for(j=0; j<np+nr;j++)​ {
rag[i][j]=0;
}
}
for(i=0;i<np;i++){
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

printf("enter the number of resources process %d, holding", i);

scanf("%d", &temp);
for(j=0; j<temp;j++){
printf("enter the ressorce number process %d holding: ", j);
scanf("%d", &temp1);
rag[np+temp1][i]=1;
}
printf("enter the number of resources process %d, requesting", i);
scanf("%d", &temp);
for(j=0; j<temp;j++){
printf("enter the ressorce number process %d requesting: ", i);
scanf("%d", &temp1);
rag[i][np+temp1]=1;
}
}
for(i=0;i<np+nr;i++){
for(j=0; j<np+nr;j++){
printf("%d ", rag[i][j]);

}
return 0;
}

}
printf("\n ");

Input: Program 8:

Process ID​ Resource Handling​ Resource Requesting

Process 0​ R0​ R2
Process 1​ R1​ R0
Process 2​ R2​ R1

Output:
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

P0 P1 P2 R0 R1 R2 P0 0 0 0 0 0 1
P1 0 0 0 1 0 0
P2 0 0 0 0 1 0
R0 1 00 0 0 0
R1 0 1 0 0 0 0
R2 0 0 1 0 0 0
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

EXPERIMENT – 9
Objective – Implementation of Banker’s Algorithm
Theory –
Banker’s Algorithm
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. Following Data structures are used to implement the
Banker’s Algorithm:
Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.
Available:
It is a 1-d array of size ‘m’ indicating the number of available resources of each type.
Available[ j ] = k means there are ‘k’ instances of resource type Rj Max:
It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system.
Max[ i, j ] = k means process Pi may request at most ‘k’ instances of resource type Rj.
Allocation:
It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently
allocated to each process.
Allocation[ i, j ] = k means process Pi is currently allocated ‘k’ instances of resource type Rj
Need :
It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process.
Need [ i, j ] = k means process Pi currently need ‘k’ instances of resource type Rj
for its execution.
Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ]

Allocationi specifies the resources currently allocated to process Pi and Needi specifies the
additional resources that process Pi may still request to complete its task.
Banker’s algorithm consists of Safety algorithm and Resource request algorithm.
Safety Algorithm
1)Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n
2)Find an i such that both
a)Finish[i] = false
b)Needi<= Work
if no such i exists goto step (4)
3)Work = Work + Allocation[i]
Finish[i] = true goto step (2)
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

4)if Finish [i] = true for all i then the system is in a safe state Resource-Request Algorithm
Let Requesti be the request array for process Pi. Requesti [j] = k means process Pi wants k
instances of resource type Rj. When a request for resources is made by process Pi, the
following actions are taken:
1)If Requesti<= Needi
Goto step (2) ; otherwise, raise an error condition, since the process has exceeded its maximum
claim.
2)If Requesti<= Available
Goto step (3); otherwise, Pi must wait, since the resources are not available.
3)Have the system pretend to have allocated the requested resources to process Pi by
modifying the state as follows:
Available = Available – Requesti Allocationi = Allocationi + Requesti Needi = Needi– Requesti

Example program for Implementation of Banker‟s algorithm

#include <stdio.h>
int main() {
int n, m, i, j, k; n = 5;
m = 3;
int alloc[5][3] = { { 0, 1, 0 }, { 2, 0, 0 }, { 3, 0, 2 }, { 2, 1, 1 }, { 0, 0, 2 } };
int max[5][3] = { { 7, 5, 3 }, { 3, 2, 2 }, { 9, 0, 2 }, { 2, 2, 2 }, { 4, 3, 3 } };
intavail[3] = { 3, 3, 2 };
intf[n], ans[n], ind = 0;
for(k = 0; k < n; k++) f[k] = 0;
int need[n][m];
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++)
need[i][j] = max[i][j] - alloc[i][j];
}
inty = 0;
for(k = 0; k < 5; k++) {
for(i = 0; i < n; i++) {
if(f[i] == 0) {
int flag = 0;
for(j = 0; j < m; j++) {
if(need[i][j] > avail[j]){
flag = 1; break;
}}
if(flag == 0) {
ans[ind++] = i;
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

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

avail[y] += alloc[i][y];
f[i] = 1;
}}}}
printf("Following is the SAFE Sequence\n");
for(i = 0; i < n - 1; i++)
printf(" P%d ->", ans[i]);
printf(" P%d", ans[n - 1]);
return0;
}
Input: Program 9:

Output:
Following is the SAFE Sequence P1 -> P3 -> P4 -> P0 -> P2
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

EXPERIMENT – 10
Objective - Conversion of resource allocation graph (RAG) to wait for graph (WFG) for each
type of method used for storing graph.
Theory –
Wait-for-Graph (WFG)
A Wait-For Graph (WFG) is the same as the SRAG with the resource elements stripped out.
Example:

Figure: Resource Allocation Graph

Figure: Equivalent Wait for graph of above resource allocation graph

10. Example program for Implementation of conversion of resource allocation graph (RAG) to
wait for graph (WFG)
#include<stdio.h> int main(){
int np, nr, temp, temp1;
printf("enter number of resources: ");
scanf("%d", &nr);
printf("enter number of processs: ");
scanf("%d", &np);
int rag[nr+np][nr+np]; int i, j;
for(i=0;i<np+nr;i++){
for(j=0; j<np+nr;j++){
rag[i][j]=0;
}
}
for(i=0;i<np;i++){
printf("enter the number of resources process %d, holding", i);
scanf("%d", &temp);
for(j=0; j<temp;j++){
printf("enter the ressorce number process %d holding: ", j);
scanf("%d", &temp1);
rag[np+temp1][i]=1;
}
printf("enter the number of resources process %d, requesting", i);
scanf("%d", &temp);
for(j=0; j<temp;j++){
printf("enter the ressorce number process %d requesting: ", i);
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

scanf("%d", &temp1);
rag[i][np+temp1]=1;
}}

for(i=0;i<np+nr;i++) {
for(j=0; j<np+nr;j++) {
printf("%d ", rag[i][j]);
}
printf("\n ");
}
int wfg[np][np];
for(i=0;i<np;i++){
for(j=0; j<np;j++){
wfg[i][j]=0;
}
}
int k;
for(i=0;i<np;i++){
for(j=np;j<np + nr; j++){
if(rag[i][j] == 1){
for(k=0;k<np;k++){
if(rag[j][k] == 1)
wfg[i][k] = 1;
}
}
}
}
for(i=0;i<np;i++){
for(j=0; j<np;j++){
printf("%d ", wfg[i][j]);
}
printf("\n ");
}
return 0;
}

Input: Program 10:

Process ID​ Resource Holding​ Resource Requesting
Process 0​ R0​ R2
 [Approved by AICTE, Govt. of India & Affiliated to Dr. APJ
KCC Abdul Kalam Technical University, Lucknow, U.P., India]
Institute of Technology & Department of Computer Science & Engineering
Management

Process 1​ R1​ R0
Process 2​ R2​ R1
Output:
​ P0​ P1 P2 R0 R1 R2
​ P0​ 000001
​ P1​ 000100
​ P2​ 000010
​ R0​ 1 00 0 0 0
​ R1​ 010000
​ R2​ 001000