如何纠正我的C程序中的分段错误

我正在调试为knapSack编写的以下程序

#include  #include  #include "timer.h" #define MAX(x,y) ((x)>(y) ? (x) : (y)) #define table(i,j) table[(i)*(C+1)+(j)] int main(int argc, char **argv) { FILE *fp; long N, C, opt; // # of objects, capacity int *weights, *profits, *table, *solution; // weights and profits int verbose; // Temp variables long i, j, count, size, size1, ii, jj; // Time double time; // Read input file: // first line: # of objects, knapsack capacity, // next lines: weight and profit of next object (1 object per line) if ( argc > 1 ) { fp = fopen(argv[1], "r"); if ( fp == NULL) { printf("[ERROR] : Failed to read file named '%s'.\n", argv[1]); exit(1); } } else { printf("USAGE : %s [filename].\n", argv[0]); exit(1); } if (argc > 2) verbose = 1; else verbose = 0; fscanf(fp, "%ld %ld", &N, &C); printf("The number of objects is %ld, and the capacity is %ld.\n", N, C); size = N * sizeof(int); size1 = C * sizeof(int); weights = (int *)malloc(size); profits = (int *)malloc(size); table = (int *)malloc(size*size1); solution= (int *)malloc(size); if ( weights == NULL || profits == NULL ) { printf("[ERROR] : Failed to allocate memory for weights/profits.\n"); exit(1); } for ( i=0 ; i < N ; i++ ) { count = fscanf(fp, "%d %d", &(weights[i]), &(profits[i])); if ( count != 2 ) { printf("[ERROR] : Input file is not well formatted.\n"); exit(1); } } fclose(fp); initialize_timer (); start_timer(); // Solve for the optimal profit (create the table) for(j=0; j<=C; j++) { table(0,j)=0; } for(ii=1;ii<=N;ii++) { for(jj=0; jjjj) { table(ii,jj)=table(ii-1,jj); } else { table(ii,jj)=MAX(table(ii-1,jj),(profits[ii-1]+table(ii-1,jj-weights[ii-1]))); } } } opt=table(N,C); // We only time the creation of the table stop_timer(); time = elapsed_time (); printf("The optimal profit is %ld Time taken : %lf.\n",opt,time); // End of "Solve for the optimal profit" // Find the solution (choice vector) by backtracking through the table printf("Solution vector is: \n"); j=C; for(i=N;i>0;i--) { if(table(i,j)==table(i-1,j)) { //printf("Object %d not picked", i); solution[i-1]=0; } else { //printf("Object %d picked", i); j=j-weights[i-1]; solution[i-1]=1; } } for(i=0; i<N; i++) { printf("%d ",solution[i]); } if (verbose) { // print the solution vector } return 0; } 

对于小输入，代码运行正常。 但是对于N = 1200和C = 38400000或C的任何其他大输入，代码显示分段错误。 以下是Valgrind的输出：

 The number of objects is 1200, and the capacity is 38400000. ==2297== Invalid write of size 4 ==2297== at 0x400A4E: main (knap1.c:73) ==2297== Address 0x8 is not stack'd, malloc'd or (recently) free'd ==2297== ==2297== ==2297== Process terminating with default action of signal 11 (SIGSEGV) ==2297== Access not within mapped region at address 0x8 ==2297== at 0x400A4E: main (knap1.c:73) ==2297== If you believe this happened as a result of a stack ==2297== overflow in your program's main thread (unlikely but ==2297== possible), you can try to increase the size of the ==2297== main thread stack using the --main-stacksize= flag. ==2297== The main thread stack size used in this run was 8388608. ==2297== ==2297== HEAP SUMMARY: ==2297== in use at exit: 14,400 bytes in 3 blocks ==2297== total heap usage: 4 allocs, 1 frees, 14,968 bytes allocated ==2297== ==2297== LEAK SUMMARY: ==2297== definitely lost: 0 bytes in 0 blocks ==2297== indirectly lost: 0 bytes in 0 blocks ==2297== possibly lost: 0 bytes in 0 blocks ==2297== still reachable: 14,400 bytes in 3 blocks ==2297== suppressed: 0 bytes in 0 blocks ==2297== Rerun with --leak-check=full to see details of leaked memory ==2297== ==2297== For counts of detected and suppressed errors, rerun with: -v ==2297== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 2 from 2) Segmentation fault 

