things

assignment.groovy

/**
@author Benjamin Silas Rhodes

Groovy is a dynamic language for the jvm
@see: http://groovy.codehaus.org/ for compiler.

Assignment IV

Based on the assignment hand out this is a basic allocation
system that fits jobs based upon a first fit scheme.  If a 
process can not be fit it skips it and moves on.  

*/

class Job
{
	int id
	int size
	boolean allocated = false
	
	String toString() {
		"Job ${id} (${size})"
	}
}

class Memory 
{
	int address
	int size
	Job job
	
	boolean isFree() {
		job == null
	}
	
	String toString() {
		if(job)
			address + "@[${job}]"
		else
			address + "@[   free   ]"
	}
	
	boolean fits(Job j) {
		j.size <= size
	}
}


def jobs = [
	new Job(id: 1, size: 30),
	new Job(id: 2, size: 50),
	new Job(id: 3, size: 30),
	new Job(id: 4, size: 25)
]

def memory = [
	new Memory(address: 200, size: 100),
	new Memory(address: 300, size: 25),
	new Memory(address: 325, size: 25),
	new Memory(address: 350, size: 50)
]


println "Mem before allocation"
for(m in memory)
	println m
	
println "Starting allocations..."

for(j in jobs)
{
	//find a memory slot for j
	for(m in memory)
	{
		//if memory is free and it fits assign it
		if(m.isFree() && m.fits(j)) {
			println "${j} is being allocated to ${m}"
			m.job = j
			j.allocated = true
			break
		}
	}
	
	if( ! j.allocated )
		println "${j} could not be allocated, moving to next."
}

println "Mem after allocation"
for(m in memory)
	println m

batch.groovy

/**
 *@author Benjamin Silas Rhodes

Groovy is a dynamic language for the jvm
@see: http://groovy.codehaus.org/ for compiler.  

Homework Question 12

c.
  This program can work in two ways:  

  The system allocates all jobs that can fit by the order in which
  the system received the jobs (an ordered list).  If the system can not
  fit the job it is skipped and the next job is checked.

  The system allocates all jobs that can fit, if it can not fit anymore 
  jobs it will coninute on with the next cycle. 

  The second way is how the book wants it so the system will wait until 
  it can allocate the job waiting. 

d.  
  The job class handles the current amount of time it has been executed.
  Each cycle it is simpley checked to see if it has ran it's course and is
  finished or the clock is advanced.  

e.  
  An event is simply the next loop in a for loop.  Everything is chcked
  against the clock to see if if should be removed from memory. 

f.  
  The best fit allocation scheme has the better performance in this example
  but this could not hold true for all instances.  There can always be a worst case
  set of inputs that would cause the best fit system to take signicantly longer than
  first fit.   

*/

/** data **/
class Job
{
	int id
	int time
	int size
	int currentExecutionTime = -1
	boolean finished = false
	
	def stats = [ timeWating : 0, timeExecuted: 0]
	
	String toString() {
		id + "@[" + time  + ":" + size + ":" + finished + "]"
	}
	
	boolean isFinished() {
		currentExecutionTime >= time || finished
	}
	
	boolean isAllocated() {
		currentExecutionTime >= 0
	}
	
}

class Memory implements Comparable
{
	int id
	int size
	Job job
	
	def stats = [ used:0 ]
	
	String toString() {
		id + "@[" + size + ":" + job + "]"
	}
	
	boolean isFree() {
		job == null
	}
	
	int compareTo(def m) {
		this.size <=> m?.size
	}
}	

def runBatch(jobs, memory)
{
	def clock = 0
	
	boolean run = true
	while(run)
	{
		println "current time: " + clock
	
		println "Deallocating..."
		deallocateFinishedJobs(memory)
		printMemory(memory)
	
	
		println "Allocating..."
		for(job in jobs )
		{
			if( !job.isFinished() && !job.isAllocated() )
			{
				boolean allocated = allocateJob(job, memory)
	
				//comment out to run continues allocation
				if( !allocated ) {
					break;
				}
			}
		}
		printMemory(memory)
	
		def more = false
		
		for( job in jobs )
		{
			if( !job.isFinished() && job.id > 14)	{
				more = true
			}
		}
	
		run = more
		clock++
	}	
	
	clock
}



