C++

Forum

 
FCFS Scheduling Algorithm

LastSeen (5)
Hello, i'm trying to write a simulation of a First Come First Served scheduling algorithm and im having problems with and error which says "deque iterator not dereferencable" what can i do to fix this error and what is causing it? thank you

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
  #include <cstdlib>
#include <iostream>
#include <deque>
#include <queue>
using namespace std;

/*
*
*/
int main(int argc, char** argv)
{
	int ps[9][19] = { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
	{ 4, 15, 5, 31, 6, 26, 7, 24, 6, 41, 4, 51, 5, 16, 4, 0, 0, 0, 0 }, // p1
	{ 9, 28, 11, 22, 15, 21, 12, 28, 8, 34, 11, 34, 9, 29, 10, 31, 7, 0, 0 }, // p2
	{ 24, 28, 12, 21, 6, 27, 17, 21, 11, 54, 22, 31, 18, 0, 0, 0, 0, 0, 0 }, // p3
	{ 15, 35, 14, 41, 16, 45, 18, 51, 14, 61, 13, 54, 16, 61, 15, 0, 0, 0, 0 }, // p4
	{ 6, 22, 5, 21, 15, 31, 4, 26, 7, 31, 4, 18, 6, 21, 10, 33, 3, 0, 0 }, // p5
	{ 22, 38, 27, 41, 25, 29, 11, 26, 19, 32, 18, 22, 6, 26, 6, 0, 0, 0, 0 }, // p6
	{ 4, 36, 7, 31, 6, 32, 5, 41, 4, 42, 7, 39, 6, 33, 5, 34, 6, 21, 9 }, // p7
	{ 5, 14, 4, 33, 6, 31, 4, 31, 6, 27, 5, 21, 4, 19, 6, 11, 6, 0, 0 } }; // p8



	deque<int> burst[9], iotime[9], remainio[9];

	// init burst and iotime
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 19; j = j + 2)
		{
			if (ps[i][j] != 0)
			{
				burst[i].push_back(ps[i][j]);
				iotime[i].push_back(ps[i][j + 1]);
				remainio[i].push_back(ps[i][j + 1]);
			}
		}
	}


	// process in ready queue and io queue
	deque<int> ready, io;
	for (int i = 1; i < 9; i++)
	{
		ready.push_back(i);
	}
	int currTime = 0;
	int currBurst = 0;
	int passTime = 0;
	int running; // running process
	int runningBurst = 0; // burst of running process
	int runningIO; // iotime of runnign process

	int count = 0;
	while (ready.size() != 0 || io.size() != 0)
	{
		
		cout << "Current Time: " << currTime << endl;
		// Get a running process from ready queue
		running = ready.front(); ready.pop_front();
		// Get burstime
		runningBurst = burst[running].front(); burst[running].pop_front();
		// Get iotime
		runningIO = iotime[running].front(); iotime[running].pop_front();

		// Shown running process
		cout << "\nNow running: P" << running << endl;
		cout << "..................................................\n" << endl;
		// Show the other queue in ready with burst time
		cout << "Ready Queue: Process Burst" << endl;

		for (int i = 0; i < ready.size(); i++)
		{
			int rp = ready.at(i); //cout << "Debug:" << rp << endl;
			int burstTime = burst[rp].front();
			cout << "             P" << rp << "      " << burstTime << endl;
		}

		// Show IO queue
		cout << "Now in I/O:  Process Remaining I/O time" << endl;
		if (io.size() == 0)
			cout << "             [empty]" << endl;
		else
		{
			for (int i = 0; i < io.size(); i++)
			{
				int iop = io.at(i);
				int remainTime = remainio[iop].front(); //
				cout << "             P" << iop << "      " << remainTime << endl;
			}
		}

		// update ready queue, io queue
		// for each process in io queue, update remain time
		// if remain time is < 0, push new process in ready

		int size = io.size();
		for (int i = 0; i < size; i++)
		{
			int iop = io.front(); io.pop_front();
			int remainTime = remainio[iop].front(); remainio[iop].pop_front();//
			remainTime -= runningBurst;

			if (remainTime > 0) // still in io queue
			{
				io.push_back(iop);
				remainio[iop].push_front(remainTime);
			}
			else // push new process in ready
			{
				ready.push_back(iop);
			}
		}
		cout << "\n.................................................." << endl;
		cout << "..................................................\n" << endl;
		// push running process to I/O queue
		io.push_back(running);

		// update current time
		currTime += runningBurst;
	}

	cout << "Total Time: " << currTime << endl;
	cout << "CPU Utiliation: " << endl;

	cout << "Waiting Times: " << endl;
	cout << "Turnaround Times: " << endl;

	cout << "Average Turnaround: " << endl;

	cout << "Response Times: "  << endl;

	cout << "Average Response: " << endl;
	return 0;
}
helios (17575)
I see several times x.front() being used without checking that x.size() > 0.
1
2
3
4
 
