COMP 3430 - Operating Systems Assignment 1

COMP 3430 - Operating Systems

Assignment 1

Summer 2021

Description

General submission requirements

Question 1: ELF

oWhat to print

ELF Header

Program Headers

Section Headers

oRunning

oChecking your output

oEvaluation

Implementation

Question 2: Comparing processes and threads

oRequirements

Hypothesis

Writing your solution

Analyzing performance

oEvaluation

Implementation

Report

Submitting your assignment

General Advice

Description

For assignment 1, we are looking for you to be able to compare and contrast threads and processes. One of the ways that you are going to be investigating that is by writing some code and running some experiments to see what the performance differences are between launching a process and launching a thread.

Assignment 1 is due Friday, June 4th, 2021 at 4:30pm CDT (Winnipeg time).

General submission requirements

Submissions that violate any of the following will not be evaluated (i.e., you will receive a score of 0 for the assignment):

All solutions must be written in C. No other languages are accepted.

All solutions must include a working Makefile.

oForget how to make a Makefile? Never knew how to make a Makefile? Thankfully, you can go to https://makefiletutorial.com and find some very easy to use basic examples.

oYour Makefile should contain a clean rule. When

make clean

is run in your directory, all the temporary files, including the executable should be removed (e.g., rm -f my_prog).

All solutions must be compiled by issuing the command make in the directory containing the Makefile. No other build commands are acceptable, even if documented in the README.md.

All solutions must include a Markdown-formatted README.md file that minimally describes how to run your submission.

oForget how to make a README.md? Never knew how to make README.md? Thankfully, you can go to https://readme.so/ and build a nice, Markdown-formatted README.md with a nice preview and some handy buttons to help you build it.

All solutions must run to successful completion. Premature termination for any reason (no obvious output, Segmentation Fault, Bus Error, etc.) is considered to be a solution implementation that does not run.

Code that runs for an unreasonably long time (e.g., > 30 seconds) without terminating is also considered to be a solution implementation that does not run.

All solutions must compile. Code that does not compile will not be evaluated.

Programs must produce no errors when compiled with the flags

-Wall -Wpedantic -Wextra -Werror

Note that -Werror prevents your code from being compiled when warnings are present.

If these flags are not in your Makefile, your submission will be treated as though it does not compile.

Your code must compile and run on a machine on aviary.cs.umanitoba.ca.

No late submissions will be accepted. The assignment deadline is enforced electronically. Submissions will not be accepted by e-mail.

Reminder: All submitted code will be evaluated using an automated similarity testing tool, alongside commonly available online solutions for problems.

Question 1: ELF

One of the first things than an operating system does when launching a new process is to read the program into memory. Some operating systems (including Linux) use ELF formatted binaries to represent compiled programs.

Using one of the two strategies for reading binary files described in class, write a program that reads an ELF formatted file and writes out some information about the program. Your program should work for both 32-bit and 64-bit ELF files.

What to print

ELF Header

From the ELF header, your program should print out:

1.Whether the program is 32-bit or 64-bit.

2.The endianness of the file.

3.The target operating system ABI.

4.The object file type.

5.The instruction set architecture.

6.The address of the entry point from where the process starts executing.

7.The size of an entry and the number of entries in the program header table.

8.The size of an entry and the number of entries in the section header table.

9.The entry in the section headers that is the string table.

ELF header sample output

ELF header:

* 64-bit

* little endian

* compiled for 0x00 (operating system)

* has type 0x02

* compiled for 0x3e (isa)

* entry point address 0x00000000004010c0

* program header table starts at 0x0000000000000040

* there are 11 program headers, each is 56 bytes

* there are 33 section headers, each is 64 bytes

* the section header string table is 32

Program Headers

For each program header, your program should print out:

1.The segment type.

2.The virtual address of the segment in memory.

3.The first (up to) 32 bytes of actual segment data, formatted as hexadecimal bytes. Your output should be 16 bytes wide.

Program header sample output

Program header #0:

* segment type 0x00000006

* virtual address of segment 0x0000000000400040

* size in file 616 bytes

* first up to 32 bytes starting at 0x0000000000000040:

06 00 00 00 04 00 00 00 40 00 00 00 00 00 00 00

40 00 40 00 00 00 00 00 40 00 40 00 00 00 00 00

Section Headers

For each section header, your program should print out:

1.The name of the section.

oThe ELF header specifies which section header is the string table section header (this is the last field in the ELF header). You can find the names for sections in the file at the offset specified by the section header that is the string table section.

2.The section header type.

3.The virtual address of the section in memory.

4.The first (up to) 32 bytes of actual section data, formatted as hexadecimal bytes. Your output should be 16 bytes wide.

Section header sample output

Section header #23

* section name .data

* type 0x01

* virtual address of section 0x0000000000400040

* first up to 32 bytes starting at 0x0000000000000040:

06 00 00 00 04 00 00 00 40 00 00 00 00 00 00 00

