COMP2240: Operating Systems Project: Simulating Memory Management

This project involves simulating an operating system with limited memory, focusing on paging and virtual memory management. The system utilizes a fixed allocation scheme with 30 frames, and each process can have a maximum of 50 pages. The simulation employs demand paging, where pages are only brought into main memory when requested, and incorporates the Least Recently Used (LRU) and Clock page replacement policies. The project also uses a Round Robin scheduling algorithm with a time quantum of 3. The code includes functions for memory allocation, paging implementation, and virtual to physical address mapping. The assignment requires the use of Ubuntu 16.04.03 LTS and the GNU C/C++ Compiler to compile and run the simulation, which handles page faults, process scheduling, and I/O requests. The simulation is designed to demonstrate the core concepts of operating system memory management, including paging, virtual memory, and scheduling algorithms, using a simplified environment.

OPERATING SYSTEM

COMP2240 - Operating Systems
Project Requirements:
The operating system used in this assignment is designed with a limited amount of
memory and the program is written to simulate the system that uses paging with virtual memory.
Memory: The system has 30 frames available in main memory. During execution, the
processor will determine if the page required for the currently running process is in main
memory.
 If the page is in main memory, the processor will access the instruction and
continue.
 If the page is not in main memory, the processor will issue a page fault and block
the process until the page has been transferred to main memory.
 Initially no page is in the memory. I.e. the simulation will be strictly demand
paging, where pages are only brought into main memory when they are requested.
 In fixed allocation scheme frames are equally divided among processes, additional
frames remain unused.
Paging and virtual memory: The system uses paging (with no segmentation).
 Each process can have a maximum 50 pages where each page contains a single
instruction.
 For page replacement you will need to apply least recently used (LRU) and clock
policy.
 Resident set is managed using ‘Fixed Allocation with Local Replacement Scope’
strategy. I.e. you can assume, frames allocated to a process do not change over the
simulation period and page replacements (if necessary) will occur within the
allocated frames.
 All pages are read-only, so no page needs to be written back to disk.
Page fault handling: When a page fault occurs, the interrupt routine will handle the fault by
placing an I/O request into a queue, which will later be processed by the I/O controller to bring
the page into main memory. This may require replacing a page in main memory using a page
replacement policy (LRU or clock). Other processes should be scheduled to run while such an
I/O operation is occurring.

 Issuing a page fault and blocking a process takes no time. If a page fault occurs
then another ready process can run immediately at the same time unit.
 Swapping in a page takes 6 units of time (if a page required by a process is not in
main memory, the process must be put into its blocked state until the required
page is available).
Scheduling: The system is to use a Round Robin short-term scheduling algorithm with time a
quantum of 3.
 Executing a single instruction (i.e. a page) takes 1 unit of time.
 Switching the processes does not take any time.
 If multiple processes becomes ready at the same time then they enter the ready
queue in the order of their ID.
 All the processes start execution at time t=0.
 If a process becomes ready at time unit t then execution of that process can occur
in the same time unit t without any delay.
Software requirements:
Download and Install ubuntu 16.04.03 LTS from the below link:
https://www.ubuntu.com/download/desktop/
To install GNU C/C++ Compiler
Open the terminal and enter the following commands:
$ sudo apt-get update

$ sudo apt-get install build-essential manpages-dev

To verify whether it is installed or not, enter the following commands into the terminal:
$ whereis gcc

$ which gcc
$ gcc –version

How to run the project?
1. Download the project and extract the zip file.
2. Open the terminal and move to the directory where the extracted file is saved.
$ cd <Filepath>

3. Compile the files as follows:
$ gcc algorithms.c getDataFromFile.c main.c memoryListFunctions.c myheader.h

4. The project can be run as follows:
$ ./a.out -i <input_file_name> -t <type_of_algorithm>
where,
File name can be “process1, process 2, process 3 and process 4” and
Type of algorithm can be “ALLMEMORY, FCFS PAGING and SEGMENTATION”

