mem.c

solutions for some problems in Linux

/******************************************************************************
 * mem.c
 * This file is part of "Assignment 2: Memory Management" 
 * Copyright (C) 2008 - c506001 (email: [e-mail] )
 *
 * Note:
 * -----
 * These codes are used for reference, but not complete. Students can modified
 * them to satisfy the requirements.
 * 
 * Content:
 * -------- 
 * Functions of memory management
 *
 * System and Networking Department
 * Faculty of Computer Science and Engineering
 * Ho Chi Minh City University of Technology
 ******************************************************************************/

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include "sys.h"

/**
 * findPageOnDisk: find data for faulty page on disk
 * @memAddr: logical address
 * 
 * @return: always 0
 **/
static int findPageOnDisk(int memAddr)
{
	/* This function find a page stored on disk.
	   However, we don't simulation this, so just make it a little delay. */
	printf("Finding page (logical addr %d) on disk ... \n", memAddr);
	sleep(1);
	return 0;
}

/**
 * findFreeFrame: find a free frame in main memory
 * @system: system
 * 
 * @return: the free frame index or error-code (ERR_NO_FREE_FRAME)
 **/
static int findFreeFrame(struct System *system)
{
	int i = 0;
	/* Search in system a free frame */
	for (i = 0; i < system->nFrames; i++) {
		if (system->frameStatus[i].state == FREE) {
			printf("Frame %d is free, can be used \n", i);
			return i;
		}
	}
	printf("There is no free frames\n");

	return ERR_NO_FREE_FRAME;
}

/**
 * chooseVictimFrame: choose a victim frame by an algorithm of page replacement
 * @task: task
 * @system: system
 * 
 * @return: the victim page
 * 
 * Note: in this example, just find a victim page in task (the first VALID page)
 * Please read requirements to modify or rewrite this function.
 **/
struct PageStatus *getPageFromFrame(struct System *system, struct Task *task, int frame){
	int i = 0;
	int j = 0;
	struct PageStatus *pageStatus;

	for (i = 0; i < (1 << N_SECTION_BITS); i++) {
		for (j = 0; j < (1 << N_PAGE_BITS); j++) {
			pageStatus = getFrameFromPage(task, i, j);
			if (pageStatus->frame == frame){
				return pageStatus;
			}
		}
	}
	return NULL;
}
struct PageStatus* chooseVictimFrame(struct System *system, struct Task *task)
{
	// TODO: Implement this function with Second chance algorithm

	int i = 0;
//	int j = 0;
	struct PageStatus *pageStatus;

	/* in this algorithm of page replacement, we choose the first VALID page 
	for (i = 0; i < (1 << N_SECTION_BITS); i++) {
		for (j = 0; j < (1 << N_PAGE_BITS); j++) {
			pageStatus = getFrameFromPage(task, i, j);
			if (pageStatus->state == VALID) {
				return pageStatus;
			}
		}
	}*/
	for (i=0;i<system->nFrames;i++)	{
		if (system->frameStatus[i].lastAccessTime == 1)
			system->frameStatus[i].lastAccessTime = 0;
		else{
			pageStatus = getPageFromFrame(system, task, i);
			return pageStatus;
		}
		if (i+1 == system->nFrames)
			i = 0;printf("bi sai o dau?");
	}

	return NULL;
}

/**
 * swapOutVictimPage: simulate the activities of swapping out victim page
 * @system: system
 * @pageStatus: the victim page
 * 
 * @return: always 0
 **/
static int swapOutVictimPage(struct System *system, 
							 struct PageStatus *pageStatus, 
							 FILE *outFile)
{
	int frame = pageStatus->frame;
	printf("swapout frame %d\n", frame);
	fprintf(outFile,"SWAPOUT %d\n",pageStatus->frame);
	pageStatus->state = INVALID;
	system->frameStatus[frame].state = FREE;
	/* Do nothing, but it costs time. */
	sleep(1);
	return 0;
}

/** 
 * loadData2FreeFrame: Load data from disk to the free frame 
 * @system: system
 * @memAddr: logical address
 * freeFrame: the free frame
 * 
 * @return: always 0
 **/ 
static int loadData2FreeFrame(struct System* system, int memAddr, int freeFrame, struct Task *task, FILE *outFile)
{
	system->frameStatus[freeFrame].state = INUSE;
	system->frameStatus[freeFrame].lastAccessTime = 1;
	/* Do nothing, just cost some time */
	printf("Load data from disk to the free frame %d \n", freeFrame);
	sleep(1);
	fprintf(outFile,"LOADTO %d %d %d\n",freeFrame, task->pid, memAddr);
	return 0;
}

/** 
 * solvePageFault: routine of processing page fault.
 * This function is called when access to a page that is not existed in memory.
 * @system: system
 * @task: process causing page fault
 * @memAddr: logical memory (page fault when accessing this address)
 * @faultyPage: page of memAddr
 * 
 * @return: always 0
 **/
static int solvePageFault(struct System *system, struct Task *task,
						  int memAddr, struct PageStatus *faultyPage,
						  FILE *outFile)
{
	int freeFrame;
	struct PageStatus *victimPage = NULL;

	findPageOnDisk(memAddr);
	freeFrame = findFreeFrame(system);
	if (freeFrame == ERR_NO_FREE_FRAME) {
		printf("\n victim page");
		victimPage = chooseVictimFrame(system, task);
		printf("\n swap page");
		swapOutVictimPage(system, victimPage, outFile);
		printf("\n free page");
		freeFrame = victimPage->frame;
	}

	loadData2FreeFrame(system, memAddr, freeFrame, task, outFile);
	updatePage(faultyPage, freeFrame, task->pid, memAddr, outFile);
	return 0;
}

