\chapter{Review}

A non-comprehensive list of topics is below.

\section{C}

\subsection{Memory and Strings}

\begin{enumerate}

\item In the example below, which variables are guaranteed to print the value of zero?

\begin{lstlisting}[language=C]
int a;
static int b;

void func() {
  static int c;
  int d;
  printf("%d %d %d %d\n",a,b,c,d);
}
\end{lstlisting}

\item In the example below, which variables are guaranteed to print the value of zero?

\begin{lstlisting}[language=C]
void func() {
  int* ptr1 = malloc(sizeof(int));
  int* ptr2 = realloc(NULL, sizeof(int));
  int* ptr3 = calloc(1, sizeof(int));
  int* ptr4 = calloc(sizeof(int), 1);

  printf("%d %d %d %d\n",*ptr1,*ptr2,*ptr3,*ptr4);
}
\end{lstlisting}

\item Explain the error in the following attempt to copy a string.

\begin{lstlisting}[language=C]
char* copy(char*src) {
  char*result = malloc( strlen(src) );
  strcpy(result, src);
  return result;
}
\end{lstlisting}

\item Why does the following attempt to copy a string sometimes work and sometimes fail?

\begin{lstlisting}[language=C]
char* copy(char*src) {
  char*result = malloc( strlen(src) +1 );
  strcat(result, src);
  return result;
}
\end{lstlisting}

\item Explain the two errors in the following code that attempts to copy a string.

\begin{lstlisting}[language=C]
char* copy(char*src) {
  char result[sizeof(src)];
  strcpy(result, src);
  return result;
}
\end{lstlisting}

\item Which of the following is legal?

\begin{lstlisting}[language=C]
char a[] = "Hello"; strcpy(a, "World");
char b[] = "Hello"; strcpy(b, "World12345", b);
char* c = "Hello"; strcpy(c, "World");
\end{lstlisting}

\item Complete the function pointer typedef to declare a pointer to a function that takes a void* argument and returns a void*. Name your type `pthread\_callback'

\begin{lstlisting}[language=C]
typedef ______________________;
\end{lstlisting}

\item In addition to the function arguments what else is stored on a thread's stack?

\item Implement a version of \keyword{char*\ strcat(char*dest,\ const\ char*src)} using only \keyword{strcpy} \keyword{strlen} and pointer arithmetic

\begin{lstlisting}[language=C]
char* mystrcat(char*dest, const char*src) {

  ? Use strcpy strlen here

  return dest;
}
\end{lstlisting}

\item Implement version of size\_t strlen(const char*) using a loop and no function calls.

\begin{lstlisting}[language=C]
size_t mystrlen(const char*s) {

}
\end{lstlisting}

\item Identify the three bugs in the following implementation of \keyword{strcpy}.

\begin{lstlisting}[language=C]
char* strcpy(const char* dest, const char* src) {
  while(*src) { *dest++ = *src++; }
  return dest;
}
\end{lstlisting}

\end{enumerate}

\subsection{Printing}

\begin{enumerate}

\item Spot the two errors!

\begin{lstlisting}[language=C]
fprintf("You scored 100%");
\end{lstlisting}

\item Complete the following code to print to a file. Print the name, a comma and the score to the file `result.txt'

\begin{lstlisting}[language=C]
char* name = .....;
int score = ......
FILE *f = fopen("result.txt",_____);
if(f) {
  _____
}
fclose(f);
\end{lstlisting}

\item How would you print the values of the variables \keyword{a}, \keyword{mesg}, \keyword{val} and \keyword{ptr} to a string? Print a as an integer, mesg as C string, val as a double val and ptr as a hexadecimal pointer. You may assume the mesg points to a short C string(\textless{}50 characters). Bonus: How would you make this code more robust or able to cope with?

\begin{lstlisting}[language=C]
char* toString(int a, char*mesg, double val, void* ptr) {
  char* result = malloc( strlen(mesg) + 50);
  _____
  return result;
}
\end{lstlisting}

\end{enumerate}

\subsection{Input parsing}

\begin{enumerate}
\item Why should you check the return value of sscanf and scanf? \#\# Q 5.2 Why is `gets' dangerous?

\item Write a complete program that uses \keyword{getline}. Ensure your program has no memory leaks.

\item When would you use calloc instead of malloc? When would realloc be useful?

\item What mistake did the programmer make in the following code? Is it possible to fix it

i) using heap memory?
ii) using global (static) memory?

\begin{lstlisting}[language=C]
static int id;

