#!/usr/bin/perl
#
# OpSys Fall 2005 - Virtual Memory Page Replacement algo homework.
#
# This is a perl program that can generate input for your simulator.
# To run this program, install the file as "generate.pl" and type
# perl generate.pl 
# at the Unix prompt. Many parameters are defined below, these
# determine the output generated by this program...
#

# some parameters that control the simulated processes and memory
$nprocs = 6;		# max number of processes
$npages = 32;		# total number of pages (in virtual address space of each process)
$pagesize=32;		# bytes per page
$numlines = 10000;	# number of memory accesses generated (lower limit, can actually be a few more...)

# at each step we can either start a new process,
# terminate a process, or run a process.
# the start/stop probabilites are defined below

$start_process_probability = 0.1;
$stop_process_probability = 0.1;

# each time a process runs, the number of memory accesses
# generated is based on these values:
$run_process_mean_accesses = 5; # 100;
$run_process_std_accesses = 1; # 20;


# derived values

$maxaddress = $pagesize * $npages;

%procstate = init_processes();

# start with 1/2 the processes active
for ($i=0;$i<$nprocs/2;$i++) {
	start_process($i);
}



$lines=0;
while ($lines < $numlines) {
	# choices: start new process, end a process,
	#  or run a process (generate memory addresses).
	# show_processes();   # generator debugging - display active processes
	if ($active_processes==0) {
		start_process(0);
	} else {
		# random number controls what we do
		$num = rand();
		if (($active_processes < $nprocs) && ($num < $start_process_probability)) {
			# start a new process (find an empty slot)
			$i=0;
			while ($procstate{$i,'running'}==1) { $i++; }
			start_process($i);
		} elsif ($num < $start_process_probability + $stop_process_probability) {
			# pick a random process to stop
			stop_process(pick_random_active_process());
		} else {
			# pick a random process to run
			run_process(pick_random_active_process());
		}
	}
}
			

# pick randomly among all active processes
sub pick_random_active_process {
	my(@active);
	my($i);

	for ($i=0;$i<$nprocs;$i++) {
		if ($procstate{$i,'running'}==1) {
			push @active,$i;
		}
	}

	my($p) = int(rand(@active));
	return($active[$p]);
}
	


# generate a random address given a mean address and standard deviation
#
# small but finite probability the address will be negative !
sub random_address{
	my($mean,$std) = @_;
	my($num);
	do {
		$num = int(gaussian_rand()*$std+$mean);
	} while ($num<0);
	return($num);
}

	

# Generating random numbers according to a normal distribution
# (code from the Perl Cookbook).

sub gaussian_rand {
    my ($u1, $u2);  # uniformly distributed random numbers
    my $w;          # variance, then a weight
    my ($g1, $g2);  # gaussian-distributed numbers

    do {
        $u1 = 2 * rand() - 1;
        $u2 = 2 * rand() - 1;
        $w = $u1*$u1 + $u2*$u2;
    } while ( $w >= 1 );

    $w = sqrt( (-2 * log($w))  / $w );
    $g2 = $u1 * $w;
    $g1 = $u2 * $w;

    return $g1;
}


# initialize each process
#
sub init_processes{
	my($i);
	for ($i=0;$i<$nprocs;$i++) {
		$procstate{$i,'running'}=-1;
	}
}

# debugging
sub show_processes{

	my($i);
	for ($i=0;$i<$nprocs;$i++) {
		if ($procstate{$i,'running'}==1) {
			printf("Process $i:\n");
			printf("  address: %d\n",$procstate{$i,'last_address'});
			printf("  std: %f\n",$procstate{$i,'std'});
		}
	}
}

sub start_process{
	my($p) = $_[0];
	if ($procstate{$p,'running'}==1) {
		printf("ERROR - CAN'T START PROCESS $p - already running!\n");
		exit;
	}

	printf("S $p\n");
	# initial address is generated uniformly somewhere in the middle of the address range.
	$procstate{$p,'last_address'} = int((rand()*($maxaddress/2)) + $maxaddress/4);
	# std used for addresses is based on random gaussian centered at 10, std 5
	$procstate{$p,'std'} = 11+(gaussian_rand()*5);
	$procstate{$p,'accesses'} = 0;
	$procstate{$p,'running'}=1;
	$active_processes++;
}

sub stop_process{
	my($p) = $_[0];
	if ($procstate{$p,'running'}!=1) {
		printf("ERROR - CAN'T STOP PROCESS $p - not running!\n");
		exit;
	}
	printf("T $p\n");
	$procstate{$p,'running'}=-1;
	$active_processes--;
}


sub run_process{
	my($p) = $_[0];

	if ($procstate{$p,'running'}!=1) {
		printf("ERROR - CAN'T RUN PROCESS $p - not running!\n");
		exit;
	}

	# number of memory accesses this step is selected
	# randomly from a gaussian
	my($refs) = int(gaussian_rand()*$run_process_std_accesses + $run_process_mean_accesses);
	my($i);
	my($address);
	# now generate the memory accesses, for now just read ('R');
	# each address is picked randomly using a gaussian centered at the 
	# last address picked and the standard deviation.
	for ($i=0;$i<$refs;$i++) {
		$address = random_address($procstate{$p,'last_address'},$procstate{$p,'std'});
		printf("R $p %d\n",$address);
		$procstate{$p,'last_address'} = $address;
		$procstate{$i,'accesses'}++;
		$lines++;
	}
}