Проблема с использованием fork () для вычисления общей суммы полученных аргументов командной строки

Question

Я пытаюсь вычислить сумму, основанную на наборах чисел, полученных из командной строки, и я использую сопутствующую программу под названием работник, чтобы вычислить меня. Если количество полученных чисел нечетное, к числу чисел добавляется ноль, чтобы сделать набор четным.

Это поток программы в понятной форме (кредит Alok):

Пример прояснит ситуацию:

Допустим, вы хотите добавить 7 цифр: 1 2 3 4 5 6 7

. / Координатор 1 2 3 4 5 6 7

1. вход = [1 2 3 4 5 6 7 0]
2. n = len (вход) = 8
3. м = н / 2 = 4
4. вывод = [0 0 0 0]
5. Разветвляемся 4 процесса, первый процесс получает [1 2], второй получает [3 4], ...
6. 4 процесса возвращают 3, 7, 11, 7 соответственно, которые мы назначаем для вывода.
7. output имеет 4 элемента, поэтому мы выделяем пространство для 4 + 1 = 5 элементов для нового входа.
8. set input = [3 7 11 7 0]
9. n = len (вход) = 5
10. м = н / 2 = 2
11. вывод = [0 0]
12. Мы разбиваем 2 процесса, первый получает [3 7], второй получает [11 7]
13. 2 процесса возвращают 10, 18, которые мы назначаем для вывода.
14. вывод имеет 2 элемента, поэтому мы выделяем пространство для 2 + 1 = 3 элемента для нового ввода.
15. установить вход = [10 18 0]
16. n = len (вход) = 3
17. м = н / 2 = 1
18. вывод = [0]
19. Мы разбиваем один процесс, который получает [10 18]
20. Процесс возвращает 28, которые мы назначаем для вывода.
21. вывод имеет 1 элемент, так что все готово.

Хотя на этом конкретном наборе чисел я получаю:

Process ID: 15195 
Sum of 1 and 2 is 3 

Process ID: 15196 
Sum of 3 and 4 is 7 

Process ID: 15197 
Sum of 5 and 6 is 11 

Process ID: 15198 
Sum of 7 and 0 is 7 

*** glibc detected *** ./coordinator: free(): invalid next size (fast): 0x080ec048 ***

Далее следует список ошибок кучи.

Мне кажется, я неправильно перераспределяю размер указателей, в которых я пытаюсь перенаправить старый вывод на новый ввод после первого вызова next_step (). Поэтому он пытается поместить данные в ту часть памяти, для которой нет места.

UPDATE:

@ Norman

Это вывод, который я получаю:

==3585== Memcheck, a memory error detector
==3585== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==3585== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==3585== Command: ./coordinator 1 2 3 4
==3585== 
calc: 2:
input[0]: 1
input[1]: 2
input[2]: 3
input[3]: 4
==3585== Use of uninitialised value of size 4
==3585==    at 0x4076186: ??? (in /lib/tls/i686/cmov/libc-2.10.1.so)
==3585==    by 0x4079A81: vfprintf (in /lib/tls/i686/cmov/libc-2.10.1.so)
==3585==    by 0x4080F7F: printf (in /lib/tls/i686/cmov/libc-2.10.1.so)
==3585==    by 0x8048833: main (in /home/bryan/cpp/coordinator)
==3585== 
==3585== Conditional jump or move depends on uninitialised value(s)
==3585==    at 0x407618E: ??? (in /lib/tls/i686/cmov/libc-2.10.1.so)
==3585==    by 0x4079A81: vfprintf (in /lib/tls/i686/cmov/libc-2.10.1.so)
==3585==    by 0x4080F7F: printf (in /lib/tls/i686/cmov/libc-2.10.1.so)
==3585==    by 0x8048833: main (in /home/bryan/cpp/coordinator)
==3585== 
==3585== Conditional jump or move depends on uninitialised value(s)
==3585==    at 0x4077877: vfprintf (in /lib/tls/i686/cmov/libc-2.10.1.so)
==3585==    by 0x4080F7F: printf (in /lib/tls/i686/cmov/libc-2.10.1.so)
==3585==    by 0x8048833: main (in /home/bryan/cpp/coordinator)
==3585== 
==3585== Conditional jump or move depends on uninitialised value(s)
==3585==    at 0x407789B: vfprintf (in /lib/tls/i686/cmov/libc-2.10.1.so)
==3585==    by 0x4080F7F: printf (in /lib/tls/i686/cmov/libc-2.10.1.so)
==3585==    by 0x8048833: main (in /home/bryan/cpp/coordinator)
==3585== 
input[4]: 0
==3586== Memcheck, a memory error detector
==3586== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==3586== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==3586== Command: ./worker 1 2
==3586== 
Process ID: 3586 
Sum of 1 and 2 is 3 

