Angrave's 2019 Acme CS 241 Exam Prep
A.K.A. Preparing for the Final Exam & Beyond CS 241...
Some of the questions require research (wikibook; websearch; wikipedia). It is accepted to work together and discuss answers, but please make an honest attempt first! Be ready to discuss and clear confusions & misconceptions in your last discussion section. The final will also include pthreads, fork-exec-wait questions and virtual memory address translation. Be awesome. Angrave.

1. C
What are the differences between a library call and a system call? Include an example of each.

system calls are functions provided by the kernel (e.g. open() is a system call)
library calls are functions within program libraries (e.g. fopen() is a library call)
What is the * operator in C? What is the & operator? Give an example of each.

the '' operator is used to declare/dereference a ptr (e.g. char c = NULL)
the '&' operator asks for an address (e.g. &c)
When is strlen(s) != 1+strlen(s+1) ?

when s == NULL
How are C strings represented in memory? What is the wrong with malloc(strlen(s)) when copying strings?

strings are represented as null-terminated character arrays
malloc(strlen(s)) doesn't copy the terminating null byte
Implement a truncation function void trunc(char*s,size_t max) to ensure strings are not too long with the following edge cases.

if (length < max)
    strcmp(trunc(s, max), s) == 0
else if (s is NULL)
    trunc(s, max) == NULL
else
    strlen(trunc(s, max)) <= max
    // i.e. char s[]="abcdefgh; trunc(s,3); s == "abc".
void trunc(char* s, size_t max) { if (s == NULL) { return; } if (strlen(s) <= max) { return; } if (strlen(s) > max) { s[max] = 0; return; } return NULL; }

Complete the following function to create a deep-copy on the heap of the argv array. Set the result pointer to point to your array. The only library calls you may use are malloc and memcpy. You may not use strdup.

void duplicate(char **argv, char ***result);

//get number of argv elements int numElems = 0; char** ptr = argv;

while (ptr != NULL) { numElems++; ptr++; }

char** copy = malloc(numElems + 1); copy[numElems] = 0;

//copy over elements ptr = argv; char* newelem = copy; while (ptr != NULL) { char* elem = *ptr; int length = strlen(elem) + 1; *newelem = malloc(length); memcpy(*newelem, elem, length);

ptr++;
newelem++;
}

result = ©

Write a program that reads a series of lines from stdin and prints them to stdout using fgets or getline. Your program should stop if a read error or end of file occurs. The last text line may not have a newline char.

char * line = NULL; size_t len = 0; ssize_t read;

while ((read = getline(&line, &len, stdin)) != -1) { printf("Retrieved line of length %zu:\n", read); printf("%s", line); }

free(line);

2. Memory
Explain how a virtual address is converted into a physical address using a multi-level page table. You may use a concrete example e.g. a 64bit machine with 4KB pages.
for a 64bit machine with 4KB pages....
Explain Knuth's and the Buddy allocation scheme. Discuss internal & external Fragmentation.

buddy allocation scheme: memory allocation algorithm that divides memory into halves to satisfy a memory request ASAP
little external fragmentation
can be lots of internal fragmentation, b/c memory requested can be slightly larger than a small block but much smaller than a large block
What is the difference between the MMU and TLB? What is the purpose of each?

MMU translates virtual memory addresses into physical ones
TLB is an associative cache of page table entries
Assuming 4KB page tables what is the page number and offset for virtual address 0x12345678 ?

What is a page fault? When is it an error? When is it not an error?

a page fault is when a processes attempts to access an address in frame that's missing in memory
3 types of page faults:
minor: address is valid, but no mapping exists yet for the page
major: mapping to the page is exclusively on disk; OS will swap page into memory and swap another page out
invalid: read/write to memory address without permission; SIGSEGV
What is Spatial and Temporal Locality? Swapping? Swap file? Demand Paging?
3. Processes and Threads
What resources are shared between threads in the same process?

open file descriptors, code section, data section

Explain the operating system actions required to perform a process context switch

since the virtual address space is changing, we must also clear the TLB cache.
(1) suspending the progression of one process and storing the CPU's state (i.e., the context) for that process somewhere in memory, (2) retrieving the context of the next process from memory and restoring it in the CPU's registers and (3) returning to the location indicated by the program counter (i.e., returning to the line of code at which the process was interrupted) in order to resume the process.

Explain the actions required to perform a thread context switch to a thread in the same process
same as above, except for the fact that the TLB does not have to be cleared since the virtual address space remains the same
How can a process be orphaned? What does the process do about it?

an orphan process is a process whose parent process has finished/been terminated
any orphaned processes are adopted as children of process 1
How do you create a process zombie?

