Ece252 Manual

User Manual:

Open the PDF directly: View PDF .
Page Count: 51

Download
Open PDF In Browser	View PDF

Electrical and Computer Engineering
(ECE) Systems Programming and
Concurrency ECE252 Laboratory
Manual
by

Yiqing Huang
Jeff Zarnett

Electrical and Computer Engineering Department
University of Waterloo

Waterloo, Ontario, Canada, June 18, 2019

c Y. Huang and J. Zarnett 2019

Contents
List of Tables

v

List of Figures

vi

Preface

1

I

1

II
1

Lab Administration
Lab Projects

6

Introduction to Systems Programming in Linux Computing Environment

7

1.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1.1

Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1.2

Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2

Starter Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.3

Pre-lab Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.4

Basic Linux Commands Exercises . . . . . . . . . . . . . . . . . . . . . .

8

1.5

Lab Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.6

1.7

1.5.1

Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.5.2

The findpng command . . . . . . . . . . . . . . . . . . . . . . . . 10

1.5.3

The catpng command . . . . . . . . . . . . . . . . . . . . . . . . 12

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.1

Pre-lab deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.2

Post-lab Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . 16

Marking Rubric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

ii

2

Multi-threaded Programming with Blocking I/O
2.1

Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2

Starter Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3

Pre-lab Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4

Lab Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.5

2.6

2.7
3

18

2.4.1

Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4.2

Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.3

Man page of paster . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Programming Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.1

The libcurl API . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.5.2

The pthreads API . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6.1

Pre-lab deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.6.2

Post-lab Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . 23

Marking Rubric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Interprocess Communication and Concurrency

24

3.1

Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2

Starter Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.3

Pre-lab Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.4

Lab Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.5

3.6

3.4.1

The Producer Consumer Problem . . . . . . . . . . . . . . . . . 25

3.4.2

Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5.1

Pre-lab Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.5.2

Post-lab Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . 29

Marking Rubric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

III Software Development Environment Quick Reference Guide
31
1

Introduction to ECE Linux Programming Environment

32

1.1

ECE Linux Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

1.2

Connecting to Linux servers . . . . . . . . . . . . . . . . . . . . . . . . . 32
iii

1.3

1.4

1.5

Basic Software Development Tools . . . . . . . . . . . . . . . . . . . . . 34
1.3.1

Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

1.3.2

C Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

1.3.3

Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

More on Development Tools . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.4.1

How to Automate Build . . . . . . . . . . . . . . . . . . . . . . . 37

1.4.2

Version Control Software . . . . . . . . . . . . . . . . . . . . . . 39

1.4.3

Integrated Development Environment . . . . . . . . . . . . . . . 40

Man Page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

A Forms

41

References

43

iv

List of Tables
0.1

Project Deliverable Weight of the Lab Grade, Scheduled Lab Sessions
and Deadlines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1

IHDR data field and value . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2

Lab1 Marking Rubric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1

Lab2 Marking Rubric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1

Timing measurement data table for given (B, P, C, X) values. . . . . . 30

3.2

Lab2 Marking Rubric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

C1

Programming Steps and Tools . . . . . . . . . . . . . . . . . . . . . . . . 35

v

List of Figures
1.1

Image Concatenation Illustration . . . . . . . . . . . . . . . . . . . . . . 10

C1

MobaXterm Path on ECE Nexus Windows 10 Machines.

C2

MobaXterm Welcome Page. . . . . . . . . . . . . . . . . . . . . . . . . . 33

C3

MobaXterm Welcome Page. . . . . . . . . . . . . . . . . . . . . . . . . . 34

C4

Linux files on P drive, a network mapped drive. . . . . . . . . . . . . . 35

vi

. . . . . . . . 33

Preface
Who Should Read This Lab Manual?
This lab manual is written for students who are taking Electrical and Computer Engineering (ECE) Systems Programming and Concurrency course ECE252 in the University of Waterloo.

What is in This Lab Manual?
The first purpose of this document is to provide the descriptions of each laboratory
project. The second purpose of this document is a quick reference guide of the relevant development tools for completing laboratory projects. This manual is divided
into three parts.
Part I describes the lab administration policies
Part II is a set of course laboratory projects as follows.
• Lab1: Introduction to systems programming in Linux computing environment
• Lab2: Multi-threaded concurrency programming with blocking I/O
• Lab3: Inter-process communication and concurrency control
• Lab4: Parallel web crawling
• Lab5: Single-threaded concurrency programming with asynchronous I/O
Part III is a quick reference guide of the Linux software development tools. We
will be using Ubuntu 18.04 LTS operating system. Materials in this part needs to be
self-studied before lab starts. The main topics are as follows.
• Linux hardware environment
• Editors
• Compiler
• Debugger
1

• Utility to automate build
• Utility for version control

Acknowledgments
We are grateful that Professor Patrick Lam shared his ECE459 projects with us. Eric
praetzel has provided continuous IT support, which makes the Linux computing
environment available to our students.
We would like to sincerely thank our students who took ECE254 and ECE459
courses in the past few years. They provided constructive feedback every term to
make the manual more useful to address problems that students would encounter
when working on each lab assignment.

2

Part I
Lab Administration

1

Lab Administration Policy
Group Lab Policy
• Group Size. All labs are done in groups of two. A size of three is only considered in a lab section that has an odd number of students and only one group
is allowed to have a size of three. All group of three requests are processed
on a first-come first-served basis. A group size of one is not permitted except
that your group is split up. There is no workload reduction if you do the labs
individually. Everyone in the group normally gets the same mark. The Learn
at URL http://learn.uwaterloo.ca is used to signup for groups. The lab
group signup is due by 10:00pm on the Second Friday of the academic term. Late
group sign-up is not accepted and will result in losing the entire lab sign-up
mark, which is 2% of the total lab grade.
• Group Split-up. If you notice workload imbalance, try to solve it as soon as
possible within your group or split-up the group as the last resort. Group splitup is only allowed once. You are allowed to join a one member group after the
split-up. But you are not allowed to split up from the newly formed group
again. There is one grace day deduction penalty to be applied to each member in the old group. We highly recommend everyone to stay with your group
members as much as possible, for the ability to do team work will be an important skill in your future career. Please choose your lab partners carefully. A
copy of the code and documentation completed before the group split-up will
be given to each individual in the group.
• Group Split-up Deadline. To split from your group for a particular lab, you
need to notify the lab instructor in writing and sign the group slip-up form (see
Appendix). Labn (n=1,2,3,4) group split-up form needs to be submitted to the
lab instructor by 4:30pm Thursday in the week that Labn has scheduled lab sessions. If you are late to submit the split-up form, then you need to finish Labn
as a group and submit your split-up form during the week where Lab(n+1) has
scheduled sessions and split starting from Lab(n+1).

2

Deliverable
Group Sign-up
LAB 1
LAB 2
LAB 3
LAB 4
LAB 5

Weight
2%
18%
20%
20%
20%
20%

Lab Session Week
N/A
Week 3
Week 5
Weeks 8
Week 10
Week 12

Deadline
10:00 pm Friday in Week 2
10:00 pm Wednesday in Week 4
10:00 pm Friday in Week 6
10:00 pm Wednesday in Week 9
10:00 pm Wednesday in Week 11
10:00 pm Last day of lecture

Table 0.1: Project Deliverable Weight of the Lab Grade, Scheduled Lab Sessions and
Deadlines.