==3586== 
==3586== HEAP SUMMARY:
==3586==     in use at exit: 0 bytes in 0 blocks
==3586==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==3586== 
==3586== All heap blocks were freed -- no leaks are possible
==3586== 
==3586== For counts of detected and suppressed errors, rerun with: -v
==3586== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 6)
==3587== Memcheck, a memory error detector
==3587== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==3587== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==3587== Command: ./worker 3 4
==3587== 
Process ID: 3587 
Sum of 3 and 4 is 7 

==3587== 
==3587== HEAP SUMMARY:
==3587==     in use at exit: 0 bytes in 0 blocks
==3587==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==3587== 
==3587== All heap blocks were freed -- no leaks are possible
==3587== 
==3587== For counts of detected and suppressed errors, rerun with: -v
==3587== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 6)
==3585== Invalid write of size 4
==3585==    at 0x8048A3A: main (in /home/bryan/cpp/coordinator)
==3585==  Address 0x417f0b4 is 8 bytes after a block of size 4 alloc'd
==3585==    at 0x4024C6C: malloc (vg_replace_malloc.c:195)
==3585==    by 0x4024CF6: realloc (vg_replace_malloc.c:476)
==3585==    by 0x8048A25: main (in /home/bryan/cpp/coordinator)
==3585== 
==3588== Memcheck, a memory error detector
==3588== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==3588== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==3588== Command: ./worker 3 7
==3588== 
Process ID: 3588 
Sum of 3 and 7 is 10 

==3588== 
==3588== HEAP SUMMARY:
==3588==     in use at exit: 0 bytes in 0 blocks
==3588==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==3588== 
==3588== All heap blocks were freed -- no leaks are possible
==3588== 
==3588== For counts of detected and suppressed errors, rerun with: -v
==3588== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 6)
==3585== Invalid read of size 4
==3585==    at 0x8048AB5: main (in /home/bryan/cpp/coordinator)
==3585==  Address 0x417f0e0 is 0 bytes after a block of size 0 alloc'd
==3585==    at 0x4024C6C: malloc (vg_replace_malloc.c:195)
==3585==    by 0x4024CF6: realloc (vg_replace_malloc.c:476)
==3585==    by 0x8048A77: main (in /home/bryan/cpp/coordinator)
==3585== 
The final sum is: 0==3585== 
==3585== HEAP SUMMARY:
==3585==     in use at exit: 28 bytes in 2 blocks
==3585==   total heap usage: 4 allocs, 2 frees, 32 bytes allocated
==3585== 
==3585== LEAK SUMMARY:
==3585==    definitely lost: 8 bytes in 1 blocks
==3585==    indirectly lost: 0 bytes in 0 blocks
==3585==      possibly lost: 20 bytes in 1 blocks
==3585==    still reachable: 0 bytes in 0 blocks
==3585==         suppressed: 0 bytes in 0 blocks
==3585== Rerun with --leak-check=full to see details of leaked memory
==3585== 
==3585== For counts of detected and suppressed errors, rerun with: -v
==3585== Use --track-origins=yes to see where uninitialised values come from
==3585== ERROR SUMMARY: 6 errors from 6 contexts (suppressed: 11 from 6)

