Created
December 28, 2019 09:30
-
-
Save is3ka1/79ee0377aeb006c7c65906396799cb99 to your computer and use it in GitHub Desktop.
OS - Optimal Page Replacement
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#define CHUNK_SIZE 10 | |
char *read_pages(size_t *len) { | |
size_t page_len = 0, pages_size = CHUNK_SIZE; | |
char *pages = (char *) calloc(pages_size + 1, sizeof(char)); | |
FILE *page_file = fopen("page.txt", "r"); | |
while (fscanf(page_file, "%c ", pages + page_len) != EOF) { | |
if (++page_len >= pages_size) { | |
pages_size += CHUNK_SIZE; | |
pages = realloc(pages, pages_size + 1); | |
if (pages == NULL) { | |
perror("realloc error"); | |
exit(-1); | |
} | |
} | |
} | |
fclose(page_file); | |
pages[page_len] = 0; | |
*len = page_len; | |
return pages; | |
} | |
void print_frame(char *frames, int len) { | |
for (int i = 0; i < len; ++i) | |
printf("%c ", frames[i]); | |
printf("\n"); | |
} | |
void optimal(char *full_pages, char *frames, int frames_len) { | |
int page_faults = 0; | |
for (int i = 0; i < strlen(full_pages); ++i) { | |
if (strchr(frames, full_pages[i]) == NULL) { | |
++page_faults; | |
char *empty_frame = strchr(frames, 0); | |
if (empty_frame < frames + frames_len) { | |
*empty_frame = full_pages[i]; | |
} else { | |
int victim, max = -1, tmp; | |
char *page_addr; | |
for (int j = 0; j < frames_len; ++j) { | |
page_addr = strchr(full_pages + i, frames[j]); | |
if (page_addr == NULL) { | |
victim = j; | |
break; | |
} | |
if ((tmp = page_addr - full_pages + i) > max) { | |
max = tmp; | |
victim = j; | |
} | |
} | |
frames[victim] = full_pages[i]; | |
} | |
} | |
print_frame(frames, frames_len); | |
} | |
printf("\nPage Faults = %d\n", page_faults); | |
} | |
int main(void) { | |
int frames_len; | |
printf("Length of frames: "); | |
scanf("%d", &frames_len); | |
char *frames = (char *) calloc(frames_len + 1, sizeof(char)); | |
size_t page_len; | |
char *pages = read_pages(&page_len); | |
printf("Reference strings:"); | |
for (int i = 0; i < page_len; ++i) { | |
printf(" %c", pages[i]); | |
} | |
printf("\n\n"); | |
optimal(pages, frames, frames_len); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment