lab_programs_OS

Code and Output

// Experiment 3: Process Scheduling
// 3.1: SJF
#include <stdio>
#include <stdlib.h>

typedef struct {
	int id;
	int at;  // Arrival time
	int bt;  // Burst time
	int st;  // Start time
	int ct;  // Completion time
	int idt; // Idle time
} Process;

// Comparison function for qsort to sort processes by arrival time and burst time
int compareProcesses(const void *a, const void *b) {
	const Process *p1 = (const Process *)a;
	const Process *p2 = (const Process *)b;

	// Compare by arrival time first
	if (p1->at < p2->at) {
		return -1;
	} else if (p1->at > p2->at) {
		return 1;
	} else {
		// If arrival times are equal, compare by burst time
		if (p1->bt < p2->bt) {
			return -1;
		} else if (p1->bt > p2->bt) {
			return 1;
		} else {
			return 0;
		}
	}
}

int main() {
	int n;
	printf("Enter the number of processes: ");
	scanf("%d", &n);

	Process processes[n];

	printf("Enter arrival times and burst times of the processes:\n");
	for (int i = 0; i < n; i++) {
		processes[i].id = i + 1;
		printf("P%d: ", processes[i].id);
		scanf("%d %d", &processes[i].at, &processes[i].bt);
	}

	// Sort processes using qsort based on arrival time and burst time
	qsort(processes, n, sizeof(Process), compareProcesses);

	// Perform SJF scheduling
	int idt = 0;
	for (int i = 0; i < n; i++) {
		if (i != 0) {
			if (processes[i].at > processes[i - 1].ct) {
				processes[i].st = processes[i].at;
				idt += processes[i].st - processes[i - 1].ct;
			}
			else
				processes[i].st = processes[i - 1].ct;
		}
		processes[i].st = processes[i].at;
		idt += processes[i].st - processes[i].at;
		processes[i].ct = processes[i].st + processes[i].bt;
	}

	// Print results
	printf("\nProcess\tAT\tBT\tST\tCT\n");
	for (int i = 0; i < n; i++) {
		printf("P%d\t%d\t%d\t%d\t%d\n", processes[i].id, processes[i].at, processes[i].bt, processes[i].st, processes[i].ct);
	}

	printf("\nTotal Idle Time: %d\n", idt);
	printf("Total Time: %d\n", processes[n - 1].ct);

	return 0;
}

// Experiment 5: Solving The Dining Philosopher Problem Using Semaphores
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <stdio.h>

#define N 5
#define THINKING 2
#define HUNGRY 1
#define EATING 0
#define LEFT (phnum + 4) % N
#define RIGHT (phnum + 1) % N

int state[N];
int phil[N] = { 0, 1, 2, 3, 4 };

sem_t mutex;
sem_t S[N];

void test(int phnum)
{
	if (state[phnum] == HUNGRY
			&& state[LEFT] != EATING
			&& state[RIGHT] != EATING) {
		// state that eating
		state[phnum] = EATING;

		sleep(2);

		printf("Philosopher %d takes chopstick %d and %d\n",
				phnum + 1, LEFT + 1, phnum + 1);

		printf("Philosopher %d is eating\n", phnum + 1);

		// sem_post(&S[phnum]) has no effect
		// during takechopstick
		// used to wake up hungry philosophers
		// during putchopstick
		sem_post(&S[phnum]);
	}
}

// take up chopsticks
void take_chopstick(int phnum)
{

	sem_wait(&mutex);

	// state that hungry
	state[phnum] = HUNGRY;

	printf("Philosopher %d is Hungry\n", phnum + 1);

	// eat if neighbours are not eating
	test(phnum);

	sem_post(&mutex);

	// if unable to eat wait to be signalled
	sem_wait(&S[phnum]);

	sleep(1);
}

// drop chopsticks
void drop_chopstick(int phnum)
{

	sem_wait(&mutex);

	// state that thinking
	state[phnum] = THINKING;

	printf("Philosopher %d drops chopstick %d and %d \n",
			phnum + 1, LEFT + 1, phnum + 1);
	printf("Philosopher %d is thinking\n", phnum + 1);

	test(LEFT);
	test(RIGHT);

	sem_post(&mutex);
}

void* philosopher(void* num)
{

	while (1) {

		int* i = num;

		sleep(1);

		take_chopstick(*i);

		sleep(1);

		drop_chopstick(*i);
	}
}