char* next_ticket() {
  id ++;
  char result[20];
  sprintf(result,"%d",id);
  return result;
}
\end{lstlisting}

\end{enumerate}

\section{Processes}

\begin{enumerate}
\item What is a process?
\item What attributes are carried over from a process on fork? How about on a successful exec call?
\item What is a fork bomb? How can we avoid one?
\item What is the wait system call used for?
\item What is a zombie? How do we avoid them?
\item What is an orphan? What happens to them?
\item How do we check the status of a process that has exited?
\item What is a common pattern of processes?
\end{enumerate}

\section{Memory}

\begin{enumerate}
\item What are the calls in C to allocate memory?
\item What must malloc memory be aligned to? Why is it important?
\item What is Knuth's Allocation Scheme?
\item How would you handle a request in a buddy allocation scheme?
\item What is a free list?
\item What are some different ways of inserting into a free list?
\item What are the benefits and drawbacks to first fit, worst fit, best fit?
\item When would a trivial malloc implementation
\begin{lstlisting}[language=C]
void *malloc(int size) {
  return (void *)sbrk(size);
}
\end{lstlisting}
Be acceptable?
\end{enumerate}

\section{Threading and Synchronization}

\begin{enumerate}
\item What is a thread? What do threads share?
\item How does one create a thread?
\item Where are the stacks for a thread located in memory?
\item What is a mutex? What problem does it solve?
\item What is a condition variable? What problem does it solve?
\item Write a thread safe linked list that supports insert front, back, pop front, and pop back. Make sure it doesn't busy wait!
\item What is Peterson's Solution to the critical section problem? How about Dekker's?
\item Is the following code thread-safe? Redesign the following code to be thread-safe. Hint: A mutex is unnecessary if the message memory is unique to each call.

\begin{lstlisting}[language=C]
static char message[20];
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void *format(int v) {
  pthread_mutex_lock(&mutex);
  sprintf(message, ":%d:" ,v);
  pthread_mutex_unlock(&mutex);
  return message;
}
\end{lstlisting}

\item Which one of the following may leave a process in running?

\begin{enumerate}
\item Returning from the pthread's starting function in the last running thread.
\item The original thread returning from main.
\item Any thread causing a segmentation fault.
\item Any thread calling \keyword{exit}.
\item Calling \keyword{pthread\_exit} in the main thread with other threads still running.
\end{enumerate}