A child that terminates, but has not been waited for becomes a "zombie".
to create a zombiem fork then exit, don't wait for the child
Under what conditions will a multi-threaded process exit? (List at least 4)

pthread_exit a thread
pthread_cancel the last thread in the process
SIGKILL
SIGINT
4. Scheduling
Define arrival time, pre-emption, turnaround time, waiting time and response time in the context of scheduling algorithms. What is starvation? Which scheduling policies have the possibility of resulting in starvation?
start time: the wall clock start time of the process (CPU starts working on it)

end time: the wall clock end time of the process( CPU finishes working on it)

run time: teh total amount of CPU time required

arrival time: the time the process enters the scheduler (CPU might start working on it)

turnaround time: the total time from when the process arrives to when it ends (end_time - arrival_time)

response time: the total time that it takes from when the process arrives to when the CPU actually starts working on it (start_time - arrival_time)

waiting time: the TOTAL wait time or the total time that a process in on the ready queue (end_time - arrival_time - run_time)

pre-emption: With preemption, the existing processes may be removed immediately if a more preferred process is added to the ready queue.

starvation: a process ready to run for CPU can wait indefinitely because of low priority.

Scheduling policies that may result in starvation:

shortest job first
Which scheduling algorithm results the smallest average wait time?

shortest job first (SJF)
What scheduling algorithm has the longest average response time? shortest total wait time?

Describe Round-Robin scheduling and its performance advantages and disadvantages.

round robin: each process is allowed to run for a limited amount of time
Advantages:

Every Thread / Process gets a chance to run.
CPU is shared between all processes.
Threads with the same priority are handled perfectly with Round Robin.
Disadvantages:

Low Priority tasks may wait for more time if the many tasks are given high priority.
High Priority tasks may not execute the full instruction given stipulated amount of time.
Describe the First Come First Serve (FCFS) scheduling algorithm. Explain how it leads to the convoy effect.

The convoy effect is when a process takes up a lot of the CPU time, leaving all other processes with potentially smaller resource needs following like a Convoy Behind them. FCFS leads to the convoy effect when a large CPU process preceeds processes with smaller resource needs, resulting in starvation.

Describe the Pre-emptive and Non-preemptive SJF scheduling algorithms.
non-preemptive SJF: the shortest job out of all currently available jobs runs first, and executes on the CPU until completion
preemptive SJF: the current shortest job will run first, but if a job with shorter TOTAL execution time arrives then the current process, we stop executing our current process and execute the shorter one.
How does the length of the time quantum affect Round-Robin scheduling? What is the problem if the quantum is too small? In the limit of large time slices Round Robin is identical to FCFS_____?
if the quantum is too small, there is lots of context switching, which is expensive
if the quantum is too large, the algorith is less effective ----> FCFS
What reasons might cause a scheduler switch a process from the running to the ready state?
Preemption brings the process back to the ready state
5. Synchronization and Deadlock
Define circular wait, mutual exclusion, hold and wait, and no-preemption. How are these related to deadlock?

circular wait: each process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource.
mutual exclusion: A resource can be held by at most one process.
hold and wait: Processes that already hold resources can wait for another resource.
no-preemption: A resource, once granted, cannot be taken away.
What problem does the Banker's Algorithm solve?

deadlock!! specifically it checks if the a resource allocation is safe before proceeding
What is the difference between Deadlock Prevention, Deadlock Detection and Deadlock Avoidance?

Deadlock detection allows the system to enter a deadlocked state. After entering, the system uses the information to break deadlock
Deadlock prevention algorithms ensure that at least one of the necessary conditions (Mutual exclusion, hold and wait, no preemption and circular wait) does not hold true.
Deadlock avoidance: e.g. Banker's algorithm, checks whether deadlock will occur for a change in state before proceeding
Sketch how to use condition-variable based barrier to ensure your main game loop does not start until the audio and graphic threads have initialized the hardware and are ready.

Implement a producer-consumer fixed sized array using condition variables and mutex lock.

Create an incorrect solution to the CSP for 2 processes that breaks: i) Mutual exclusion. ii) Bounded wait.

Create a reader-writer implementation that suffers from a subtle problem. Explain your subtle bug.

6. IPC and signals
Write brief code to redirect future standard output to a file.

Write a brief code example that uses dup2 and fork to redirect a child process output to a pipe

Give an example of kernel generated signal. List 2 calls that can a process can use to generate a SIGUSR1.

e.g. SIGINT, SIGQUIT
to generate SIGUSR1: kill() or raise()
What signals can be caught or ignored?

signals such as SIGINT and SIGTERM can be caught/ignored
What signals cannot be caught? What is signal disposition?

SIGKILL cannot be caught
The signal disposition is a per-process attribute: in a multithreaded application, the disposition of a particular signal is the same for all threads. A child created via fork(2) inherits a copy of its parent's signal dispositions.
Write code that uses sigaction and a signal set to create a SIGALRM handler.