以下是有关使用不同输入文件（k10.txt到k1200.txt）运行的本地（从gdb获取）的值的信息：

  for files with which I got correct output until it exceeded that fix. no. of byte value fp = 0x0 N = 4131212846 C = 140737488347792 opt = 4294967295 weights = 0x0 profits = 0x36dd221168 table = 0x7ffff7ffc6b8 solution = 0x36dd8101c0 verbose = 0 i = 0 j = 140737488348128 count = 2 size = 4198301 size1 = 1 ii = 4196160 jj = 4198224 time = 2.0728237613194911e-317 for k1200.txt k1200.txt fp = 0x177b010 N = 1200 C = 38400000 opt = 4294967295 weights = 0x177b250 profits = 0x177c520 table = 0x8 solution = 0x7f3cd40008c0 verbose = 0 i = 1200 j = 0 count = 2 size = 4800 size1 = 153600000 ii = 4196160 jj = 4198224 time = 2.0728237613194911e-317 

有关我的代码有什么问题的任何输入？ 以及如何更正程序以便它永远不会显示分段错误？

Answer 1

你在这里要求太多的记忆：

 table = (int *)malloc(size*size1); 

正好是1200 * 38400000 * sizeof (int) * sizeof (int) ，大约是74GB的内存（假设sizeof (int) == 4 ）。 您的计算机无法彻底处理如此大的块，因此分配失败，并且当它失败时，返回NULL指针。 你应该检查这个条件：

 if (table == NULL) { fprintf(stderr, "Memory allocation failed :("); exit(1); } 

您没有使用NULL指针，导致分段错误。

不幸的是，这里没有简单的解决方法。 您应该重新考虑算法并查看您是否确实需要一次这么大的块，或者您可以重用较小的块。

一个小问题是你需要4倍的内存（仍然假设sizeof (int) == 4 ）。 实际上，当你使用malloc size * size1 bytes时，你将sizeof (int)考虑在内两次，一次是size = N * sizeof (int) ，一次是size1 = D * sizeof (int) ，而你很清楚想要一个N * C * sizeof(int)矩阵。

74GB / 4意味着18.5GB仍然太多：你的操作系统可能能够在虚拟内存中处理它，但是当交换开始时它会变得非常慢。除非你安装了18 + GB的RAM，当然。

无论如何，我想你使用table作为真/假布尔矩阵。 每个元素可能是一个32位的int ，其中你只使用1位。 如果使用按位运算将32个单元格打包到一个整数中，则可以将分配的大小减少32倍。 它可能会对性能产生影响，但它肯定会将内存占用减少到计算机可以处理的大小。

正如评论中所建议的那样，你也可以使用char或bool而不是int ，因为它们通常较小。

Answer 2

在N = 1200和C = 38400000时，N * C为46,080,000,000。 您使用的是32位还是64位操作系统？ 在32位你的多头可能会溢出。 此外，您可能没有足够的内存用于此计算。

看看你的算法，我发现你可能不需要将表分配为N * C，而只需要2 * C.

for循环仅使用行ii-1更新行ii。 所以，一旦你计算完毕，ii，你就不再需要ii-1了。 这意味着您可以重新使用第ii-1行的内存来存储ii + 1等。因此，您实际上只需要两行。

更像是这样的东西：

 table = malloc(2*size1); ... for(ii=1;ii<=N;ii++) { iiOut = ii%2; iiIn = (ii-1)%2; for(jj=0; jj<=C; jj++) { if(weights[ii-1]>jj) { table(iiOut,jj)=table(iiIn,jj); } else { table(iiOut,jj)=MAX(table(iiIn,jj),(profits[ii-1]+table(iiIn,jj-weights[ii-1]))); } } } opt=table(iiOut,C); 

Answer 3

好吧，除了dohashi的问题之外还有一些事情。

您应该添加检查以查看以下内存分配是否失败：

 if ( table == NULL ) { printf("[ERROR] : Failed to allocate memory for calculation table.\n"); exit(1); } if ( solution == NULL) { printf("[ERROR] : Failed to allocate memory for solution.\n"); exit(1); } 

如果你没有足够的内存来分配这些，现在你就会知道了。

接下来，我注意到用于索引到2d表的宏神秘地添加了一个未分配的额外列：

 #define table(i,j) table[(i)*(C+1)+(j)] 

看到“（C + 1）”那里？ 它说该表的实际大小为N *（C + 1）。 接下来，您稍后将表从1到N和1到C进行索引

 for(ii=1;ii<=N;ii++) { for(jj=0; jj<=C; jj++) { if(weights[ii-1]>jj) { table(ii,jj)=table(ii-1,jj); } else { table(ii,jj)=MAX(table(ii-1,jj),(profits[ii-1]+table(ii-1,jj-weights[ii-1]))); } } } opt=table(N,C); 

将宏处理table的大小设置为大小为N *（C + 1），这实际上要求表具有大小（N + 1）*（C + 2）。

我认为这里至少有一个问题是有人从FORTRAN翻译了这个代码而没有考虑到C中的数组是从零开始而不是从一开始的事实。 见这里的例子。