CS 485-006, Spring 2016
Final Exam Review

The final exam for CS 485G will be held in the usual classroom (CB 212) on Friday, 4 March, 2016 on 10:30 AM. You may bring one letter-sized page of notes (8.5 x 11 inches or smaller).

• Exam topics
• Study questions

There will be a mix of multiple-choice, fill-in-the-blank, short-answer (one or two sentences), long-answer (a paragraph or two), and code-writing questions (C or C++ and assembly).

Questions will cover material from both the first and second half of the class, so see also the midterm exam review.

Topics

In addition to all the topics from the midterm exam, you should prepare for questions about:

• Chapter 7: Linking (Lecture 10)
  • Difference between object and executable files.
  • Sections in an ELF (object or executable) file:
    • text, rodata, data, bss
  • Symbol resolution.
    • Global, external, and local symbols.
    • The meaning of static on a "global" variable.
    • How duplicate symbols are handled.
    • Weak and strong symbols.
  • Relocation: What is it, and why is it necessary?
  • Static and dynamic libraries
    • Advantages and disadvantages.
    • How to make them (ar, gcc -shared)
  • Run-time dynamic linking and interpositioning
  • Function pointers: syntax and usage.
• Chapter 9: Virtual memory (Lecture 11)
  • Reasons for virtual memory.
  • Physical and virtual addresses.
  • Page tables, valid and invalid pages.
  • How the OS handles page faults.
  • Sharing pages among processes.
  • Memory protection.
• Chapter 10: System-level I/O (Lecture 12)
  • Unix system calls for low-level I/O.
    • File descriptors.
    • open(), close(), read(), write().
    • How system calls indicate errors: return value and errno.
    • Short counts.
  • Directory organization, structure of a directory, opendir() and readdir()
  • File system metadata: size, ownership, permission, timestamps.
  • Sharing open files between processes: file descriptor table and open file table.
  • Redirection: dup2()
  • stdio: Implemented using low-level I/O system calls.
    • Buffering: why and how.
    • FILE *
    • fopen, fclose, fgets, fputs.
• Chapter 9 (part I): Exceptional control flow: exceptions and processes (Lecture 13)
  • Types of CPU exceptions:
    • Asynchronous: interrupts (timer, hardware, etc).
    • Synchronous: traps (intentional: syscalls, breakpoints)
    • Synchronous: faults and aborts (unintentional: page faults, divide by zero, etc).
  • Exceptions transfer control from the executing process to the kernel.
  • Process: Instance of a running program.
    • Process abstractions: logical control flow, private memory.
    • Context switching: save registers into previous process, load registers from next process, transfer control to next process.
  • System calls for processes:
    • fork(), waitpid(), exit(), execve()/execvp()/etc.
    • How fork works: returns twice.
    • Parent and child process.
    • Reaping children with waitpid(); zombie processes.
    • Exit status: set by exit(), read by waitpid().
    • How a shell works (Program 4).
• Chapter 9 (part II): Signals (Lecture 14)
  • Common signals: SIGINT, SIGTERM, SIGSEGV, SIGCHLD.
  • Signal actions: ignore, terminate, or catch/handle.
  • Setting signal actions: signal()
  • Blocked and pending signals.
  • Limitations of signal handlers:
    • Should only call async-signal-safe functions: avoid malloc() and stdio.
    • Writing to global data structures can be a problem: handler might have interrupted code that modifies or reads the same structure.
• Chapter 11: Networking (Lecture 15 and Lecture 16):
  • Client/server model.
  • IP, UDP, and TCP: differences.
  • IP(v4) addresses: 128.163.146.21
  • DNS: mapping between host names and IP addresses.
  • Connections, sockets, and ports:
    • Connection: reliable communication channel between two processes (possibly on different computers).
      Uniquely identified by two socket addresses (one for each end).
    • Socket: one endpoint of a connection.
      • Represented in code by a file descriptor.
      • Socket address: IP address + port number.
    • Port: number that indicates which process and FD is handling the connection.
    • Ephemeral ports vs. well-known ports.
    • Common port numbers: 22 (ssh), 80 (http)
  • Socket programming:
    • Translating hostname and port to a socket address: getaddrinfo().
    • Creating a socket: socket()
    • Server side: bind(), listen(), and accept().
      Listening vs connected socket file descriptors.
    • Client side: connect().
    • csapp.c wrappers: open_listenfd, open_clientfd, rio_readlineb, rio_writen.