Why is it unsafe to call printf, and malloc inside a signal handler?

they use a lock, but signal handlers are called asynchronously. therefore deadlock may occur
7. Networking
Explain the purpose of socket, bind, listen, and accept functions

want to set up a TCP server

socket: creates an endpoint for communication and returns a file descriptor that refers to that endpoint

bind: assigns the address specified by addr to the socket referred to by the file descriptor sockfd

listen: marks the socket referred to by sockfd as a passive socket

connect: connects the socket referred to by the file descriptor sockfd to the address specified by addr

Write brief (single-threaded) code using getaddrinfo to create a UDP IPv4 server. Your server should print the contents of the packet or stream to standard out until an exclamation point "!" is read.

Write brief (single-threaded) code using getaddrinfo to create a TCP IPv4 server. Your server should print the contents of the packet or stream to standard out until an exclamation point "!" is read.

Explain the main differences between using select and epoll. What are edge- and level-triggered epoll modes?

Describe the services provided by TCP but not UDP.

resend dropped packets
orders packets correctly
How does TCP connection establishment work? And how does it affect latency in HTTP1.0 vs HTTP1.1?

Wrap a version of read in a loop to read up to 16KB into a buffer from a pipe or socket. Handle restarts (EINTR), and socket-closed events (return 0).

How is Domain Name System (DNS) related to IP and UDP? When does host resolution not cause traffic?

What is NAT and where and why is it used?

8. Files
Write code that uses fseek, ftell, read and write to copy the second half of the contents of a file to a pipe.

Write code that uses open, fstat, mmap to print in reverse the contents of a file to stderr.

Write brief code to create a symbolic link and hard link to the file /etc/password

"Creating a symlink in my home directory to the file /secret.txt succeeds but creating a hard link fails" Why?

Briefly explain permission bits (including sticky and setuid bits) for files and directories.

read
write
execute
sticky: prevents users from renaming, moving or deleting contained files owned by users other than themselves, even if they have write permission to the directory. Only the directory owner and superuser are exempt from this.
setuid: When a file with setuid is executed, the resulting process will assume the effective user ID given to the owner class. This enables users to be treated temporarily as root (or another user).
Write brief code to create a function that returns true (1) only if a path is a directory. int is_directory(const char *path) { struct stat path_stat; stat(path, &path_stat); return S_ISDIR(path_stat.st_mode); }

Write brief code to recursive search user's home directory and sub-directories (use getenv) for a file named "xkcd-functional.png' If the file is found, print the full path to stdout.

The file 'installmeplz' can't be run (it's owned by root and is not executable). Explain how to use sudo, chown and chmod shell commands, to change the ownership to you and ensure that it is executable.

9. File system
Assume 10 direct blocks, a pointer to an indirect block, double-indirect, and triple indirect block, and block size 4KB.

A file uses 10 direct blocks, a completely full indirect block and one double-indirect block. The latter has just one entry to a half-full indirect block. How many disk blocks does the file use, including its content, and all indirect, double-indirect blocks, but not the inode itself? A sketch would be useful.

How many i-node reads are required to fetch the file access time at /var/log/dmesg ? Assume the inode of (/) is cached in memory. Would your answer change if the file was created as a symbolic link? Hard link?

What information is stored in an i-node? What file system information is not? Stored: Device ID (this identifies the device containing the file; that is, the scope of uniqueness of the serial number). File serial numbers. The file mode which determines the file type and how the file's owner, its group, and others can access the file. A link count telling how many hard links point to the inode. The User ID of the file's owner. The Group ID of the file. The device ID of the file if it is a device file. The size of the file in bytes. Timestamps telling when the inode itself was last modified (ctime, inode change time), the file content last modified (mtime, modification time), and last accessed (atime, access time). The preferred I/O block size. The number of blocks allocated to this file.

Using a version of stat, write code to determine a file's size and return -1 if the file does not exist, return -2 if the file is a directory or -3 if it is a symbolic link.

int is_directory(const char *path) { struct stat path_stat; fstat(path, &path_stat); if (S_ISDIR(path_stat.st_mode)) { return -1; }

    if (S_LNK(path_stat.st_mode)) {
        return -3;
    }

    return -1;
}
If an i-node based file uses 10 direct and n single-indirect blocks (1 <= n <= 1024), what is the smallest and largest that the file contents can be in bytes? You can leave your answer as an expression.

When would fstat(open(path,O_RDONLY),&s) return different information in s than lstat(path,&s)?

10. "I know the answer to one exam question because I helped write it"
Create a hard but fair 'spot the lie/mistake' multiple choice or short-answer question. Ideally, 50% can get it correct.