Lab Assignments Grading and Deadline Policy
Labs are graded by lab TAs based on the rubric listed in each lab. The weight of each
lab towards your final lab grade is listed in Table 0.1.
• Lab Assignment Preparation and Due Dates. Students are required to prepare
the lab well before they come to the schedule lab session. Pre-lab deliverable for
each lab is due before the scheduled lab session starts. During the scheduled lab
session, we either provide in lab help or conduct lab assignment evaluation or
do both at the same time.
The detailed deadlines of post-lab deliverables are displayed in Table 0.1.
• Lab Assignment Late Submissions. Late submission is accepted within five
days after the deadline of the lab. No late submission is accepted five days after
the lab deadline. There are five grace days 1 that can be used for some post-lab
deliverables late submissions 2 . A group split-up will consume one grace day.
After all grace days are consumed, a 10% per day late submission penalty will
be applied. However if it is five days after the lab deadline, no late submission
is accepted.
• Lab Re-grading. To initiate a re-grading process, contact the grading TA in
charge first. The re-grading is a rigid process. The entire lab will be re-graded.
Your new grades may be lower, unchanged or higher than the original grade
received. If you are still not satisfied with the grades received after the regrading, escalate your case to the lab instructor to request a review and the lab
instructor will finalize the case.
1

Grace days are calendar days. Days in weekends are counted.
A post-lab deliverable that does not accept a late submission will be clearly stated in the lab
assignment description. Normally grace days are for lab reports. Labs whose evaluation involves
demonstrations do not accept late submissions of the code.
2

3

Lab Repeating Policy
For a student who repeats the course, labs need to be re-done with a new lab partner.
Simply turning in the old lab code is not allowed. We understand that the student
may choose a similar route to the solution chosen last time the course was taken.
However it should not be identical. The labs will be done a second time, we expect
that the student will improve the older solutions. Also the new lab partner should
be contributing equally, which will also lead to differences in the solutions.
Note that the policy is course specific to the discretion of the course instructor
and the lab instructor.

Lab Assignments Solution Internet Policy
It is not permitted to post your lab assignment solution source code or lab report
on the internet freely for public to access. For example, it is not acceptable to host a
public repository on GitHub that contains your lab assignment solutions. A warning
with instructions to take the lab assignment solutions off the internet will be sent out
upon the first offence. If no action is taken from the offender within twenty-four
hours, then a lab grade zero will automatically be assigned to the offender.

Seeking Help Outside Scheduled Lab Hours
• Discussion Forum. We recommend students to use the Piazza discussion forum to ask the teaching team questions instead of sending individual emails to
lab teaching staff. For questions related to lab projects, our target response time
is one business day before the deadline of the particular lab in question 3 . There
is no guarantee on the response time to questions of a lab that passes the submission
deadline.
• Office Hours. The Learn system calendar gives the office hour details.
• Appointments. Students can also make appointments with lab teaching staff
should their problems are not resolved by discussion forum or during office
hours. The appointment booking is by email.
To make the appointment efficient and effective, when requesting an appointment, please specify three preferred times and roughly how long the appointment needs to be. On average, an appointment is fifteen minutes per project
group. Please also summarize the main questions to be asked in your appointment requesting email. If a question requires teaching staff to look at a
3

Our past experiences show that the number of questions spike when deadline is close.The teaching staff will not be able to guarantee one business day response time when workload is above average, though we always try our best to provide timely response.

4

code fragment, please bring a laptop with necessary development software installed.
Please note that teaching staff will not debug student’s program for the student. Debugging is part of the exercise of finishing a programming assignment.
Teaching staff will be able to demonstrate how to use the debugger and provide case specific debugging tips. Teaching staff will not give direct solution
to a lab assignment. Guidances and hints will be provided to help students to
find the solution by themselves.

Lab Facility After Hour Access Policy
After hour access to the lab will be given to the class when we start to use the Keil
boards in lab. However please be advised that the after hour access is a privilege.
Students are required to keep the lab equipment and furniture in good conditions to
maintain this privilege.
No food or drink is allowed in the lab. Please be informed that you may share
the lab with other classes. When resources become too tight, certain cooperation is
required such as taking turns to use the stations in the lab.

5

Part II
Lab Projects

6

Lab 1
Introduction to Systems Programming
in Linux Computing Environment
1.1
1.1.1

Introduction
Objectives

This lab is to introduce system programming in a general Linux Development Environment at ECE Department. After finishing this lab, students will be able to
• apply basic Linux commands to interact with the Linux system through shell;
• apply standard Linux C programming tools for system programming and
• create a program to interact with Linux file systems by applying the relevant
system and libray calls.

1.1.2

Topics

Concretely, the lab will cover the following topics:
• Basic Linux commands
• C programming toolchain including gcc, make, and ddd
• Linux manual pages
• Linux system calls and file I/O library calls to traverse a directory and perform
read/write operations on selected files.

7

1.2

Starter Files

The starter files are on GitHub at url: http://github.com/yqh/ece252/tree/master/
lab1/starter. It contains the following sub-directories where we have example code
and image files to help you get started:
• the cmd arg demonstrates how to capture command line input arguments;
• the images contains some image files;
• the ls demonstrates how to list all files under a directory and obtain file types;
• the png util provides a set of utility functions to process a PNG image file; and
• the pointer demonstrates how to use pointers to access a C structure.
Using the code in the starter files is permitted and will not be considered as plagiarism.

1.3

Pre-lab Preparation

Read the Introduction to ECE Linux Programming Environment supplementary material in Part III Chapter 1.

1.4

Basic Linux Commands Exercises

These in-lab exercises are to practice some basic commands on Linux.
1. Use the MobaXterm to login onto eceubuntu.uwaterloo.ca . You are
now inside the Linux shell and in your home directory. The home directory
usually has a path name in the format of /home/username, where username
normally is your UWID. For example, a user with UWID of jsmith has a home
directory of /home/jsmith.
2. Use the pwd command to print the full filename of the current working directory. You should see your home directory name printed on the screen. For
example: /home/jsmith.
3. Use the echo $HOME command to print your home directory path name.
You will notice that the output matches the pwd output of exercise 2.
4. Use the env command to list all the environment variables and their values.
Note that HOME is one of the many environment variables.
5. One important environment variable is PATH. It specifies a set of directories
the system searches for executible programs. Use echo $PATH to see your
PATH environment variable setting.
8

6. Execute command which ls to locate the directory the ls command is in.
You will notice the directory is listed in PATH environment variable. When
you issue a command and get an error message of “command not found”, it
means the command cannot be found after searching all the directories listed
in PATH environment variable. A commonly seen error is that a command in
your current working directory gives you “command not found“ error. This
is normally due to the fact that the current working directory . or ./ is not in
the PATH. Consequently you need to add the path to the command name for
the system to know where the command is. For example ./a.out tells the
system to run the command a.out located in the current working directory.
7. Use the ls command to list all files in your current working directory.
8. Read the online manual of the ls command by issuing man ls command to
the shell. Find out from the manual what options -l, -a and -la do. Execute
the ls command with these three options and see the execution results.
9. Create a directory as the work space of labs under your home directory. Name
the newly created directory as labs. Read the man page of the command
mkdir to see how to do it.
10. Change directory to the newly create directory of labs. Read the man page of
command cd to find out how to change directory.
11. Clone the ece252 lab repository by using the command:
git clone https://github.com/yqh/ece252.git .
A new directory named ece252 will be created. It has lab manual and starter
code of ECE252 labs.
12. Read the man page of the find command by issuing man find command
to the shell. Read what the -name option does. Use find with the -name
option to find all the files with .png file extension in the $HOME/labs/ece252
directory.
13. Change directory to where the WEEF_1.png is. Use file WEEF 1.png
command to obtain the file type and image properties such as dimensions and
bit depth.
14. Use file command to obtain the file type information of Disguise.png.
You should see that this is not an image file though the file exension is .png.
Use a text editor to open the file and see the contents. This exercise is to show
you that the file command does not obtain the file type information based
on the file extension. It looks into the contents of file to extract the file type
information 1 .
1

