Operating Systems Programming assignment 3. Multithread.

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

Computer Architecture and Technology Area

Universidad Carlos III de Madrid

Operating Systems

Programming assignment 3. Multithread. 

Bachelor’s Degree in Computer Science and Engineering

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

Index

1. Practice statement....................................................................................................................2

2. Description of the programming assignment..........................................................................3

2.1 Cost calculation Manager in computer center...................................................................4

2.2 N-Producers & 1-Consumer..............................................................................................5

2.2.1 Queue on a circular buffer..........................................................................................6

2.3 Auto-correction..................................................................................................................7

3. Submission..............................................................................................................................8

3.1 Deadline.............................................................................................................................8

3.2 Submission........................................................................................................................8

3.3 Files to be submitted..........................................................................................................8

4. Rules......................................................................................................................................10

5. Appendix...............................................................................................................................11

5.1 man function....................................................................................................................11

6. Bibliography..........................................................................................................................12

1

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

1. Practice statement

This programming assignment allows the student to become familiar with services used

for process management provided by POSIX.

For the management of lightweight processes (threads), the functions pthread_create,

pthread_join, pthread_exit, will be used and, mutex and conditional variable will be used

for the synchronization between them. 

 pthread_create: creates a new thread that executes a function that is indicated as

an argument in the call.

 pthread_join: waits for a thread that must end and that is indicated as an argument

in the call.

 pthread_exit: ends the execution of the process that makes the call.

The student must design and implement in C and for LINUX operating systems, a

program that acts as a manufacturing process manager. It will include several processes that

will be in charge of managing different phases of the factory and a process that will be in

charge of planning the different phases. 

2

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

2. Description of the programming assignment

The objective of this programming assignment is to code a concurrent multi-threaded

system that calculates the cost of using the machines in a processing center. Given a file with

a specific format, you must calculate how much to charge the customer according to the type

of machines he wants to use, as well as the time he wants to use them. 

To realize the functionality, it is recommended to implement two basic functions, which

represent the roles of the program:

 Producer: It will be the function executed by the threads in charge of adding elements

in the shared circular queue.

 Consumer: It will be the function executed by the thread in charge of extracting

elements from the shared circular queue.

In this way, the program will have the following behavior:

Illustration 1. Example of operation with N producers, 1 consumer and a buffer.

I. The main thread will be the one in charge of:

a) Read the input arguments.

b) Load the data from the file provided into memory.

c) Distribute the file load among the number of producers threads indicated.

d) Launch the N producers and the consumer.

e) Wait for the finalization of all the threads and show the total calculated cost (result 

of waiting for the finalization of the consumer thread).

3

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

II. Each producer thread must:

a) Obtain the data extracted from the file and insert them, one by one, in the circular 

buffer.

b) This task must be executed concurrently with the other producers, as well as the 

consumer. Under no circumstances may the threads be left "manually" blocked or 

an order forced between them (e.g. waiting for a thread to insert all its elements, or

those that fit in the queue, and then giving way to the consumer to remove them; 

then giving way to the next producer, etc.).

III. The consumer thread must:

a) Obtain concurrently, the elements inserted in the queue.

b) Each extracted element represents a type of machine and the time of use. 

Therefore, the consumer must calculate the cost and accumulate it until all the 

elements have been processed.

c) Once all the elements have been processed, the thread will finish its execution by 

returning the total calculated cost to the main thread. 

2.1 Cost calculation Manager in computer center

The main program will import arguments and data from the indicated file. To do this, it

must be considered that the execution of the program will be as follows:

./calculator

The label corresponds to the name of the file to be imported. The label

to generate. Finally, the label is an integer that indicates the size of the circular

queue (maximum number of elements that can be stored).

Additionally, the input file must have the following format:

4

500

1 1 4

2 2 12

3 1 100

4 3 45

...

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

The first line of the file represents the number of operations to be calculated. There can be

more operations in the file, but only those indicated by this value should be processed. Under

any circumstances there may be fewer operations in the file than operations indicated by the

first value. 

The rest of the lines in the file represent an operation:

use>. These are three integer values separated by a space and ending in a line break. The

is consecutive: it increases with each operation. The represents

whether it is a common node (cost 1 €/minute), a computation node (cost 3 €/minute), or a

super-computer (cost 10 €/minute). The last value represents the time of use. With all this, the

total cost to be calculated by the consumer is ∑(type*time).

The main process must load the information contained in the file into memory for further