Answer 1

Вам следует подумать о написании функции, давайте назовем ее step_once(), которая будет принимать input с n числами и записывать в соответствующие output с m = n/2 элементами. n выше - это число входных чисел + 1, с последним элементом input, равным 0.

В вашей функции драйвера, скажем, main(): если output содержит 1 число, все готово. В противном случае вы перераспределяете input для содержания n_new = m+1 элементов, перераспределяете output для содержания m_new = n_new/2 элементов и снова вызываете функцию step_once(). Вы продолжаете делать это, пока не получите один номер:

function next_step(input, output, n, m):
    n := number of input numbers # this is 1 greater than
                                 # the number of numbers being summed
    m := n / 2 # C division
    n_children := m
    i := 0
    while i < m:
        fork worker with input[2*i] and input[2*i+1]
        get result in output[i]
        i := i + 1

function main:
    set n := length(input) + 1
    set m := n/2
    allocate memory for input # n+1 elements, last = 0
    allocate memory for output # m elements
    set values in input
    while True:
        next_step(input, output, n, m)
        if length or output == 1:
             done, return
        else:
            set n := length(output) + 1
            set m := n/2
            allocate space for new_input # n elements
            set new_input := output + [0]
            free input and output
            set input := new_input
            allocate memory for output # m elements

Преимущество заключается в том, что вы можете протестировать функцию next_step(), чтобы убедиться, что она работает и, таким образом, облегчает отладку.

Пример прояснит ситуацию:

Допустим, вы хотите добавить 7 цифр: 1 2 3 4 5 6 7

1. input = [1 2 3 4 5 6 7 0]
2. n = len (input) = 8
3. m = n/2 = 4
4. output = [0 0 0 0]
5. Разветвляемся 4 процесса, первый процесс получает [1 2], второй получает [3 4], ...
6. 4 процесса возвращают 3, 7, 11, 7 соответственно, что мы присваиваем output.
7. output имеет 4 элемента, поэтому мы выделяем место для 4 + 1 = 5 элементов для нового input.
8. набор input = [3 7 11 7 0]
9. n = len (input) = 5
10. m = n/2 = 2
11. output = [0 0]
12. Мы разбиваем 2 процесса, первый получает [3 7], второй получает [11 7]
13. 2 процесса возвращают 10, 18, которые мы присваиваем output.
14. output имеет 2 элемента, поэтому мы выделяем пространство для 2 + 1 = 3 элемента для нового input.
15. набор input = [10 18 0]
16. n = len (input) = 3
17. m = n/2 = 1
18. output = [0]
19. Мы разбиваем один процесс, который получает [10 18]
20. Процесс возвращает 28, которые мы присваиваем output.
21. вывод имеет 1 элемент, так что мы закончили.

Answer 2

Рэй, трудно понять, что не так, не видя подробностей об ошибках. Если, как я подозреваю, это ошибки времени выполнения, можете ли вы запустить код под valgrind? valgrind чрезвычайно эффективно выявляет ошибки памяти; с вашим приложением вы захотите

valgrind --trace-children=yes ./coordinator 1 2 3 4

EDIT : ОК, с ошибками valgrind мы можем видеть, что (a) вы передаете что-то хитрое в printf (если вы скомпилируете с -g, вы получите точный номер строки ), а также вы звоните realloc, но не по указателю, который вы вернули с malloc. Может быть, вы сделали некоторую арифметику указателей?

Не могу сказать больше, не увидев код, но я надеюсь, что вам полезен valgrind.

Answer 3

У вас есть две ошибки:

1. for(i = 0; i < argc; i++)
2. while(calc > 0)

Answer 4

Попробуйте, если хотите изменить указатели.

void ChangePointers (int ** input, int ** output)

и

ChangePointers (& input, & output);