A file has a magic number to indicate its type. The magic number is a sequence of bytes usually
appearing near the beginning of the file. The file command checks the magic number. The PNG file’s
magic number is 89 50 4E 47 in hexadecimal, which is .PNG in ASCII.

9

1.5

Lab Assignment

1.5.1

Problem statement

You are given a directory under which some
files are PNG images and some files are not. The
directory may contain nested sub-directories2 .
All valid PNG images under the given directory are horizontal strips of a bigger whole image. They all have the same width. The height
of each image might be different. The PNG images have the naming convention of *_N.png,
where N is the image strip sequence number and
N=0, 1, 2, .... However a file with .png or
.PNG extension may not be a real PNG image
file. You need to located all the real PNG image files under the given directory first. Then
you will concatenate these horizontal strip images sequentially based on the sequence numFigure 1.1: Image Concatenation
ber in the file name to restore the original whole
Illustration
image. The sequence number indicates the order the image should be concatenated from top
to bottom. For example, file img_1.png is the first horizontal strip and img_2.png
is the second horizontal strip. To concatenate these two strips, the pixel data in
img_1.png should be followed immediately by the pixel data in img_2.png file.
Figure 1.1 illustrates the concatenation order.
To solve the problem, first you will create a tool named findpng to search the
given directory hierarchy to find all the real PNG files under it. Secondly you will
create an image data concatenation tool named catpng to concatenate pixel data of
a set of PNG files to form a single PNG image file. The catpng only processes PNG
images with the same width in dimension.

1.5.2

The findpng command

The expected behaviour of the findpng is given in the following manual page of
the command.
2

A nested sub-directory is a sub-directory that may contain many layers of sub-directories.

10

Man page of findpng
NAME
findpng - search for PNG files in a directory hierarchy
SYNOPSIS
findpng DIRECTORY
DESCRIPTION
Search for PNG files under the directory tree rooted at DIRECTORY and return the search results to the standard output. The command does not follow
symbolic links.
OUTPUT FORMAT
The output of search results is a list of PNG file relative path names, one file
pathname per line. The order of listing the search results is not specified. If the
search result is empty, then output “findpng: No PNG file found”.
EXAMPLES
findpng .
Find PNG of the current working directory. A non-empty search results might
look like the following:
./lab1/sandbox/new_bak.png
./lab1/sandbox/t1.png
./png_img/rgba_scanline.png
./png_img/v1.png
An empty search result will look like the following:
findpng: No PNG file found

11

Searching PNG files under a given directory
UNIX file system is organized as a tree. A file has a type. Three file types that this
assignment will deal with are regular, directory and symbolic link. A PNG file is a
regular file. A directory is a directory file. A link created by ls -n is a symblic link.
Read the section 2 of stat family system calls man page for information about
other file types. The ls/ls_ftype.c in the starter code gives a sample program to
determine the file type of a given file.
To search all the files under a given directory and its subdirectories, one need
to traverse the given directory tree to its leaf nodes. The library call of opendir
returns a directory stream for readdir to read each entry in a directory. One need
to call closedir to close the directory stream once operations on it is completed.
The control flow is to go through each entry in a directory and check the file type.
If it is a regular file, then further check whether it is a PNG file by comparing the
first 8 bytes with the PNG file header bytes (see Section 1.5.3). If it is a directory file,
then you need to check files under the sub-directory and repeat what you did in the
parent directory. The ls/ls_fname.c in the starter code gives a sample program
that lists all file entries of a given directory.
Always check the man page of the systems calls and library calls for detailed
information.

1.5.3

The catpng command

The expected behaviour of the catpng is given in the following manual page of the
command.
Man page of the catpng
NAME
catpng - concatenate PNG images vertically to a new PNG named all.png
SYNOPSIS
catpng [PNG FILE]...
DESCRIPTION
Concatenate PNG FILE(s) vertically to all.png, a new PNG file.

12

OUTPUT FORMAT
The concatenated image is output to a new PNG file with the name of all.png.
EXAMPLES
catpng ./img1.png ./png/img2.png
Concatenate the listed PNG images vertically to all.png.
File I/O
There are two sets of functions for file I/O operations under Linux. At system call
level, we have the unbufferred I/O functions: open , read , write , lseek and
close . At library call level, we have standard I/O functions: fopen , fread
, fwrite , fseek and fclose . The library is built on top of unbufferred
I/O functions. It handles details such as buffer allocation and performing I/O in
optimal sized chunks to minimize the number of read and write usage, hence
is recommended to be used for this lab.
The fopen returns a FILE pointer given a file name and the mode. A PNG
image file is a binary file, hence when you call fopen , use mode ” rb ” for reading
and ” wb+ ” for reading and writing, where the ”b” indicates it is a binary file that
we are opening. Read the man page of fopen for more mode options.
After the file is opened, use fread to read the number of bytes from the stream
pointed by the FILE pointer returned by fopen . Each opened file has an internal
state of file position indicator. The file position indicator sets to the beginning of the
file when it is just opened. The fread operation will advance the file position
indicator by the number of bytes that has been read from the file. The fseek sets
the file position indicator to the user specified location. The fwrite writes user
specified number of bytes to the stream pointed by the FILE pointer. The file position
indicator also advances by the number of bytes that has been written. It is important
to call fclose to close the file stream when I/O operations are finished. Failure to
do so may result in incomplete files.
The man pages of the standard I/O library is the main reference for details including function prototypes and how to use them.
PNG File Format
In order to finish this assignment, one need to have some understanding of the png
file format and how an image is represented in the file. One way to store an image
is to use an array of coloured dots referred to as pixels. A row of pixels within an
image is called a scanline. Pixels are ordered from left-to-right within each scanline.
13

Scanlines appear top-to-bottom in the pixel array. In this assignment, each pixel is
represented as four 8-bit 3 unsigned integers (ranging from 0 to 255) that specify the
red, green, blue and alpha intensity values. This encoding is often referred to as the
RGBA encoding. RGB values specify the colour and the alpha value specifies the
opacity of the pixel. The size of each pixel is determined by the number of bits per
pixel. The dimensions of an image is described in terms of horizontal and vertical
pixels.

(a) PNG File Format

(b) PNG Chunk Format

PNG stands for “Portable Network Graphics”. It is a computer file format for
storing, transmitting and displaying images[1]. A PNG file is a binary file. It starts
with an 8-byte header followed by a series of chunks. You will notice the second,
third and fourth bytes are the ASCII code of ’P’, ’N’ and ’G’ respectively (see Figure
1.2(a)).
The first chunk is the IHDR chunk, which contains meta information of the image
such as the dimensions of the pixels. The last chunk is always the IEND chunk,
which marks the end of the image datastream. In between there is at least one IDAT
chunk which contains the compressed filtered pixel array of the image. There are
other types chunks that may appear between IHDR chunk and IEND chunk. For all
the PNG files we are dealing with in this assignment, we use the format that only
has one IHDR chunk, one IDAT chunk and one IEND chunk (see Figure 1.2(a)).
Each chunk consists of four parts. A four byte length field, a four byte chunk type
code field, the chunk data field whose length is specified in the chunk length field,
and a four byte CRC (Cyclic Redundancy Check) field (see Figure 1.2(b)).
The length field stores the length of the data field in bytes. PNG file uses big
endian byte order, which is the network byte order. When we process any PNG data
that is more than one byte such as the length field, we need to convert the network
byte order to host order before doing arithmetic. The ntohl and htonl library
3

