Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Программирование под Unix/Linux > сортировка строки, используя fork() и pipe

Автор: awake 14.5.2012, 10:52

Дали задание используя системный вызов fork() и pipe. Решить какую-то задачу.
Я решил сделать "сортировку пузырьком".
Вот код

Код


#include <string.h>
#include <stdio.h>
#include <stdlib.h>

void bubble(char *items, int count);

int main(void)
{
  char s[255];

  printf("Input string:");
  gets(s);
  bubble(s, strlen(s));
  printf("Sorted string: %s.\n", s);

  return 0;
}
/* Пузырьковая сортировка. */
void bubble(char *items, int count)
{
  int a, b;
  char t;

  for(a=1; a < count; ++a)
    for(b=count-1; b >= a; --b) {
      if(items[b-1] > items[b]) {
        /* exchange elements */
        t = items[b-1];
        items[b-1] = items[b];
        items[b] = t;
      }
    }
}

А как теперь этот код передалать используя fork() и pipe.

Если я правильно понял задание то нужно создать процесс(потомок) , используя fork(), затем отсортировать сроку и записать её в канал(write), а затем сам результат прочитать в Родителе(read).

Я вот немного не пойму в где производить саму сортировку. в Потомке или в Родителе? и как правильно всё туда записать?

Автор: xvr 14.5.2012, 14:05

Цитата(awake @ 14.5.2012, 10:52

)

Я решил сделать "сортировку пузырьком".

Не самый удачный выбор. Нужно делать то, что можно легко распараллелить. Пузырек не параллелится. Лучше возьмите QuickSort, если уж хочется что то посортировать

Автор: sergioK1 14.5.2012, 20:58

Цитата(awake @ 14.5.2012, 09:52)

А как теперь этот код передалать используя fork() и pipe.

ну как то так

Код


 int status;
 char s[255];
  char    readbuffer[255];
 int     fd[2], nbytes;
  printf("Input string:");
  gets(s);

  printf("Sorted string: %s.\n", s);
 pipe(fd);
int pid=fork();
if(pid<0)
{
/*error code*/
}
else if(pid==0)
{
     bubble(s, strlen(s));
        close(fd[0]);
      write(fd[1], s, (strlen(s)+1));
     exit(0);

}
else{
waitpid(pid,&status,0);
   int nbytes = read(fd[0], readbuffer, sizeof(readbuffer));
     printf("Received string: %s", readbuffer);
    close (fd[1]);
/* parent work */
}

хотя на компе не проверял , лины нет под рукой

xvr
Не понял ваш пост
Какая разница какой алгоритм потомок юзает ?, главное что результат был в трубе, и папа его вытащит

Автор: xvr 15.5.2012, 10:27

Цитата(sergioK1 @ 14.5.2012, 20:58

)

Не понял ваш пост

У меня есть подозрение, что от ТС хотели параллельной сортировки (ну или чего то параллельного), а не 'общения через трубу'. Т.к. первое еще имеет какой то смысл, а второе никакого смысла не имеет smile

Автор: awake 15.5.2012, 12:16

Цитата(xvr @ 15.5.2012, 10:27)

Цитата(sergioK1 @ 14.5.2012, 20:58

)

Не понял ваш пост

Да вы правы мне действительно нужна параллельная сортировка.И "пузырёк" не подходит. По вашему совету думаю взять "быструю сортировку".

Как я понял часть сортировки нужно реализовать в потомке, а затем через трубу отправить результат для дальнейшей сортировки в родителе.
Или сортировку реализовать в 2 потомках а затем результаты их сортировки отправить через трубу родителю.

А как правильно это сделать? Не могли бы вы привести пример.

Автор: sergioK1 15.5.2012, 13:21

Цитата(awake @ 15.5.2012, 11:16)

Или сортировку реализовать в 2 потомках а затем результаты их сортировки отправить через трубу родителю.

это логичнее IMHO.
каждый процесс занимаеться своей задачей,
в реальных системах - один програмист "сортирует", другой "соединяет "

Автор: xvr 15.5.2012, 17:06

Цитата(awake @ 15.5.2012, 12:16

)

Как я понял часть сортировки нужно реализовать в потомке, а затем через трубу отправить результат для дальнейшей сортировки в родителе.
Или сортировку реализовать в 2 потомках а затем результаты их сортировки отправить через трубу родителю.

Быстрая сортировка вещь рекурсивная и в принципе паралельная. Сначала пробегаете массив и ищите середину (с обменом байтов). Потом делаете fork, и в новом процессе запускаете себя рекурсивно на 1ю часть массива, а в родителе продолжаете со 2й частью. По окончанию новый процесс отправляет родителю свою отсортированную часть через pipe, а родитель ждет ее, присоединяет 2ю часть массива и завершается (или отправляет через pipe то, что получилось своему родителю)

PS. pipe можно использовать для всех процессов один