\item Write a mathematical expression for the number of ``W'' characters that will be printed by the following program. Assume a,b,c,d are small positive integers. Your answer may use a `min' function that returns its lowest valued argument.

\begin{lstlisting}[language=C]
unsigned int a=...,b=...,c=...,d=...;

void* func(void* ptr) {
  char m = * (char*)ptr;
  if(m == 'P') sem_post(s);
  if(m == 'W') sem_wait(s);
  putchar(m);
  return NULL;
}

int main(int argv, char** argc) {
  sem_init(s,0, a);
  while(b--) pthread_create(&tid, NULL, func, "W");
  while(c--) pthread_create(&tid, NULL, func, "P");
  while(d--) pthread_create(&tid, NULL, func, "W");
  pthread_exit(NULL);
  /*Process will finish when all threads have exited */
}
\end{lstlisting}

\item Complete the following code. The following code is supposed to print alternating \keyword{A} and \keyword{B}. It represents two threads that take turns to execute. Add condition variable calls to \keyword{func} so that the waiting thread need not to continually check the \keyword{turn} variable. Q: Is pthread\_cond\_broadcast necessary or is pthread\_cond\_signal sufficient?

\begin{lstlisting}[language=C]
pthread_cond_t cv = PTHREAD_COND_INITIALIZER;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

void* turn;

void* func(void* mesg) {
  while(1) {
    // Add mutex lock and condition variable calls ...

    while(turn == mesg) {
      /* poll again ... Change me - This busy loop burns CPU time! */
    }

    /* Do stuff on this thread */
    puts( (char*) mesg);
    turn = mesg;

  }
  return 0;
}

int main(int argc, char** argv){
  pthread_t tid1;
  pthread_create(&tid1, NULL, func, "A");
  func("B"); // no need to create another thread - use the main thread
  return 0;
}
\end{lstlisting}

\item Identify the critical sections in the given code. Add mutex locking to make the code thread safe. Add condition variable calls so that \keyword{total} never becomes negative or above 1000. Instead the call should block until it is safe to proceed. Explain why \keyword{pthread\_cond\_broadcast} is necessary.

\begin{lstlisting}[language=C]
int total;
void add(int value) {
  if(value < 1) return;
  total += value;
}
void sub(int value) {
  if(value < 1) return;
  total -= value;
}
\end{lstlisting}

\item An thread unsafe data structure has \keyword{size()} \keyword{enq} and \keyword{deq} methods. Use condition variable and mutex lock to complete the thread-safe, blocking versions.

\begin{lstlisting}[language=C]
void enqueue(void* data) {
  // should block if the size() would become greater than 256
  enq(data);
}
void* dequeue() {
  // should block if size() is 0
  return deq();
}
\end{lstlisting}

\item Your startup offers path planning using the latest traffic information. Your overpaid intern has created a thread unsafe data structure with two functions: \keyword{shortest} (which uses but does not modify the graph) and \keyword{set\_edge} (which modifies the graph).

\begin{lstlisting}[language=C]
graph_t* create_graph(char* filename); // called once

// returns a new heap object that is the shortest path from vertex i to j
path_t* shortest(graph_t* graph, int i, int j);

// updates edge from vertex i to j
void set_edge(graph_t* graph, int i, int j, double time);

\end{lstlisting}

For performance, multiple threads must be able to call \keyword{shortest} at the same time but the graph can only be modified by one thread when no threads other are executing inside \keyword{shortest} or \keyword{set\_edge}.

\item Use mutex lock and condition variables to implement a reader-writer solution. An incomplete attempt is shown below. Though this attempt is thread safe (thus sufficient for demo day!), it does not allow multiple threads to calculate \keyword{shortest} path at the same time and will not have sufficient throughput.

\begin{lstlisting}[language=C]
path_t* shortest_safe(graph_t* graph, int i, int j) {
  pthread_mutex_lock(&m);
  path_t* path = shortest(graph, i, j);
  pthread_mutex_unlock(&m);
  return path;
}
void set_edge_safe(graph_t* graph, int i, int j, double dist) {
  pthread_mutex_lock(&m);
  set_edge(graph, i, j, dist);
  pthread_mutex_unlock(&m);
}
\end{lstlisting}
\item How many of the following statements are true for the reader-writer problem?

\begin{itemize}
\tightlist
\item
  There can be multiple active readers
\item
  There can be multiple active writers
\item
  When there is an active writer the number of active readers must be zero
\item
  If there is an active reader the number of active writers must be zero
\item
  A writer must wait until the current active readers have finished
\end{itemize}

\end{enumerate}

\section{Deadlock}

\begin{enumerate}

\item What do each of the Coffman conditions and what do they mean? Can you provide a definition of each one and an example of breaking them using mutexes?

\item Give a real life example of breaking each Coffman condition in turn. A situation to consider: Painters, paint and paint brushes.

  \begin{enumerate}
  \item Hold and wait
  \item Circular wait
  \item No preemption 
  \item Mutual exclusion
  \end{enumerate}

\item Identify when Dining Philosophers code causes a deadlock (or not). For example, if you saw the following code snippet which Coffman condition is not satisfied?

\begin{lstlisting}[language=C]
// Get both locks or none.
pthread_mutex_lock( a );
if( pthread_mutex_trylock( b ) ) { /*failed*/
  pthread_mutex_unlock( a );
  ...
}
\end{lstlisting}

\item How many processes are blocked?

\begin{itemize}
\tightlist
\item
  P1 acquires R1
\item
  P2 acquires R2
\item
  P1 acquires R3
\item
  P2 waits for R3
\item
  P3 acquires R5
\item
  P1 acquires R4
\item
  P3 waits for R1
\item
  P4 waits for R5
\item
  P5 waits for R1
\end{itemize}

\item What are the pros and cons for the following solutions to dining philosophers
  \begin{enumerate}
  \item Arbitrator
  \item Dijkstra
  \item Stalling's
  \item Trylock
  \end{enumerate}
\end{enumerate}

\section{IPC}

\begin{enumerate}

\item What are the following and what is their purpose?
  \begin{enumerate}
  \item Translation Lookaside Buffer
  \item Physical Address
  \item Memory Management Unit
  \item The dirty bit
  \end{enumerate}

\item How do you determine how many bits are used in the page offset?

\item 20 ms after a context switch the TLB contains all logical addresses used by your numerical code which performs main memory access 100\% of the time. What is the overhead (slowdown) of a two-level page table compared to a single-level page table?

\item Explain why the TLB must be flushed when a context switch occurs (i.e.~the CPU is assigned to work on a different process).

\item Fill in the blanks to make the following program print 123456789. If \keyword{cat} is given no arguments it simply prints its input until EOF. Bonus: Explain why the \keyword{close} call below is necessary.

\begin{lstlisting}[language=C]
int main() {
  int i = 0;
  while(++i < 10) {
    pid_t pid = fork();
    if(pid == 0) { /* child */
      char buffer[16];
      sprintf(buffer, ______,i);
      int fds[ ______];
      pipe(fds);
      write(fds[1], ______,______ ); // Write the buffer into the pipe
      close(______);
      dup2(fds[0], ______);
      execlp("cat", "cat",  ______);
      perror("exec"); exit(1);
    }
    waitpid(pid, NULL, 0);
  }
  return 0;
}
\end{lstlisting}

\item Use POSIX calls \keyword{fork} \keyword{pipe} \keyword{dup2} and \keyword{close} to implement an autograding program.
  Capture the standard output of a child process into a pipe.
  The child process should \keyword{exec} the program \keyword{./test} with no additional arguments (other than the process name).
  In the parent process read from the pipe: Exit the parent process as soon as the captured output contains the !
  character.
  Before exiting the parent process send SIGKILL to the child process.
  Exit 0 if the output contained a !.
  Otherwise if the child process exits causing the pipe write end to be closed, then exit with a value of 1.
  Be sure to close the unused ends of the pipe in the parent and child process

\item This advanced challenge uses pipes to get an ``AI player'' to play itself until the game is complete. The program \keyword{tic tac toe} accepts a line of input - the sequence of turns made so far, prints the same sequence followed by another turn, and then exits. A turn is specified using two characters. For example ``A1'' and ``C3'' are two opposite corner positions. The string \keyword{B2A1A3} is a game of 3 turns/plys. A valid response is \keyword{B2A1A3C1} (the C1 response blocks the diagonal B2 A3 threat). The output line may also include a suffix \keyword{-I\ win} \keyword{-You\ win} \keyword{-invalid} or \keyword{-draw} Use pipes to control the input and output of each child process created. When the output contains a \keyword{-}, print the final output line (the entire game sequence and the result) and exit.

\item Write a function that uses fseek and ftell to replace the middle character of a file with an `X'