Formally, we say the image has a bit depth of 8 bits per sample.

14

calls convert a 32 bit unsigned integer from network order to host order and vice
versa respectively.
The chunk type code consists four ASCII character. IHDR, IDAT and IEND are
the three chunk type code that this assignment involves with.
The data field contains the data bytes appropriate to the chunk type. This field
can be of zero length.
The CRC field calculates on the proceeding bytes in the type and data fields of
the chunk. Note that the length field is not included in the CRC calculation. The
crc function under the png_util starter code can be used to calculate the CRC
value.
The IHDR chunk data field has a fixed
length of 13 bytes and they appear in the
order as shown in Table 1.1. Width and Name
Length Value
height are four-byte unsigned integers
4 bytes N/A
giving the image dimensions in pixels. Width
You will need these two values to com- Height
4 bytes N/A
plete this assignment. Bit depth gives the
1 byte
8
number of bits per sample. In this as- Bit depth
signment, all images have a bit depth of Colour type
1 byte
6
8. Colour type defines the PNG image
Compression method 1 byte
0
type. All png images in this assignment
1 byte
0
have a colour type of 6, which is truecolor Filter method
with alpha (i.e. RGBA image). The image Interlace method
1 byte
0
pixel array data are filtered to prepare
for the next step of compression. The
Table 1.1: IHDR data field and value
Compression method and Filter method
bytes encode the methods used. Both
only have 0 values defined in the current
standard. The Interlace method indicates the transmission order of the image data. 0
(no interlace) and 1 (Adam7 interlace) are the only two defined. In this assignment,
all PNG images are non-interlaced. Table 1.1 Value column gives the typical IHDR
values the PNG images you will be processing.
The IDAT chunk data field contains compressed filtered pixel data. For each scanline, first an extra byte is added at the very beginning of the pixel array to indicate
the filter method used. Filtering is for preparing the next step of compression. For
example, if the raw pixel scanline is 4 bytes long, then the scanline after applying filter will be 5 bytes long. This added one byte per scanline will help to achieve better
compression result. After all scanlines have be filtered, then the data are compressed
according to the compression method encoded in IHDR chunk. The compressed data
stream conforms to the zlib 1.0 format.
The IEND chunk marks the end of the PNG datastream. It has an empty data
field.

15

Concatenate the pixel data
To concatenate two horizontal image strips, the natural way of thinking is to start
with the pixel array of each image and then concatenate the two pixel arrays vertically. Then we apply the filter to each scanline. Lastly we compress the filtered pixel
array to fill the data field of the new IDAT chunk of the concatenated image. However a simpler way exists. We can start with the filtered pixel data of each image and
then concatenate the two chunks of filtered pixel data arrays vertically, then apply
the compression method to generate the data field of the new IDAT chunk.
How do we get filtered pixel data from a PNG IDAT chunk? Recall that the
data field in IDAT chunk is compressed data that conforms to zlib format 1.0. We
can use zlib functions to uncompress(i.e. inflate) the data. The mem inf in the
starter code takes in memory compressed(i.e. deflated) data as input and returns the
uncompressed data to a another memory location. For each IDAT chunk you want
to concatenate, call this function and stack the returned data in the order you wish
and then you have the concatenated filtered pixel array. To create an IDAT chunk,
we need to compress the filtered pixel data. The mem def function in the starter
code uses the zlib to compress (i.e. deflate) the input in memory data and returns
the deflated data. The png_util directory in the starter code demos how to use the
aforementioned two functions.
To create a new PNG for the concatenated images, IHDR chunk also needs to
have the new dimension information of the new PNG file. The rest of the fields of
IHDR chunk can be kept the same as one of the PNG files to be concatenated. In
this assignment, we assume that catpng can only process PNG files whose IHDR
chunks only differ in the height field. So the new image will have a different height
field, the rest of fields are the same as the input images.

1.6
1.6.1

Deliverables
Pre-lab deliverables

There is no pre-lab deliverable.

1.6.2

Post-lab Deliverables

The following are the steps to create your post-lab deliverable submission.
• Create a directory and name it lab1.
• Put the entire source code with a Makefile under the directory lab lab1. The
Makefile default target includes catpng and findpng. That is command
make should generate the aforementioned two executable files. We also ex-

16

pect that command make clean will remove the object code and the default
target. That is the .o files and the two executable files should be removed.
• Use zip command to zip up the contents of lab1 directory and name it lab1.zip.
We expect unzip lab1.zip will produce a lab1 sub-directory in the current
working directory and under the lab1 sub-directory is your source code and
the Makefile.
Submit the lab1.zip file to Lab1 Dropbox in Learn.

1.7

Marking Rubric
Points
10
35
55

Description
Makefile correctly builds and cleans
Implementation of findpng
Implementation of catpng
Table 1.2: Lab1 Marking Rubric

Table 1.2 shows the rubric for marking the lab.

17

Lab 2
Multi-threaded Programming with
Blocking I/O
2.1

Objectives

This lab is to learn about and gain practical experience in multi-threaded programming in a general Linux environment. A single-thread implementation using blocking I/O to request a resource across the network is provided. Students are asked
to reduce the latency of this operation by sending out multiple requests simultaneously to different machines by using the pthreads library. After this lab, students
will have a good understanding of
• how to design and implement a multi-threaded program by using the pthreads
library; and
• the role mutli-threading plays in reducing the latency of a program.

2.2

Starter Files

The starter files are on GitHub at url: http://github.com/yqh/ece252/tree/master/
lab2/starter. It contains the following sub-directories where we have example code
to help you get started:
• the cURL demonstrates how to use cURL to fetch an image segment from the
lab web server;
• the fn ptr demonstrates how C function pointers work;
• the getopt demonstrates how to parse command line options;
• the pthreads demonstrates how to create two threads where each thread takes
multiple input parameters and return multiple values; and
18

• the times provides helper functions to profile program execution times.
Using the code in the starter files is permitted and will not be considered as plagiarism.

2.3

Pre-lab Preparation

Build the starter code and run the executables. Work through the code and understand what they do and how they work. Create a single-threaded implementation of
the paster command.

2.4

Lab Assignment

2.4.1

Problem Statement

In the previous lab, a set of horizontal strips of a whole PNG image file were stored
on a disk and you were asked to restore the whole image from these strips. In this
lab, the horizontal image segments are on the web. I have three 400 × 300 pictures
(whole images) on three web servers. When you ask a web server to send you a
picture, the web server crops the picture into fifty 400 × 6 equally sized horizontal
strips 1 . The web server assigns a sequence number to each strip from top to bottom
starting from 0 and increments by 1 2 . Then the web server sleeps for a random
time and then sends out a random strip in a simple PNG format that we assumed
in lab1. That is the horizontal strip PNG image segment consists one IHDR chunk,
one IDAT chunk and one IEND chunk (see Figure 1.2(a)). The PNG segment is an
8-bit RGBA/color image (see Table 1.1 for details). The web server uses an HTTP
response header that includes the sequence number to tell you which strip it sends to
you. The HTTP response header has the format of “X-Ece252-Fragment: M ” where
M ∈ [0, 49]. To request a random horizontal strip of picture N , where N ∈ [1, 3], use
the following URL: http://machine:2520/image?img=N, where
machine is one of the following:
• ece252-1.uwaterloo.ca,
• ece252-2.uwaterloo.ca, and
• ece252-3.uwaterloo.ca .
For example, when you request data from the following URL:
http://ece252-1.uwaterloo.ca:2520/image?img=1,
1

