Killed process by SIGKILL

Question

I have a process that get killed immediately after executing the program. This is the code of the compiled executable, and it is a small program that reads several graphs represented by numbers from standard input (a descriptive file usually) and finds the minimum spanning tree for every graph using the Prim's algorithm (it does not show the results yet, it just find the solution).

#include <stdlib.h>  
#include <iostream>  

using namespace std;

const int MAX_NODOS = 20000;
const int infinito = 10000;

int nnodos;
int nAristas;
int G[MAX_NODOS][MAX_NODOS]; 
int solucion[MAX_NODOS][MAX_NODOS];
int menorCoste[MAX_NODOS];
int masCercano[MAX_NODOS];



void leeGrafo(){
    if (nnodos<0 || nnodos>MAX_NODOS) {
        cerr << "Numero de nodos (" << nnodos << ") no valido\n";
        exit(0);
    }  
    for (int i=0; i<nnodos ; i++)
        for (int j=0; j<nnodos ; j++)
            G[i][j] = infinito; 
    int A,B,P;
    for(int i=0;i<nAristas;i++){
        cin >> A >> B >> P; 
        G[A][B] = P;
        G[B][A] = P;
    }   
}


void prepararEstructuras(){
    // Grafo de salida
    for(int i=0;i<nnodos;i++)
        for(int j=0;j<nnodos;j++)
            solucion[i][j] = infinito;
    // el mas cercaano 
    for(int i=1;i<nnodos;i++){
        masCercano[i]=0;
        // menor coste
        menorCoste[i]=G[0][i];
    }           
}

void prim(){
    prepararEstructuras();
    int min,k;  
    for(int i=1;i<nnodos;i++){
        min = menorCoste[1];
        k = 1;
        for(int j=2;i<nnodos;j++){
            if(menorCoste[j] < min){
                min = menorCoste[j];
                k = j;
            }
        }
        solucion[k][masCercano[k]] = G[k][masCercano[k]];
        menorCoste[k] = infinito;
        for(int j=1;j<nnodos;j++){
            if(G[k][j] < menorCoste[j] && menorCoste[j]!=infinito){
                menorCoste[j] = G[k][j];
                masCercano[j] = k;
            }       
        }           
    }
}

void output(){
    for(int i=0;i<nnodos;i++){
        for(int j=0;j<nnodos;j++)
            cout << G[i][j] << ' ';
        cout << endl;
    }
}

int main (){
    while(true){
        cin >> nnodos;
        cin >> nAristas;
        if((nnodos==0)&&(nAristas==0)) break;
        else{
            leeGrafo();
            output();
            prim(); 
        }
    }   
}

I have learned that i must use strace to find what is going on, and this is what i get :

execve("./412", ["./412"], [/* 38 vars */] <unfinished ...>
+++ killed by SIGKILL +++
Killed

I am runing ubuntu and this is the first time i get this type of errors. The program is supposed to stop after reading two zeros in a row from the input wich i can guarantee that i have in my graphs descriptive file. Also the problem happens even if i execute the program without doing an input redirection to my graphs file.

Saporific

Your program logic is very hard to follow. What did your debugger say about the situation? – Calbert

Something to note: Your fixed sized arrays are huge. At launch you'll need > 3.2 GB... That could be the issue. – Templin

@TomalakGeret'kal: The program logic is irrelevant; none of it executes! – Crescint

So should i use pointers to int for example to solve the memory problem ? – Saporific

@Gabe: It's relevant to the OP, and to anyone who'll use his code later. – Calbert

@YoussefKhloufi: I would start by changing int to short. If that doesn't fix the problem, change MAX_NODOS to a much lower number. – Crescint

Answer 1

Although I'm not 100% sure that this is the problem, take a look at the sizes of your global arrays:

const int MAX_NODOS = 20000;

int G[MAX_NODOS][MAX_NODOS]; 
int solucion[MAX_NODOS][MAX_NODOS];

Assuming int is 4 bytes, you'll need:

20000 * 20000 * 4 bytes * 2 = ~3.2 GB

For one, you might not even have that much memory. Secondly, if you're on 32-bit, it's likely that the OS will not allow a single process to have that much memory at all.

Assuming you're on 64-bit (and assuming you have enough memory), the solution would be to allocate it all at run-time.

Templin

This is probably the answer. I would suggest changing those int arrays to short to see if that helps. – Crescint

I can see now that this is the problem i am having, i just changed 2000 to 20 and it works. One more question please, if i want to continue using arrays for graph representation without changing to the list alternative, can i use pointers to int ? instead of just int. Will it solve the problem ? or i have to change to a dynamic structure necessary ? – Saporific

If you're not careful, pointers will simply exacerbate the problem by taking up still more space. You may simply not have enough memory available. Are you on a 32-bit or a 64-bit machine? If on 32-bit, you probably cannot do problems of size 20,000 (because the total size of the data is too close to 4 GiB). If you're on 64-bit, it depends on your virtual memory limits rather than the limitations of the CPU addressing. – Bursiform

In your case, you're probably just better using vector<vector<int> > and building it at run-time. It looks like you take the # of nodes from the input. So it makes more sense to build it at run-time. – Templin

Answer 2

Your arrays G and solucion each contain 400,000,000 integers, which is about 1.6 GiB each on most machines. Unless you have enough (virtual) memory for that (3.2 GiB and counting), and permission to use it (try ulimit -d; that's correct for bash on MacOS X 10.7.2), your process will fail to start and will be killed by SIGKILL (which cannot be trapped, not that the process is really going yet).

Bursiform