int main()
{

	int i;
	pthread_t thread_id[N];

	// initialize the semaphores
	sem_init(&mutex, 0, 1);

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

		sem_init(&S[i], 0, 0);

	for (i = 0; i < N; i++) {

		// create philosopher processes
		pthread_create(&thread_id[i], NULL,
				philosopher, &phil[i]);

		printf("Philosopher %d is thinking\n", i + 1);
	}

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

		pthread_join(thread_id[i], NULL);
}

// Output:
/*
 * Philosopher 1 is thinking
 * Philosopher 2 is thinking
 * Philosopher 3 is thinking
 * Philosopher 4 is thinking
 * Philosopher 5 is thinking
 * Philosopher 1 is Hungry
 * Philosopher 2 is Hungry
 * Philosopher 3 is Hungry
 * Philosopher 5 is Hungry
 * Philosopher 4 is Hungry
 * Philosopher 4 takes chopstick 3 and 4
 * Philosopher 4 is eating
 * Philosopher 4 drops chopstick 3 and 4
 * Philosopher 4 is thinking
 * Philosopher 3 takes chopstick 2 and 3
 * Philosopher 3 is eating
 * Philosopher 5 takes chopstick 4 and 5
 * Philosopher 5 is eating
 * Philosopher 3 drops chopstick 2 and 3
 * Philosopher 3 is thinking
 * Philosopher 2 takes chopstick 1 and 2
 * Philosopher 2 is eating
 * Philosopher 5 drops chopstick 4 and 5
 * Philosopher 5 is thinking
 * Philosopher 4 is Hungry
 * Philosopher 4 takes chopstick 3 and 4
 * Philosopher 4 is eating
 * Philosopher 5 is Hungry
 * Philosopher 3 is Hungry
 * Philosopher 2 drops chopstick 1 and 2
 * Philosopher 2 is thinking
 * Philosopher 1 takes chopstick 5 and 1
 * Philosopher 1 is eating
 * Philosopher 4 drops chopstick 3 and 4
 * Philosopher 4 is thinking
 * Philosopher 3 takes chopstick 2 and 3
 * Philosopher 3 is eating
 * Philosopher 1 drops chopstick 5 and 1
 * Philosopher 1 is thinking
 */





// Experiment 6: Solving Producer-Consumer Problem using a Monitor
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define BUFFER_SIZE 3

// Buffer to hold the produced items
int buffer[BUFFER_SIZE];
int count = 0;  // Number of items in the buffer

// Monitor structure
typedef struct {
	pthread_mutex_t mutex;
	pthread_cond_t cond_producer;
	pthread_cond_t cond_consumer;
} Monitor;

Monitor monitor = {
	PTHREAD_MUTEX_INITIALIZER,
	PTHREAD_COND_INITIALIZER,
	PTHREAD_COND_INITIALIZER
};

// Function prototypes
void* producer(void* param);
void* consumer(void* param);
void* counter(void* param);
void produce(int item);
int consume();

// Main function
int main() {
	pthread_t tid_counter;
	pthread_create(&tid_counter, NULL, counter, NULL);

	pthread_t tid_producer[2], tid_consumer[2];

	// Create producer and consumer threads
	for (int i = 0; i < 2; i++) {
		pthread_create(&tid_producer[i], NULL, producer, NULL);
		pthread_create(&tid_consumer[i], NULL, consumer, NULL);
	}

	// Wait for all threads to finish
	for (int i = 0; i < 2; i++) {
		pthread_join(tid_producer[i], NULL);
		pthread_join(tid_consumer[i], NULL);
		pthread_join(tid_counter, NULL);
	}

	return 0;
}

// Producer thread function
void* producer(void* param) {
	while (1) {
		int item = rand() % 100;  // Produce an item
		produce(item);
		sleep(1);  // Simulate time taken to produce an item
	}
}

// Consumer thread function
void* consumer(void* param) {
	while (1) {
		int item = consume();
		printf("Consumed: %d\n", item);
		sleep(2);  // Simulate time taken to consume an item
	}
}

void* counter(void* param) {
	while (1) {
		printf("Buffer: ");
		for (int i = 0; i < count; i++) {
			printf("%d ", buffer[i]);
		}
		printf("\n");
		sleep(1);
	}
}