Each image segment will have a size less than 8KB.
The first horizontal strip has a sequence number of 0, the second strip has a sequence number of
1. The sequence number increments by 1 from top to bottom and the last strip has a sequence number
of 49.
2

19

you may receive a random horizontal strip of picture 1. Assume this random strip
you receive is the third horizontal strip (from top to bottom of the original picture),
the received HTTP header will contain “X-Ece52-Fragment: 2“. The received data
will be the image segment in PNG format. You may use the browser to view a random horizontal strip of the PNG image the server sends. You will notice the same
URL displays a different image strip every time you hit enter to refresh the page.
Each strip has the same dimensions of 400 × 6 pixels and is in PNG format.
Your objective is to request all horizontal strips of a picture from the server and
then concatenate these strips to restore the original picture. Because every time the
server sends a random strip, if you use a loop to keep requesting a random strip
from a server, you may receive the same strip multiple times before you receive all
the fifty distinct strips. Due to the randomness, it will take a variable amount of time
to get all the strips you need to restore the original picture.

2.4.2

Requirements

Use the pthreads library, design and implement a threaded program to request
all image segments from a web server by using blocking I/O and concatenate these
segments together to form the whole image.
The provided starter code main_write_header_cb.c under cURL directory
is a single-threaded implementation which uses libcurl blocking I/O function
curl_easy_peform()to fetch one random horizontal strip of picure 1 from one
of the web servers into memory and then output the received image segment to a
PNG file. Your program should repeatedly fetch the image strips until you have
them all. Recall because every time you get a random strip, the amount of time to
get all the fifty distinct strips of a picture varies.
A very inefficient approach is to use a single-threaded loop to keep fetching until
you get all fifty distinct strips of a picture and paste them together. You will notice
the blocking I/O operation is the main cause of the latency. Your program will be
blocked while each time waiting for the curl_easy_perform() to finish. One
way to reduce the latency of this operation is to send out multiple blocking I/O
requests simultaneously (to different machines) by using pthreads. You will use
this approach to reduce the latency in this lab 3 .
Your program should create as many threads as specified by the user command
line input, and distribute the work among the three provided servers. Make sure
all of your library (standard glibc and libcurl) calls are thread-safe (for glibc, e.g.
man 3 printf to look at the documentation). Name your executable as paster.
The behaviour of the command paster is given in the following section.
The provided three pictures on the server are for you to test your program. Your
program should work for all these pictures. You may want to reuse part of your lab1
code to paste the received image segments together.
3

Asynchronous I/O is another method to reduce the latency and we will explore it in lab5.

20

2.4.3

Man page of paster

NAME
paster - pasting downloaded png files together by using multiple threads and
blocking I/O through libcurl.
SYNOPSIS
paster [OPTION]...
DESCRIPTION
With no options, the command retrieves all horizontal image segments of picture 1 from http://ece252-1.uwaterloo.ca:2520/image?img=1 and paste all distinct segments received from top to bottom in the order of the image segment
sequence number. Output the pasted image to disk and name it output.png.
-t=NUM
create NUM threads simultaneously requesting random image segments
from multiple lab web servers. When this option is not specified, assumes
a single-threaded implementation.
-n=NUM
request a random image segment of picture NUM from the web server.
Valid values are 1, 2 and 3. Default value is set to 1.
OUTPUT FORMAT
The concated image is output to a PNG file with the name of output.png.
EXAMPLES
paster -t 6 -n 2
Use 6 threads to simultaneously download all image segments of picture 2
from multiple web servers and concatenate these segments to restore picture 2.
Output the concatenated picture to disk and name it output.png.

21

2.5
2.5.1

Programming Tips
The libcurl API

