Description
Project 1: Multithreaded Programming and Synchronization CECS 326
1. Summary
The first project is regarding several important topics on process management. But instead of
developing it in kernel, we will do it in user space using a widely-used threads programming
interface, POSIX Threads (Pthreads). You should implement this in Linux, which supports Pthreads
as part of the GNU C library.
2. Description
In this assignment, you will be working with the “threads”‘ subsystem of Linux. This is the part of
Linux that supports multiple concurrent activities within the kernel. In the exercises below, you
will write a simple program that creates multiple threads, you will demonstrate the problems that
arise when multiple threads perform unsynchronized access to shared data, and you will rectify
these problems by introducing synchronization (in the form of Pthreads mutex) into the code.
2.1 Environment Set Up
It’s recommendable to use Ubuntu as operating system to accomplish this project. Ubuntu is an
open source operating system software for computers. It is one of the distribution systems of Linux,
and is based on the Debian architecture. For those who don’t have Ubuntu installed in their
computers, it’s doable to use virtual machine and install the virtual Ubuntu in your Local operating
system.
For virtual machine, it’s recommendable to use VirtualBox:
https://www.virtualbox.org/wiki/Downloads
If you have Windows operating system installed with your computer, try to download “Windows
hosts”; if you use Mac, try to download “OS X hosts”.
After you download and install VirtualBox in your computer, next step is to download the .iso file
of Ubuntu from the official website (You can choose a new version):
https://www.ubuntu.com/download/desktop
When you finish downloading the .iso file of Ubuntu, then it’s time to install a virtual Ubuntu in
your virtual machine.
To do this, first you need to open VirtualBox, then click “New”:
In the configuration window, you need to set a name for your virtual Ubuntu, select “Linux” for
“Type”, and select “Ubuntu(64-bit)” for “Version”:
Select the amount of memory for your virtual Ubuntu.
Here we recommend 2GB:
In this window, select “Create a virtual hard disk now”, then click “Create”:
Click “Next” in this configuration window:
In this configuration window, you can select “Dynamically allocated”, which can make your
allocated storage of the virtual Ubuntu grows if it fills up (up to a size that you will configure in
the next step); or you can select “Fixed size” and then configure a size of storage for your virtual
Ubuntu:
Set a size for your virtual Ubuntu. Here we set 20GB, then “Create”:
At this point, we have finished the configuration. Now you can see your virtual Ubuntu has been
created in the left menu. Next you need to click “Start”:
After starting, VirtualBox will ask you to “select start-up disk”, which means you need to select
the .iso file of Ubuntu that you just download, then click “Start”:
Now it’s time to install Ubuntu in VirtualBox. Click “Install Ubuntu”:
Click “Continue”:
Click “Install Now” and then “Continue”:
Click “Continue” for both of them:
Set up your name, computer’s name, username and password for your virtual Ubuntu, then
“Continue”:
After finishing installation, click “Restart Now”:
If you get a message “Please remove the medium and press ENTER”, just simply do so or shut
down your virtual machine and start it again.
Now you get your virtual Ubuntu installed, next you can continue working on this project with it.
2.2 Simple Multi-Thread Programming
The purpose of this exercise is for you to get some experience using the threads primitives provided
by Pthreads [1], and to demonstrate what happens if concurrently executing threads access shared
variables without proper synchronization. Then you will use the mutex synchronization primitives
in Pthreads to achieve proper synchronization.
Step 1: Simple Multi-Thread Programming without Synchronization
First, you need to write a C program using the Pthreads library that forks a few threads each
executes the loop in the SimpleThread function below. The number of threads is a command line
parameter of your program. All the threads modify a shared variable SharedVariable and display
its value within and after the loop.
Your program must validate the command line parameter to make sure that it is a number, not an
arbitrary string.
Your program must be able to run properly with any reasonable number of threads (e.g., 200).
Try your program with the command line parameter set to 1, 2, 3, 4, and 5. Analyze and explain
the results. Put your explanation in your project report.
Step 2: Simple Multi-Thread Programming with Proper Synchronization
Modify your program by introducing Pthreads mutex variables, so that accesses to the shared
variable are properly synchronized. Try your synchronized version with the command line
parameter set to 1, 2, 3, 4, and 5. Accesses to the shared variables are properly synchronized if (i)
each iteration of the loop in SimpleThread() increments the variable by exactly one and (ii)
each thread sees the same final value. It is necessary to use a Pthreads barrier [2] in order to allow
all threads to wait for the last to exit the loop.
You must surround all your synchronization-related changes with preprocessor commands, so that
we can easily compile and get the version of your program developed in Step 1. E.g.,
One acceptable output of your program is (assuming 4 threads):
*** thread 0 sees value 0
*** thread 0 sees value 1
*** thread 0 sees value 2
*** thread 0 sees value 3
*** thread 0 sees value 4
*** thread 1 sees value 5
*** thread 1 sees value 6
*** thread 1 sees value 7
*** thread 1 sees value 8
*** thread 1 sees value 9
*** thread 2 sees value 10
*** thread 2 sees value 11
*** thread 2 sees value 12
*** thread 3 sees value 13
*** thread 3 sees value 14
*** thread 3 sees value 15
*** thread 3 sees value 16
*** thread 3 sees value 17
*** thread 2 sees value 18
*** thread 2 sees value 19
……
Thread 0 sees final value 80
Thread 2 sees final value 80
Thread 1 sees final value 80
Thread 3 sees final value 80
Step 3: The Required Deliverable Materials
(1) A README file, which describes how we can compile and run your code.
(2) Your source code, must include a Makefile and be submitted in the required format.
(3) A recorded video shows the details of execution and outputs of your design (must have
screenshot of the outputs with your identification info (the current time or your computer ID)).
(3) Your report, which discusses the design of your program without Pthreads synchronization
and the one with Pthreads synchronization, as well as the reason for the difference; includes your
processing of design and why to implement in this way.
3. Submission Requirements
You need to strictly follow the instructions listed below:
1) This is a group project, please submit a .zip/.rar file that contains all files, only one submission
from one group.
2) The submission should include your source code and project report. Do not submit your binary
code.
3) Make a video to record your code execution and outputs. The video should present your name
or time as identification.
4) Your code must be able to compile; otherwise, you will receive zero for the design part.
5) Your code should not produce anything else other than the required information in the output.
6) Your code must validate command line parameters to make sure that only numbers can be
accepted.
7) If you code is partially completed, also explain in the report what has been completed and the
status of the missing parts.
8) Provide sufficient comments in your code to help the TA understand your code. This is
important for you to get at least partial credit in case your submitted code does not work properly.
Grading criteria:
Details Points
Submission follows the right formats 5 pts
Have a README file shows how to compile and test your submission 5 pts
Submitted code has proper comments to show the design 10 pts
Screen a video to record code execution and outputs 10 pts
Have a report (pdf or word) file explains the details of your entire design 20 pts
Report contains clearly individual contributions of your groupmates 10 pts
Code can be compiled and shows correct outputs 40 pts
4. Policies
1) Late submissions will be graded based on our policy discussed in the course syllabus.
2) We encourage high-level discussions among the groups to help each other understand the
concepts and principles. However, any code-level discussion is prohibited. We will use antiplagiarism tools to detect violations of this policy.
5. Resources
The Pthreads tutorials at https://computing.llnl.gov/tutorials/pthreads and
https://pages.cs.wisc.edu/~travitch/pthreads_primer.html are good references to learn Pthreads
programming.
6. References
[1] POSIX Threads Programming: https://computing.llnl.gov/tutorials/pthreads/
[2] Pthreads Primer: https://pages.cs.wisc.edu/~travitch/pthreads_primer.html
[3] POSIX thread (pthread) libraries:
https://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html
Group Project 2: Application for Threads Sorting CECS 326
1. Summary
This project follows the topic of threads and asks you to design a real scenario/application with
multiple threads. You will use the threads programming interface, POSIX Threads (Pthreads). You
should implement this in Linux, which supports Pthreads as part of the GNU C library.
2. Description
This project asks to write a multithreaded sorting program that works as follows: A list of integers
is divided into two smaller lists of equal size. Two separate threads (which we will term sorting
threads) sort each sublist using a sorting algorithm of your choice. The two sublists are then merged
by a third thread—a merging thread—which merges the two sublists into a single sorted list. In the
above list, x is a placeholder for the student identifier.
Because global data are shared across all threads, perhaps the easiest way to set up the data is to
create a global array. Each sorting thread will work on one half of this array. A second global
array of the same size as the unsorted integer array will also be established. The merging thread
will then merge the two sublists into this second array.
Graphically, this program is structured as
in the below figure:
This programming project will require passing parameters to each of the sorting threads. In
particular, it will be necessary to identify the starting index from which each thread is to begin
sorting.
The parent thread will output the sorted array once all sorting threads have exited.
3: The Required Deliverable Materials
(1) A README file, which describes how we can compile and run your code.
(2) Your source code, you may use a Makefile and be submitted in the required format.
(3) Your report, which discusses the design of your program.
(4) A recorded video shows the output and runtime
3. Submission Requirements
You need to strictly follow the instructions listed below:
1) This is a group project, please submit a .zip/.rar file that contains all files, only one submission
from one group.
2) Make a video to record your code execution and outputs. The video should present your name
or time as identification.
3) The submission should include your source code and project report. Do not submit your binary
code. Project report should contain your groupmates name and ID.
4) Your code must be able to compile; otherwise, you will receive a grade of zero.
5) Your code should not produce anything else other than the required information in the output
file.
7) If you code is partially completed, please explain the details in the report what has been
completed and the status of the missing parts, we will grade it based on the entire performance.
8) Provide sufficient comments in your code to help the TA understand your code. This is
important for you to get at least partial credit in case your submitted code does not work properly.
Grading criteria:
Details Points
Have a README file shows how to compile and test your submission 5 pts
Submitted code has proper comments to show the design 5 pts
Screen a video to record code execution and outputs 10 pts
Have a report (pdf or word) file explains the details of your entire design 30 pts
Report contains clearly individual contributions of your group mates 5 pts
Code can be compiled and shows correct outputs 45 pts
4. Policies
1) Late submissions will be graded based on our policy discussed in the course syllabus.
2) Code-level discussion is prohibited. We will use anti-plagiarism tools to detect violations of
this policy.
5. Resources
The Pthreads tutorials at https://computing.llnl.gov/tutorials/pthreads and
https://pages.cs.wisc.edu/~travitch/pthreads_primer.html are good references to learn Pthreads
programming.
6. References
[1] POSIX Threads Programming: https://computing.llnl.gov/tutorials/pthreads/
[2] Pthreads Primer: https://pages.cs.wisc.edu/~travitch/pthreads_primer.html
[3] POSIX thread (pthread) libraries:
https://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html
Group Assignment 3: Paper Review CECS 326
1. Summary
This assignment requires to thoroughly review one high-quality research paper from famous
conferences or journals. You should select one interested paper from the given paper list and
summarize your review into a file.
2. Description
Reading a good research paper can greatly improve your perspective and interests for one
particular research area. Here list several papers that are from high qualified or famous conferences,
and each represents one excellent insight or improvement in a particular real problem.
Please only
select one paper from the below list:
• Taiji: managing global user traffic for large-scale internet services at the edge, SOSP’19.
• EdgeWise: A Better Stream Processing Engine for the Edge, ATC’19.
• Optimizing data-intensive computations in existing libraries with split annotations,
SOSP’19
• StreamBox-TZ: Secure Stream Analytics at the Edge with TrustZone, ATC’19
• Tangram: Bridging Immutable and Mutable Abstractions for Distributed Data Analytics,
ATC’19
• SR3: Customizable Recovery for Stateful Stream Processing Systems, Middleware’ 20
• HiveD: Sharing a GPU Cluster for Deep Learning with Guarantees, OSDI’20
• GrandSLAm: Guaranteeing SLAs for Jobs in Microservices Execution Frameworks,
Eurosys’19
• Efficient, Consistent Distributed Computation with Predictive Treaties, Eurosys’19
• GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs, Eurosys’19
• Twine: A Unified Cluster Management System for Shared Infrastructure, OSDI 20
• Ansor: Generating High-Performance Tensor Programs for Deep Learning, OSDI 20
• PipeSwitch: Fast Pipelined Context Switching for Deep Learning Applications, OSDI 20
• Unearthing inter-job dependencies for better cluster scheduling, OSDI 20
• KungFu: Making Training in Distributed Machine Learning Adaptive, OSDI 20
How to Get a Copy of Paper:
Once you’ve found the citation for a paper that is relevant to your advanced science project, the
next step is getting a copy so that you can read it. Some search engines provide links to free
online versions of the paper, if one exists.
There are several ways to find the paper or copies:
• Look for a free online version. Try searching for the full title of the paper in a regular search
engine like Google Scholar, Yahoo, or Microsoft Scholar. The paper may come up multiple
times, and one of those might be a free, downloadable copy. So, if the first link isn’t
downloadable, try another. Tips: For Google Scholar, click the “All # versions”, you may find
some versions can be freely accessed.
• Search directly for the homepage of the first or last author of the paper and see if he or she
has a PDF of the paper on his or her website. If so, you can download it directly from there.
Generally, it is only worth looking up the first author (the one who contributed the most to the
paper) or the last author (usually the professor in whose lab the work was done and who
supervised the science project).
• Go directly to the online homepage of the journal in which the paper was published. Some
scientific journals are “open-source,” meaning that their content is always free online to the
public. Others are free online (often after registering with the website) if the paper
• Utilize the CSULB network. You can utilize the “CSULB Library” (the link is in the above
table) to access the articles with your student account.
Reading Instructions:
Review the paper should concentrate on the motivation and the design methodology of the
proposed work. You should pay attention to the author’s motivation, design novelty, proposed
system/architecture, and comparison with previous work. You may skip the technical details that
you are not familiar with. You should focus on the improvement or novel part of the proposed
work.
2. Write Instructions
You should write the summary via Word or Latex. The submitted file must be a pdf format.
Component 1: Summary of paper
In this component, you should use one or two paragraphs to summarize the paper your read. You
should introduce the problem they provided, the design motivation, design novelty, proposed
architecture/methodology, and evaluated results.
Component 2: Your views or analysis
In this component, you should provide your analysis or perspectives about the paper. You should
comment on their proposed problem, discuss their design, and provide your own views about their
work. For example, you can point out the possible improvement of the proposed solution, or clarify
the drawback or inefficiency of their work from any point. You can also analyze the difference
from previous work, and show your perspective of their novelty, or classify the possible
shortcoming in their design. This component will be the majority part of your report.
Formats requirements:
• We will do similarity check. The accepted similarity must be less than 20%, otherwise it
will be taken as plagiarism.
• The length of your report is around 2 pages. (Except the title and name info, etc.)
• The font should be Times New Roman, Size 11, single line space, 0 bt in before or after
space, 8.5*11’.
• The submission only includes one pdf file, no other files should be submitted.
3. Grades Criteria:
Details Points
Submitted file with correct format. 10 pts
Typo identification. 10 pts
Detailed paper summary. 20 pts
Details of your analysis or discussion. 60 pts
Group Project 4: CPU scheduler CECS 326
1. Summary
This project follows the topic of CPU scheduling, where it requires to design and implement several
classic CPU scheduling algorithms.
2. Description
This project involves implementing several different process scheduling algorithms. The scheduler
will be assigned a predefined set of tasks and will schedule the tasks based on the selected
scheduling algorithm.
Each task is assigned a priority and CPU burst. The following scheduling
algorithms will be implemented:
• First-come, first-served (FCFS), which schedules tasks in the order in which they request
the CPU.
• Priority scheduling, which schedules tasks based on priority.
• Round-robin (RR) scheduling, where each task is run for a time quantum (or for the
remainder of its CPU burst).
Priorities range from 1 to 10, where a higher numeric value indicates a higher relative priority. For
round-robin scheduling, the length of a time quantum is 10 milliseconds.
You need to complete the three scheduling algorithms in the attached sample code (schedule_fcfs.c,
schedule_priority.c, schedule_rr.c) or (FCFS.java, Priority.java, RR.java).
3. Implementation
The implementation of this project should be completed in C or java, and supported program files
are provided in the sample code. These supporting files read in the schedule of tasks, insert the
tasks into a list, and invoke the scheduler.
The schedule of tasks has the form [task name] [priority] [CPU burst], with the following
example format:
T1, 4, 20
T2, 2, 25
T3, 3, 25
T4, 3, 15
T5, 10, 10
Thus, task T1 has priority 4 and a CPU burst of 20 milliseconds, and so forth. It is assumed that all
tasks arrive at the same time, so your scheduler algorithms do not have to support higher-priority
processes preempting processes with lower priorities. In addition, tasks do not have to be placed
into a queue or list in any particular order.
There are a few different strategies for organizing the list of tasks. One approach is to place all
tasks in a single unordered list, where the strategy for task selection depends on the scheduling
algorithm. Alternatively, a list could be ordered according to scheduling criteria (that is, by priority).
One other strategy involves having a separate queue for each unique priority. It is also worth
highlighting that we are using the terms list and queue somewhat interchangeably. However, a
queue has very specific FIFO functionality, whereas a list does not have such strict insertion and
deletion requirements. You are likely to find the functionality of a general list to be more suitable
when completing this project.
4. C Implementation Details (You can also use the java repo)
The file driver.c reads in the schedule of tasks, inserts each task into a linked list, and invokes the
process scheduler by calling the schedule() function. The schedule() function executes each task
according to the specified scheduling algorithm.
Tasks selected for execution on the CPU are
determined by the pickNextTask() function and are executed by invoking the run() function
defined in the CPU.c file. A Makefile is used to determine the specific scheduling algorithm that
will be invoked by driver. For example, to build the FCFS scheduler, we would enter
make fcfs
and would execute the scheduler (using the schedule of tasks schedule.txt) as follows:
./fcfs schedule.txt
Refer to the Makefile in the source code download for further details. Before proceeding, be sure
to familiarize yourself with the source code provided as well as the Makefile.
3: The Required Deliverable Materials
(1) Your source code, must be submitted in the required format.
(2) Your report, which discusses the design of your program. Report should display the outputs of
different scheduling algorithms from your code.
3. Submission Requirements
You need to strictly follow the instructions listed below:
1) This is a group project, please submit a .zip/.rar file that contains all files, only one submission
from one group.
2) The submission should include your source code and project report. Do not submit your binary
code. Project report should contain your groupmates name and ID.
3) Make a video to record your code execution and outputs. The video should present your name
or time as identification.
4) Your code must be able to compile; otherwise, you will receive a grade of zero.
5) Your code should not produce anything else other than the required information in the output
file.
6) If you code is partially completed, please explain the details in the report what has been
completed and the status of the missing parts, we will grade it based on the entire performance.
7) Provide sufficient comments in your code to help the TA understand your code. This is
important for you to get at least partial credit in case your submitted code does not work properly.
Grading criteria:
Details Points
Submission follows the right formats 5 pts
Have a README file shows how to compile and test your submission 5 pts
Submitted code has proper comments to show the design 5 pts
Screen a video to record code execution and outputs 10 pts
Have a report (pdf or word) file explains the details of your entire design 25 pts
Report contains clearly individual contributions of your group mates 5 pts
Code can be compiled and shows correct outputs 45 pts
4. Policies
1) Late submissions will be graded based on our policy discussed in the course syllabus.
2) Code-level discussion is prohibited. We will use anti-plagiarism tools to detect violations of
this policy.
