Description
Video Binary Quantization with Multi-threading
1. Goals
This assignment is designed to help you:
a. get familiar with multi-threaded programming with pthreads
b. get familiar with mutual exclusion enforcement with mutexes
2. Background
Quantization is a basic module in image/video compression aiming to achieve a compact data
representation of the original data. Considering a simple scenario of video capture and
quantization, the camera transmits captured frames with float values (between 0 and 1) to the
quantizer for quantization, in which the float values will be rounded to 0 or 1. The captured frame
is usually represented by a m×n matrix where m is the number of rows and n is the number of
columns. For simplicity, it is flattened into a one-dimension vector before being loaded into the
camera cache. Since the cache has limited size and could hold only a few frames, the camera feeds
data into the cache for quantization only when there is available space in the cache. Meanwhile,
the quantizer will quantize the frames stored in cache, print the quantization results, and delete the
quantized frames from the cache to save space for new frames.
3. Requirements
In this assignment, you are required to design and implement a multi-threaded C/C++ program using
pthreads and mutexes to simulate the simplified binary quantization as follows.
You are provided with a function generate_frame_vector() to generate flattened frames. The
prototype of the function is given below:
double* generate_frame_vector(int l);
The parameter l is the length of the flattened frame which equals m×n. In this assignment, we
set m = 4, n = 2 and thus l = 8. The function returns a one-dimension array with length l,
denoted as a pointer to the type double.
The camera cache is implemented as a first-in-first-out (FIFO) queue. Each entry in the cache
can store a flattened frame (a linear array) and the cache size is 5 frames. You need to
implement your own queue data structure and its related functions which means that you
cannot use the queue data structure provided by the C/C++ library.
The camera thread is created to load frames into the cache. Specifically, the camera thread
checks the cache every interval seconds, which is a program input parameter. If the cache
is not full, the camera thread calls generate_frame_vector() to generate one flattened frame and
loads the frame into the cache. Otherwise, the camera thread retries after interval
seconds. After a certain number of frames are generated, the function
generate_frame_vector() returns NULL and the camera thread ends.
The quantizer thread is created to perform data quantization in the cache. Specifically, the
quantizer thread continuously checks the cache. If the cache is not empty, the quantizer
thread quantizes one frame in the cache in arrival order. Note that the quantization has to be
done in place, which means that the quantizer thread modifies the data in the cache directly.
The quantization takes 3 seconds per frame. After quantization, the quantizer thread prints the
quantization result on the screen (see Input/Output Sample below) and deletes the quantized
frame from the cache. If the cache is empty, the quantizer thread checks again after 1 second.
When the quantizer thread finds the cache empty in 3 consecutive checks, it is assumed that all
frames are quantized and the quantizer thread ends.
CS3103 Operating Systems Programming Assignment 2
The data quantization operation is defined as follows:
A = (𝑎1, 𝑎2, … , 𝑎𝑙
)
0.0 ≤ 𝑎𝑖 ≤ 1.0,𝑖 = 1,2, … , 𝑙
where the vector A represents a flattened frame and the quantization on A is expressed as
follows:
𝑎𝑖
′ = {
0 𝑎𝑖 ≤ 0.5
1 𝑎𝑖 > 0.5
, 1 ≤ i ≤ 𝑙
Since both threads need to access some shared resources such as variable or data structure, the
code segment for accessing these shared resources which is a critical section must be protected
with a mutex.
4. Important Notes
You are required to implement your solution in C/C++ on Linux (other languages are NOT
allowed). Your work will be tested on the Linux server cs3103-01.cs.cityu.edu.hk.
The function generate_frame_vector() is provided in the file generate_frame_vector.cpp.
Compile it along with your source code (See Input/Output Sample below). Do not copy the
code to your own file. In fact, you only need to declare its prototype (see Requirements above)
in your code, outside main() just like declaring a normal function.
5. Input/Output Sample
Your program needs to accept one integer input, interval in seconds, and the output must be
formatted as shown below.
$ g++ generate_frame_vector.cpp 51234567.cpp –lpthread –o 51234567
$ ./51234567 2
1.0 0.0 0.0 0.0 1.0 1.0 0.0 1.0
0.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0
1.0 1.0 1.0 1.0 0.0 1.0 0.0 1.0
6. Marking Scheme
Your program will be tested on our CSLab Linux servers (cs3103-01, cs3103-02, cs3103-03). You
should describe clearly how to compile and run your program in the readme file. If an executable
file cannot be generated and running successfully on our Linux servers, it will be considered as
unsuccessful. If the program can be run successfully, your program will be graded according to the
following marking scheme.
Design and use of multithreading (30%)
Thread-safe multithreaded design and correct use of thread-management functions
Non-multithreaded implementation (0%)
Design and use of mutexes (30%)
Complete, correct and non-excessive use of mutexes
No or useless/unnecessary use of mutexes (0%)
Degree of concurrency (15%)
A design with higher concurrency is preferable to one with lower concurrency.
An example of lower concurrency: only one thread can access the cache at a time.
An example of higher concurrency: both threads can access the cache but works on different
frames (cache entries) at a time.
No concurrency (0%)
CS3103 Operating Systems Programming Assignment 2
Program correctness (15%)
Complete and correct implementation of other features such as
o correct logic and coding of thread functions and other functions such as quantization
o correct coding of queue and related operations
o passing parameter to the program on the command line
o program input and output conform to the format of the sample
o successful program termination
Fail to pass the g++ complier on our CSLab Linux servers to generate a runnable executable
file (0%)
Programming style and documentation (10%)
Good programming style
Clear comments in the program to describe the design and logic (no need to submit a
separate file for documentation)
Unreadable program without any comment (0%)
7. Bonus (20%)
Students who want to earn the bonus need to have their programs to satisfy the following additional
requirements and indicate this in the readme file.
Support two quantizer threads to allow two frames in the cache to be quantized concurrently.
The output order of the quantized frames on the screen must be consistent with the input order.
8. Submission
This assignment is to be done individually or by a group of two students. You are encouraged to
discuss the high-level design of your solution with your classmates but you must implement the
program on your own. Academic dishonesty such as copying another student’s work or allowing
another student to copy your work, is regarded as a serious academic offence.
Each submission consists of two files: a source program file (.cpp) and a readme text file (.txt),
telling us how to compile your program and possible outputs produced by your program.
Write down your name(s), eid(s) and student ID(s) in the first few lines of your program as
comment.
Use your student ID(s) to name your submitted files, such as 5xxxxxxx.cpp and 5xxxxxxx.txt for
individual submission, or 5xxxxxxx_5yyyyyyy.cpp and 5xxxxxxx_5yyyyyyy.txt for group
submission. You may ignore the version number appended by Canvas to your files. Only one
submission is required for each group.
Submit the files to Canvas. As far as you follow the above submission procedure, there is no
need to add comment to repeat your information in Canvas.
The deadline is 11:00 am, . No late submission will be accepted.
9. Question?
This is not a programming course. You are encouraged to debug the program on your own first.
If you have any questions, please submit your questions to the Discussion board “Programming
Assignment #2”.
To avoid possible plagiarism, do not post your source code on the Discussion board.