Though the image segment download code using libcurl is provided, familiarize yourself with the libcurl API will help you understand the provided code. The
libcurl documentation URL is https://curl.haxx.se/libcurl. The man page of each
function in the libcurl API can be found at URL https://curl.haxx.se/libcurl/c/
allfuncs.html.
Note the provided example cURL code downloads the received image segment
to memory and then output the data in memory to a PNG file. The output to a
PNG file is just to make it easier for you to view the downloaded image segment
to help you understand the example code. However your paster program does
not need to output each segment received to a file. An efficient way (i.e. without
unnecessary file I/O) is to directly use the received image segment data in memory
instead of outputting the data to a file first and then reading the data back from file
into memory.
Thread Safety
Libcurl is thread safe but there are a few exceptions. The man page of libcurlthread(3) (see https://curl.haxx.se/libcurl/c/threadsafe.html) is the ultimate reference. We re-iterate key points from libcurl manual that are relevant to this lab as
follows:
• The same libcurl handle should not be shared in multiple threads.
• The libcurl is thread safe but does not have internal thread synchronization
mechanism. You will need to take care of the thread synchronization.

2.5.2

The pthreads API

The pthreads(7) man page gives an overview of POSIX threads and should be
read. The SEE ALSO section near the bottom of the man page lists functions in the
API. The man pages of pthread_create(3), pthread_join(3) and pthread_exit(3)
provide detailed information of how to create, join and terminate a thread.
The pthread Memory Leak Bug
There is a known memory leak bug related to pthread_exit(). Please refer to
https://bugzilla.redhat.com/show bug.cgi?id=483821 for details. Using return()
instead of pthread_exit() will avoid the memory leak bug.

22

2.6
2.6.1

Deliverables
Pre-lab deliverables

None.

2.6.2

Post-lab Deliverables

Create a multi-threaded implementation of the paster command. The following
are the steps to create your post-lab deliverable submission.
• Create a directory and name it lab2.
• Put the entire source code with a Makefile under the directory lab lab2. The
Makefile default target is paster. That is command make should generate
the paster executable file. We also expect that command make clean will
remove the object code and the default target. That is the .o files and the
executable file should be removed.
• Use zip command to zip up the contents of lab2 directory and name it lab2.zip.
We expect unzip lab2.zip will produce a lab2 sub-directory in the current
working directory and under the lab2 sub-directory is your source code and
the Makefile.
Submit the lab2.zip file to Lab2 Dropbox in Learn.

2.7

Marking Rubric
Points
10
25
65

Description
Makefile correctly builds and cleans paster
Implementation of single-threaded paster
Implementation of multi-threaded paster
Table 2.1: Lab2 Marking Rubric

Table 2.1 shows the rubric for marking the lab.

23

Lab 3
Interprocess Communication and
Concurrency
3.1

Objectives

This lab is to learn about, and gain practical experience in interprocess communication and concurrency control in a general Linux environment. Shared memory
allows multiple processes to share a given region of memory. It is the fastest form
for different processes to communicate. Processes need to take care of the shared
memory conflicting operations. The operating system provides concurrency control
facility such as semaphore API.
After this lab, students will be able to
• design and implement a multi-processes concurrent program by using the producerconsumer pattern;
• program with
– the fork() system call to create a new child process;
– the wait() family system calls to obtain the status-change information of
a child process;
– the Linux shared memory API to allow processes to communicate; and
– the Linux semaphore facility to synchronize processes.

3.2

Starter Files

The starter files are on GitHub at url: http://github.com/yqh/ece252/tree/master/
lab3/starter.It contains the following sub-directories where we have example code
to help you get started:

24

• the fork has example code of creating multiple processes and time the total
execution time; it also demonstrate how a zombie process is created when the
parent process does not call wait family calls;
• the sem has example code of using POSIX semaphore shared between processes;
• the shm has example code of using System V shared memory; and
• the cURL IPC has example code of using a shared memory region as a cURL
call back function buffer to download one image segment from a lab server by
the child process and writing the downloaded image segment to a file by the
parent process.

3.3

Pre-lab Preparation

Build and run the starter code to see what they do. You should work through the
provided starter code to understand how they work. The following activities will
help you to understand the code.
1. Execute man fork to read the man page of fork(2).
2. Execute man 2 wait to read the man page of wait(2) family system calls.
3. Execute man ps to read the man page of the ps command.
4. Execute man shm overview to read Linux man page of POSIX shared memory API overview. At the bottom of the man page, it talks about system V
shared memory facilities. Read the corresponding man pages of the system V
shared memory API.
5. Execute man sem overview to read Linux man page of POSIX semaphore
API overview.
Linux man pages are also available on line at https://linux.die.net/.
Circular queue is the main data structure that we will be using in the lab. You
may want to create it or use one from an existing library.

3.4
3.4.1

Lab Assignment
The Producer Consumer Problem

A producer-consumer problem is a classic multi-tasking problem. There are one or
more tasks that create data and they are referred to as producers. There are one or
25

more tasks that use the data and they are referred to as consumers. We will have a
system of P producers and C consumers. Producers and consumers do not necessarily complete their tasks at the same speed. How many producers should be created
and how many consumers should be created to achieve maximum latency improvement1 ? What if the buffer receiving the produced data has a fixed size? Another
problem to think about is that when we fix the number of producers and consumers,
how big the bounded buffer size should be? Is it true the bigger the buffer size is, the
more latency improvement we will get, or there is a limit beyond which the bigger
buffer size will not bring any further latency improvement? We will do some experiments to answer these questions by solving a similar problem that we solved in lab2
with some additional assumptions.
In lab2 we used multi-threading to download image segments from the web
server and then paste all the segments together. This falls into the unbounded buffer
producer consumer problem pattern. We can let producers download the image segments (i.e. creating data) and let consumers extract the image pixel data information
(i.e. processing data) for future processing. One easy solution to lab 2 (also commonly seen) is to have one thread that does both the producer and the consumer jobs.
This implicitly assumes that the number of producers and consumers are equal. But
what if data creation and data processing are running at different speeds2 ? It may
take more time to download data than to process data or vice versa. Then having the
same number of producers and consumers are not optimal. In addition, in lab2, we
did not restrict the receiving data buffer size. In a real world, resources are limited
and the situation that a fixed size of buffer space to receive the incoming data is more
realistic. In this lab, we have the additional constraint that the buffer to receive the
image segments from the web server has a fixed size. So the problem we are solving
is a bounded buffer producer-consumer problem3 .

3.4.2

Problem Statement

We are still solving an image concatenation problem. The image strips are the same
ones that you have seen in lab2. In lab2, the lab web server sleeps a random seconds before it sends a random horizontal strip of an image to the client. In this
lab, we have a different server running at port 2530 which sleeps for a fixed time
before it sends a specific image strip requested by the client. The deterministic
1

You probably have already noticed in lab2 that once the number of threads reaches a certain
number, you reach the maximum performance improvement.
2
For example, the data processing part could be more involved such as doing some image transformation. It could also be that the network bandwidth is tight or the lab server is slow so that it takes
long to download the image segment.
3
Here is another producer consumer problem example: you can think of the producer as a keyboard device driver and the consumer as the application wishing to read keystrokes from the keyboard; in such a scenario the person typing at the keyboard may enter more data than the consuming
program wants, or conversely, the consuming program may have to wait for the person to type in
characters. This is, however, only one of many cases where producer/consumer scenarios occur, so
do not get too tied to this particular usage scenario.

26

sleep time in the server is to simulate the time to produce the data. The image
format sent by the server is still the simple PNG format (see Figure 1.2(a)). The
PNG segment is still an 8-bit RGBA/color image (see Table 1.1 for details). The
web server still uses an HTTP response header that includes the sequence number
to tell you which strip it sends to you. The HTTP response header has the format of “X-Ece252-Fragment: M ” where M ∈ [0, 49]. To request a horizontal strip
with sequence number M of picture N , where N ∈ [1, 3], use the following URL:
http://machine:2530/image?img=N&part=M, where
machine is one of the following:
• ece252-1.uwaterloo.ca,
• ece252-2.uwaterloo.ca, and
• ece252-3.uwaterloo.ca .
For example, when you request data from http://ece252-1.uwaterloo.ca:2530/
image?img=1&part=2, you will receive a horizontal image strip with sequence number 2 of picture 1 . The received HTTP header will contain “X-Ece52-Fragment: 2“.
The received data will be the image segment in PNG format. You may use the
browser to view a horizontal strip of the PNG image the server sends. Each strip
has the same dimensions of 400 × 6 pixels and is in PNG format.
Your objective is to request all horizontal strips of a picture from the server and
then concatenate these strips in the order of the image sequence number from top to
bottom to restore the original picture as quickly as possible for a given set of given
input arguments specified by the user command. You should name the concatenated
image as all.png and output it to the current working directory.
There are three types of work involved. The first is to download the image segments. The second is to process downloaded image data and copy the processed
data to a global data structure for generating the concatenated image. The third is
to generate the concatenated all.png file once the global data structure that holds the
concatenated image data is filled.
The producers will make requests to the lab web server and together they will
fetch all 50 distinct image segments. Each time an image segment arrives, it gets
placed into a fixed-size buffer of size B, shared with the consumer tasks. When
there are B image segments in the buffer, producers stop producing. When all 50
distinct image segments have been downloaded from the server, all producers will
terminate. That is the buffer can take maximum B items, where each item is an
image segment. The horizontal image strips sent out by the lab servers are all less
than 10, 000 bytes.
Each consumer reads image segments out of the buffer, one at a time, and then
sleeps for X milliseconds specified by the user in the command line4 . Then the consumer will process the received data. The main work is to validate the received
4

This is to simulate data processing takes time.

27

image segment and then inflate the received IDAT data and copy the inflated data
into a proper place inside the memory.
Given that the buffer has a fixed size, B, and assuming that B < 50, it is possible
for the producers to have produced enough image segments that the buffer is filled
before any consumer has read any data. If this happens, the producer is blocked,
and must wait till there is at least one free spot in the buffer.
Similarly, it is possible for the consumers to read all of the data from the buffer,
and yet more data is expected from the producers. In such a case, the consumer is
blocked, and must wait for the producers to deposit one or more additional image
segments into the buffer.
Further, if any given producer or consumer is using the buffer, all other consumers and producers must wait, pending that usage being finished. That is, all
access to the buffer represents a critical section, and must be protected as such.
The program terminates when it finishes outputting the concatenated image segments in the order of the image segment sequence number to a file named all.png.
Note that there is a subtle but complex issue to solve. Multiple producers are
writing to the buffer, thus a mechanism needs to be established to determine whether
or not some producer has placed the last image segment into the buffer. Similarly,
multiple consumers are reading from the buffer, thus a mechanism needs to be established to determine whether or not some consumer has read out the last image
segment from the buffer 5 .

Requirements
Let B be the buffer size, P be the number of producers, C be the number of consumers and X be the number of milliseconds that a consumer sleeps before it starts
to process the image data. The producer consumer system is called with the execution command syntax of:
./paster2  
  
The command will execute per the above description and will then print out the
time it took to execute. You should measure the time before you create the first
process and the time after the last image segment is consumed and the concatenated
all.png image is generated. Use the timing starter code in lab2 for time measurement
and terminal screen for display. Thus your last line of output should be something
like:
5

Due to network transmission has randomness, the order of image segments placed in the buffer
may not necessarily be the same order that they have been requested by the producers. The last image
segment in the buffer may not necessarily be the image segment with the biggest sequence number.
We do not want to request the same image segment twice since this will bring down the performance,
so both producers and consumers know the buffer in total will serve 50 image segments.

28

paster2 execution time: 
For a set of given (B, P, C, X) tuple values, run your application and measure the time it takes. Note for a give value of (B, P, C, X), you need to run
multiple times to compute the average execution time in a general Linux environment.
Implement each producer/consumer as an individual process. You start your
program with one process which then forks multiple producer processes and multiple consumer processes. The parent process will wait for all the child processes to
terminate and then start to process the data structure that holds the concatenated
image data and create the final all.png file. Aside from the parent process, the P
producer processes that download the image segments and C consumer processes
that process the image segment data, you are allowed to create extra processes to
do other type of work when you see a need. Just keep in mind that having more
processes is not cost free. Hence a good implementation will try to minimize system
resource usage unless extra resource usage will bring meaningful improvement.
Use shared memory for processes to communicate. You may use System V shared
memory API. The bounded buffer is a shared data structure such as a circular queue
that all processes share access to. Note that shared memory access needs to be taken
care of at the application level. The POSIX semaphore are to be used for concurrency
control.

A Sample Program Run
[eceTesla1:]./produce 2 1 3 10
paster2 execution time: 100.45 seconds
Note that due to concurrency, your output may not be exactly the same as the sample output above. Also depending on the implementation details and the platform
where the program runs, the sample system execution time is only for illustration
purpose. The exact paster2 execution time value your program produces will be
different than the one shown in the sample run.

3.5
3.5.1

Deliverables
Pre-lab Deliverables

There is no pre-lab deliverable for this lab.

3.5.2

Post-lab Deliverables

Put the following items under a directory named lab3:
29

1. All the source code and a Makefile. The Makefile default target is paster2 executable file. That is command make should generate the paster2 executable
file. We also expect that the command make clean will remove the object
code and the default target. That is the .o files and the executable files should
be removed.
2. A timing result .csv file named lab3 hostname.csv which contains the timing results by running paster2 on a server whose name is hostname. For example, lab3_eceubuntu1.csv means paster2 was executed on the server
eceubuntu1 and the file contains the timing results. The first line of the file is
the header of the timing result table. The rest of the rows are the timing result
command line argument values and the timing results. The columns of the .csv
file from left to right are values of B, P , C, X, and the corresponding paster2
average execution time. We have an example .csv file in the starter code folder
named lab3_eceubuntu1.csv for illustration purpose.
Run your paster2 on eceubuntu1. Record the average timing measurement
data for the (B, P, C, X) values shown in Table 3.1 for a particular host.
Note that for each given {B, P, C, X) value in the table, you need to run
the program n (We recommend n = 5.) times and compute the average time.
B
P
C
X
TBA TBA TBA TBA

Time

Table 3.1: Timing measurement data table for given (B, P, C, X) values.

Use zip command to archive and compress the contents of lab3 directory and name
it lab3.zip. We expect the command unzip lab3.zip will produce a lab3 subdirectory in the current working directory and under the lab3 sub-directory is your
source code, the Makefile and the lab3 hostname.csv file.

3.6

Marking Rubric

The Rubric for marking is listed in Table 3.2.
Points
10
70
20

Description
Makefile correctly builds and cleans paster2
Implementation of paster2
Correct timing results in lab3 hostname.csv file
Table 3.2: Lab2 Marking Rubric

30

Part III
Software Development Environment
Quick Reference Guide

31

Chapter 1
Introduction to ECE Linux
Programming Environment
1.1

ECE Linux Servers

There are a group of Linux Ubuntu servers that are open to ECE undergraduate
students. The machines are listed at url: https://ece.uwaterloo.ca/Nexus/arbeau/
clients. To access one of the machines, we recommend to use the alias name of
eceubuntu.uwaterloo.ca, which will direct the user to the most lightly loaded
machine at the time of login.
To access these machines from off campus. One way is to use the campus VPN.
Another way is to first connect to ecelinux4.uwaterloo.ca or eceterm.uwaterloo.ca
and then connect to other Linux servers from there. Note that the ecelinux4
should not be used for computing jobs, it is for accessing other Linux servers on
campus.

1.2

Connecting to Linux servers

A terminal client software that supports secure shell (ssh) will allow you to remotely
connect to the Linux servers. MobaXterm is a convenient application that not only
supports ssh, but also has a built-in X server that allows one to run Graphical User
Interface (GUI) applications from the Linux servers.
Use the File Explorer to navigate to Q:\eng\ece\Util folder, scroll down until
you find the MobaXterm icon and double click it (see Figure C1). The MobaXterm
window will pop up. There is a grey rectangular button labelled “Start local terminal” in the middle (see Figure C2). Click this button.
Then a terminal session starts. You will need to use the command line ssh command to connect to the Linux server. Use your UWID and password to login. The

32

Figure C1: MobaXterm Path on ECE Nexus Windows 10 Machines.

Figure C2: MobaXterm Welcome Page.
syntax of the command is as follows:
ssh -XY @eceubuntu.uwaterloo.ca

See Figure C3 for reference.
33

Figure C3: MobaXterm Welcome Page.
All your ECE Linux account files are accessible through P Drive on Nexus machines (See Figure C4). The P Drive is only accessible within campus network. Mapping the Linux account as a network drive off campus is not supported due to security reasons.

1.3

Basic Software Development Tools

To develop a program, there are three important steps. First, a program is started
from source code written by programmers. Second, the source code is then compiled
into object code, which is a binary. Non-trivial project normally contains more than
one source file. Each source file is compiled into one object code and the linker would
finally link all the object code to generate the final target, which is the executable that
runs. The steps of compiling and linking are also known as building a target. It is
very rare that the target will run perfectly the first time it is built. Most of time we
need to fix defects and bugs in the code and the this is the third step. The debugger
is a tool to help you identify the bug and fix it. Table C1 shows the key steps in
programming work flow and example tools provided by a general purpose Linux
operating system.
Most of you probably are more familiar with a certain Integrated Development
34

Figure C4: Linux files on P drive, a network mapped drive.
Task
Tool
Examples
Editing the source code
Editor
vi, emacs
Compiling the source code Compiler gcc
Debugging the program
Debugger gdb, ddd
Table C1: Programming Steps and Tools

Environment (IDE) which integrates all these tools into a single environment. For
example Eclipse and Visual Studio. A different approach is to select a tool in each
programming step and build your own tool chain. Many seasoned Linux programmers build their own tool chains. A few popular tools are introduced in the following
subsections.

1.3.1

Editor

Some editors are designed to better suit programmers’ needs than others. The vi (vim
and gvim belong to the vi family) and emacs (xemacs belongs to emacs family) are the
two most popular editors for programming purposes.
Two simple notepad editors pico and nano are also available for a simple editing
job. These editors are not designed for programming activity. To use one of them to
write your first Hello World program is fine though.
After you finish editing the C source code, give the file name an extension of .c.
Listing 1.1 is the source code of printing ”Hello World!” to the screen.
35

#include 
#include 
int main()
{
printf("Hello World!\n");
exit(0);
}
Listing 1.1: HelloWorld C source Code

1.3.2

C Compiler

The source code then gets fed into a compiler to be come an executable program.
The GNU project C and C++ compiler is gcc. To compile the HelloWorld source code
in Listing 1.1, type the following command at the prompt:
gcc helloworld.c+

You will notice that a new file named a.out is generated. This is the executable generated from the source code. To run it, type the following command at the prompt
and hit Enter.
./a.out

The result is“Hello World!” appearing on the screen.
You can also instruct the compiler to name the executable another name instead
of the default a.out. The -o option in gcc allows one to name the executable a
name. For example, the following command will generate an executable named
“helloworld.out”.
gcc helloworld.c -o helloworld.out

although there is no requirement that the name ends in .out.

1.3.3

Debugger

The GNU debugger gdb is a command line debugger. Many GUI debugger uses
gdb as the back-end engine. One GNU GUI debugger is ddd. It has a powerful data
display functionality.
36

GDB needs to read debugging information from the binary in order to be able to
help one to debug the code. The -g option in gcc tells the compiler to produce such
debugging information in the generated executable. In order to use gdb to debug our
simple HelloWorld program, we need to compile it with the following command:
gcc -g helloworld.c -o helloworld.out

The following command calls gdb to debug the helloworld.out
gdb helloworld.out

This starts a gdb session. At the (gdb) prompt, you can issue gdb command such
as b main to set up a break point at the entry point of main function. The l lists
source code. The n steps to the next statement in the same function. The s steps
into a function. The p prints a variable value provided you supply the name of the
variable. Type h to see more gdb commands.
Compared to gdb command line interface, the ddd GUI interface is more user
friendly and easy to use. To start a ddd session, type the command
ddd

and click File → Open Program to open an executable such as helloworld.out. You
will then see gdb console in the bottom window with the source window on top
of the gdb console window. You could see the value of variables of the program
through the data window, which is on top of the source code window. Select View
→ to toggle all these three windows.

1.4

More on Development Tools

For any non-trivial software project, it normally contains multiple source code files.
Developers need tools to manage the project build process. Also project normally
are done by several developers. A version control tool is also needed.

1.4.1

How to Automate Build

Make is an utility to automate the build process. Compilation is a cpu-intensive job
and one only wants to re-compile the file that has been changed when you build a
target instead of re-compile all source file regardless. The make utility uses a Makefile to specify the dependency of object files and automatically recompile files that
has been modified after the last target is built.
37

In a Makefile, one specifies the targets to be built, what prerequisites the target
depends on and what commands are used to build the target given these prerequisites. These are the rules contained in Makefile. The Makefile has its own syntax. The
general form of a Makefile rule is:
target ...: prerequisites ...
recipe
...
...

One important note is that each recipe line starts with a TAB key rather than white
spaces. To build a target, use command make followed by the target name or omit
the target name to default to the first target in the Makefile. For example
make

will build your lab starter code.
Listing 1.2 is our first attempt to write a very simple Makefile.
helloworld.out: helloworld.c
gcc -o helloworld.out helloworld.c
Listing 1.2: Hello World Makefile: First Attempt
The following command will generate the helloworld.out executable file.
make helloworld.out

Our second attempt is to break the single line gcc command into two steps. First
is to compile the source code into object code .o file. Second is to link the object code to
one final executable binary. Listing 1.3 is our second attempted version of Makefile.
helloworld.out: helloworld.o
gcc -o helloworld.out helloworld.o
helloworld.o: helloworld.c
gcc -c helloworld.c
Listing 1.3: Hello World Makefile: Second Attempt
When a project contains multiple files, separating object code compilation and
linking stages would give a clear dependency relationship among code. Assume that
we now need to build a project that contains two source files src1.c and src2.c
and we want the final executable to be named as app.out. Listing 1.4 is a typical
example Makefile that is closer to what you will see in the real world.
38

all: app.out
app.out: src1.o src2.o
gcc -o app.out src1.o src2.o
src1.o: src1.c
gcc -c src1.c
src2.o: src2.c
gcc -c src2.c
clean:
rm *.o app.out
Listing 1.4: A More Real Makefile: First Attempt
We also have added a target named clean so that make clean will clean the build.
So far we have seen the Makefile contains explicit rules. Makefile can also contain
implicit rules, variable definitions, directives and comments. Listing 1.5 is a Makefile that
is used in the real world.

5

# Makefile to build app.out
CC=gcc
CFLAGS=-Wall -g
LD=gcc
LDFLAGS=-g

7

OBJS=src1.o src2.o

1
2
3
4

9
10
11
12
13
14
15
16

all: app.out
app.out: $(OBJS)
$(LD) $(CFLAGS) $(LDFLAGS) -o $@ $(OBJS)
.c.o:
$(CC) $(CFLAGS) -c $<
.PHONY: clean
clean:
rm -f *.o *.out
Listing 1.5: A Real World Makefile
Line 1 is a comment. Lines 2 − 7 are variable definitions. Line 12 is an implicit rule to
generate .o file for each .c file. See http://www.gnu.org/software/make/manual/
make.html to explore more of makefile.

1.4.2

Version Control Software

We use Git version control software. It is installed both on the Linux servers and
Nexus windows machines. If you decide to use GitHub to host your repository,

39

please make sure it is a private one. Go to http://github.com/edu to see how to
obtain five private repositories for two years on GitHub for free.

1.4.3

Integrated Development Environment

Eclipse with C/C++ Plug-in has been installed on all ECE Linux servers. Type the
following command to bring up the eclipse frontend.
/opt/eclipse64/eclipse

This eclipse is not the same as the default eclipse under /usr/bin directory. You
may find running eclipse over network performs poorly at home though. It depends
on how fast your network speed is.
If you have Linux operating system installed on your own personal computer,
then you can download the eclipse with C/C++ plugin from the eclipse web site
and then run it from your own local computer. However you should always make
sure the program will also work on ecelinux machines, which is the environment
TAs would be using to test your code.

1.5

Man Page

Linux provides manual pages. You can use the command man followed by the specific command or function you are interested in to obtain detailed information.
Mange pages are grouped into sections. We list frequently used sections here:
• Section 1 contains user commands.
• Section 2 contains system calls
• Section 3 contains library functions
• Section 7 covers conventions and miscellany.
To specify which section you want to see, provide the section number after the
man command. For example,
man 2 stat

shows the system call stat man page. If you omit the 2 in the command, then it
will return the command stat man page.
You can also use man -k or apropos followed by a string to obtain a list of
man pages that contain the string. The Whatis database is searched and now run
man whatis to see more details of whatis.
40

Appendix A
Forms
Lab administration related forms are given in this appendix.

41

ECE252 Request to Leave a Project Group Form
Name:
Quest ID:
Student ID:
Lab Assignment ID
Group ID:
Name of Other Group Members:

Provide the reason for leaving the project group here:

Signature

Date

42

Bibliography
[1] Greg Roelofs. PNG: The Definitive Guide. O’Reilly & Associates, Inc., Sebastopol,
CA, USA, 1999.

43



File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.5
Linearized                      : No
Page Count                      : 51
Page Mode                       : UseOutlines
Author                          : 
Title                           : 
Subject                         : 
Creator                         : LaTeX with hyperref package
Producer                        : pdfTeX-1.40.18
Create Date                     : 2019:06:18 14:35:59-04:00
Modify Date                     : 2019:06:18 14:35:59-04:00
Trapped                         : False
PTEX Fullbanner                 : This is pdfTeX, Version 3.14159265-2.6-1.40.18 (TeX Live 2017/Debian) kpathsea version 6.2.3