# CS4328 – Operating Systems Program Assignment #1 solved

\$35.00

## Description

5/5 - (1 vote)

Overview
OpenMP. There are three independent parts of this project. Please read instructions carefully.
You must submit your project in one zip file (named as firstname_lastname_proj1) to the Project Turn In
Site (https://hwupload.cs.txstate.edu/), which should include all your source code for part1, part2, part 3
and the according doc file for part 2 and part3 questions. You only need to submit a hard copy of the doc
file in class on Oct. 23. Do not print out the code.
The submission system will automatically record your submission time, which will be used to decide
whether or not you miss the deadline. There will be a penalty of 20% per day (including weekend and
holiday) for late submission. The late submission after two days (including weekend and holiday) will not
be accepted. Therefore, DO NOT DELAY. Start writing the program from Day 1. If you wait until the
night before the due date, you will have a miserable night and it is less likely you could complete the
project.
You are encouraged to discuss with other students but you have to DO YOUR OWN WORK. You may
get ZERO for this project or FAIL the class if you copy code from others or allow others to copy your
code.
Part 1: Implement Fibonacci Sequence using Pthreads and Win32 Thread (50 points).
The Fibonacci sequence is the series of numbers 0, 1, 1, 2, 3, 5, 8, …. Formally, it can be expressed as:
That is, after two starting values, each number is the sum of the two preceding numbers. The Fibonacci
numbers for n = 0, 1, 2, … ,20 are:
F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19 F20
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
Part 1a (25 points): Write a multithreaded program that generates the Fibonacci sequence using
Pthreads. This program should work as follows: The user will enter on the command line the number of
Fibonacci numbers that the program is to generate. The program will then create a separate thread that
will generate the Fibonacci numbers, placing the sequence in data that can be shared by the threads (an
array is probably the most convenient data structure). When the thread finishes execution, the parent
outputting the Fibonacci sequence until the child thread finishes, this will require having the parent thread
wait for the child thread to finish, using the thread join techniques described in class.
Part 1b (25 points): Write a multithreaded program that does the same Fibonacci calculate as stated in
Part 2 a: Implement Matrix Multiplication using Pthreads (30 points)
Background of Matrix Multiplication
Given two matrices, A and B, where matrix A contains M rows and K columns and matrix B contains K
rows and N columns, the matrix product of A and B is matrix C, where C contains M rows and N
columns. The entry in matrix C for row i, column j, denoted as Ci,j, is the sum of the products of the
elements for row i in matrix A and column j in matrix B. That is,

For example, if A is a 2-by-3 matrix and B is a 3-by-2 matrix, the result matrix will be a 2-by-2 matrix.
The parent thread will create M ×N worker threads, passing each worker the values of row i and column j
that it is to use in calculating the matrix product. This requires passing two parameters to each thread. The
easiest approach with Pthreads is to create a data structure using a struct. The members of this structure
are i and j, and the structure appears as follows:
/* structure for passing data to threads */
Struct v
{
int i ; /* row */
int j ; /* column */
};
The Pthreads program will create the worker threads using a strategy similar to that shown below:
/* We have to create M ×N worker threads */
for ( i = 0; i < M, i++) for ( j = 0; j < N; j++ ) { struct v *data = (struct v *) malloc (sizeof (struct v)) ; data->i = i
data->j = j
/* Now create the thread passing its data as a parameter */
}
}
The data pointer will be passed to the pthread_create (), which in turn will pass it as a parameter to the
function that is to run as a separate thread.
Once all worker threads have completed, the main thread will output the product contained in matrix C.
This requires the main thread to wait for all worker threads to finish before it can output the value of the
matrix product. Several different strategies can be used to enable a thread to wait for other threads to
finish. In this example, the main thread has to wait for multiple threads to finish before it can continue its
execution.
The following code shows how you could join on ten threads using the Pthreads: