***********************************************************************************************
/**
* Factory class to start five threads.
*
*/
public class Factory
{
public static void main(String args[]) {
//get user input of memory size and frame size, calculate the number of frames
in memory
//construct physical memory and pass the number of frames as a parameter
PhysicalMemory physicalMemory = new PhysicalMemory();
Thread[] threadArray = new Thread[5];
for(int i=0; i
threadArray[i] = new Thread(new MemoryThread(physicalMemory, i));
for(int i=0; i
threadArray[i].start();
}
}
*****************************************************************************************************************
/**
* This is the thread to simulate the request, access and release of memory space
*/
import java.util.Random;
public class MemoryThread implements Runnable
{
public MemoryThread(PhysicalMemory m, int id) {
physicalMemory = m;
threadID = id;
}
public void run()
{
//Generate a memory request of a random size
Random generator = new Random();
int requestSize = 1 + generator.nextInt(MAX_REQUEST_SIZE);
//Debuging message
//System.out.println("Thread " + threadID + " has been started");
//request memory space
boolean flag = physicalMemory.requestMemory(threadID, requestSize);
//Debuging message
//System.out.println("Thread " + threadID + " has been allocate memory space
" + flag);
while (!flag)
{
flag = physicalMemory.requestMemory(threadID, requestSize);
}
//Generate a random memory access
int requestPageNumber = generator.nextInt(requestSize);
int frameNumber = physicalMemory.accessMemory(threadID, requestPageNumber);
System.out.printf("Thread %d requests for page number %d which has frame
number %d ", threadID, requestPageNumber, frameNumber);
// Release the memory
physicalMemory.releaseMemory(threadID);
}
private PhysicalMemory physicalMemory;
private int threadID;
public static final int MAX_REQUEST_SIZE = 50;
}
***************************************************************************************************************
/*
This class implements a page table associated with a thread
*/
import java.util.Arrays;
public class PageTable
{
/* id of the thread a page table is associated with */
private int tid;
/* size of the page table */
private int size;
/* frame number array. page number is used to index the array to find the
corresponding frame number */
private int[] pageTableArray;
/* length of the page table */
private int length;
public PageTable(int id, int s)
{
tid = id;
size = s;
length = 0;
pageTableArray = new int[s];
}
/* return the frame number of the page number (index) */
public int lookupPageTable(int index)
{
return pageTableArray[index];
}
/* add an entry to the end of the page table */
public void appendEntry(int frameNumber)
{
pageTableArray[length] = frameNumber;
length++;
}
/* return length of the page table */
public int getLength()
{
return length;
}
/* return thread ID */
public int getThreadID()
{
return tid;
}
/* print the content of the page table */
public void printPageTable()
{
for(int i=0; i {
System.out.println("Thread " + tid + " Page " + i + " has frame
number " + pageTableArray[i]);
}
}
}
****************************************************************************************************
/* This class implements a linked list which contains all the page tables in the
system */
public class PageTableList
{
public PageTableList()
{
first = null;
}
/* add a new entry to the head of the linked list */
public void addFirst(PageTable pt)
{
Node newNode = new Node();
newNode.pt = pt;
newNode.next = first;
first = newNode;
}
/* return the page table associated with the thread id */
public PageTable lookup(int id)
{
Node t = first;
while(t != null)
{
if(t.pt.getThreadID() == id)
return t.pt;
t = t.next;
}
return null;
}
/* head of the linked list */
private Node first;
private class Node
{
public PageTable pt;
public Node next;
}
}
Project Description: The goal of this project is to simulate the paging scheme in memory management and get familiar with semaphore/synchronized method. The tester code has been provided in Factory.java and MemoryThread.java. As you can see, 5 threads are created. Each thread requests for a certain number of pages (simulates the load of new process into memory), then accesses a certain page (simulates the memory reference of logical address), then releases the memory request (simulate the termination of a process). You are asked to implement the PhysicalMemory class with the following public interfaces: /* constructor */ public PhysicalMemory(int numofFrames) /* If the memory has enough free frames to serve the memory request from a thread, allocate the free frames to the thread, build the thread's page table, and update free frames state @param id the threadID of the requesting thread @param requestLength the number of pages the thread requests @return If the request can be served (which means the free frames in memory is greater or equal to the requestLength), return true else return false * public boolean requestMemory(int id, int requestLength) /* Convert logical page number to physical frame number. @param id the threadID of the requesting thread @param pageNumber the page number the thread wants to access @return the frameNumber (physical address of the pageNumber (logical address) */ public int access Memory(int id, int pageNumber) /* Set the frames allocated to the calling thread to free @param id the threadID of the calling thread * public void release Memory(int id) You need to think carefully about the data structure for tracking the allocated and free frames in the physical memory, and the data structure for the page table of each thread. You can choose any data structures (for example, array, array list, linked list, etc) you feel necessary and comfortable with. Here is some suggestion: - Use a boolean array to track the memory allocation status. Each frame in the physical memory has a corresponding entry in the boolean array. The entry value false indicates the frame is free. The item value true indicates the frame is occupied (allocated to a thread). If you want more practice, think how to use a list to keep track of all available frames as mentioned in the book. - For page table, use a linked list of page tables of all the thread. Each object in the linked list is a page table for a thread. I have attached the implementation of page tables PageTableList.java and Page Table.java. You can add any new methods you might need for your design. You can also use other data structure such as hashtable to save page tables if you want more practice of programming. Note: 1) You need to modify the tester code to get memory size and frame size from user input. The number of frames is equal to memory size / frame size. 2) In the tester code, I have put the code to print out the page number and frame number for a certain memory access. How do you know whether this mapping is correct or not? Call the method printPageTable in Page Table class to print out the page table for the calling thread, thus you can check whether the mapping is correct or not. 3) This project will take some time to implement and debug. I recommend you start as soon as possible. Think and plan carefully. Know what to do before you start coding. Figure out all the instance fields and the details of each method in the PhysicalMemory class. Since there are multiple threads, if you don't know what are you are doing, you will spend more time on debugging than implementing the correct logic. 4) Since there are multiple threads trying to check and set the memory allocation status at the same time, you need to have a binary semaphore or use synchronized method to protect the checking and setting of memory allocation status. Think carefully which pieces of code need to be protected by the semaphore or synchronized method. Your program will hang if you don't use the semaphore or synchronized method correctly 5) To debug your code, consider adding debugging messages (use System.out.println) in your code Extra Credit (20 points): When a process requests more space than what is available in the memory, block the process instead of returning false and let it keep requesting. This is a synchronization problem. Project Description: The goal of this project is to simulate the paging scheme in memory management and get familiar with semaphore/synchronized method. The tester code has been provided in Factory.java and MemoryThread.java. As you can see, 5 threads are created. Each thread requests for a certain number of pages (simulates the load of new process into memory), then accesses a certain page (simulates the memory reference of logical address), then releases the memory request (simulate the termination of a process). You are asked to implement the PhysicalMemory class with the following public interfaces: /* constructor */ public PhysicalMemory(int numofFrames) /* If the memory has enough free frames to serve the memory request from a thread, allocate the free frames to the thread, build the thread's page table, and update free frames state @param id the threadID of the requesting thread @param requestLength the number of pages the thread requests @return If the request can be served (which means the free frames in memory is greater or equal to the requestLength), return true else return false * public boolean requestMemory(int id, int requestLength) /* Convert logical page number to physical frame number. @param id the threadID of the requesting thread @param pageNumber the page number the thread wants to access @return the frameNumber (physical address of the pageNumber (logical address) */ public int access Memory(int id, int pageNumber) /* Set the frames allocated to the calling thread to free @param id the threadID of the calling thread * public void release Memory(int id) You need to think carefully about the data structure for tracking the allocated and free frames in the physical memory, and the data structure for the page table of each thread. You can choose any data structures (for example, array, array list, linked list, etc) you feel necessary and comfortable with. Here is some suggestion: - Use a boolean array to track the memory allocation status. Each frame in the physical memory has a corresponding entry in the boolean array. The entry value false indicates the frame is free. The item value true indicates the frame is occupied (allocated to a thread). If you want more practice, think how to use a list to keep track of all available frames as mentioned in the book. - For page table, use a linked list of page tables of all the thread. Each object in the linked list is a page table for a thread. I have attached the implementation of page tables PageTableList.java and Page Table.java. You can add any new methods you might need for your design. You can also use other data structure such as hashtable to save page tables if you want more practice of programming. Note: 1) You need to modify the tester code to get memory size and frame size from user input. The number of frames is equal to memory size / frame size. 2) In the tester code, I have put the code to print out the page number and frame number for a certain memory access. How do you know whether this mapping is correct or not? Call the method printPageTable in Page Table class to print out the page table for the calling thread, thus you can check whether the mapping is correct or not. 3) This project will take some time to implement and debug. I recommend you start as soon as possible. Think and plan carefully. Know what to do before you start coding. Figure out all the instance fields and the details of each method in the PhysicalMemory class. Since there are multiple threads, if you don't know what are you are doing, you will spend more time on debugging than implementing the correct logic. 4) Since there are multiple threads trying to check and set the memory allocation status at the same time, you need to have a binary semaphore or use synchronized method to protect the checking and setting of memory allocation status. Think carefully which pieces of code need to be protected by the semaphore or synchronized method. Your program will hang if you don't use the semaphore or synchronized method correctly 5) To debug your code, consider adding debugging messages (use System.out.println) in your code Extra Credit (20 points): When a process requests more space than what is available in the memory, block the process instead of returning false and let it keep requesting. This is a synchronization