// Get burstime
runningBurst = burst[running].front(); burst[running].pop_front();
// Get iotime
runningIO = iotime[running].front(); iotime[running].pop_front();
Last edited on
Enoizat (1343)
This part of your code
1
2
3
4
5
6
7
8
9
10
11
12
 
for (int i = 0; i < 9; i++)
{
    for (int j = 0; j < 19; j = j + 2)
    {
        if (ps[i][j] != 0)
        {
            burst[i].push_back(ps[i][j]);
            iotime[i].push_back(ps[i][j + 1]);
            remainio[i].push_back(ps[i][j + 1]);
        }
    }
}

involves undefined behaviour (you’re accessing a C-style array beyond its boundaries). It means from that block on everything may happen, even an apparently correct behaviour.

Just to give you an example, on my pc this code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include <iostream>
#include <deque>

int main()
{
    int ps[4][3] = {  {  0,  0,  0 },
                      {  4, 15,  5 },
                      {  9, 28, 11 },
                      { 24, 28, 12 }  };

    std::deque<int> burst[4], iotime[4];

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j = j + 2) {
            if (ps[i][j] != 0) {
                burst[i] .push_back( ps[i][j]     );
                iotime[i].push_back( ps[i][j + 1] );
            }
            std::cout << "i: "       << i << "; j: " << j
                      << "; burst["  << i << "]: "   << ps[i][j]
                      // << "; iotime[" << i << "]: "   << ps[i][j+1]
                      << '\n';
        }
    }
    return 0;
}

outputs:
i: 0; j: 0; burst[0]: 0
i: 0; j: 2; burst[0]: 0
i: 1; j: 0; burst[1]: 4
i: 1; j: 2; burst[1]: 5
i: 2; j: 0; burst[2]: 9
i: 2; j: 2; burst[2]: 11
i: 3; j: 0; burst[3]: 24
i: 3; j: 2; burst[3]: 12

(apparently works without issues), while this other one:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include <iostream>
#include <deque>

int main()
{
    int ps[4][3] = {  {  0,  0,  0 },
                      {  4, 15,  5 },
                      {  9, 28, 11 },
                      { 24, 28, 12 }  };

    std::deque<int> burst[4], iotime[4];

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j = j + 2) {
            if (ps[i][j] != 0) {
                burst[i] .push_back( ps[i][j]     );
                iotime[i].push_back( ps[i][j + 1] );
            }
            std::cout << "i: "       << i << "; j: " << j
                      << "; burst["  << i << "]: "   << ps[i][j]
                      << "; iotime[" << i << "]: "   << ps[i][j+1]
                      << '\n';
        }
    }
    return 0;
}

