· 8 years ago · Feb 24, 2018, 12:40 AM
1// Kyle Savell & Antony Qin
2
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6#include <ctype.h>
7#include <assert.h>
8
9#define SIZE 64
10#define MAXPROC 4
11#define MAXPAGE 4
12
13// Memory
14unsigned char memory[SIZE];
15
16// PID array
17int pids[MAXPROC];
18
19// Free list
20int freeList[MAXPROC];
21
22// Permissions
23int perm[MAXPROC][MAXPAGE];
24
25// Existing Pages
26int page_exists[MAXPROC][MAXPAGE];
27
28// Page Location on Disk
29int on_disk[MAXPROC][MAXPAGE + 1];
30
31// Disk
32FILE *disk;
33
34// Round Robin Eviction
35int last_evict = 0;
36
37// Function Declarations
38int getPage(int addr); // Returns a corresponding page based on an address
39int getAddr(int page); // Returns address of the begin of a given page
40int toMem(int begin, char* value); // Writes integer into memory, begin is the physical address we want to write to
41int fromMem(int begin); // Reads integer from memory
42int translate_ptable(int pid, int v_addr); // Translate page table, return physical address from virtual address
43int create_ptable(int pid); // Allocates page table entry into virtual page
44int map(int pid, int v_addr, int r_value); // Maps virtual page to physical page
45int store(int pid, int v_addr, int value); // Stores value in physical memory
46int load(int pid, int v_addr); // Loads value from physical memory
47int evict(int pid); // Returns physical page that is to be evicted
48int remap(int pid, int v_page, int p_page); //Remaps virtual page if pulled from disk
49int replace_page(int pid, int v_page); // Handles page replacements
50int swap(int page, int lineNum); // Swaps page from physical memory and disk, returns lineNum page was put in disk
51int putToDisk(char page[16]); // Puts page in disk
52int getFromDisk(char (*pageHolder)[16], int lineNum); // Gets page from disk
53
54//getPage gets page from virtual address
55int getPage(int addr){
56 if(addr>=0 && addr<16){
57 return 0;
58 }
59 else if(addr<32){
60 return 1;
61 }
62 else if(addr<48){
63 return 2;
64 }
65 else if(addr<64){
66 return 3;
67 }
68 else{
69 return -1;
70 }
71}
72
73//getAddress gets address from page
74int getAddr(int page){
75 if(page==0){
76 return 0;
77 }
78 else if(page==1){
79 return 16;
80 }
81 else if(page==2){
82 return 32;
83 }
84 else if(page==3){
85 return 48;
86 }
87 else{
88 return -1;
89 }
90}
91
92// Writes integer into memory, begin is the physical address we want to write to
93int toMem(int begin, char* val){
94 int bytes = strlen(val);
95 int isRoom = begin%16;
96
97 if ((isRoom + bytes) >= 15){
98 return -1;
99 }
100
101 int count=0;
102 for(int i=begin; i<16+begin; i++){
103 if(val[i - begin] != 0){
104 memory[i] = val[i - begin];
105 count=i;
106 }
107 else{
108 break;
109 }
110 }
111
112 return (count - begin);
113}
114
115// Reads integer from memory
116int fromMem(int begin)
117{
118 int read_val;
119 char buffer[4];
120 for(int i = 0; i < 4; i++)
121 {
122 if(memory[begin + i] != '*' && i != 3)
123 buffer[i] = memory[begin + i];
124 else
125 {
126 buffer[i] = '\0';
127 break;
128 }
129 }
130 if(buffer[0] == '\0') return -1;
131 else
132 {
133 sscanf(buffer, "%d", &read_val);
134 return read_val;
135 }
136}
137
138// Translate page table, return physical address from virtual address
139// ptable format is an array {0,',',1,1,',',2} -> single digit to immediate left of , is virtual page, single digit to immediate right of , is physical page the vitual page is mapped to.
140// In example, virtual page 0 is mapped to physical page 1 & virtual page 1 is mapped to physical page 2
141int translate_ptable(int pid, int v_addr)
142{
143 int begin = pids[pid];
144 int v_page = getPage(v_addr);
145 int offset = v_page * 16;
146 int phys_addr = -1;
147 int cur_addr = begin;
148 for (int i = 0; i < 16; i++) // Only look up to end of page table virtual page
149 {
150 if (memory[cur_addr] == ',') // PTE Separator
151 {
152 if(memory[cur_addr - 1] - '0' == getPage(v_addr))
153 return getAddr
154 (memory[cur_addr + 1] - '0') + v_addr - offset;
155 }
156 cur_addr++;
157 }
158 return phys_addr; // Return physical address, -1 if address not found
159}
160
161// Allocates page table entry into virtual page
162int create_ptable(int pid)
163{
164 int been_allocated = -1;
165 for(int i = 0; i < 4; i++)
166 {
167 if (freeList[i] == -1)
168 {
169 freeList[i] = 0;
170 pids[pid] = getAddr
171 (i); // Put physical address into pid register
172 been_allocated = 1;
173 printf("Put page table for PID %d into physical frame %d\n", pid, i);
174 break;
175 }
176 }
177
178 if (been_allocated == -1)
179 {
180 int to_evict = evict(pid);
181 swap(to_evict, -1);
182 //replace_page(pid, -1);
183 int p_page = last_evict;
184 pids[pid] = getAddr
185 (p_page);
186 printf("Put page table for PID %d into physical frame %d\n", pid, p_page);
187 }
188}
189
190// Maps virtual page to physical page
191int map(int pid, int v_addr, int r_value)
192{
193 int page_table = pids[pid];
194 int been_allocated = -1;
195 char full_str[16] = "";
196 char buffer[10];
197 char new_entry[10];
198
199 int v_page = getPage(v_addr);
200 int p_page;
201
202 // Create page table for process if one does not exist
203 if (page_table == -1 && on_disk[pid][0] == -1)
204 {
205 create_ptable(pid);
206 }
207
208 // Check if entry already exists and update it
209 if (page_exists[pid][v_page] == 1)
210 {
211 if (perm[pid][v_page] == r_value) {
212 printf("ERROR: virtual page %d is already mapped with rw_bit=%d\n", v_page, r_value);
213 } else {
214 printf("Updating permissions for virtual page %d (frame %d)\n", v_page, getPage(translate_ptable(pid, getAddr
215 (v_page)))); //
216 perm[pid][v_page] = r_value;
217 }
218 }
219
220 // Create new entry
221 // memset(&buffer[0], 0, sizeof(buffer));
222 else
223 {
224 for(int i = 0; i < 4; i++)
225 {
226 if (freeList[i] == -1)
227 {
228 freeList[i] = 0;
229 perm[pid][v_page] = r_value; // Set permissions
230 page_exists[pid][v_page] = 1; // Set existence of page
231 been_allocated = 1;
232 p_page = i;
233
234 int write_addr = pids[pid];
235 for(int j = 0; j < 16; j++)
236 {
237 if (memory[write_addr] == '*') // Write entry to ptable
238 {
239 sprintf(buffer, "%d", v_page);
240 strcat(full_str, buffer);
241 strcat(full_str, ",");
242 sprintf(buffer, "%d", p_page);
243 strcat(full_str, buffer);
244 write_addr += toMem(write_addr, full_str);
245 break;
246 }
247 write_addr++;
248 }
249
250 printf("Mapped virtual address %d (page %d) into physical frame %d\n", v_addr, v_page, p_page);
251 break;
252 }
253 }
254 if (been_allocated == -1)
255 {
256 int to_evict = evict(pid);
257 swap(to_evict, -1);
258 //replace_page(pid, -1);
259 perm[pid][v_page] = r_value; // Set permissions
260 page_exists[pid][v_page] = 1; // Set existence of page
261 been_allocated = 1;
262 p_page = last_evict;
263
264 int write_addr = pids[pid];
265 for(int j = 0; j < 16; j++)
266 {
267 if (memory[write_addr] == '*') // Write entry to ptable
268 {
269 sprintf(buffer, "%d", v_page);
270 strcat(full_str, buffer);
271 strcat(full_str, ",");
272 sprintf(buffer, "%d", p_page);
273 strcat(full_str, buffer);
274 write_addr += toMem(write_addr, full_str);
275 break;
276 }
277 write_addr++;
278 }
279
280 printf("Mapped virtual address %d (page %d) into physical frame %d\n", v_addr, v_page, p_page);
281 }
282 }
283
284 return 0; // Success
285}
286
287// Changes mapping of virtual page in a page table when swapping in from disk
288int remap(int pid, int v_page, int p_page){
289 // Change physical address of page and overwrite entry in page table
290 char full_str[16] = "";
291 char buffer[10];
292 int been_allocated = -1;
293
294 int write_addr = pids[pid];
295 int v_flag = 1; // Whether specific entry is virtual page or not
296 int p_flag = 0; // Whether specific entry is a physical page or not
297 int correct_p = 0; // Flag for correct page to overwrite
298 for(int j = 0; j < 16; j++){
299 if (memory[write_addr] == ','){
300 if(memory[write_addr - 1] == v_page){
301 memory[write_addr + 1] = p_page;
302 }
303 }
304 write_addr++;
305 }
306
307 printf("Remapped virtual page %d into physical frame %d\n", v_page, p_page);
308 return 0; //Success
309}
310
311// Stores value in physical memory
312int store(int pid, int v_addr, int value)
313{
314 if (on_disk[pid][0] != -1)
315 {
316 int to_evict = evict(pid);
317 swap(to_evict, on_disk[pid][0]);
318 }
319 int phys_addr = translate_ptable(pid, v_addr);
320 int v_page= getPage(v_addr);
321 char buffer[10] = "";
322
323 if (perm[pid][v_page] == 1)
324 {
325 if (page_exists[pid][v_page] == 1)
326 {
327 if (on_disk[pid][v_page + 1] != -1)
328 {
329 int to_evict = evict(pid);
330 swap(to_evict, on_disk[pid][v_page+1]);
331 //replace_page(pid, v_page);
332 }
333 sprintf(buffer, "%d", value);
334 int num_bytes = toMem(phys_addr, buffer);
335 if (num_bytes == -1)
336 {
337 printf("ERROR: Write goes over end of page! Value not stored\n");
338 }
339 else
340 {
341 printf("Stored value %d at virtual address %d (physical address %d)\n", value, v_addr, phys_addr);
342 }
343 }
344 else
345 {
346 printf("ERROR: Virtual page %d has not been allocated for process %d!\n", v_page, pid);
347 }
348 }
349 else
350 {
351 printf("ERROR: Writes are not allowed to this page\n");
352 }
353
354 return 0; // Success
355}
356
357// Loads value from physical memory
358int load(int pid, int v_addr)
359{
360 int v_page = getPage(v_addr);
361 printf("On disk for pid %d: %d\n", pid, on_disk[pid][0]);
362 if (on_disk[pid][0] != -1)
363 {
364 int to_evict = evict(pid);
365 swap(to_evict, on_disk[pid][0]);
366 }
367 printf("On disk for v_page %d: %d\n", v_page, on_disk[pid][v_page + 1]);
368 if (on_disk[pid][v_page + 1] != -1)
369 {
370 int to_evict = evict(pid);
371 swap(to_evict, on_disk[pid][v_page+1]);
372 //replace_page(pid, v_page);
373 }
374 int phys_addr = translate_ptable(pid, v_addr);
375 int value = fromMem(phys_addr);
376 if (value == -1)
377 {
378 printf("ERROR: No value stored at virtual address %d (physical address %d)\n", v_addr, phys_addr);
379 }
380 else
381 {
382 printf("The value %d is virtual address %d (physical address %d)\n", value, v_addr, phys_addr);
383 }
384
385 return 0; // Success
386}
387
388// Chooses physical page to evict from memory
389// Current algorithm is round robin, will skip page if it is the process's page table
390int evict(int pid)
391{
392 int ptable = getPage(pids[pid]); // Physical page where pid's ptable is
393
394 int cur_evict = last_evict + 1;
395 if (cur_evict >= 4)
396 {
397 cur_evict = 0;
398 }
399 if (cur_evict == ptable)
400 {
401 cur_evict++;
402 if (cur_evict >= 4)
403 {
404 cur_evict = 0;
405 }
406 }
407
408 last_evict = cur_evict;
409 return cur_evict;
410}
411
412// Swaps page from physical memory and disk, returns lineNum page was put in disk
413int swap(int page, int lineNum)
414{
415 int begin = getAddr
416(page);
417 char putTemp[16];
418 char getTemp[16];
419 int replaceMem = -1;
420 int putLine = -1;
421 int ptable_flag = -1;
422
423 // If page to swap is a page table, erase address in pids
424 for(int i = 0; i < MAXPROC; i++)
425 {
426 if (begin == pids[i])
427 {
428 pids[i] = -1;
429 ptable_flag = i;
430 break;
431 }
432 }
433
434 for(int i = 0; i < 16; i++)
435 {
436 putTemp[i] = memory[begin + i];
437 }
438
439 if(lineNum != -1) // If lineNum is -1, don't try to get something from disk
440 {
441 replaceMem = getFromDisk(&getTemp, lineNum);
442 freeList[page] = 0;
443 }
444 putLine = putToDisk(putTemp);
445
446 if(putLine == -1)
447 {
448 printf("ERROR: Could not put page to disk.\n");
449 return -1;
450 }
451 else if(replaceMem != -1)
452 {
453 for(int i = 0; i < 16; i++)
454 {
455 memory[begin + i] = getTemp[i];
456 }
457 }
458 else // Cannot swap in new memory after putting old in disk, replace memory with empty page
459 {
460 for(int i = 0; i < 16; i++)
461 {
462 memory[begin + i] = '*';
463 }
464 }
465
466 // Find the process & page we are putting in memory
467 if(lineNum != -1)
468 {
469 for(int i = 0; i < MAXPROC; i++)
470 {
471 for(int j = 0; j < MAXPROC + 1; j++)
472 {
473 if(on_disk[i][j] == lineNum)
474 {
475 on_disk[i][j] = -1;
476 if(j != 0)
477 remap(i, j - 1, page);
478 else if(j == 0 && ptable_flag == -1)
479 pids[i] = begin;
480 break;
481 }
482 }
483 }
484 }
485
486 // Find the process and page we are removing from memory
487if(ptable_flag != -1) // Swapping out page instead of page table
488{
489 int r_pid = -1;
490 int r_vpage = -1;
491 // Page table in physical memory
492 for (int i = 0; i < MAXPROC; i++)
493 {
494 if (pids[i] != -1) // Find page table
495 {
496 int cur_addr = pids[i];
497 printf("cc page table of %d is ", i);
498 for (int j = 0; j < 16; j++) // Only look up to end of page table virtual page
499 {
500 printf("%c", memory[cur_addr]);
501 if (memory[cur_addr] == ',') // PTE Separator
502 {
503 if(memory[cur_addr + 1] - '0' == page)
504 {
505 r_pid = i;
506 r_vpage = memory[cur_addr - 1] - '0';
507 }
508 }
509 cur_addr++;
510 }
511 printf(" cc\n");
512 }
513 }
514 // Page table in disk
515 int cur_ptable = -1;
516 if (r_pid == -1)
517 {
518 for (int i = 0; i < MAXPROC; i++)
519 {
520 cur_ptable = on_disk[i][0]; // ptable location on disk
521 if (cur_ptable != -1)
522 {
523 replaceMem = getFromDisk(&getTemp, cur_ptable);
524 for (int j = 0; j < 16; j++) // Only look up to end of page table virtual page
525 {
526 if (getTemp[j] == ',') // PTE Separator
527 {
528 if(getTemp[j + 1] - '0' == page)
529 {
530 r_pid = j;
531 r_vpage = getTemp[j - 1] - '0';
532 }
533 }
534 }
535 }
536 if (r_pid != -1) break;
537 }
538 }
539 if(r_pid != -1 && r_vpage != -1)
540 {
541 on_disk[r_pid][r_vpage + 1] = putLine;
542 }
543 else
544 {
545 printf("ERROR: Page being swapped out doesn't exist in a process?\n");
546 }
547}
548 else
549 {
550 on_disk[ptable_flag][0] = putLine;
551 }
552 printf("Swapped frame %d to disk at swap slot %d\n", page, putLine);
553 if (lineNum != -1)
554 {
555 printf("Swapped disk slot %d into frame %d\n", lineNum, page);
556 }
557 if (ptable_flag != -1)
558 {
559 printf("Put page table for PID %d into swap slot %d\n", ptable_flag, putLine);
560 }
561 return putLine;
562}
563
564// Puts page in disk
565int putToDisk(char page[16])
566{
567 int line_placement = -1; // Where line is on disk
568 char currChar;
569 int pageCounter = 0; // Counts each character of a page
570
571 disk = fopen("disk.txt", "r+");
572 if(disk == NULL)
573 {
574 printf("ERROR: Cannot open disk in putToDisk.\n");
575 return -1;
576 }
577
578 do
579 {
580 currChar = fgetc(disk);
581 pageCounter++;
582
583 if(feof(disk)) // Empty file, put page in
584 {
585 for(int i = 0; i < 16; i++)
586 {
587 fputc(page[i], disk);
588 }
589 fputc('\n', disk);
590 line_placement = 0;
591 break;
592 }
593 else // Look for a free space
594 {
595 printf("%c", currChar);
596 if(pageCounter == 16)
597 {
598 line_placement++;
599 printf(" end \n");
600 }
601 if(currChar == '!' && pageCounter == 16) // This line in disk is free, all '!'
602 {
603 fseek(disk, -16, SEEK_CUR);
604 for(int i = 0; i < 16; i++)
605 {
606 fputc(page[i], disk);
607 }
608 break;
609 }
610 else if(pageCounter > 16)
611 {
612 pageCounter = 0;
613 }
614 }
615 }
616 while(currChar != EOF);
617
618 fclose(disk);
619 return line_placement;
620}
621
622// Gets page from disk
623int getFromDisk(char (*pageHolder)[16], int lineNum)
624{
625 int line_placement = -1; // Where line is on disk
626 char currChar;
627 int pageCounter = 0; // Counts each character of a page
628
629 disk = fopen("disk.txt", "r+");
630 if(disk == NULL)
631 {
632 printf("ERROR: Cannot open disk in getFromDisk.\n");
633 return -1;
634 }
635
636 do
637 {
638 currChar = fgetc(disk);
639 pageCounter++;
640
641 if(feof(disk) && line_placement == -1)
642 {
643 printf("ERROR: Cannot get page from empty disk.\n");
644
645 fclose(disk);
646 return -1;
647 }
648 else
649 {
650 if(pageCounter == 16)
651 {
652 line_placement++;
653 }
654 if(line_placement == lineNum && pageCounter == 16) // Get this line from disk
655 {
656 fseek(disk, -16, SEEK_CUR);
657 for(int i = 0; i < 16; i++)
658 {
659 currChar = fgetc(disk);
660 (*pageHolder)[i] = currChar;
661 fseek(disk, -1, SEEK_CUR);
662 fputc('!', disk); // Replace this line with a free line, all '!'
663 }
664 fputc('\n', disk);
665
666 fclose(disk);
667 return 0;
668 }
669 else if(pageCounter > 16)
670 {
671 pageCounter = 0;
672 }
673 }
674 }
675 while(currChar != EOF);
676
677 fclose(disk);
678 return -1;
679}
680
681//function to split user input
682char** splitInput(char* string, const char toSplit){
683 char** final=0;
684 size_t size=0;
685 char* temp=string;
686 char* prevComma=0;
687 char delim[1];
688 delim[0]=toSplit;
689
690 while(*temp){
691 if(toSplit==*temp){
692 size++;
693 prevComma=temp;
694 }
695 temp++;
696 }
697
698 size+=prevComma<(string+strlen(string)-1);
699
700 size++;
701
702 final=malloc(sizeof(char*)*size);
703
704 if(final){
705 size_t i=0;
706 char* token=strtok(string, delim);
707
708 while(token){
709 assert(i<size);
710 *(final+(i++))=strdup(token);
711 token=strtok(0,delim);
712 }
713 assert(i==size-1);
714 *(final+i)=0;
715 }
716 return final;
717}
718
719//compare two strings
720int cmp(char a[], char b[]){
721 for(int i=0; a[i]!='\0'||b[i]!='\0'; i++){//compare elements if not NULL
722 if(a[i]!=b[i]){//if chars don't match, set false
723 return 0;
724 }
725 }
726 return 1;
727}
728
729
730// Main
731int main(int argc, char *argv[])
732{
733 //create temporary array for stripped input
734 char** temp;
735
736 //create strings for user input
737 char* input=(char*)malloc(sizeof(char*)); //gets user input
738 char* instruct=(char*)malloc(sizeof(char*)); //function chosen by user
739
740 int pid = 0; // Process ID
741 int inst_type = 0; // Instruction type
742 int v_addr = 0; // Virtual address
743 //int input = 0; // Value
744 int is_end = 0; // Boolean for ending simulation
745
746 char buffer[20]; // Holds stdin buffer
747 char cmd_seq[20]; // The command sequence read from stdin
748 char* cmd_array[4]; // Holds the commands read from file
749 char* token;
750
751 // Clean disk
752 disk = fopen("disk.txt", "w");
753 if(disk == NULL)
754 {
755 printf("ERROR: Cannot open disk in main.");
756 return -1;
757 }
758 else
759 fclose(disk);
760
761 // Initialize ptable, free and write lists
762 for (int i = 0; i < MAXPROC; i++)
763 {
764 pids[i] = -1;
765 freeList[i] = -1;
766 for (int j = 0; j < MAXPAGE + 1; j++)
767 {
768 if (j < 4)
769 {
770 perm[i][j] = 0;
771 page_exists[i][j] = 0;
772 }
773 on_disk[i][j] = -1;
774 }
775 }
776
777 // Initialize physical memory
778 for (int i = 0; i < SIZE; i++)
779 {
780 memory[i] = '*';
781 }
782
783 while(1){
784 //prompt instructions
785 printf("Instruction? ");
786
787 //get instructions
788 if(fgets(input, 15, stdin)==NULL) {
789 printf("End of file. Exiting.\n");
790 exit(1);
791 }
792 printf("\n");
793
794 //split input at every comma
795 temp=splitInput(input, ',');
796
797 //assign input to vars
798 int pid=atoi(temp[0]); //process id user input in range [0,3]
799 instruct=temp[1]; //instruction from user input
800 int virt=atoi(temp[2]); //virtual address user input in range [0,63]
801 int value=atoi(temp[3]); //depends on instruct, int in range [0,255]
802
803 //print out what is being done
804 if(cmp("map", instruct)){
805 map(pid, virt, value);
806 printf("\n");
807 }
808 else if(cmp("store", instruct)){
809 store(pid, virt, value);
810 printf("\n");
811 }
812 else if(cmp("load", instruct)){
813 load(pid, virt);
814 printf("\n");
815 }
816 }
817
818 /*logMem();
819 for (int i = 0; i < MAXPROC; i++)
820 {
821 printf("%d\n", pids[i]);
822 }
823 return 0;*/
824}