// Function to produce an item and add it to the buffer
void produce(int item) {
	pthread_mutex_lock(&monitor.mutex);

	// Wait if the buffer is full
	while (count == BUFFER_SIZE) {
		pthread_cond_wait(&monitor.cond_producer, &monitor.mutex);
	}

	// Add the item to the buffer
	buffer[count++] = item;
	printf("Produced: %d\n", item);

	// Signal the consumer that an item is available
	pthread_cond_signal(&monitor.cond_consumer);

	pthread_mutex_unlock(&monitor.mutex);
}

// Function to consume an item from the buffer
int consume() {
	pthread_mutex_lock(&monitor.mutex);

	// Wait if the buffer is empty
	while (count == 0) {
		pthread_cond_wait(&monitor.cond_consumer, &monitor.mutex);
	}

	// Remove the item from the buffer
	int item = buffer[--count];

	// Signal the producer that there is space available
	pthread_cond_signal(&monitor.cond_producer);

	pthread_mutex_unlock(&monitor.mutex);

	return item;
}

/* Output:
 * Buffer: 83
 * Produced: 83
 * Consumed: 83
 * Produced: 86
 * Consumed: 86
 * Buffer:
 * Produced: 77
 * Produced: 15
 * Consumed: 15
 * Buffer:
 * Produced: 93
 * Produced: 35
 * Consumed: 77
 * Buffer: 93 35
 * Produced: 86
 * Consumed: 86
 * Produced: 92
 * Buffer: 93 35 92
 * Consumed: 92
 * Produced: 49
 * Buffer: 93 35 49
 * Consumed: 49
 * Produced: 21
 * Consumed: 21
 * Produced: 62
 * Buffer: 93 35 62
 * Buffer: 93 35 62
 */
























// Experiment 7 - Safety Algorithm
#include <stdio.h>
int main()
{
	int i, j, m, n, k, alloc[10][10], max[10][10], avail[10];
	printf("Enter no. of processes:");
	scanf("%d", &n);
	printf("Enter resources:");
	scanf("%d", &m);
	printf("Enter allocation matrix:\n");
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &alloc[i][j]);
	printf("enter max matrix:\n");
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &max[i][j]);
	printf("Enter available:");
	for (i = 0; i < m; i++)
		scanf("%d", &avail[i]);
	int f[n], ans[n], ind = 0, need[n][m], y = 0;
	for (k = 0; k < n; k++)
		f[k] = 0;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			need[i][j] = max[i][j] - alloc[i][j];
	printf("Need matrix are:\n");
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
			printf("%d ", need[i][j]);
		printf("\n");
	}
	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;
					for (y = 0; y < m; y++)
						avail[y] += alloc[i][y];
					f[i] = 1;
				}
			}
	int flag = 1;
	for (i = 0; i < n; i++)
		if (f[i] == 0)
		{
			flag = 0;
			printf("The following system is not safe\n");
			break;
		}
	if (flag == 1)
	{
		printf("Following is safe sequence\n");
		printf("System have no deadlock\n");
		for (i = 0; i < n - 1; i++)
			printf("p%d->", ans[i]);
		printf("p%d\n", ans[n - 1]);
	}
	return 0;
}

/* ----------------- OUTPUT -----------------
 *
 *  Enter no. of processes: 5
 *	Enter resources: 4
 *	Enter allocation matrix:
 *	0 0 1 2
 *	2 0 0 0
 *	0 0 3 4
 *	2 3 5 4
 *	0 3 3 2
 *	enter max matrix:
 *	0 0 1 2
 *	2 7 5 0
 *	6 6 5 5
 *	4 3 5 6
 *	0 6 5 2
 *	Enter available: 3 3 2 0
 *	Need matrix are:
 *	0 0 0 0
 *	0 7 5 0
 *	6 6 2 1
 *	2 0 0 2
 *	0 3 2 0
 *	Following is safe sequence
 *	System have no deadlock
 *	p0->p3->p4->p1->p2
 *
 */

































// Experiment 8 - Paging Algorithms
#include <limits.h>
#include <stdio.h>
#include <string.h>

