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.

Your program logic is very hard to follow. What did your debugger say about the situation? — Lightness Races in Orbit, Jan 02 '12 at 01:50
Something to note: Your fixed sized arrays are huge. At launch you'll need > `3.2 GB`... That could be the issue. — Mysticial, Jan 02 '12 at 01:52
@TomalakGeret'kal: The program logic is irrelevant; none of it executes! — Gabe, Jan 02 '12 at 01:52
So should i use pointers to int for example to solve the memory problem ? — Youssef Khloufi, Jan 02 '12 at 01:53
@Gabe: It's relevant to the OP, and to anyone who'll use his code later. — Lightness Races in Orbit, Jan 02 '12 at 01:55
@YoussefKhloufi: I would start by changing `int` to `short`. If that doesn't fix the problem, change `MAX_NODOS` to a much lower number. — Gabe, Jan 02 '12 at 02:00

score 8 · Accepted Answer · answered Jan 02 '12 at 01:54

8

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.

answered Jan 02 '12 at 01:54

Mysticial

464,885
45
335
332

This is probably the answer. I would suggest changing those `int` arrays to `short` to see if that helps. – Gabe Jan 02 '12 at 01:59
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 ? – Youssef Khloufi Jan 02 '12 at 02:02
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. – Jonathan Leffler Jan 02 '12 at 02:05
In your case, you're probably just better using `vector >` 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. – Mysticial Jan 02 '12 at 02:05

score 6 · Answer 2 · answered Jan 02 '12 at 01:54

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).

Killed process by SIGKILL

2 Answers2