User Tools

Site Tools


os:lab06
Return to Home page

Return to Operationg Systems home


Operating Systems Course: Lab06

Laboratory number 06

Exercise 01: From recursion to concurrency

The program named 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

pgrm n strA strB

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:

5
102
99
34
234
25

The program, after the generation of the n names of the two input and output files, activates n threads.

Each thread:

  1. reads from “its” input files the integer vector
  2. sorts (with a sorting algorithm of your choice) the vector with a numeric sort, and in an increasing order
  3. saves the result in “its” corresponding output file

Note that the program implements the following precedence graph:

    Mi---------
    /\        |  
   /  \       |
  R1    R2   ...
  |     |
  O1    O2   ...
  |     |
  W1    W2   ...
   \  /
    \/        |
    Mf---------

where:

  1. Mi and Mf are the initial and final operations of the main
  2. The flows Ri, Oi and Wi represent the execution of the threads, each of which
    1. read its input file (Ri)
    2. sort it (Oi)
    3. 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:

  1. each thread reads and sorts the data stored in a file (but it does not write the results on an output file)
  2. 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
  3. 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?do=
/web/htdocs/www.skenz.it/home/data/pages/os/lab06.txt · Last modified: 2022/11/22 11:04 by zioskenz