// 1 2 1 3 7 4 5 6 3 1 2 4 6 3 1
int printTable(int pages[], int n, int capacity, char *policy) {
	int pageFaults = 0;
	int pageFrames[capacity];
	int pageFutureRef[capacity];
	int lruCounter[capacity];
	int fifoIndex = 0;

	// Initialize all page frames as -1
	for (int i = 0; i < capacity; i++) {
		pageFrames[i] = -1;
	}

	// Initialize lruCounter for LRU algorithm
	for (int i = 0; i < capacity; i++) {
		lruCounter[i] = -1;
	}

	printf("\nPage Replacement Policy: %s\n", policy);
	printf("Reference String | Page Frames  | Page Faults\n");
	printf("-----------------|--------------|------------\n");

	// Fill the pageFutureRef array for OPT algorithm
	if (!strcmp(policy, "OPT")) {
		for (int i = 0; i < capacity; i++) {
			pageFutureRef[i] = INT_MAX;
			for (int j = i + 1; j < n; j++) {
				if (pages[j] == pages[i]) {
					pageFutureRef[i] = j;
					break;
				}
			}
		}
	}

	// Iterate through the reference string
	for (int i = 0; i < n; i++) {
		int pageIndex = -1;
		int farthestRef = INT_MIN;
		int lruIndex = INT_MAX;

		// Check if the page is already present in the page frames
		int presentFlag = 0;
		for (int j = 0; j < capacity; j++) {
			if (pageFrames[j] == pages[i]) {
				presentFlag = 1;
				if (!strcmp(policy, "LRU")) {
					lruCounter[j] = i;
				}
				break;
			}
		}

		// If not present, find the page to be replaced
		if (!presentFlag) {
			pageFaults++;
			if (!strcmp(policy, "FIFO")) {
				pageIndex = fifoIndex;
				fifoIndex = (fifoIndex + 1) % capacity;
			} else if (!strcmp(policy, "LRU")) {
				for (int j = 0; j < capacity; j++) {
					if (lruCounter[j] < lruIndex) {
						lruIndex = lruCounter[j];
						pageIndex = j;
					}
				}
			} else if (!strcmp(policy, "OPT")) {
				for (int j = 0; j < capacity; j++) {
					int futureRef = INT_MAX;
					for (int k = i + 1; k < n; k++) {
						if (pages[k] == pageFrames[j]) {
							futureRef = k;
							break;
						}
					}
					if (futureRef > farthestRef) { // Find the farthest reference
						farthestRef = futureRef;
						pageIndex = j;
					}
				}
			}
			pageFrames[pageIndex] = pages[i];
			if (!strcmp(policy, "LRU")) {
				lruCounter[pageIndex] = i;
			}
		}

		// Print the current state
		printf("%16d | ", pages[i]);
		for (int j = 0; j < capacity; j++) {
			printf("%2d ", pageFrames[j]);
		}
		printf("\t| %2d\n", pageFaults);
	}

	printf("Total page faults: %d\n\n", pageFaults);
	return pageFaults;
}

int main() {

	int len;
	printf("Enter Reference String Length: ");
	scanf("%d", &len);
	int pages[len];

	printf("Enter Reference String: ");
	for (int i = 0; i < len; i++) {
		scanf("%d", &pages[i]);
	}

	int n = len;
	int capacity = 3;

	printTable(pages, n, capacity, "FIFO");
	printTable(pages, n, capacity, "LRU");
	printTable(pages, n, capacity, "OPT");

	return 0;
}

