Díficil: Quicksort con fork...
Publicado por Alonso Guillén (2 intervenciones) el 19/03/2001 23:11:54
Hola amigos, soy un estudiante de programación y recién empecé a estudiar programación con C para UNIX, con llamadas al sistema, comunicación entre procesos... Mi profesor me propuso que resuelva un problema propuesto por una Universidad gringa, es este:
Write a sorting program using Quicksort Algorithm(in case you have forgotten, see any standard C book (e.g. Kernighan Ritchie)). For each recursive call to quicksort, you should fork(system call : fork) a new process which should sort the subpart of the original array to be sorted. The child processes should use message passing mechanism(system calls : msgctl, msgget, msgop) to pass the sorted subarray back to the parent.
This kind of forking will form a tree of processes. Each process should get the sorted subarrays from the child, combine them, and pass to its own parent. The root process should output the sorted result to the terminal.
(To find out detailed information on any of the above system calls, just type 'man systemcall' on '$' prompt. i.e. you can use 'man msgctl' to find out the header file, as well as function prototype, and description of the arguments for the system call 'msgctl').
Run the program on following sequences:
1,2,3,....... (sorted)
9999, 9998,9997,......(reverse sorted)
1,8,54,89,5432, 4523, 5, ..... ( a random sequence)
1,1000, 2, 1001,3, 1002,..... (merged)
Your program wont work for large sequences (as the number of processes that you fork will consume all the system resources, and new process wont get created)(Hint: fork() will return -1, if the new process can not be created).
Write a sorting program using Quicksort Algorithm(in case you have forgotten, see any standard C book (e.g. Kernighan Ritchie)). For each recursive call to quicksort, you should fork(system call : fork) a new process which should sort the subpart of the original array to be sorted. The child processes should use message passing mechanism(system calls : msgctl, msgget, msgop) to pass the sorted subarray back to the parent.
This kind of forking will form a tree of processes. Each process should get the sorted subarrays from the child, combine them, and pass to its own parent. The root process should output the sorted result to the terminal.
(To find out detailed information on any of the above system calls, just type 'man systemcall' on '$' prompt. i.e. you can use 'man msgctl' to find out the header file, as well as function prototype, and description of the arguments for the system call 'msgctl').
Run the program on following sequences:
1,2,3,....... (sorted)
9999, 9998,9997,......(reverse sorted)
1,8,54,89,5432, 4523, 5, ..... ( a random sequence)
1,1000, 2, 1001,3, 1002,..... (merged)
Your program wont work for large sequences (as the number of processes that you fork will consume all the system resources, and new process wont get created)(Hint: fork() will return -1, if the new process can not be created).
Valora esta pregunta
0