Return to Home page

Differences

This shows you the differences between two versions of the page.

@@ Line 1: / Line 1: @@
+Return to [[os:|Operationg Systems home]]
+----
+====== Operating Systems Course: Lab06 ======
+===== Laboratory number 06 =====
+==== Exercise 01: From recursion to concurrency ====
+The program named [[https://www.skenz.it/listing/os/lab/lab06e01recursive.c|lab06e01recursive.c]] receives from the command line an integer value ''n'' and, using recursion (see funcition ''binary''), it generates and visualizes all the binary numbers of ''n'' bits.
+Transform the program from recursive to concurrent, i.e., substitute the recursive implementation with the generation (by means of a ''fork()'') of an adequate number of processes capable of printing the binary numbers (the order is not important).
+==== Exercise 02: Concurrent file sorting ====
+Implement a concurrent program with ''n'' threads that sorts an input file. The program must proceed in parallel on different files, according to the following specifications.
+The program (which name ''pgrm'') receives 3 parameters from command line
+<code bash>
+pgrm n strA strB
+</code>
+where:
+  * ''n'' is an integer value
+  * ''strA'' is a string that identifies the name of ''n'' input files of name 'strA1.txt, strA2.txt, ..., strAn.txt'
+  * ''strB'' is a string that identifies the name of ''n'' output files of name 'strB1.txt, strB2.txt, ..., strBn.txt'
+The input files ''strA'' contain:
+  * in the first row, the number of integer numbers stored in the lines following the first
+  * in the following rows, the integer numbers.
+The following is an example of correct file:
+<code strA1.txt>
+</code>
+The program, after the generation of the ''n'' names of the two input and output files, activates ''n'' threads.
+Each thread:
+  - reads from "its" input files the integer vector
+  - sorts (with a sorting algorithm of your choice) the vector with a numeric sort, and in an //increasing// order
+  - saves the result in "its" corresponding output file
+Note that the program implements the following //precedence graph//:
+<code txt>
+    Mi---------
+    /\        |
+   /  \       |
+  R1    R2   ...
+  |     |
+  O1    O2   ...
+  |     |
+  W1    W2   ...
+   \  /
+    \/        |
+    Mf---------
+</code>
+where:
+  - Mi and Mf are the initial and final operations of the main
+  - The flows Ri, Oi and Wi represent the execution of the threads, each of which
+    - read its input file (Ri)
+    - sort it (Oi)
+    - save it in its output file (Wi).
+==== Exercise 03: Concurrent file sorting and merging ====
+Modify the previous program in a way that the ''n'' sorted sequences (read from file) are merged to generate a single ordered sequence.
+More in detail:
+  - each thread reads and sorts the data stored in a file (but it does **not** write the results on an output file)
+  - the ''main()'', after executing the threads, waits for their termination, and after the termination of one of them, it starts the //merging// of the data just ordered with those merged previously
+  - once all threads are terminated and all the sequences have been //merged//, the main stores the entire list of ordered data into a (single) output file.
+The third command line parameter of the program indicates the name of the output file.
+For simplicity (to allocate the data structure) it is possible to suppose that all the files store the same number of values and, eventually, this number is known a priori.
+=== Suggestions ===
+Use a matrix to store the data read by the input files, and dedicate a row (or a column) to each file (or, alternatively, a vector of structures with a vector field).
+Each thread manipulates exclusively its //own// row (or column) of the matrix (or element of the vector).
+The ''main()'' perform the merge of the sequences sorted in pair:
+  * at the termination of the first thread, it merges ''0'' (zero) data with ''n'' data
+  * at the termination of the second thread, it merges ''n'' old data with ''n'' new data
+  * at the termination of the third thread, it merges ''2*n'' old data with ''n'' new data
+  * ...
+The ''main()'' can make use of one or more support vector for the merging of the matrix data.

If you found any error, or if you want to partecipate to the editing of this wiki, please contact: admin [at] skenz.it

You can reuse, distribute or modify the content of this page, but you must cite in any document (or webpage) this url: https://www.skenz.it/os/lab06?rev=1574661824&do=diff