eg:
./a.out -i "files/process_3.txt" -t "PAGING"
Source code explanation:
This program shows how memory management can be implemented by the kernel, the
memory addresses used in this programs are virtual addresses not physical addresses.
The structure of the linked list is implemented in code as follows.
typedef struct __s_block{
struct __s_block *next;
bool isfree;
size_t size;
void *memoryAddress;
}_SBLOCK;
#define BLOCK_SIZE sizeof(_SBLOCK)
next : Pointer that points to a next memory block.
isfree : To check whether memory block is free or not.
size : Size which is allocated in the memory.
memoryAddress : Starting memory address from where the memory is allocated.
BLOCK_SIZE : Size of the structure.
Function to allocate Memory is as follows:
_SBLOCK *allocateMemBlock(size_t size)
{
_SBLOCK *block = (_SBLOCK*)sbrk(0);
void *memadr = (void*)sbrk(0);
void *allocate_mem = (void*)sbrk(BLOCK_SIZE + size);
if(allocate_mem == (void*)-1){
return NULL;

}else{
block->next = NULL;
block->isfree = false;
block->size = size;
block->memoryAddress = memadr+BLOCK_SIZE;
return block;
}
}
Code Description:
The function to allocate memory is designed in such a way that it takes the size to be allocated as
argument.
_SBLOCK *block = (_SBLOCK*)sbrk(0);
First store sbrk(0) means store break point memory address to block so that we can starts our
memory allocation from break point.
void *memadr = (void*)sbrk(0);
Store memory address to memadr.
void *allocate_mem = (void*)sbrk(BLOCK_SIZE + size);
Change the location of program break by calling sbrk() call with increment of our metadata
block size and how much memory needs to allocate.Check allocate_mem is equal to (void*)-1
means error in increasing then return NULL.
If not then store approriate data into structure variables and return an allocated block.
Paging:
Paging technique is used in memory management for dividing each process into equal size of
pages. After dividing the process memory will be allocated for their processing.

Paging becomes more efficient with virtual memory. Virtual memory is the memory whose little
bit part is of the physical memory address.it is infinite and uses mapping to calculate actual
physical memory address.
The code below in our program implements paging.
#define MAX_MEM_SIZE (1024*1024)
#define PAGE_SIZE 4096
#define MAX_PAGES 256
#define PAGE_MEM_SIZE 0x256
//structure for store virtual memory data using paging
typedef struct __memvirtpageblocks{
struct __memvirtpageblocks *next;
size_t size;
int process;
int pagenumber;
void *memoryaddress;
}_VIRTMEMPAGEBLOCKS;
//structure for allocate memory using paging

typedef struct __mempageblocks{
struct __mempageblocks *next;
bool isfree;
void *memoryaddress;
}_MEMPAGEBLOCKS;
#define MEM_PAGE_BLOCK_SIZE sizeof(_MEMPAGEBLOCKS)
Code description:
MAX_MEM_SIZE : Which is our maximum whole memory(main memory) size which is
1MB.
MAX_PAGES : Maximum number of pages.
PAGE_MEM_SIZE : Size of each page.
I used three functions to implement paging
void divideProc_Mem_IntoPageBlocks(_PROCINTNODE *procinthead,
_VIRTMEMPAGEBLOCKS
**virtmempageblockshead,
_MEMPAGEBLOCKS **mempageblocksHead)
void mapVirtPhyAddressPageTable(_VIRTMEMPAGEBLOCKS **virtmempageblockshead,
_MEMPAGEBLOCKS **mempageblocksHead)
void AllocatePAGING(_SBLOCK *s_blockHead, _VIRTMEMPAGEBLOCKS
*virtmempageBlocks,
_MEMPAGEBLOCKS *mempageBlocks, const char *inputFile)
The first function divides our process & memory into equal size of page blocks and
forming a linked list of them(_VIRTMEMPAGEBLOCKS & _MEMPAGEBLOCKS).
The second function maps a virtual to physical address, as you know we dont know
actual physical address,so we will just print the address provided by sbrk() sys call.

Note: Screenshot of the output will be added to this documentation after reviewing the project
by the client.
References
Operating System Memory Management. (2017). Operating System Memory Management.
[online] Available at:
https://www.tutorialspoint.com/operating_system/os_memory_management.htm [Accessed
22 Nov. 2017].
Operating System Scheduling algorithms. (2017). Operating System Scheduling algorithms.
[online] Available at:
https://www.tutorialspoint.com/operating_system/os_process_scheduling_algorithms.htm
[Accessed 22 Nov. 2017].
Steps taken by operating system to handle a page fault. (2017). Steps taken by operating system
to handle a page fault - More Process. [online] Available at:
http://www.moreprocess.com/operating-systems/steps-taken-by-operating-system-to-
handle-a-page-fault [Accessed 22 Nov. 2017].
Virtual Memory in OS. (2017). Virtual Memory in OS | Operating System Tutorial |
Studytonight. [online] Available at: http://www.studytonight.com/operating-system/virtual-
memory [Accessed 22 Nov. 2017].