processing by the producers. To do this, it is recommended to use the scanf function and the

dynamic memory reserve with malloc (and free for later free up). The idea is:

1. Obtain the number of operations (first value in the file).

2. Reserve memory for all those operations with malloc.

3. Store the operations in the array.

4. Distribute the operations among the producers:

a) To simplify the task, it is recommended to make a distribution of the operations, so

that each producer thread knows in which position to start processing and in which

position to finish. 

b) In this way each thread is aware of when it must finish its execution.

c) To do this, arguments can be passed to each producer thread at launch with

pthread_create.

5. After processing the threads, free the reserved memory with free.

NOTE: To store the data from the file, an array of structures can be generated. It is also

recommended to use a structure for passing parameters to the threads. 

An example of the program output is shown below:

5

$> ./calculator input_file 5 10

Total: 234234 €.

$>

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

2.2 N-Producers & 1-Consumer

The problem to be implemented is a classic example of process synchronization: when

sharing a shared queue (circular buffer), it is necessary to control the concurrency when

depositing objects in it, and when extracting them. 

For the implementation of the producers threads it is recommended that the function

follows the following scheme for simplicity:

1. Obtain the indexes to be accessed from the data in the file. It is recommended to

pass parameters to the thread.

2. Loop from the beginning to the end of the operations that should be processed:

a) Obtain the operation data.

b) Create an element with the operation data to insert in the queue.

c) Insert element in the queue.

3. End the thread with pthread_exit.

For the implementation of the consumer thread it is recommended to follow a similar

scheme to the previous one for simplicity:

1. Extract element from the queue.

2. Process the cost of the operation and accumulate it.

3. When all the operations have been processed, finish the thread with

pthread_exit returning the total cost calculated.

NOTE: Mutex and condition variables must be used for concurrency control.

Concurrency can be managed in the producer and consumer functions, or in the circular queue

code (in queue.c). The choice is of the practice group. 

2.2.1 Queue on a circular buffer

Communication between producers and consumers will be implemented through a

circular queue shared. Since changes to this element will constantly occur, mechanisms for

the control of concurrency must be implemented for light processes. 

The circular queue and its functions must be implemented in a file called queue.c, and it

must contain at least the following functions 

6

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

 queue* queue_init (int num_elements): function that creates the queue and

reserves the size specified as a parameter.

 int queue_destroy (queue* q): function that removes the queue and frees up all

assigned resources.

 int queue_put (queue* q , struct element * ele): function that inserts elements

in the queue if there is space available. If there is no space available, it must wait

until the insertion can be done.

 struct element * queue_get (queue* q): function that extracts elements from the

queue if it is not empty. If the queue is empty, it must wait until an element is

available.

 int queue_empty (queue* q): function that consults the status of the queue and

determines if it is empty (return 1) or not (return 0)

 int queue_full (queue* q): function that consults the status of the queue and

determines if it is full (return 1) or still has available positions (return 0).

The implementation of this queue must be done in such a way that there are no

concurrency problems between the threads that are working with it. To do this you should use

the proposed mechanisms of mutex and condition variables.

The object to be stored and extracted from the circular queue must correspond to a defined

structure with at least the following fields:

 int type: 1 if it is a common node; 2 if it is a computation node; 3 if it is a

super computer.

 int time: represents the time that the machine will be used with the

characteristics defined by type.

2.3 Auto-correction

The support code includes a automatic corrector related to the correction of the program

functionality. To run the corrector it is necessary to compress the source files requested in the

delivery in a ZIP and give it the appropriate name. Then, the correction script must be

executed: ./corrector_ssoo_p3.sh

NOTE: It is also possible to generate new files (recommended), and to perform new tests on

them.

7

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

3. Submission

3.1 Deadline

The deadline for the delivery of this programming assignment in AULA GLOBAL will be

Friday 8th May (until 23:55h).

3.2 Submission

The submission must be done using Aula Global using the links available in the first

assignment section. The submission must be done separately for the code and using

TURNITIN for the report.

3.3 Files to be submitted

You must submit the code in a zip compressed file with name

ssoo_p3_AAA_BBB_CCC.zip where A…A, B…B and C...C are the student identification

numbers of the group. The file to be submitted must contain, in addition to the files generated

by the student:

 costCalculator.c

 queue.c

 queue.h: 

 Makefile

 Authors.txt: file in csv format with one author on each line: NIA, Surname, First

name.

