Contents
CS 3214 Spring 2020 Final Exam
May 11, 2020
1 Input and Output (16 pts) 2
2 Running Threads (12 pts) 3
3 Dynamic Memory Management (18 pts) 3
3.1 Sequence1(8pts) ………………………………. 3 3.2 Sequence2(10pts)………………………………. 4
4 Automatic Memory Management (18 pts) 4
4.1 ObjectReachabilityGraph,Take1,(12pts)………………….. 4 4.2 ObjectReachabilityGraph,Take2,(6pts) ………………….. 5
5 Virtual Memory (18 pts) 5
5.1 On-demandPaging(6pts)…………………………… 5 5.2 FilesandMemory(6pts) …………………………… 7 5.3 The3C’sofVirtualMemory(6pts)……………………… 8
6 Networking (18 pts) 8
6.1 FileTransfer(6pts) ……………………………… 8 6.2 JWT(6pts) …………………………………. 9 6.3 TooQUIC?(6pts)………………………………. 9
7 Submission Requirements 10
Rules
This exam is open book, open notes, and open Internet, but in a read-only way. You are not allowed to post or otherwise communicate with anyone else about these problems. If you have a question, you may post it as a private question on Piazza.
1
1 Input and Output (16 pts)
As part of this class, we have the goal of ensuring that everyone has mastered basic Unix skills. Consider the shell script runmyst.sh shown below. It invokes a command ./myst which refers to an executable in the current directory.
When sourced from a bash shell, you would see:
$ source runmyst.sh
output 1
one
two
three
output 2
four
five
Write a program myst.c that, when compiled to myst, will produce this exact output when it is invoked as part of running this shell script.
You may not hardwire any of the values of the variables shown at the beginning of the script (VAR1, VAR2, etc.) in your program. In other words, your program should still produce equiv- alent output if any of these are replaced in the shell script. Each variable is assumed to be a distinct sequence of only alphanumeric characters; that is, “VAR1=one” could be replaced with “VAR1=OneOne”, but not with “VAR1=one one” or “VAR1=2>one” or similar.
#!/bin/bash
VAR1=one
VAR2=two
VAR3=three
VAR4=four
VAR5=five
FILE=file
STDERR=stderr
STDOUT=stdout
STDIN=stdin
echo -n ${VAR1} > ${STDIN}
echo -n ${VAR4} > ${FILE}
export ENVVAR=${VAR3}
./myst < ${STDIN} ${VAR2} ${VAR5} ${FILE} 2> ${STDERR} | cat > ${STDOUT}
echo “output 1”
# must be VAR1, VAR2, VAR3 on 3 lines cat ${STDOUT}
echo “output 2”
# must be VAR4, VAR5 on 2 lines
cat ${STDERR}
2
2 Running Threads (12 pts)
Process or threads that are in the RUNNING state consume CPU time. Write a (possibly multi- threaded) program that, when run with the bash builtin time command on an unloaded machine with at least 4 CPUs or cores, outputs this:
$ time ./two2eight
real 0m2.002s
user 0m7.998s
sys 0m0.004s
(The reported real time should be about 2s, the user time about 8s, the system time less than 0.01s. Small deviations of less than 0.2s are ok. Hint: use gettimeofday(2) and timersub(3))
3 Dynamic Memory Management (18 pts)
Suppose a user-level implementation of malloc() implements the following policies:
• A single free list is kept.
• A first-fit policy is used.
• The free list is accessed in LIFO fashion (the most recently freed block appears at the head of the list).
• Block splitting makes use of the lower address portion of a block and puts the higher address portion onto the free list.
• Boundary tag headers and footers are used to enable coalescing.
• Freed blocks are immediately coalesced.
• If possible, realloc() always extends a block.
• If the allocator is out of memory, it will extend the heap in chunks of 8000 bytes each time. Initially, the heap is contains 0 bytes.
3.1 Sequence 1 (8 pts)
Consider the following sequence of calls:
void * a1 = malloc(2000);
void * a2 = malloc(1000);
void * a3 = malloc(1000);
free(a2);
realloc(a1, 2500)
free(a3);
3
Sketch the layout of the memory region managed by the allocator. For the purposes of this question, you may ignore the space taken up by boundary tags and link elements. Clearly denote used and free blocks of memory and their respective sizes. For instance, after a single call to malloc(7000), a sketch of the heap when managed by an allocator that followed above mentioned policies would look like this:
<-------- used block (7000) ------->
<-------- free block (1000) ------->
where the first line denotes the block with the lowest address in memory.
3.2 Sequence 2 (10 pts)
Consider the following sequence of calls:
void * a1 = malloc(1000);
void * a2 = malloc(500);
void * a3 = malloc(1000);
void * a4 = malloc(500);
void * a5 = malloc(1000);
void * a6 = malloc(500);
free(a4);
free(a6);
free(a5);
a4 = malloc(250);
free(a3);
free(a4);
and sketch the heap layout resulting from this sequence as well.
4 Automatic Memory Management (18 pts) 4.1 Object Reachability Graph, Take 1, (12 pts)
In systems using automatic memory management, it is important to understand how the object reachability graph changes as a result of a program’s action. Figure 1 shows a snapshot of reacha- bility graph produced by the execution of a small Java program.
Reconstruct this program, and denote with a comment the point in time at which the reachability graph has the structure displayed in Figure 1.
4
Figure 1: A snapshot of an object reachability graph produced by a Java program. On the left, roots that are part of stack frames are shown, corresponding to static methods main and fun.
4.2 Object Reachability Graph, Take 2, (6 pts)
Now consider the following reachability graph.
Figure 2: Object reachability graph (garbage collection has yet to occur). Roots are shown as squares, heap-allocated objects are shown as ovals.
Write a program in a garbage-collected language of your choice that would produce this reach- ability graph. (root may be an arbitrary root, and obj0 to obj9 may be arbitrary objects in your chosen language.)
5 Virtual Memory (18 pts) 5.1 On-demand Paging (6 pts)
Like most modern OS, Linux uses fully on-demand paged virtual memory. The getrusage system call can be used to obtain information regarding the number of page faults a process experienced during its execution. Consider the following program pagefaults.c:
5
#include
static void
report_vm_stats()
{
struct rusage u;
getrusage(RUSAGE_SELF, &u);
printf(“ru_minflt %ld\n”, u.ru_minflt);
printf(“ru_majflt %ld\n”, u.ru_majflt);
}
/* you may make changes here */
int
main() {
/* you may make changes here */
report_vm_stats();
}
When run on a Linux machine, it outputs the number of minor page faults and major page faults that have occurred from when this process was created with fork() to when getrusage() was called. The man page for getrusage() describes these values as:
ru_minflt
The number of page faults serviced without any I/O activity; here I/O
activity is avoided by “reclaiming” a page frame from the list of pages
awaiting reallocation.
ru_majflt
The number of page faults serviced that required I/O activity.
When compiled and run as given, this program will output the number of minor page faults it experienced (on our current rlogin machines, this number can vary slightly between runs and is approx. 175). The number differs between Linux OS versions and possibly also between the versions of the toolchains used to build the executable.
Task 1: Modify pagefaults.c such that the number of minor page faults reported increases by approximately 256. A range from 240 to 270 is acceptable. For instance, on our rlogin machines, a range from 175 + 240 = 415 to 175 + 270 = 445 would be acceptable.
Task 2: We claim that modifying pagefaults.c to reliably cause a similar number of major page faults is much more difficult.
Either modify pagefaults.c to reliably cause it to encounter a similar number of major page faults, or explain why it is difficult for a user program to influence the number of major page faults they encounter during execution.
6
5.2 Files and Memory (6 pts)
Unix provides facilities that can make a file’s content appear as random access memory. Complete the program below by adding any missing statement(s) in main()!
#include
#define N 1000
struct pair {
uint32_t sum;
uint32_t fd;
};
static struct pair
writefile(int n) {
const char * fname = “.myfile”;
int myfd = open(fname, O_CREAT | O_TRUNC | O_RDWR, 0600);
unlink(fname);
uint32_t sum = 0;
for (uint32_t i = 0; i < n; i++) {
uint32_t rnd = rand() % n;
sum += rnd;
write(myfd, &rnd, sizeof (rnd));
}
return (struct pair){ .sum = sum, .fd = myfd };
}
int
main() {
uint32_t sum = 0;
srand(time(NULL));
struct pair sumfd = writefile(N);
/* Insert missing code here so that this program prints "Ok".
* You may not use the read, readv, preadv, or preadv2 system calls
*/
7
for (uint32_t i = 0; i < N; i++)
sum += addr[i];
if (sum != sumfd.sum)
abort();
printf("Ok\n");
}
5.3
The 3 C’s of Virtual Memory (6 pts)
Virtual memory can be viewed as a cache for disks or other forms of secondary storage. Data is cached in pages in RAM that may otherwise reside on disk or may be swapped out to disk.
From Computer Architecture, you are familiar with the 3 C’s of cache misses: compulsory (cold), conflict, and capacity misses. These are ordinarily defined for processor caches such as the L1 cache. Let us extend these definitions to virtual memory. For each type of miss, explain whether and how it can occur in the context of virtual memory, and why.
6 Networking (18 pts)
6.1 File Transfer (6 pts)
Consider the following hypothetical file transfer protocol proposal, which consists of multiple steps:
• A client opens a TCP connection to a server.
• Upon successful connection, the client sends GET
• The server retrieves the file from its file system and responds with the file’s content.
• The client saves the content to a local file as it receives it.
• After the file is sent, the server closes the connection by calling close() on the file descriptor of the TCP connection.
• If the client learns that the connection has been closed by the server, it will exit after having saved the content to a local file.
Answer the following 2 questions regarding the feasibility of this proposed protocol:
a) If the protocol were implemented as described, would it be possible for the client to learn when the server completes the file transfer?
b) Based on your knowledge of transport layer protocols, would this hypothetical protocol guar- antee the reliable and complete transfer of files from the server to the requesting client?
8
Your p4 server
Second server
Client
Figure 3: Could a client send the JWT obtained from your p4 to another server?
6.2 JWT (6 pts)
Consider your use of JWT in project 4, and consider the scenario shown in Figure 3.
How would you change your p4 implementation so that users can authenticate with your server, but access the “second server” after successful authentication? You should assume that this server is operated by an organization that the client trusts, but that is not affiliated with the operator of
your modified p4 server.
Describe what changes you would need to make. If your implementation already does part of
what would be required to accommodate this scenario, state it.
6.3 Too QUIC? (6 pts)
The QUIC Protocol is being hailed as a key component of HTTP/3. A Google search as of the time of this writing yields the following panel:
9
Sends username +password
Obtains JWT
???
Figure 4: Google Search Result Panel for QUIC
Which important detail did Google’s AI (which apparently compiled this panel) get wrong about QUIC?
7 Submission Requirements
Submit a tar file that contains the following files:
• myst.c to answer Question 1
• twoeight.c to answer Question 2
• malloc.txt with answers to both parts of Question 3
• A.java to answer Question 4.1
• reachability.txt to answer Question 4.2. This will contain source code in your chosen language, but for uniformity, please give it this name.
10
• pagefault.c to answer Question 5.1, Task 1 and 2. Please answer Task 2 using a comment (of if statement) in this file.
• randomsum.c to answer Question 5.2
• vmcache.txt to answer Question 5.3 (3 answers required)
• networking.txt with answers to Question 6. This means 4 separate answers for 6.1 (a), (b), 6.2, and 6.3.
11