Quá trình bị giết bởi SIGKILL

Question

Tôi có một quy trình bị giết ngay lập tức sau khi thực hiện chương trình. Đây là mã của tệp thực thi được biên dịch, và nó là một chương trình nhỏ đọc một số biểu đồ được biểu thị bằng số từ đầu vào tiêu chuẩn (tệp mô tả thường) và tìm cây bao trùm tối thiểu cho mọi đồ thị bằng thuật toán của Prim (nó không hiển thị kết quả nào, nó chỉ tìm ra giải pháp).

#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(); 
     } 
    } 
} 

Tôi đã học được rằng tôi phải sử dụng strace để tìm thấy những gì đang diễn ra, và đây là những gì tôi nhận được:

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

Tôi đang runing ubuntu và đây là lần đầu tiên tôi nhận được loại lỗi. Chương trình được cho là dừng sau khi đọc hai số không trong một hàng từ đầu vào mà tôi có thể đảm bảo rằng tôi có trong tệp mô tả đồ thị của tôi. Ngoài ra vấn đề xảy ra ngay cả khi tôi thực hiện chương trình mà không làm một chuyển hướng đầu vào vào tệp đồ thị của tôi.

Answer 1

Mặc dù tôi không chắc chắn 100% rằng đây là vấn đề, hãy nhìn vào kích thước của mảng toàn cầu của bạn:

const int MAX_NODOS = 20000; 

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

Giả sử int là 4 byte, bạn sẽ cần:

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

Đối với một, bạn có thể thậm chí không có nhiều bộ nhớ. Thứ hai, nếu bạn đang trên 32-bit, có khả năng là hệ điều hành sẽ không cho phép một quá trình duy nhất để có nhiều bộ nhớ ở tất cả.

Giả sử bạn đang sử dụng 64 bit (và giả sử bạn có đủ bộ nhớ), giải pháp sẽ là phân bổ tất cả trong thời gian chạy.

Answer 2

Mảng của bạn G và solucion mỗi mảng chứa 400.000.000 số nguyên, tức là khoảng 1,6 GiB trên mỗi máy. Trừ khi bạn có đủ (ảo) bộ nhớ cho điều đó (3,2 GiB và đếm), và cho phép sử dụng nó (hãy thử ulimit -d; đó là chính xác cho bash trên MacOS X 10.7.2), quá trình của bạn sẽ không bắt đầu và sẽ bị giết bởi SIGKILL (mà không thể bị mắc kẹt, không phải là quá trình thực sự đang được nêu ra).