/* ----------------- OUTPUT -----------------
 * Enter Reference String Length: 15
 * Enter Reference String: 1 2 1 3 7 4 5 6 3 1 2 4 6 3 1
 *
 * Page Replacement Policy: FIFO
 * Reference String | Page Frames  | Page Faults
 * -----------------|--------------|------------
 *                1 |  1 -1 -1     |  1
 *                2 |  1  2 -1     |  2
 *                1 |  1  2 -1     |  2
 *                3 |  1  2  3     |  3
 *                7 |  7  2  3     |  4
 *                4 |  7  4  3     |  5
 *                5 |  7  4  5     |  6
 *                6 |  6  4  5     |  7
 *                3 |  6  3  5     |  8
 *                1 |  6  3  1     |  9
 *                2 |  2  3  1     | 10
 *                4 |  2  4  1     | 11
 *                6 |  2  4  6     | 12
 *                3 |  3  4  6     | 13
 *                1 |  3  1  6     | 14
 * Total page faults: 14
 *
 *
 * Page Replacement Policy: LRU
 * Reference String | Page Frames  | Page Faults
 * -----------------|--------------|------------
 *                1 |  1 -1 -1     |  1
 *                2 |  1  2 -1     |  2
 *                1 |  1  2 -1     |  2
 *                3 |  1  2  3     |  3
 *                7 |  1  7  3     |  4
 *                4 |  4  7  3     |  5
 *                5 |  4  7  5     |  6
 *                6 |  4  6  5     |  7
 *                3 |  3  6  5     |  8
 *                1 |  3  6  1     |  9
 *                2 |  3  2  1     | 10
 *                4 |  4  2  1     | 11
 *                6 |  4  2  6     | 12
 *                3 |  4  3  6     | 13
 *                1 |  1  3  6     | 14
 * Total page faults: 14
 *
 *
 * Page Replacement Policy: OPT
 * Reference String | Page Frames  | Page Faults
 * -----------------|--------------|------------
 *                1 |  1 -1 -1     |  1
 *                2 |  1  2 -1     |  2
 *                1 |  1  2 -1     |  2
 *                3 |  1  2  3     |  3
 *                7 |  1  7  3     |  4
 *                4 |  1  4  3     |  5
 *                5 |  1  5  3     |  6
 *                6 |  1  6  3     |  7
 *                3 |  1  6  3     |  7
 *                1 |  1  6  3     |  7
 *                2 |  2  6  3     |  8
 *                4 |  4  6  3     |  9
 *                6 |  4  6  3     |  9
 *                3 |  4  6  3     |  9
 *                1 |  1  6  3     | 10
 * Total page faults: 10
 *
 */



























// Experiment 9 - Virtual Memory
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define NFP 10

typedef struct Process {
	int pid;
	int pages;
	int page_table[NFP][2];
} Process;

int main() {
	size_t f, fsize, np, nfpp;

	printf("Enter total number of frames: ");
	scanf("%zu", &fsize);

	printf("Enter size of each frame: ");
	scanf("%zu", &f);

	printf("Memory size: %zu\n", fsize * f);

	printf("Enter number of processes: ");
	scanf("%zu", &np);

	printf("Enter number of frames per process: ");
	scanf("%zu", &nfpp);

	printf("Remaining frames: %d\n", (int) (fsize - np * nfpp));

	Process p[np];
	int frame_no = 0;

	for (size_t i = 0; i < np; ++i) {
		printf("Enter number of pages per process %zu: ", i + 1);
		scanf("%d", &p[i].pages); // Corrected index from np to i
		printf("Enter the pages to be allocated to process %zu\n", i + 1);
		for (size_t j = 0; j < nfpp; ++j) {
			scanf("%d", &p[i].page_table[j][0]);
			p[i].page_table[j][1] = frame_no++;
		}
	}

	for (size_t i = 0; i < np; ++i) {
		printf("Page table for process %zu\n", i + 1);
		printf("Page\tFrame\n");
		for (size_t j = 0; j < nfpp; ++j) {
			printf("%4d\t%5d\n", p[i].page_table[j][0], p[i].page_table[j][1]);
		}
		printf("\n");
	}

	int ch = 1; // To ensure loop runs initially

	while (ch == 1) {
		int pno, inst;
		int found = 0, frame = 0;

		printf("Enter process number: ");
		scanf("%d", &pno);
		printf("Enter instruction no. to be executed: ");
		scanf("%d", &inst);

		// Correct the page calculation
		int page = inst / f;
		if (inst % f != 0) {
			page++;
		}

		for (size_t i = 0; i < nfpp; ++i) {
			if (p[pno - 1].page_table[i][0] == page) {
				found = 1;
				frame = p[pno - 1].page_table[i][1];
				break;
			}
		}

		if (found == 1) {
			int loc = frame * f + (inst - 1) % f;
			printf("Instruction %d is in frame %d at location %d\n", inst, frame, loc + 1);
		} else {
			printf("Instruction %d is not found\n", inst);
			printf("Page fault\n");
		}

		printf("Do you want to continue? (1 for yes, 0 for no): ");
		sleep(1);
		scanf("%d", &ch); // Prompt user to continue or not
	}

	return 0;
}


