You are to write a program to simulate the arrivals placemen

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) int time at ThisTime 1 alvays increment time before each initial placement attempts removesegmentsDueToDepart (tine); while (!placed (r.getsize() ,r.getLifetine time)) tine to depart lifetime time time remove segmentsDueToDepart(tine) return t 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 time ToDepart; boolean occupied; true if it is a segment, false if it is a hole Node next public Node (int segmentsize, int tineToLeave, 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 segments and holes whose 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! 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 aa

Solution

import java.util.*;

import java.io.*;

class Node {

    boolean segment;     

    int     location;      

    int     size;          

    int     timeToDepart;  

    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;

    }

}

class Memory {

    private static int memorySize;     Node head;                     

    Node lastPlacement;            

    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 (!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;

                        lastPlacement = current = n;

                        if (verbose) {

                            System.out.println (\"Segment at location: \" + lastPlacement.location + \"\\twith size: \" + lastPlacement.size + \"\\tdeparts at: \" + lastPlacement.timeToDepart);

                        }

                        return true;

                    }

                }

                current = current.next;

            }

            current = this.head;

            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 + \"\\twith size: \" + lastPlacement.size + \"\\tdeparts at: \" + lastPlacement.timeToDepart);

                        }

                        return true;

                    }

                }

                current = current.next;

            }

        }

        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;

            }

            if ((previous.segment == false) && (current.segment == false)) {

                if (current == lastPlacement) {

                    lastPlacement = previous;

                }

                previous.size += current.size;

                previous.next = current.next;

            }

            else {

                previous = current;

            }

        }

    }

    void printLayout() {

        Node current = head;

        int numNodes = 0;

        while (current != null) {

            numNodes++;

            current = current.next;

        }

        Node [] nodeArray = new Node [numNodes];

        int y = 0;

        current = head;

        while (current != null) {

            nodeArray[y] = current;

            y++;

            current = current.next;

        }

        nodeArray = sort (nodeArray, numNodes);

        for (int i = 0; i < numNodes; i++) {

            System.out.println (nodeArray[i].location + \"\\t\" + nodeArray[i].size + \"\\t\" + 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++) {

              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;

    }

}

public class EVBEP1 {

    public static void main(String[] args) throws FileNotFoundException {

        Scanner sc = new Scanner(new File(\"p115sd5.txt\"));

        String line = \"\";

        boolean done = false;

        Memory memory = new Memory(0);

        int timeOfDay = 0;     

        int placements = 0;    

        long totalSpaceTime = 0;

        float meanOccupancy = 0;

        while (!done) {

            line = sc.nextLine();  

            String [] tokens = line.split(\" \");

            switch (tokens[0]) {

            case \"N\": {

                    System.out.println(\"Evan Clay Bechtol\");

                    break;

                }

            case \"C\": {

                    memory = new Memory(Integer.parseInt(tokens[1]));

                    break;

                }

            case \"E\": {

                    System.out.println();

                    done = true;   

                    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);

                        }

                    placements++;

                    System.out.printf(\"Segment of size\\t%4d\", size);

                    System.out.printf(\" placed at time\\t%4d\", timeOfDay);

                    System.out.printf(\" at location\\t%4d\", memory.lastPlacement.location);

                    System.out.printf(\" departs at\\t%4d\", memory.lastPlacement.timeToDepart);

                    break;

                }

            case \"P\": {

                    System.out.println ();

                    memory.printLayout();

                    break;

                }

            case \"R\": {

                    int size = Integer.parseInt(tokens[1]);

                    memory = new Memory(size);

                    int minSegSize = Integer.parseInt(tokens[2]);  

                    int maxSegSize = Integer.parseInt(tokens[3]);  

                    int maxLifeTime = Integer.parseInt(tokens[4]);

                    int numSegs = Integer.parseInt(tokens[5]);     

                    timeOfDay = 0;

                    placements = 0;

                    Random ran = new Random ();

                    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);

                        }

                        placements++;

                    }

                    meanOccupancy = totalSpaceTime / (timeOfDay);

                    System.out.printf (\"Number of placements made = %6d\ \", placements);

                    System.out.printf (\"Mean occupancy of memory = %8.2f\ \", meanOccupancy);

                }

            }

        }

        sc.close();

    }

}