• Chapter 12: Concurrency (Lecture 17):
  • Difficulties of concurrent programming: Race conditions, deadlock, and livelock/starvation
  • Limitations of iterative network servers: only one request at a time.
  • Models of concurrent network programming:
    • Process based: fork a new process for each connection.
    • Event-driven: use select() to wait for something to happen on any file descriptor, then decide how to handle it based on which FD it was.
    • Process based: create one thread for each connection.
  • Threads vs processes:
    • Each process has its own flow of control, memory, etc.
    • Threads share memory (but each has its own stack).
    • Each thread has its own flow of control, copy of the registers, etc.
  • Advantages/disadvantages of process-based vs thread-based concurrency.
  • Multithreaded programming:
    • pthread_create(), pthread_join(), pthread_detach().
    • Passing arguments to a thread: void *arg
• Programming on Unix: Tools:
  • ltrace (Lab 3) and strace (Lab 4).
  • nslookup (Lab 4).
  • ifconfig or ip addr (Lab 4).
  • netstat (Lab 4).

Study questions

The following questions and problems are representative of those that might appear on the exam. The actual exam will be nowhere near this long, of course.

We will not be posting solutions to these problems. If you would like to verify your answers, send them to Dr. Moore by email.

See also the midterm practice questions.

1. A statically-linked executable can run on any Linux machine, regardless of what libraries are installed. Why might we, despite that advantage, prefer to use dynamic linking?
2. What is interpositioning? List at least two things you can do using interpositioning.
3. Suppose foo.c contains the global definition int secret = 4;, and bar.c contains the global definition int secret = 8;
   What will happen when foo.c and bar.c are linked together?
4. Suppose foo.c contains the global definition int secret = 4;, and bar.c contains the global definition char secret[16];
   What will happen when foo.c and bar.c are linked together? How much memory will be reserved for secret?
5. Which section of an executable or object file would each of the following global definitions be placed in?
   1. int main() { ... }
   2. int table[4] = { 1, 2, 4, 8 };
   3. int table[4];
6. What kind of things go into each of the following sections of an executable or object file:
   1. .text
   2. .data
   3. .rodata
   4. .bss
7. Given the declaration: int (*handler)(double);
   1. What is the name of the variable being declared?
   2. What kind of thing does the variable point to?
   3. What is the meaning of the int?
   4. What is the meaning of the double?
8. Suppose I run two copies of a program at the same time. In both copies, the global variable table is at address 0x4105f0. Why don't these two copies of the table overwrite one another?
9. List three different reasons that modern operating systems use virtual memory, and explain how virtual memory addresses those reasons.
10. When a process tries to access a page that is marked as invalid in the page table, is that always an error? If not, what must be done to make the page valid?
11. If the OS needs to allocate a new page of memory, but there are no free pages in physical memory, how does the OS page fault handler resolve that situation?
12. Why might two processes share the same page of physical memory?
13. What value is returned by open() if there was an error? What value is returned if there was not an error?
14. If a system call fails, what global variable holds a code indicating the reason for the failure?
15. If we determine that a system call failed, what library function should be used to obtain a readable error message?
    (There are two possible answers.)
16. Suppose file descriptor 5 refers to an open file that we want to supply as standard input to another program. What system call and parameters would we use to set up that redirection. Should we call the system call before calling fork, after fork in the parent process, or after fork in the child process?
17. What are the three standard file descriptors that are (usually) opened before a program begins executing? List the file descriptor numbers and the names for each of those descriptors.
18. What does the write system call return? What do positive, negative, and zero mean? Why might the return value be less than expected, even if it is positive?
19. Write a piece of code that uses the low-level Unix I/O system calls (not stdio or iostreams) that does the following:
    • Open a file named "data.txt" for reading.
    • Read up to 512 bytes from the file into an array named buf.
    • Close the file.
    If there was an error at any step, print an error message and exit the program.
    Include the definitions of any variables used by your code.
20. Write a piece of code that uses the low-level Unix I/O system calls (not stdio or iostreams) that does the following:
    • Open an existing file named "data.txt" for writing, truncating the file to zero bytes.
    • Write the line "Magic\n" to the file.
    • Close the file.
    If there was an error at any step, print an error message and exit the program.
    Include the definitions of any variables used by your code.