\begin{lstlisting}[language=C]
void xout(char* filename) {
  FILE *f = fopen(filename, ____ );

  // Your code here ...
}
\end{lstlisting}

\item What is an MMU? What are the drawbacks to using it versus a direct memory system?
\item What is a pipe?
\item What are the pros and cons between named and unnamed pipes?

\end{enumerate}

\section{Filesystems}

\begin{enumerate}
\item What is the file API?
\item Where are the names of the files stored?
\item What is contained in an inode?
\item What are the two special file names in every directory
\item How do you resolve the following path \keyword{a/../b/./c/../../c}
\item What are the rwx groups?
\item What is an UID? GID? What is the difference between UID and Effective UID?
\item What is umask?
\item What is the sticky bit?
\item What is a virtual file system?
\item What is RAID?
\item In an \keyword{ext2} filesystem how many inodes are read from disk to access the first byte of the file \keyword{/dir1/subdirA/notes.txt} ? Assume the directory names and inode numbers in the root directory (but not the inodes themselves) are already in memory.

\item In an \keyword{ext2} filesystem what is the minimum number of disk blocks that must be read from disk to access the first byte of the file \keyword{/dir1/subdirA/notes.txt} ? Assume the directory names and inode numbers in the root directory and all inodes are already in memory.

\item In an \keyword{ext2} filesystem with 32 bit addresses and 4KiB disk blocks, an inode can store 10 direct disk block numbers. What is the minimum file size required to require a single indirection table? ii) a double direction table?

\item Fix the shell command \keyword{chmod} below to set the permission of a file \keyword{secret.txt} so that the owner can read,write,and execute permissions the group can read and everyone else has no access.

\begin{lstlisting}[language=bash]
$ chmod 000 secret.txt
\end{lstlisting}

\end{enumerate}

\section{Networking}

\begin{enumerate}

\item What is a socket?
\item What are the different layers of the internet?
\item What is IP? What is an IP address?
\item What is TCP? What is UDP? What are the differences?
\item Create a TCP client that send ``Hello'' to a server.
\item Create a simple TCP echo server. This is a server that reads bytes from a client until it closes and echoes the bytes back to the client.
\item Create a UDP client that would send a flood of packets to a hostname at argv[1].
\item What is HTTP?
\item What is DNS?
\item Why do we use non-blocking IO for networking?
\item What is an RPC?
\item What is special about listening on port 1000 vs port 2000?

