Final exam
Due 5:00PM Wed, March 16
Submit via Moodle as final.tar. Include your answers in final.pdf or final.txt, with source code (if any) in appropriately named C files.
This is a takehome exam. You may your textbook and online sources, as long as you cite them clearly. You may not speak with anyone other than Jeff Ondich about the content of this exam. That means in particular that you may not talk with your classmates or post questions on online forums. You may, however, ask questions during class and via the #questions channel of our class Slack workspace (and, of course, via Slack direct message to Jeff).
When answering questions on this exam, you should show your work to get full credit. For example, in the very first question 1(a), it's not sufficient to provide the correct 8-digit hexadecimal number. You must also explain (concisely and clearly) why that particular 32-bit number represents the given real number.
(8 points) Floating point numbers
Read Section 2.4 ("Floating Point") of your textbook. All of the following questions refer to the IEEE 754 single precision (32-bit) representation of real numbers.
- What is the representation of the real number -49.625? Give your answer as a single 8-digit hexadecimal number.
- To what real number does the 32-bit IEEE 754 representation 0x40155555 correspond? Please express your answer as a fraction. (Note: since the significand appears to have a repeating pattern, you may find that extending that pattern infinitely gives you a simpler fraction than the rounded off version stored in this 32-bit float.)
- What is the largest real number that IEEE 754 single precision can represent?
- What is the 32-bit representation of NaN? (i.e. "not a number"). Show your answer as an 8-digit hexadecimal number.
- Show a small amount of C code that can be used to cause a float-type variable x to contain NaN. (You can test this using a printf("%f", x); statement.)
(6 points) C miscellany
What does the following code print? Explain why.
int k = 6778724; char *char_pointer = (char *)(&k); printf("%s", char_pointer);What does the following code print? Explain why.
char s[6] = "goat"; char *p1 = s; p1++; unsigned long k = ((unsigned long)p1) - ((unsigned long)s); printf("First: %ld\n", k); int a[6] = {21, 22, 23, 31, 32, 33}; int *p2 = a; p2++; k = ((unsigned long)p2) - ((unsigned long)a); printf("Second: %ld\n", k);
(8 points) Parameter passing in C
Consider the short program person.c. This program defines a type person_t and some functions that take person_t objects as parameters or return values. Because a variable of type person_t takes up more than 8 bytes, you can't fit it in a register. This exercise gives you a chance to briefly investigate how the gcc compiler arranges for passing parameters that don't fit in registers.
Answer each of the following questions, justifying your answer in terms of the assembly language generated by compiling person.c on mantis using
gcc -Wall -Werror -g -Og -no-pie -o person person.c- Show a diagram of the stack frame for person_test just before the first callq create_person instruction in person_test is executed.
- Show a diagram of the stack frames for person_test and create_person just before the add $0x40,%rsp instruction in create_person (immediately preceding a pop instruction and a retq instruction) is executed. Do this for the first time create_person is called in person_test.
If we uncomment the line:
strcpy(person1.name, "Friedrich Schiller");in the is_older function, does the printed output produced by this program change? Why or why not? (Explain your answer in terms of the actual assembly language code and the contents of the stack, not just in terms of more generic statements about C.)
(8 points) x86_64 adressing modes
Write this short C function:
// Returns the sum of the first n integers in the specified array. // Returns 0 if n <= 0 or numbers == NULL. int sum(int *numbers, int n) { // ... }Put your function in a source file named sum.c and include it in your exam submission.
- Show the assembly language generated by using gcc -g -Og ... to compile your function.
Read about x86_64 addressing modes. Your textbook discusses them on page 181. The addressing mode names referenced on that page are the ones I want you to focus on. Specifically:
- immediate
- register
- absolute
- indirect
- base + displacement
- indexed
- scaled indexed
(There are tons of readings about addressing modes online, and you can certainly look around. Note that it gets messy, though, since there are several different notations for instructions, and there are some variations in the naming of addressing modes. "Immediate" always means "there's a hard-coded number in the instruction", but "Base + displacement" might sometimes be called "Direct-Offset" or something similar. Just pay careful attention to the meanings of the words being defined.)
- Identify as many addressing modes as you can in the assembly language compiled from your sum() function. For each addressing mode you find, point to one instruction that exemplifies it, and give a brief explanation of what that addressing mode is used for in context (in most cases this shouldn't take more than one short sentence).
(10 points) Paged virtual memory
For this exercise, you're going to identify all the virtual pages used by the person.c program. The point here is to get a sense of (1) how much total memory a small program uses and (2) which categories and regions the relevant pages fall in.
Make the following assumptions:
- Pages are 4KB long (2^12 bytes)
- There's 16GB of physical memory (2^34 bytes)
- And, of course, addresses are 64 bits
For some of the questions below, you should compile person.c with the -g -Og -no-pie flags and either examine the code in gdb or dump it with objdump -d (or both). (By the way, the -no-pie flag will give us a consistent set of addresses for to refer to when studying this code.)
- How many bytes of virtual memory are there?
- How many virtual pages are there?
- How many bits are in a virtual page number?
- How many physical pages are there?
List all the virtual pages (by starting virtual address) that are used during one run of the person program. (You may specify ranges of page numbers.) Please
For each page or page range that you list here,
briefly state what the page is used for (e.g. instructions, stack, etc.)
You should simplify this item by only counting pages that are referenced in some way by the functions in person.c (create_person, is_older, age, person_test, and main). You don't need to try to figure out what memory is used by strncpy or printf or deregister_tm_clones.
- What percentage of total available virtual memory space do the pages you listed in the previous item use?
- If all the pages you listed two items ago were in physical memory at once, what percentage of the available physical memory would they use?
(2 points) I need something new to read. Could you recommend a book for me?
(10 points) Threaded programming (please submit as threads.c)
Earlier this term, you learned to use fork() to create new processes. Though it was possible to get those processes to communicate with each other using pipes, Unix signals and shared memory, those techniques can be quite awkward to manage.
Another common technique for causing different pieces of code to execute simultaneously (or at least to simulate simultaneity by taking turns) is called threading. A single process can have multiple threads, each of which is performing different computations. The threads within a single process can communicate via global variables, which tends to make inter-thread communication a lot simpler than inter-process communication.
In C, a very common way to use threads is via the pthreads library. For this exercise, you are going to write a simple multi-threaded program using pthreads.
One common use of threads is to have one thread communicate with the user (sometimes called a UI thread or interface thread), and another thread (a worker thread) perform some intensive computation. Sometimes, the worker thread will occasionally report back to the UI thread so the user can receive some feedback. This pthreads_sample.c, for example, uses a UI thread to wait for the user to hit Enter, while the worker thread does the all-important work of counting as high as possible as fast as possible. By separating these two jobs (taking input from the user and counting-real-high), the resulting code is simpler.
Another common use of threading is to enable a program to accept and process a sequence of user requests, even if some of the requests take a long time to execute. In this scenario, the program might have a UI thread to accept user input, and then each time the user makes a request, the program spawns a new thread to handle the request, allowing the UI thread to wait for another request. Web servers work a lot like this: receive a query, spawn a thread or process or thread to handle the query, go back to listening for new queries. Again, by separating the UI from the other computations, the overall structure of the code is (or can be) simpler, and thus easier to debug and maintain.
For this exercise, you're going to write a threaded program of this latter variety. When the user runs the program, it should do the following:
Spawn a UI thread that does:
- Print a prompt along the lines of "Type a positive integer:"
- Read user input using fgets(..., stdin).
- If the user typed "q" or "Q", exit the program.
- If the user typed an integer N, spawn a worker thread and pass it N as an argument.
- If the user typed something else, don't do anything.
- Repeat
For each worker thread:
- Count the number of prime numbers <= N
Do the count using a crappy algorithm so it takes plenty of time. Here's a particularly bad function you could use to ensure inefficiency:
// Returns 1 if n is prime, 0 otherwise. int is_prime(int n) { if (n <= 1) { return 0; } for (int k = 2; k < n; k++) { if (n % k == 0) { return 0; } } return 1; }- Done counting? Print a message to stdout reporting the number of primes <= N.
- End this thread's execution by returning from the thread's main function.
NOTE: because the worker threads and the UI thread are all printing to stdout, some users may become confused. For today, we're not going to worry about that.
You should be able to get well started just using pthreads_sample.c, but if you have questions and ask nicely, I might have another sample or two to help with specific issues.