shows the disaster:
i: 0; j: 0; burst[0]: 0; iotime[0]: 0
i: 0; j: 2; burst[0]: 0; iotime[0]: 0
i: 0; j: 4; burst[0]: 5109312; iotime[0]: 0
i: 0; j: 6; burst[0]: 4596989; iotime[0]: 0
i: 0; j: 8; burst[0]: 5107792; iotime[0]: 0
i: 0; j: 10; burst[0]: 4912318; iotime[0]: 0
i: 0; j: 12; burst[0]: 6446896; iotime[0]: 0
i: 0; j: 14; burst[0]: 8; iotime[0]: 0
i: 0; j: 16; burst[0]: 6444704; iotime[0]: 0
i: 0; j: 18; burst[0]: 6444704; iotime[0]: 0
i: 0; j: 20; burst[0]: 6445216; iotime[0]: 0
i: 0; j: 22; burst[0]: 6446920; iotime[0]: 0
i: 0; j: 24; burst[0]: 6444748; iotime[0]: 0
i: 0; j: 26; burst[0]: 6444704; iotime[0]: 0
i: 0; j: 28; burst[0]: 6445216; iotime[0]: 0
i: 0; j: 30; burst[0]: 6446920; iotime[0]: 0
i: 0; j: 32; burst[0]: 6446976; iotime[0]: 0
i: 0; j: 34; burst[0]: 8; iotime[0]: 0
i: 0; j: 36; burst[0]: 6445232; iotime[0]: 0
i: 0; j: 38; burst[0]: 6445232; iotime[0]: 0
i: 0; j: 40; burst[0]: 6445744; iotime[0]: 0
i: 0; j: 42; burst[0]: 6447000; iotime[0]: 0
i: 0; j: 44; burst[0]: 6445232; iotime[0]: 0
i: 0; j: 46; burst[0]: 6445232; iotime[0]: 0
i: 0; j: 48; burst[0]: 6445744; iotime[0]: 0
i: 0; j: 50; burst[0]: 6447000; iotime[0]: 0
...

Luckily there’s an easy solution: don’t use C-style arrays :-)
For example, if you use C++ std::array or std::vector, you can take advantage of the “at()” method, which checks the boundaries for you:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <array>
#include <iostream>
#include <deque>

int main()
{
    std::array<std::array<int, 3>, 4> ps { { {  0,  0,  0 },
                                             {  4, 15,  5 },
                                             {  9, 28, 11 },
                                             { 24, 28, 12 }  } };

    std::deque<int> burst[4], iotime[4];

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j = j + 2) {
            if (ps[i][j] != 0) {
                burst[i] .push_back( ps.at(i).at(j)     );
                iotime[i].push_back( ps.at(i).at(j + 1) );
            }
            std::cout << "i: "       << i << "; j: " << j
                      << "; burst["  << i << "]: "   << ps.at(i).at(j)
                      << "; iotime[" << i << "]: "   << ps.at(i).at(j + 1)
                      << '\n';
        }
    }
    return 0;
}

Output:
i: 0; j: 0; burst[0]: 0; iotime[0]: 0
i: 0; j: 2; burst[0]: 0; iotime[0]:
This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

The program crashes instead of deceiving you into thinking it works.
Turning your C-style arrays of std::deques into std::vectors of std::deques will help you a lot in making your code more robust:
1
2
3
4
5
6
7
8
 
std::vector<std::deque<int>> burst(4), iotime(4);

for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 3; j = j + 2) {
        if (ps.at(i).at(j) != 0) {
            burst.at(i) .push_back( ps.at(i).at(j)     );
            iotime.at(i).push_back( ps.at(i).at(j + 1) );
        }

Enoizat (1343)
OPS! Please, ignore my previous post. Your ‘if’ condition
if (ps[i][j] != 0)
correctly protects you from violating ‘ps’ boundaries.
Sorry, I haven’t tested it the right way!
LastSeen (5)
Thank you for the replys,ill see what i can do based on the suggestions provided
Last edited on
Topic archived. No new replies allowed.