21. Suppose we need to scan through a file to find the first occurrence of the character 'A'. We could do this with a loop that reads one character at a time. Why would such a loop be much faster if it used a stdio call such as fgetc, rather than the low-level read() system call?
22. List at least two reasons a correctly-functioning program without errors might still cause a CPU exception.
23. What is the difference between a synchronous exception and an asynchronous exception?
24. What is the difference between a trap exception and a fault exception?
25. What is the difference between a program and a process?
26. What is a zombie process? What causes processes to become zombies? How do you free the resources associated with a zombie process?
27. Assuming there was not an error, fork() returns two different values. What value is returned to the child process, and what value is returned to the parent process?
28. What is the output of the following code? Assume that both calls to fork() are successful.

              fork();
              fork();
              fprintf(stdout, "!");
              exit(0);
          

29. What is the difference between execv and execvp?
30. Write an execvp call to execute the command "ls -l /". Define any necessary variables: you will need at least an array of C string pointers.
31. In the following program, the child process exits with a random exit status.

              pid_t pid = fork();
              if (/* A: is this the child process? */) {
                  /* child process */
                  exit(rand() % 10);
              } else {
                  /* parent process */
                  /* B: wait for child to terminate */
                  /* C: print the exit status */
              }
          

    1. What expression goes in slot A to check whether this is the child process?
    2. Write the waitpid call to wait for the child process to terminate and save its exit status. Declare any necessary variables. You may ignore error handling.
    3. Write the code to determine and print the exit status of the child process, using the macros WIFEXITED and WEXITSTATUS.
32. One of these two programs produces zombie processes. Which is it, and why does the other not produce zombies?

              while (fork())
                  ; /* do nothing */
              exit(0);

              while (!fork())
                  ; /* do nothing */
              exit(0);

33. What signal is sent when the user presses ctrl-c? What is the default behavior when a process receives that signal?
34. What signal is sent to a process when one of its children terminates? What is the default behavior when a process receives that signal?
35. How would you make a program not terminate when the user presses ctrl-c?
36. What command-line program can be used to send a signal to a process?
37. Why is it unsafe to call malloc inside a signal handler?
38. Which of the following are valid IPv4 addresses?
    1. 128.163.146.21
    2. 10.300.5.15
    3. 4.72.8
    4. 127.0.0.1
    5. 204.12.9.40.42
39. Approximately how many possible IPv4 addresses are there?
40. What is special about the IP address 127.0.0.1?
41. List at least two differences between UDP and TCP.
42. What does it mean when we say TCP is reliable?
43. What library function can be used to translate a host name such as "www.google.com" and a port name or number such as "http" or "80" into a struct sockaddr?
44. What command-line program can be used to translate a host name into an IP address?
45. In a network server, in what order should we call the following system calls? bind, accept, socket, listen?
46. In a network client, which system call specifies the address and port to connect to?
47. In a network server, which system call specifies the address and port to listen on?
48. The accept system call accepts a socket file descriptor as one parameter, and returns a different socket file descriptor. What is the difference between the two sockets?
49. What system call is used to disconnect a network connection?
50. In a client-server protocol, which endpoint of the connection usually uses a well-known port? Which endpoint usually uses an ephemeral port?
51. What is the difference between a thread and a process? How are they similar?
52. List at least two things that are shared among all the threads in a single process. List at least two things that are not shared (i.e., each thread has its own copy).
53. What is a race condition? Give an example, either in computing or in the real world.
54. List at least two advantages and two disadvantages of thread-based network servers compared to process-based network servers.
55. Suppose we establish a network connection, then have both the client and server try to read from the connection as their first actions. Nothing will happen? What is the name for situations like this where two or more processes or threads are unable to make progress because each is waiting for the other?
56. The signature of the pthread_create function is:

                 int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                                    void *(*start_routine) (void *), void *arg);
          

    1. Why is the first argument a pointer?
    2. What argument will be passed to the start_routine when it is called?
57. What does the p in pthreads stand for?
58. What function is the equivalent of waitpid() for threads?
59. If we do not intend to use the function from the previous question, what library call should we use to indicate this?
60. What is the difference between the ltrace and strace programs?