\begin{itemize}
\tightlist
\item
  Port 2000 is twice as slow as port 1000
\item
  Port 2000 is twice as fast as port 1000
\item
  Port 1000 requires root privileges
\item
  Nothing
\end{itemize}

\item Describe one significant difference between IPv4 and IPv6?

\item When and why would you use ntohs?

\item If a host address is 32 bits which IP scheme am I most likely using? 128 bits?

\item Which common network protocol is packet based and may not successfully deliver the data?

\item Which common protocol is stream-based and will resend data if packets are lost?

\item What is the SYN ACK ACK-SYN handshake?

\item Which one of the following is NOT a feature of TCP?
  \begin{enumerate}
  \item Packet reordering
  \item Flow control
  \item Packet retranmission
  \item Simple error detection
  \item Encryption
  \end{enumerate}

\item What protocol uses sequence numbers? What is their initial value? And why?

\item What are the minimum network calls are required to build a TCP server? What is their correct order?

\item What are the minimum network calls are required to build a TCP client? What is their correct order?

\item When would you call bind on a TCP client?

\item What is the purpose of socket bind listen accept ?

\item Which of the above calls can block, waiting for a new client to connect?

\item What is DNS? What does it do for you? Which of the CS241 network calls will use it for you?

\item For getaddrinfo, how do you specify a server socket?

\item Why may getaddrinfo generate network packets?

\item Which network call specifies the size of the allowed backlog?

\item Which network call returns a new file descriptor?

\item When are passive sockets used?

\item When is epoll a better choice than select? When is select a better choice than epoll?

\item Will \keyword{write(fd,\ data,\ 5000)} always send 5000 bytes of data? When can it fail?

\item How does Network Address Translation (NAT) work?

\item Assuming a network has a 20ms One Way Transit Time between Client and Server, how much time would it take to establish a TCP Connection?
  \begin{enumerate}
  \item 20ms
  \item 40ms
  \item 100ms
  \item 60ms
  \end{enumerate}

\item What are some of the differences between HTTP 1.0 and HTTP 1.1? How many ms will it take to transmit 3 files from server to client if the network has a 20ms transmit time? How does the time taken differ between HTTP 1.0 and HTTP 1.1?

\item Writing to a network socket may not send all of the bytes and may be interrupted due to a signal. Check the return value of \keyword{write} to implement \keyword{write\_all} that will repeatedly call \keyword{write} with any remaining data. If \keyword{write} returns -1 then immediately return -1 unless the \keyword{errno} is \keyword{EINTR} - in which case repeat the last \keyword{write} attempt. You will need to use pointer arithmetic.

\begin{lstlisting}[language=C]
// Returns -1 if write fails (unless EINTR in which case it recalls write
// Repeated calls write until all of the buffer is written.
ssize_t write_all(int fd, const char *buf, size_t nbyte) {
  ssize_t nb = write(fd, buf, nbyte);
  return nb;
}
\end{lstlisting}

\item Implement a multithreaded TCP server that listens on port 2000. Each thread should read 128 bytes from the client file descriptor and echo it back to the client, before closing the connection and ending the thread.

\item Implement a UDP server that listens on port 2000. Reserve a buffer of 200 bytes. Listen for an arriving packet. Valid packets are 200 bytes or less and start with four bytes 0x65 0x66 0x67 0x68. Ignore invalid packets. For valid packets add the value of the fifth byte as an unsigned value to a running total and print the total so far. If the running total is greater than 255 then exit.

\end{enumerate}

\section{Security}

\begin{enumerate}
\item What are the three measures for data security?
\item What is stack smashing?
\item What is buffer overflows?
\item How does an operating system provide security? What are some examples from Networking and Filesystems?
\item What security features does TCP provide?
\item Is DNS secure?
\end{enumerate}

\section{Signals}

\begin{enumerate}
\item Give the names of two signals that are normally generated by the kernel
\item Give the name of a signal that can not be caught by a signal
\item Why is it unsafe to call any function (something that it is not signal handler safe) in a signal handler?
\item Write brief code that uses SIGACTION and a SIGNALSET to create a SIGALRM handler.
\item What is the difference between a disposition, mask, and pending signal set?
\item What attributes are passed over to process children? How about exececuted processes?
\end{enumerate}