/**
 * getTask: Find a process based on pid
 * @system: system.
 * @pid: process ID.
 * 
 * @return: task or NULL
 **/
static struct Task* getTask(struct System *system, int pid)
{
	int i = 0;
	struct TaskList *taskList = &(system->taskList);
	struct Task *tmp = taskList->first;

	for (i = 0; i < taskList->nTasks; i++) {
		if (tmp->pid == pid) {
			return tmp;
		}
		tmp = tmp->next;
	}
	return NULL;
}

/**
 * createTask: Find or Create a PCB of process
 * @system: system.
 * @pid: process ID.
 * @memSize: size of memory a process needs.
 * 
 * @return: task
 **/
static struct Task* createTask(struct System *system, int pid, int memSize)
{
	struct TaskList *taskList = &(system->taskList);
	struct Task *tmp = getTask(system, pid);
	/* Because task cannot be found, it will be created */
	if (tmp == NULL) {
		tmp = malloc(sizeof(struct Task));
		initTask(tmp);
		tmp->pid = pid;
		tmp->memSize = memSize;
		addTask2List(taskList, tmp);
	}
	return tmp;
}

/**
 * convertMemSize2Pages: Bytes --> pages
 * @system: the system that describe the framesize
 * @memSize: size of memory that will be converted (unit: Byte)
 * 
 * @return: a number of pages
 **/
static int convertMemSize2Pages(struct System *system, int memSize)
{
	int frameSize = 1 << N_OFFSET_BITS;
	int pages = memSize / frameSize;
	int remain = memSize % frameSize;
	return (pages + (remain > 0));
}

/**
 * addFrame2PageTable: after loading data to frame, this frame will be used by 
 *                      the process (task)
 * @system: system
 * @task: task using this frame
 * @frame: frame after loading new data
 * 
 * @return: always 0
 **/ 
int addFrame2PageTable(struct System *system, struct Task* task, int frame, FILE *outFile)
{
	struct PageStatus *page = findUnusedPage(task);
	system->frameStatus[frame].state = INUSE;
	system->frameStatus[frame].lastAccessTime = 1;
	updatePage(page, frame, task->pid, task->memSize, outFile);
	return 0;
}

/**
 * allocFrame4Task: called when the program does "START pid mem".
 *                  This task asks for allocating a memory space
 * @system: system
 * @pid: process ID
 * @memSize: size of memory that process pid needs (unit: Byte).
 * @outFile: output file
 * 
 * @return: always 0
 * 
 * Note: In this function, a memory space is just allocated from free frames.
 * Please read the requirements carefully.
 **/
int allocFrames4Task(struct System *system, int pid, int memSize, FILE *outFile)
{
	struct Task *task;
	task = createTask(system, pid, memSize);
	int maxNPages = convertMemSize2Pages(system, task->memSize);
	int i = 0;
	int count = 0;
	/* find free frames and add them to task's page table */
	for (i = 0; (i < system->nFrames) && (count <= maxNPages); i++) {
		if (system->frameStatus[i].state == FREE) {
			addFrame2PageTable(system, task, i, outFile);
			fprintf(outFile,"ALLOC %d %d %d %d\n",pid, 0, count, i);
			count++;
		}
	}
	return 0;
}

/**
 * access2Mem: called when the process does "ACCESS pid memAddr".
 *             Process pid want to access a memory byte.
 * @system: system
 * @pid: process id
 * @memAddr: logical memory 
 * @outFile: output file
 * 
 * @return: frame 
 **/
static int releaseFrame(struct System *system, struct Task *task, FILE *outFile);

int access2Mem(struct System *system, int pid, int memAddr, 
			   FILE *outFile)
{
	struct Task *task = getTask(system, pid);
	if (task==NULL){
		fprintf(outFile,"SEGFAULT %d\n", pid);
		releaseFrame(system, task, outFile);
		return -1;
	}
	struct PageStatus *page = getFrameFromMem(task, memAddr);

	int frame = page->frame;
	fprintf(outFile,"ACCESS %d\n",system->frameStatus[frame]);

	if (page->state == INVALID) {

		int section;
		int p;
		section = (memAddr >> N_OFFSET_BITS);
		p = section & ((1 << N_PAGE_BITS) - 1); // get page number
		section = (section >> N_PAGE_BITS); // get section number

		fprintf(outFile,"INVALID %d %d %d\n",pid, section, p);

		solvePageFault(system, task, memAddr, page, outFile);
		printf("Finished solve Page Fault...\n");
	}
	printf("access frame: %d\n",frame);
	system->frameStatus[frame].lastAccessTime = 1;

	return (frame);
}

/**
 * releaseFrame: when finishing, all frames of process are returned to system
 * @system: system
 * @task: process
 * 
 * @return: always 0
 **/
static int releaseFrame(struct System *system, struct Task *task, FILE *outFile)
{
	int i = 0;
	int j = 0;
	int frame = 0;
	struct PageStatus *page;

	for (i = 0; i < (1 << N_SECTION_BITS); i++) {
		for (j = 0; j < (1 << N_PAGE_BITS); j++) {
			page = getFrameFromPage(task, i, j);
			if (page->state == VALID) {
				frame = page->frame;
				fprintf(outFile,"FREE  %d\n", frame);
				system->frameStatus[frame].state = FREE;
				page->state = INVALID;
			}
		}
	}
	return 0;
}

/**
 * finishTask: called when the program does "FINISH pid 0"
 * @system: system
 * @pid: process id
 * @outFile: output file
 * 
 * @return: always 0
 **/
int finishTask(struct System *system, int pid, FILE *outFile)
{
	struct Task *task = getTask(system, pid);
	/* Release resources to system */
	releaseFrame(system, task, outFile);
	removeTask(&(system->taskList), task);
	return 0;
}