htP14N5S

1# Angrave's 2019 Acme-CS241-Exam Prep		
2## AKA Preparing for the Final Exam & Beyond CS 241... 
3
4Some of the questions require research (wikibook; websearch; wikipedia). 
5It is ok to work together & discuss answers! 
6Be ready to discuss and clear confusions & misconceptions in your last discussion section.
7The final will also include pthreads, fork-exec-wait questions and virtual memory address translation. 
8Be awesome. Angrave.
9
10## 1. C 
11
12
131.	What are the differences between a library call and a system call? Include an example of each.
14    
15    -system call
16        -carried out by kernel
17        -executed in kernel space (the final frontier)
18        -expensive
19        -Ex:  write(file_fd, "Hello!", 6);
20    -library call
21        -carried out by program
22        -Ex:  fprintf()
23        
24
252.	What is the `*` operator in C? What is the `&` operator? Give an example of each.
26
27    `*` can be used to dereference a pointer in order to gain access to whatever the pointer is pointing to. 
28    `&` does the opposite, allowing the user to add another layer of abstraction by getting the address of a piece of data instead of the data itself.
29    
30    ```
31    int a = 42;
32    int * refa = &a; //refa becomes a pointer to a
33    a = 33;
34    b = *refa //dereferencing refa gives 33
35    ```
36
373.	When is `strlen(s)` != `1+strlen(s+1)` ?
38
39    -If s is just string of length 0 (not inc. null byte)
40
414.	How are C strings represented in memory? What is the wrong with `malloc(strlen(s))` when copying strings?
42
43    strings are representated as a pointer to a null-terminated arrray of chars in memory.
44    malloc(strlen(s)) wouldn't copy the null character, and therefore "break" the string.
45
465.	Implement a truncation function `void trunc(char*s,size_t max)` to ensure strings are not too long with the following edge cases.
47```
48void trunc(char*s, size_t max){
49length = strlen(s);
50
51if (length < max)
52    //strcmp(trunc(s, max), s) == 0
53    return;
54else if (!s)
55    return;
56else
57    strlen(trunc(s, max)) <= max
58    // i.e. char s[]="abcdefgh; trunc(s,3); s == "abc". 
59    s[max] = '\n';
60    return;
61}
62```
63
64
656.	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.
66
67    ```
68    void duplicate(char **argv, char ***result){
69        char **iter1 = argv;
70        
71    char *arr = malloc(sizeof(argv));
72    memcpy(arr, argv, sizeof(arr));
73    char * iter2;
74        while(iter1){
75            malloc(*iter1 * sizeof(char))
76            iter1++;
77    result = &arr;
78}
79    ```
80    
81        
82
837.	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.
84
85    ```
86    char str[512];
87    getline(str, 256, stdin))
88    do{
89        printf(stdout, "%s\n", str);
90    }while (getline(str, 256, stdin));
91    printf(stdout, "%s", str);
92    ```
93
94## 2. Memory 
95
961.	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. 
97
98    5 levels of page tables with 10 bits each can be setup
99    and the last 12 will determine the offset for the 4KB page.
100    
101
1022.	Explain Knuth's and the Buddy allocation scheme. Discuss internal & external Fragmentation.
103
104    The scheme divides blocks into power-of-2 sizes, but the problem is that if a fily is just over one of these threshholds, a lot of unnecessary data is allocated (and therefore wasted)
105
1063.	What is the difference between the MMU and TLB? What is the purpose of each?
107    
108    The goal of the MMU is to translate virtual mem addresses into phsyical addresses.
109    The TLB is a place (cache) where recently retrieved addresses are stored for future reference (and efficiency)
110    
1114.	Assuming 4KB page tables what is the page number and offset for virtual address 0x12345678  ?
112
113    pagenumber = 0x12345
114    offset = 0x678
115
1165.	What is a page fault? When is it an error? When is it not an error?
117
118    Page fault: unable to retrieve a page
119    It's an error when the page should be there, but there was some mistake made in the request for the page
120    It's not an error if the page just hasn't been placed there before or exists in a different level of cache / disk
121
1226.	What is Spatial and Temporal Locality? Swapping? Swap file? Demand Paging?
123
124    Spatial and Temporal Locality: the concepts that describe how close data is when accessed.
125        data has temporal locality when it is accessed again and again
126        data has spatial locality when a selection of data (like an array) is accessed without randomly having to load in other pages to access certain pieces of data
127        **more locality, better efficiency**
128        swapping happens when data from two different pages causes each page to be loaded in and out when needing to be accessed. 
129        
130        swap files are places on disk where pages have been swapped out (stored)
131        
132         Demand Paging: data isn't copied from disk into disk until it is actually *Needed*.
133
134## 3. Processes and Threads 
135
1361.	What resources are shared between threads in the same process?
137
138    address space
139    live inside same virtual memory
140        -heap
141        -global variables
142        -program code
143
1442.	Explain the operating system actions required to perform a process context switch
145
146    -switching registers
147    -stack pointer
148    -program counter
149    -address space
150
1513.	Explain the actions required to perform a thread context switch to a thread in the same process
152
153    -switching registers
154    -stack pointer
155    -program counter
156    
1574.	How can a process be orphaned? What does the process do about it?
158
159    -When the parent process dies before the children have completed their computations. 
160    -Any orphaned children will have their parent pid set to 1 (assigned to init)
161    -After children finish, they will become zombies for a moment before being cleaned up.
162
1635.	How do you create a process zombie?
164
165    -Child terminates, but still takes up a spot on the kernel process table.
166    -Only way to kill the zombies is by having the parent wait on the (zombie) child
167    
168
1696.	Under what conditions will a multi-threaded process exit? (List at least 4)
170    - last active thread calls pthread_exit()
171    - a thread calls exit()
172    - The process recieves a signal
173    - returning from main (?)
174
175## 4. Scheduling 
1761.	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?
177
1782.	Which scheduling algorithm results the smallest average wait time?
179
1803.	What scheduling algorithm has the longest average response time? shortest total wait time?
181
1824.	Describe Round-Robin scheduling and its performance advantages and disadvantages.
183
1845.	Describe the First Come First Serve (FCFS) scheduling algorithm. Explain how it leads to the convoy effect. 
185
1866.	Describe the Pre-emptive and Non-preemptive SJF scheduling algorithms. 
187
1887.	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 _____?
189
1908.	What reasons might cause a scheduler switch a process from the running to the ready state?
191
192## 5. Synchronization and Deadlock
193
1941.	Define circular wait, mutual exclusion, hold and wait, and no-preemption. How are these related to deadlock?
195
1962.	What problem does the Banker's Algorithm solve?
197
1983.	What is the difference between Deadlock Prevention, Deadlock Detection and Deadlock Avoidance?
199
2004.	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.
201
2025.	Implement a producer-consumer fixed sized array using condition variables and mutex lock.
203
2046.	Create an incorrect solution to the CSP for 2 processes that breaks: i) Mutual exclusion. ii) Bounded wait.
205
2067.	Create a reader-writer implementation that suffers from a subtle problem. Explain your subtle bug.
207
208## 6. IPC and signals
209
2101.	Write brief code to redirect future standard output to a file.
211
2122.	Write a brief code example that uses dup2 and fork to redirect a child process output to a pipe
213
2143.	Give an example of kernel generated signal. List 2 calls that can a process can use to generate a SIGUSR1.
215
2164.	What signals can be caught or ignored?
217
2185.	What signals cannot be caught? What is signal disposition?
219
2206.	Write code that uses sigaction and a signal set to create a SIGALRM handler.
221
2227.	Why is it unsafe to call printf, and malloc inside a signal handler?
223
224## 7. Networking 
225
2261.	Explain the purpose of `socket`, `bind`, `listen`, and `accept` functions
227
2282.	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.
229
2303.	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.
231
2324.	Explain the main differences between using `select` and `epoll`. What are edge- and level-triggered epoll modes?
233
2345.	Describe the services provided by TCP but not UDP. 
235
2366.	How does TCP connection establishment work? And how does it affect latency in HTTP1.0 vs HTTP1.1?
237
2387.	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).
239
2408.	How is Domain Name System (DNS) related to IP and UDP? When does host resolution not cause traffic?
241
2429.	What is NAT and where and why is it used? 
243
244## 8. Files 
245
2461.	Write code that uses `fseek`, `ftell`, `read` and `write` to copy the second half of the contents of a file to a `pipe`.
247
2482.	Write code that uses `open`, `fstat`, `mmap` to print in reverse the contents of a file to `stderr`.
249
2503.	Write brief code to create a symbolic link and hard link to the file /etc/password
251
2524.	"Creating a symlink in my home directory to the file /secret.txt succeeds but creating a hard link fails" Why? 
253
2545.	Briefly explain permission bits (including sticky and setuid bits) for files and directories.
255
2566.	Write brief code to create a function that returns true (1) only if a path is a directory.
257
2587.	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.
259
2608.	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.
261
262## 9. File system 
263Assume 10 direct blocks, a pointer to an indirect block, double-indirect, and triple indirect block, and block size 4KB.
264
2651.	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.
266
2672.	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?
268
2693.	What information is stored in an i-node?  What file system information is not? 
270
2714.	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.
272
2735.	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.
274
2756.	When would `fstat(open(path,O_RDONLY),&s)` return different information in s than `lstat(path,&s)`?
276
277## 10. "I know the answer to one exam question because I helped write it"
278
279Create a hard but fair 'spot the lie/mistake' multiple choice or short-answer question. Ideally, 50% can get it correct.