操作系统代写 | CS 3214 Spring 2020 Final Exam

这个作业是完成操作系统相关的题目
CS 3214 Spring 2020 Final Exam
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 equivalent 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 multithreaded) 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 reachability 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 reachability 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

#include


#include


#include


#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


#include


#include


#include


#include


#include


#include


#include


#include


#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

followed by a CRLF to the

sender, where

is the name of the file the client wants to retrieve.

• 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 guarantee the reliable and complete transfer of files from the server to the requesting client?

8

Second

server

Your p4

server

Client

Sends

username

+password

Obtains JWT

???

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

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