40 00 40 00 00 00 00 00 40 00 40 00 00 00 00 00

Running

Your program should accept the name of the ELF file it should read as its first (and only) argument. Your program should be able to read itself. Here are some examples of what you might want to check out:

./a1q1 a1q1

./a1q1 /usr/bin/cat

Checking your output

Use the readelf command to help you check your output. The readelf command will let you print out different parts of the file (different headers) by passing different flags. To learn more about which flags print out which section, take a look at man readelf.

To check that you’re printing the correct bytes for the different sections, you can use a tool like hexdump along with the -s option. To learn more about how to use hexdump, take a look at man hexdump.

Evaluation

Implementation

5 points are awarded for code quality and design. “High quality” is defined as code that follows the standards and best practices that you can find in the “Standards and Best Practices” folder at the root of the Assignments section on UM Learn:

Level Description

0 The code is very poor quality (e.g., no comments at all, no functions, poor naming conventions for variables, etc).

1–3 The code is low quality, while some coding standards are applied, their use is inconsistent (e.g., inconsistent use of comments, some functions but functions might do too much, code is repeated that should be in a function, etc).

This is the maximum level you can earn if the implementation of your program is substantially incomplete.

4–5 the code is high quality, coding standards are applied consistently throughout the code base.

10 points are awarded for implementation (5 × 2):

Level Description

0 Submitted code does not run or compile.

1–2 Submitted code is substantially incomplete (e.g., only the ELF header is read and produced as output).

3–4 Submitted code is substantially complete, but still incomplete (e.g., all sections are present, but some are not correctly reproduced).

5 Submitted code is complete and accurate.

Question 2: Comparing processes and threads

Experiment (Pixabay License)

Here’s a function that does some really hard work:

#define NANOS_PER_SECOND 1000000000

static void *hard_work(void *work)

{

long *amount = (long*) work;

long seconds = *amount / NANOS_PER_SECOND;

long nanos = *amount % NANOS_PER_SECOND;

struct timespec t = { .tv_sec = seconds, .tv_nsec = nanos };

int ret;

{

ret = nanosleep( &t, &t ); // **Really** hard work.

// need to loop, `nanosleep` might return before sleeping

// for the complete time (see `man nanosleep` for details)

} while (ret == -1 && (t.tv_sec || t.tv_nsec));

return work;

}

This function takes exactly 1 argument (work), which is a pointer to an long. The function will “work” for work nanoseconds, then return. Conveniently, this function is written in a way that’s straightforward to use with pthreads.

Your job is to implement two programs (in 2 different .c files) that will run this code fragment many times:

1.One that uses threads to run this code, and

2.One that uses processes to run this code.

Your goal is to experimentally determine the time difference between creating a thread and creating a process.

We cannot reliably measure the amount of time it takes to launch 1 process or 1 thread, launching just one of either will take very little time. Instead, you’re going to be launching many threads or processes over a period of time and measuring the cumulative cost of launching threads or processes.

Requirements

Hypothesis

Before you start writing any code, you should come up with a hypothesis and record that hypothesis in your README.md: do you think that processes are going to take longer to create, or do you think that threads are going to take longer to create?

Your original hypothesis might not be correct! That’s OK!

Writing your solution

While this is mostly left as an exercise for the reader, there are some strict requirements about how you implement this:

1.Your program is going to run many processes/threads over a long period of time, let’s say x in total, but your program should not be running x processes/threads at the same time.

Instead, at any point in time, your program should not be running more processes or threads than some fixed number y. A good starting point would be to set y = 1 (one process/thread at a time), then increase the number of processors available on the system (e.g., if there are 8 processors on the system, then set y = 8). This means that your program will only ever have up to y processes/threads running at any given time.

You can find out how many processors are installed on a Linux system by running lscpu and looking at the “CPU(s)” property.

So while your code might cumulatively launch x = 40000 processes/threads, if y = 8, then only up to 8 will ever be running at the same time.

2.Your code should not use any kind of locks, inter-process communication, files, etc. Introducing any of those will change the measurements that you are taking from “how long does a thread or process take to launch?” into “how long does locking or I/O take?”

The main process in your code has the responsibility of launching y processes/threads before it waits for at least one of those processes/threads to terminate. You do not need any special tools to do this; conditional statements, loops, and counters are enough to limit the number of processes/threads that you launch.

3.Your program should be able to be configured at runtime (i.e., passing command-line arguments) to launch different numbers of concurrent processes/threads and a different number of total processes/threads. That is, I should be able to say “run the experiment with 10 total processes 3 at a time”, then “run the experiment with 10,000 processes 16 at a time”.

For example:

./a1q2 10 3 # 10 total processes, 3 at a time

./a1q2 10000 16 # 10000 total processes, 16 at a time

4.There are at least two options for how you limit the number of workers: start y at a time and then wait for all y to complete before launching another y, or start y and launch another as soon as one finishes.