The report must be submitted in a PDF file through TURNITIN. Notice that only PDF files

will be reviewed and marked. The file must be named ssoo_p3_AAA_BBB_CCC.pdf. A

minimum report must contain:

 Cover with the authors (including the complete name, NIA, number of group and

email address).

 Table of contents: with navigation options to the sections indicated by the titles.

 Description of the code detailing the main functions and functionalities it is

composed of. Do not include any source code in the report.

8

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

 Tests cases used and the obtained results. All test cases must be accompanied by a

description with the motivation behind the tests. In this respect, there are three

clarifications to take into account.

◦ Avoid duplicated tests that target the same code paths with equivalent

inputparameters.

◦ Passing a single test does guarantee the maximum marks. This section will be

marked according to the level of test coverage of each program, nor the number of

tests per program.

◦ Compiling without warnings does not guarantee that the program fulfills the

requirements.

 Conclusions, describing the main problems found and how they have been solved.

Additionally, you can include any personal conclusions from the realization of this

assignment.

Additionally, marks will be given attending to the quality of the report. Consider that a 

minimum report:

 Must contain a title page with the name of the authors and their student

identification numbers.

 Must contain an index.

 Every page except the title page must be numbered.

 Text must be justified.

The maximum length of the report is 15 pages including cover and index. Do not

neglect the quality of the report as it is a significant part of the grade of each assignment.

NOTE: The memory delivery tool allows for a single delivery. The evaluation of this delivery

is the only valid and definitive one.

9

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

4. Rules

1) Programs that do not compile or do not satisfy the requirements will receive a

mark of zero.

2) Special attention will be given to detecting copied functionalities between two

practices. In case of finding common implementations in two practices, the

students involved (copied and copiers) will lose the grades obtained by

continuous evaluation.

3) All programs should compile without reporting any warnings.

4) The programs must run under a Linux system, the practice is not allowed for

Windows systems. In addition, to ensure the correct functioning of the practice,

its compilation and execution should be checked in the university computer labs

or on the guernika.lab.inf.uc3m.es server. If the code presented does not compile

or does not work on these platforms the implementation will not be considered

correct. 

5) Programs without comments will receive a grade of 0.

6) The assignment must be submitted using the available links in Aula Global.

Submitting the assignments by mail is not allowed without prior authorization.

7) It is mandatory to follow the input and output formats indicated in each program

implemented. In case this is not fulfilled there will be a penalization to the mark

obtained.

8) It is mandatory to implement error handling methods in each of the programs.

Failing to follow these rules will be translated into zero marks in the affected

programs.

10

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

5. Appendix

5.1 man function

man is a command that formats and displays the online manual pages of the different

commands, libraries and functions of the operating system. If a section is specified, man only

shows information about name in that section. Syntax:

$ man [section] name

The pages used as arguments when running man are usually names of programs, utilities

or functions. Normally, the search is performed on all available man sections in a

predetermined order, and only the first page found is presented, even if that page is in several

sections.

A manual page has several parts. These are labeled NAME, SYNOPSIS, DESCRIPTION,

OPTIONS, FILES, SEE ALSO, BUGS, and AUTHOR. The SYNOPSIS label lists the

libraries (identified by the #include directive) that must be included in the user's C program in

order to make use of the corresponding functions. The utilization of man is recommended for

the realization of all lab assignments. To exit a man page, press q.

The most common ways of using man are:

1. man section element: It presents the element page available in the section of the manual.

2. man –a element: It presents, sequentially, all the element pages available in the manual.

Between page and page you can decide whether to jump to the next or get out of the pager

completely.

3. man –k keyword It searches the keyword in the brief descriptions and manual pages and

present the ones that coincide. 

11

Bachelor’s Degree in Computer

Science and Engineering

Operating Systems (2019-2020)

Programming assignment 3 -

Multithread

6. Bibliography

 El lenguaje de programación C: diseño e implementación de programas Félix García,

Jesús Carretero, Javier Fernández y Alejandro Calderón. Prentice-Hall, 2002.

 The UNIX System S.R. Bourne Addison-Wesley, 1983.

 Advanced UNIX Programming M.J. Rochkind Prentice-Hall, 1985.

 Sistemas Operativos: Una visión aplicada Jesús Carretero, Félix García, Pedro de

Miguel y Fernando Pérez. McGraw-Hill, 2001.

 Programming Utilities and Libraries SUN Microsystems, 1990.

 Unix man pages (man function)