/* ----------------- OUTPUT -----------------
 *
 *   Enter total number of frames: 10
 *   Enter size of each frame: 3
 *   Memory size: 30
 *   Enter number of processes: 3
 *   Enter number of frames per process: 3
 *   Remaining frames: 1
 *   Enter number of pages per process 1: 1
 *   Enter the pages to be allocated to process 1
 *   2 3 4
 *   Enter number of pages per process 2: 3
 *   Enter the pages to be allocated to process 2
 *   5 6 7
 *   Enter number of pages per process 3: 3
 *   Enter the pages to be allocated to process 3
 *   8 9 10
 *   Page table for process 1
 *   Page    Frame
 *   2        0
 *   3        1
 *   4        2
 *
 *   Page table for process 2
 *   Page    Frame
 *   5        3
 *   6        4
 *   7        5
 *
 *   Page table for process 3
 *   Page    Frame
 *   8        6
 *   9        7
 *   10        8
 *
 *   Enter process number: 1
 *   Enter instruction no. to be executed: 4
 *   Instruction 4 is in frame 0 at location 1
 *   Do you want to continue? (1 for yes, 0 for no): 1
 *   Enter process number: 1
 *   Enter instruction no. to be executed: 6
 *   Instruction 6 is in frame 0 at location 3
 *
 * */



































// Experiment 10.1 - First Fit Algorithm
#include <stdio.h>

int main(void)
{
	int bsize[10], psize[10], bno, pno, flags[10], allocation[10];

	for (size_t i = 0; i < 10; i++)
	{
		flags[i] = 0;
		allocation[i] = -1;
	}

	printf("Enter the number of blocks: ");
	scanf("%d", &bno);

	printf("Enter the size of the blocks: ");
	for (size_t i = 0; i < bno; i++)
	{
		scanf("%d", &bsize[i]);
	}

	printf("Enter the number of processes: ");
	scanf("%d", &pno);

	printf("Enter the size of the processes: ");
	for (size_t i = 0; i < pno; i++)
	{
		scanf("%d", &psize[i]);
	}

	for (size_t i = 0; i < pno; i++)
	{
		for (size_t j = 0; j < bno; j++)
		{
			if (flags[j] == 0 && bsize[j] >= psize[i])
			{
				allocation[j] = i;
				flags[j] = 1;
				break;
			}
		}
	}

	int intf[100] = { 0 };

	for (size_t i = 0; i < pno; ++i) {
		if (bsize[i] >= psize[i]) {
			intf[i] = bsize[i] - psize[i];
		}
	}

	printf(" Fist Fit\n");
	printf("\nBlock no.\tBlock size\tProcess no.\tProcess size\tInternal Fragmentation");
	for (size_t i = 0; i < bno; i++)
	{
		printf("\n%zu\t\t%d\t\t", i + 1, bsize[i]);
		if (flags[i] == 1)
		{
			printf("%d\t\t%d\t\t%d", allocation[i] + 1, psize[allocation[i]], intf[i]);
		}
		else
		{
			printf("Not allocated");
		}
	}
	printf("\n");

	return 0;
}


/* ----------------- OUTPUT -----------------
 *
 *	Enter the number of blocks: 3
 *	Enter the size of the blocks:
 *	8 10 12
 *	Enter the number of processes: 3
 *	Enter the size of the processes:
 *	2 3 12
 *	 Fist Fit
 *
 *	Block no.       Block size      Process no.     Process size    Internal Fragmentation
 *	1               8               1               2               6
 *	2               10              2               3               7
 *	3               12              3               12              0
 *
 */

// Experiment 10.2 - Best Fit Algorithm
#include <stdio.h>
#include <stdbool.h>