You’re welcome to use either of these approaches (or a different approach entirely), but whichever approach you choose should be used consistently for both processes and threads.

Analyzing performance

To analyze performance, you’re going to need to run several different experiments. Each experiment that you run should change the total number of processes/threads that are being launched, and you should record the total time taken to run the experiment.

The output for your program will change each time you run it, so you can consider taking an average of several runs with the same settings.

An example table for these experiments would look like:

Total processes/ threads (x) Concurrent processes/ threads (y) Threads time Processes time

100 4 … …

100 8 … …

100 32 … …

1000 4 … …

1000 8 … …

1000 32 … …

10000 4 … …

10000 8 … …

10000 32 … …

Your report should clearly answer some questions:

1.Which is faster: threads or processes?

2.Does your result match your hypothesis? Why do you think it does, or why do you think it does not? You can refer to our textbook here in terms of what happens when threads and processes are launched.

3.Is there a point of diminishing returns on how many concurrent processes/threads are running? That is, when does execution time start to grow very quickly as you increase the number of concurrent processes/threads (y)? Try to explain what might be happening here. (Note: you’re probably going to have to use y > 32 to get to this point of diminishing returns)

For timing, do not use the system time command – it is not granular enough. Take a look at Profiling Code Using clock_gettime by Guy Rutenberg for a complete example on how to profile code with high precision. The code in Guy’s blog post is explicitly permitted to be used in your own solutions.

You should include your report in your README.md file.

Suggestions

Working with tables in text (e.g., Markdown) is sorta painful, but almost all popular text editors have extensions or plugins that help ease this pain:

Text Tables by RomanPeshkov is one that seems to be popular for VS Code.

VIM Table Mode by Dhruva Sagar is one that I use personally in vim.

Evaluation

Implementation

Level Description

0 The code is very poor quality (e.g., no comments at all, no functions, poor naming conventions for variables, etc).

This is the maximum level you can earn if the implementation of your program is substantially incomplete.

4–5 the code is high quality, coding standards are applied consistently throughout the code base.

10 points are awarded for implementation (5 × 2):

Level Description

0 Submitted code does not run or compile.

1 Submitted code is not concurrent (does not use threads or processes).

2–3 Submitted code is minimally concurrent. Threads and processes are used, but the implementation may not appropriately constrain the number of concurrent threads or processes.

4–5 Submitted code is concurrent. Threads and processes are used and the implementation appropriately constraints the number of concurrent threads or processes.

Report

5 points are awarded for the report:

Level Description

0 No report is included in the submission package.

1 – 2 A report is submitted, but is missing substantial parts and provides no meaningful conclusions about threading vs processes.

3 – 4 The report is submitted and coherent, but is missing some parts or does not include enough data points in the experiment to reasonably draw conclusions. The conclusions drawn about threading vs processes does not include any discussion about OS implementation of threads and processes.

5 The report is submitted, coherent, and complete. The conclusions drawn about threading vs processes includes meaningful discussion about OS implementation of threads and processes.

Bonus

A 5 point bonus is available for an extended analysis: Conduct and report on your experiments on all three of Windows (2 points), macOS (2 points) and Linux. Does the conclusion you came to about threads vs processes hold for all three OS implementations? Can you draw any inferences about OS-specific implementations of threads and processes based on these results? (1 point for extended report)

Note 1: macOS here is explicitly defined as rodents.cs.umanitoba.ca (i.e., not your personal mac). If you attempt this bonus, but your code does not compile and run on rodents, you will not be awarded bonus points for macOS.

Note 2: Windows here is explicitly not WSL; you must get this to run natively on Windows, noting further that native Windows software does not use pthreads. If you attempt this bonus, but your code does not compile and run on Windows 10 with Visual Studio, you will not be awarded bonus points for Windows.

Submitting your assignment

Submissions will be made using the handin command available on all CS UNIX systems.

You should be submitting at least the following files:

A Makefile (you are permitted to have more than 1 Makefile, e.g., if you want to have one Makefile per question).

A README.md that includes a summary of how to compile and run your programs (compiling should be “run make”, but you should explicitly tell the grader how to run your program, e.g., what arguments to pass to the program on the command line).

Your solution for question 1 (probably just 1 .c file).

Your solution for question 2 (probably 2 .c files).

If your files are in a folder named my_a1, you would run the command:

handin 3430 a1 my_a1

You can see man handin if you need more information.

General Advice

Here’s some general advice that you can choose to follow or ignore:

1.The debugger is your best friend. Don’t even start trying to solve these problems until you’re comfortable with a debugger (either lldb or gdb). The first question I’m going to ask when you come to ask me for help is: “Have you tried running it through the debugger yet?” If you answer “no”, I’ll send you away to do that first, then come back.

2.Source control is your second best friend. The department hosts an instance of GitLab that you can use to store private projects. You’re also welcome to use private repositories on GitHub.

联系我们