Can't find the runtime error...

[group256]

Hi everyone,

I have been playing with a piece of code that is to simulate "shortest job scheduler" for almost 2 days and there is a runtime bug which it's seems I am not able to find. Any help is really appreciated.

Here is the code:

int sjf_scheduler(int number_of_jobs, process_attrib process[])
{
	process_attrib temp;
	vector<int> arrival, time, pid;
	
	cout << "\n\nNow We go to Shortest Job First Algorithm\n";
	cout << "Hit a key....\n";
	cin.get();
	//clscr();

	cout << "==================================================\n"
	     << "              Shortest Job First                  \n";

	//Sort and arrange based on arrival time 
	for (int i = 0; i < number_of_jobs; i++)
	{
		for (int j = 0; j < number_of_jobs - 1 ; j++)
		{
			if (process[j].arrival > process[j+1].arrival)
			{
				temp = process[j];
				process[j] = process[j+1];
				process[j+1] = temp;
			}

		}
	}

	/* Now copy all the data into 3 vectors to keep the time, arrival,
	 * and PID */
	for (int i = 0; i < number_of_jobs; i++)
	{
		arrival.push_back(process[i].arrival);
		time.push_back(process[i].time);
		pid.push_back(process[i].pid);
	}


	int shortest_job;
	int biggest_arrival_time = process[number_of_jobs - 1].arrival;
	int i, index = 0; /* Counter */

	for (int tick = 0; !arrival.empty(); tick++)
	{
		cout << "Tick: " << tick << endl << endl;
		shortest_job = 1000;  /* Set the burst time to a huge value */

		/* We have to get the smallest ARRIVED job */
		cout << "arrival: " << arrival.size() << endl;
		for (i = 0; i < arrival.size(); i++)
			if (arrival[i] <= tick && shortest_job > time[i])
			{
				shortest_job = time[i];
				index = i;
			}
		/* When exiting the loop, we have the shortest job by that 
		 * specific time, now it's time to process it, as it's 
		 * NON-Preemptive, so it takes the whole CPU time until it's
		 * fully finished */
		cout << "Index: " << index << endl;
		if (shortest_job != 1000)
		{
			cout << "\tProcess " << pid[index] << " finished...\n";
			tick += shortest_job - 1; /* Time to finish the process */
			arrival.erase(arrival.begin() + (index - 1)); /* get rid of the process */
			time.erase(time.begin() + (index - 1)); /* get rid of the process */
			pid.erase(pid.begin() + (index - 1)); /* get rid of the process */
		}
	}
	cout << "********Done!!*********\n";
}

and here is the error in the console when I say "make":

/**** some parts are deleted here ****/
arrival: 2
Index: 0
	Process 1 finished...
Tick: 63

arrival: 1
Index: 0
	Process 2 finished...
********Done!!*********
*** glibc detected *** ./a.out: munmap_chunk(): invalid pointer: 0x082e20b8 ***
======= Backtrace: =========
/lib/tls/i686/cmov/libc.so.6(+0x6b591)[0x401db591]
/lib/tls/i686/cmov/libc.so.6(+0x6c80e)[0x401dc80e]
/usr/lib/libstdc++.so.6(_ZdlPv+0x21)[0x400ef741]
./a.out[0x804c171]
./a.out[0x804be6f]
./a.out[0x804b7f6]
./a.out[0x804b13b]
./a.out[0x804a4fe]
./a.out[0x8048f52]
/lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xe6)[0x40186bd6]
./a.out[0x8048de1]
======= Memory map: ========
08048000-0804e000 r-xp 00000000 08:01 396319     /home/sam/OS/a.out
0804e000-0804f000 r--p 00005000 08:01 396319     /home/sam/OS/a.out
0804f000-08050000 rw-p 00006000 08:01 396319     /home/sam/OS/a.out
082e2000-08303000 rw-p 00000000 00:00 0          [heap]
40000000-4001b000 r-xp 00000000 08:01 3676549    /lib/ld-2.11.1.so
4001b000-4001c000 r--p 0001a000 08:01 3676549    /lib/ld-2.11.1.so
4001c000-4001d000 rw-p 0001b000 08:01 3676549    /lib/ld-2.11.1.so
4001d000-4001e000 r-xp 00000000 00:00 0          [vdso]
4001e000-40022000 rw-p 00000000 00:00 0 
40034000-4011d000 r-xp 00000000 08:01 7081651    /usr/lib/libstdc++.so.6.0.13
4011d000-4011e000 ---p 000e9000 08:01 7081651    /usr/lib/libstdc++.so.6.0.13
4011e000-40122000 r--p 000e9000 08:01 7081651    /usr/lib/libstdc++.so.6.0.13
40122000-40123000 rw-p 000ed000 08:01 7081651    /usr/lib/libstdc++.so.6.0.13
40123000-4012a000 rw-p 00000000 00:00 0 
4012a000-4014e000 r-xp 00000000 08:01 3676439    /lib/tls/i686/cmov/libm-2.11.1.so
4014e000-4014f000 r--p 00023000 08:01 3676439    /lib/tls/i686/cmov/libm-2.11.1.so
4014f000-40150000 rw-p 00024000 08:01 3676439    /lib/tls/i686/cmov/libm-2.11.1.so
40150000-40151000 rw-p 00000000 00:00 0 
40151000-4016e000 r-xp 00000000 08:01 3672391    /lib/libgcc_s.so.1
4016e000-4016f000 r--p 0001c000 08:01 3672391    /lib/libgcc_s.so.1
4016f000-40170000 rw-p 0001d000 08:01 3672391    /lib/libgcc_s.so.1
40170000-402c3000 r-xp 00000000 08:01 3676435    /lib/tls/i686/cmov/libc-2.11.1.so
402c3000-402c4000 ---p 00153000 08:01 3676435    /lib/tls/i686/cmov/libc-2.11.1.so
402c4000-402c6000 r--p 00153000 08:01 3676435    /lib/tls/i686/cmov/libc-2.11.1.so
402c6000-402c7000 rw-p 00155000 08:01 3676435    /lib/tls/i686/cmov/libc-2.11.1.so
402c7000-402cb000 rw-p 00000000 00:00 0 
bff41000-bff56000 rw-p 00000000 00:00 0          [stack]
make: *** [make] Aborted

Thank you.

[group256]

Anyone with any help???

[mike_2000_17]

At line 65, 66, and 67, you should have (index) instead of (index - 1). In the case you have index == 0, that would result in -1 and delete the element before the first one, which should result in the error you have got.

[group256]

Alright,

This is really odd!!!! I actually tried this before, and got segmentation ERROR!!!

But I did it now, it works fine. Really confused.

Secondly, in vector.erase, when you say

myvector.erase(myvector.begin() + 3) // 3 is here

but it actually is clearing the 4th element. How could it work here???

As the element that is being returned to "index" here is absolute index (Starting from zero) but what is being deleted is one element after that. Do you know how???

Thanks a lot anyway.

[mike_2000_17]

>>but it actually is clearing the 4th element. How could it work here???

It deletes the 4th element because the begin() points to the first element, so, begin() + 3 points to the fourth element. That makes total sense, doesn't it? And vector.erase will erase the element that is pointed to by the iterator you give it. So that's all there is to it, it makes perfect sense.