int main(void) {

	int n, p, total = 0;

	printf("Enter the number of processes: ");
	scanf("%d", &p);

	int process_size[p];

	printf("Memory Required by each process: ");
	for(size_t i = 0; i < p; ++i) {
		scanf("%d", &process_size[i]);
	}

	printf("Enter the number of Memory Partitions: ");
	scanf("%d", &n);

	int block_size[n];
	printf("Memory Size of each partition: ");
	for(size_t i = 0; i < n; ++i) {
		scanf("%d", &block_size[i]);
		total += block_size[i];
	}

	printf("Best Fit:\n");

	int alloc[p], sum = 0, best_index = 0;
	bool external[n];

	for (size_t i = 0; i < p; ++i) {
		alloc[i] = -1;
	}

	for (size_t i = 0; i < n; ++i) {
		external[i] = false;
	}

	for (size_t i = 0; i < p; ++i) {
		best_index = -1;
		for (size_t j = 0; j < n; ++j) {
			if (!external[j] && block_size[j] >= process_size[i]) {
				if (best_index == -1) {
					best_index = j;
				} else if (block_size[best_index] > block_size[j]) {
					best_index = j;
				}
			}

			if (best_index != -1) {
				alloc[i] = best_index;
				external[best_index] = true;
			}
		}
	}

	printf("Process No.\tProcess Size\tBlock Size\tInternal Fragmentation\n");
	for (size_t i = 0; i < p; ++i) {
		printf("%zu\t\t%d\t\t", i + 1, process_size[i]);
		if (alloc[i] == -1) {
			printf("Not Allocated\n");
		} else {
			printf("%d\t\t%d\n", block_size[alloc[i]], block_size[alloc[i]] - process_size[i]);
		}
	}

	printf("External Fragmentation: ");
	for (size_t i = 0; i < n; ++i) {
		if (!external[i]) {
			sum += block_size[i];
			printf("Block: %zu\n", i);
		}
	}
	printf("Total External Fragmentation: %d\n", sum);


	return 0;
}

/* ----------------- OUTPUT -----------------
 *
 *	Enter the number of processes: 4
 *	Memory Required by each process:
 *	150 50 230 300
 *	Enter the number of Memory Partitions: 5
 *	Memory Size of each partition:
 *	50 100 200 300 400
 *	Best Fit:
 *	Process No.     Process Size    Block Size      Internal Fragmentation
 *	1               150             200             50
 *	2               50              50              0
 *	3               230             300             70
 *	4               300             400             100
 *	External Fragmentation: Block: 1
 *	Total External Fragmentation: 100
 *
 */






























// Experiment 11 - Contiguos File Allocation
#include <stdio.h>

int main(void) {

	int n = 0;
	int c = 0;
	int file[10];
	int len[10];

	printf("No.of Files to allocate: ");
	scanf("%d", &n);

	printf("Enter File no. to allocate: ");
	for (int i = 1; i <= n; i++) {
		scanf("%d", &file[i]);
	}

	printf("Enter File length: ");
	for (int i = 1; i <= n; i++) {
		scanf("%d", &len[i]);
	}

	printf("Allocated File data: \n");
	printf("File Name\tFile Length\tStart Block\n");
	int k = 1, count = 0, i = 1;
	while (i <= n) {
		int z = k + len[i];
		count += len[i];
		printf("%d\t\t%d\t\t%d\n", file[i], len[i], count - len[i] + 1);
		printf("\n");
		++i;
	}

	return 0;
}

/* ----------------- OUTPUT -----------------
 *
 *	No.of Files to allocate: 2
 *	Enter File no. to allocate: 1 2
 *	Enter File length: 4 10
 *	Allocated File data:
 *	File Name       File Length     Start Block
 *	1               4               1
 *
 *	2               10              5
 *
 */







































// Experiment 12 - Bitmap Allocation
#include <stdio.h>

int main(void) {
	int a[32], n;

	for (size_t i = 1; i <= 32; i++) {
		a[i] = 1;
	}

	printf("No. of Blocks to allocate: ");
	scanf("%d", &n);

	printf("Which blocks need to be allocated: ");
	for (size_t i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		a[x] = 0;
	}
	printf("\n");

	printf("Allocated blocks are: \n");
	printf("Index\tAllocation\n");
	for (size_t i = 1; i <= 32; i++) {
		printf("%zu\t%d\n", i, a[i]);
	}

}

/* ----------------- OUTPUT -----------------
 *
 *	No. of Blocks to allocate: 9
 * 	Which blocks need to be allocated: 2 3 4 5 8 9 10 11 12
 *
 *	Allocated blocks are:
 *	Index   Allocation
 *	1       1
 *	2       0
 *	3       0
 *	4       0
 *	5       0
 *	6       1
 *	7       1
 *	8       0
 *	9       0
 *	10      0
 *	11      0
 *	12      0
 *	13      1
 *	14      1
 *	15      1
 *	16      1
 *	17      1
 *	18      1
 *	19      1
 *	20      1
 *	21      1
 *	22      1
 *	23      1
 *	24      1
 *	25      1
 *	26      1
 *	27      1
 *	28      1
 *	29      1
 *	30      1
 *	31      1
 *	32      1
 *
 */