def allocateJob(Job j, def memory) 
{
	boolean allocated = false
	
	int size = j.size
	
	//loop through memory slots
	for(int i = 0; i < memory.size(); i++)
	{
		if( j.isAllocated() ) break//break if j has a home...
		
		def firstFree = memory[i]
		
		if( ! firstFree.isFree() ) continue//if not free check next slot
		
		// can we fit our job?
		
		if( size <= firstFree.size ) {
			allocate(j, firstFree);
			allocated = true
			break//we be done with this job
		}
		
		//ok we can't fit it in one slot... let's chceck the addjecnt slots
		for(int k = i + 1; k < memory.size(); k++) 
		{
			def nextSlot = memory[k];
			
			if( !nextSlot.isFree() ) {
				break//can't use i as a starting point
			}
			
			def memorySlots = (i..k).collect{ memory[it] }//create of a list of slots i through k
			def totalSize  = memorySlots.collect{ it.size }.sum()//sum of the size
			
			if( size <= totalSize ) {
				allocate(j, memorySlots)
				allocated = true
				break
			}
			
		}
		
		if( allocated ) break
		
		
	}
	
	allocated	
}

def allocate(Job j, Memory m) {
	allocate(j, [m])
}

def allocate(Job j, List memorySlots) {
	println "Allocated: " + j.id  + " to " + memorySlots.collect{ it. id}
	
	j.currentExecutionTime = 0
	
	for(m in memorySlots) {
		m.job = j
		m.stats.used++
	}
}


def deallocateFinishedJobs(def memory) 
{	
	boolean hasJobs = false
	for(m in memory)
	{
		def job = m.job
		
		if(!job) continue;

		if( job?.isFinished() ) {
			println "Deallocating job: " + job.id + " from " + m.id
			
			job.finished = true
			m.job = null
			
		} else {
			job?.currentExecutionTime++
			hasJobs = true
		}
	}
	
	hasJobs
}

def printMemory(def memory) 
{
	println "+-----+-----+-----+"
	
	for(m in memory)
	{
		print "|  " + m.id + " "
		if( m.id > 9 ) print "|" else print " |"
		
		print m.size
		if(m.size <= 999) print "  |" else print " |"
		
		if( m.job && m.job.id < 10) print "  " + m.job.id + "  |"
		else if ( m.job && m.job.id >= 10) print " " + m.job.id + "  |"
		else print "     |"
		
		println " "
	}
	
	println "+-----+-----+-----+"
	
}

/** run stuff **/
int id = 1
def jobs = [
	new Job(id: id++, time: 5, size: 5790),
	new Job(id: id++, time: 4, size: 4190),
	new Job(id: id++, time: 8, size: 3290),
	new Job(id: id++, time: 2, size: 2030),
	new Job(id: id++, time: 2, size: 2550),
	new Job(id: id++, time: 6, size: 6990),
	new Job(id: id++, time: 8, size: 8940),
	new Job(id: id++, time: 10, size: 740),
	new Job(id: id++, time: 7, size: 3930),
	new Job(id: id++, time: 6, size: 6890),
	new Job(id: id++, time: 5, size: 6580),
	new Job(id: id++, time: 8, size: 3820),
	new Job(id: id++, time: 9, size: 9140),
	new Job(id: id++, time: 10, size: 420),
	new Job(id: id++, time: 10, size: 220),
	new Job(id: id++, time: 7, size: 7540),
	new Job(id: id++, time: 3, size: 3210),
	new Job(id: id++, time: 1, size: 1380),
	new Job(id: id++, time: 9, size: 9850),
	new Job(id: id++, time: 3, size: 3610),
	new Job(id: id++, time: 7, size: 7540),
	new Job(id: id++, time: 2, size: 2710),
	new Job(id: id++, time: 8, size: 8390),
	new Job(id: id++, time: 5, size: 5950),
	new Job(id: id++, time: 10, size: 760)
]
id = 1
def memory = [
	new Memory(id: id++, size: 9500),
	new Memory(id: id++, size: 7000),
	new Memory(id: id++, size: 9500),
	new Memory(id: id++, size: 4500),
	new Memory(id: id++, size: 8500),
	new Memory(id: id++, size: 3000),
	new Memory(id: id++, size: 9000),
	new Memory(id: id++, size: 1000),
	new Memory(id: id++, size: 5500),
	new Memory(id: id++, size: 1500),
	new Memory(id: id++, size: 500),
]


println "First fit finished in: " + runBatch(jobs, memory)

for(j in jobs) { j.currentExecutionTime = -1; j.finished = false}
for(m in memory) { m.stats = [used: 0] }
memory = memory.sort()

println "Best fit finished in: " + runBatch(jobs, memory)