Do in JAVA You are to write a program to simulate the arrivals, placements, and
ID: 3794249 • Letter: D
Question
Do in JAVA
You are to write a program to simulate the arrivals, placements, and departures of segments in a segmented virtual memory. The input file will contain a sequence of commands. Your program will obey these commands in the sequence given and print the results specified below A placement request comprises its size and length of stay in memory. The program either finds room for the segment, or it fails to do so. In the latter case, the program loops, incrementing the time variable, and removing segments that have exhausted their lifetimes until there is room in memory for the placement to take place. Here is the pseudocode of the placement process int place (Request r, int atThisTime) C int time-atThisTime + 1; // always increment time before // each initial placement attempt removeSegmentsDueToDepart (time); while(!placed(r.getSize),r.getLifetime)+time)) [ // time to depart - lifetime+time time++ removeSegmentsDueToDepart (time); return time; // at which the placement finally took place The memory should be simulated by a linked list of Node objects: class Node private: int size; int timeToDepart; boolean occupied; Node next; // true if it is a segment, false if it is a hole public: Node(int segmentSize, int timeToLeave, boolean type); // constructor Initially the linked list will contain a single Node with occupied set to false and size equal to memorySize. As the simulation progresses, the linked list will represent a memory with multiple s total sizes always equals memorySize. Design and implement you own single-linked list class for holding Node objects DO NOT: use ANY Java Collection Class Objects, such as ArrayList, LinkedList, Vector and all others. DO NOT use an array (except for String split for input). If in doubt, ASK! egments and holes whose 1. Simulate the First Fit placement policy, where the program scans the unoccupied spaces (holes) in memory, beginning with the one with the lowest address, progressing through the holes in address order, and stopping when it finds the first hole big enough, or when it reaches the end of memory without finding any hole big enough 2. Simulate Best Fit, where the program chooses the hole of the smallest size that is large enough to accommodate the request, or it fails to find any hole big enough.Explanation / Answer
import java.util.*;
import java.io.*;
class Node {
boolean segment; // Equals false if this Node represents a hole
int location; // Position in memory of first byte
int size; // Size that node occupies
int timeToDepart; // Only valid when this Node represents a segment
Node next;
Node (int locn, int sz, int endOfLife, Node nxt) {
segment = true;
location = locn;
size = sz;
timeToDepart = endOfLife;
next = nxt;
}
Node (int locn, int sz, Node nxt) {
segment = false;
location = locn;
size = sz;
next = nxt;
}
} // End Node class
class Memory {
private static int memorySize; // Defines the total size for the memory
Node head; // Refers to first node in memory
Node lastPlacement; // Refers to the last node that was placed, or hole if the last placed segment is removed
Memory (int size) {
memorySize = size;
Node n = new Node (0, memorySize, null);
lastPlacement = head = n;
}
boolean place (int size, int timeOfDay, int lifeTime, boolean verbose) {
if (isEmpty()) {
Node current = new Node (0, size, 0, null);
lastPlacement = head = current;
return true;
}
else {
Node current = lastPlacement; //We start searching for a hole at our lastPlacement
while (current != null) {
// If we are looking at a hole
if (!current.segment && current.timeToDepart <= timeOfDay) {
if (current.size >= size) {
Node n = new Node (current.location, size, timeOfDay + lifeTime, current.next);
current.next = n;
current.size = current.size - size; // Adjust size of hole after placing segment
lastPlacement = current = n;
// If verbose == true, print the confirmation
if (verbose) {
System.out.println ("Segment at location: " + lastPlacement.location + " with size: " + lastPlacement.size + " departs at: " + lastPlacement.timeToDepart);
}
return true;
}
}
current = current.next;
} // End while
current = this.head; // To traverse from start of list
while (current != lastPlacement) {
if (!current.segment && current.timeToDepart <= timeOfDay) {
if (current.size >= size) {
Node n = new Node (current.location + size, size, timeOfDay + lifeTime, current.next);
current.next = n;
current.size = current.size - size;
lastPlacement = current = n;
if (verbose) {
System.out.println ("Segment at location: " + lastPlacement.location + " with size: " + lastPlacement.size + " departs at: " + lastPlacement.timeToDepart);
}
return true;
}
}
current = current.next;
} // End while
}
// If we reach this point, segment could not be placed
return false;
}
void removeSegmentsDueToDepart (int timeOfDay) {
if ((head.segment == true) && (head.timeToDepart <= timeOfDay)) {
head.segment = false; // Allow node to become a hole
}
Node previous = head;
while (previous.next != null) {
Node current = previous.next;
if ((current.segment == true) && (current.timeToDepart <= timeOfDay)) {
current.segment = false;
//System.out.println ("Case 2.");
}
if ((previous.segment == false) && (current.segment == false)) {
if (current == lastPlacement) {
lastPlacement = previous;
//System.out.println ("Case 4.");
}
previous.size += current.size;
previous.next = current.next;
}
else {
previous = current;
}
} // End while
}
void printLayout() {
Node current = head;
int numNodes = 0; // Number of nodes in the array
while (current != null) {
numNodes++;
current = current.next;
}
Node [] nodeArray = new Node [numNodes];
int y = 0; // Used as increment in while-loop
current = head;
while (current != null) {
nodeArray[y] = current;
y++;
current = current.next;
}// End while
nodeArray = sort (nodeArray, numNodes);
for (int i = 0; i < numNodes; i++) {
System.out.println (nodeArray[i].location + " " + nodeArray[i].size + " " + nodeArray[i].timeToDepart);
}
}
Node [] sort (Node [] node, int length)
{
Node tempNode;
for (int i = 0; i < ( length - 1 ); i++) {
for (int j = 0; j < length - i - 1; j++) {
// Sort the array by location in ascending order
if (node[j].location > node[j + 1].location)
{
tempNode = node[j];
node[j] = node[j + 1];
node[j + 1] = tempNode;
}
}
}
return node;
}
public boolean isEmpty () {
if (head == null) {
return true;
}
return false;
}
} // End Memory class
public class EVBEP1 {
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner(new File("p115sd5.txt")); //Place file name here for different tests
String line = "";
boolean done = false;
Memory memory = new Memory(0); // Memory object
int timeOfDay = 0; // Simulated wall clock, begins with value zero
int placements = 0; // Number of placements completed, begins with value zero
long totalSpaceTime = 0; // Sum of placed segmentSize(i) x segmentLifetime(i)
float meanOccupancy = 0;
while (!done) {
line = sc.nextLine(); // Store data gathered from file into String
String [] tokens = line.split(" "); // Split the string using space as delimiter
switch (tokens[0]) {
case "N": {
System.out.println("Evan Clay Bechtol");
break;
}
case "C": {
memory = new Memory(Integer.parseInt(tokens[1])); // Create a new Memory object
break;
}
case "E": {
System.out.println();
done = true; // Break the loop, end the program
break;
}
case "A": {
int size = Integer.parseInt(tokens[1]);
int lifeTime = Integer.parseInt(tokens[2]);
timeOfDay++;
memory.removeSegmentsDueToDepart(timeOfDay);
while (!memory.place(size, timeOfDay, lifeTime, true)) {
timeOfDay++;
memory.removeSegmentsDueToDepart(timeOfDay);
} // End while
placements++;
System.out.printf("Segment of size %4d", size);
System.out.printf(" placed at time %4d", timeOfDay);
System.out.printf(" at location %4d", memory.lastPlacement.location);
System.out.printf(" departs at %4d", memory.lastPlacement.timeToDepart);
break;
}
case "P": {
System.out.println ();
memory.printLayout();
//System.out.println ("End at time: " + timeOfDay);
break;
}
case "R": {
int size = Integer.parseInt(tokens[1]); // Size
memory = new Memory(size);
int minSegSize = Integer.parseInt(tokens[2]); // Minimum seg. size
int maxSegSize = Integer.parseInt(tokens[3]); // Maximum seg. size
int maxLifeTime = Integer.parseInt(tokens[4]); // Maximum lifetime of segs.
int numSegs = Integer.parseInt(tokens[5]); // Number of segs. to simulate
timeOfDay = 0;
placements = 0;
Random ran = new Random (); // "Random" number generator
while (placements < numSegs) {
timeOfDay++;
memory.removeSegmentsDueToDepart(timeOfDay);
int newSegSize = minSegSize + ran.nextInt(maxSegSize - minSegSize + 1);
int newSegLifetime = 1 + ran.nextInt(maxLifeTime);
totalSpaceTime += newSegSize * newSegLifetime;
while (!memory.place(newSegSize, timeOfDay, newSegLifetime, false)) {
timeOfDay++;
memory.removeSegmentsDueToDepart(timeOfDay);
} // End while
placements++;
} // End while
// Print final summary of execution
meanOccupancy = totalSpaceTime / (timeOfDay);
System.out.printf ("Number of placements made = %6d ", placements);
System.out.printf ("Mean occupancy of memory = %8.2f ", meanOccupancy);
}
} // End switch
} // End while
sc.close();
} // End main
} // End EVBEP1 class
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.