nyqWrAPj

1Angrave's 2019 Acme CS 241 Exam Prep
2A.K.A. Preparing for the Final Exam & Beyond CS 241...
3Some 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.
4
51. C
6What are the differences between a library call and a system call? Include an example of each.
7
8system calls are functions provided by the kernel (e.g. open() is a system call)
9library calls are functions within program libraries (e.g. fopen() is a library call)
10What is the * operator in C? What is the & operator? Give an example of each.
11
12the '' operator is used to declare/dereference a ptr (e.g. char c = NULL)
13the '&' operator asks for an address (e.g. &c)
14When is strlen(s) != 1+strlen(s+1) ?
15
16when s == NULL
17How are C strings represented in memory? What is the wrong with malloc(strlen(s)) when copying strings?
18
19strings are represented as null-terminated character arrays
20malloc(strlen(s)) doesn't copy the terminating null byte
21Implement a truncation function void trunc(char*s,size_t max) to ensure strings are not too long with the following edge cases.
22
23if (length < max)
24    strcmp(trunc(s, max), s) == 0
25else if (s is NULL)
26    trunc(s, max) == NULL
27else
28    strlen(trunc(s, max)) <= max
29    // i.e. char s[]="abcdefgh; trunc(s,3); s == "abc". 
30void 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; }
31
32Complete 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.
33
34void duplicate(char **argv, char ***result);
35
36//get number of argv elements int numElems = 0; char** ptr = argv;
37
38while (ptr != NULL) { numElems++; ptr++; }
39
40char** copy = malloc(numElems + 1); copy[numElems] = 0;
41
42//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);
43
44ptr++;
45newelem++;
46}
47
48result = ©
49
50Write 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.
51
52char * line = NULL; size_t len = 0; ssize_t read;
53
54while ((read = getline(&line, &len, stdin)) != -1) { printf("Retrieved line of length %zu:\n", read); printf("%s", line); }
55
56free(line);
57
582. Memory
59Explain 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.
60for a 64bit machine with 4KB pages....
61Explain Knuth's and the Buddy allocation scheme. Discuss internal & external Fragmentation.
62
63buddy allocation scheme: memory allocation algorithm that divides memory into halves to satisfy a memory request ASAP
64little external fragmentation
65can be lots of internal fragmentation, b/c memory requested can be slightly larger than a small block but much smaller than a large block
66What is the difference between the MMU and TLB? What is the purpose of each?
67
68MMU translates virtual memory addresses into physical ones
69TLB is an associative cache of page table entries
70Assuming 4KB page tables what is the page number and offset for virtual address 0x12345678 ?
71
72What is a page fault? When is it an error? When is it not an error?
73
74a page fault is when a processes attempts to access an address in frame that's missing in memory
753 types of page faults:
76minor: address is valid, but no mapping exists yet for the page
77major: mapping to the page is exclusively on disk; OS will swap page into memory and swap another page out
78invalid: read/write to memory address without permission; SIGSEGV
79What is Spatial and Temporal Locality? Swapping? Swap file? Demand Paging?
803. Processes and Threads
81What resources are shared between threads in the same process?
82
83open file descriptors, code section, data section
84
85Explain the operating system actions required to perform a process context switch
86
87since the virtual address space is changing, we must also clear the TLB cache.
88(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.
89
90Explain the actions required to perform a thread context switch to a thread in the same process
91same as above, except for the fact that the TLB does not have to be cleared since the virtual address space remains the same
92How can a process be orphaned? What does the process do about it?
93
94an orphan process is a process whose parent process has finished/been terminated
95any orphaned processes are adopted as children of process 1
96How do you create a process zombie?
97
98A child that terminates, but has not been waited for becomes a "zombie".
99to create a zombiem fork then exit, don't wait for the child
100Under what conditions will a multi-threaded process exit? (List at least 4)
101
102pthread_exit a thread
103pthread_cancel the last thread in the process
104SIGKILL
105SIGINT
1064. Scheduling
107Define 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?
108start time: the wall clock start time of the process (CPU starts working on it)
109
110end time: the wall clock end time of the process( CPU finishes working on it)
111
112run time: teh total amount of CPU time required
113
114arrival time: the time the process enters the scheduler (CPU might start working on it)
115
116turnaround time: the total time from when the process arrives to when it ends (end_time - arrival_time)
117
118response 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)
119
120waiting time: the TOTAL wait time or the total time that a process in on the ready queue (end_time - arrival_time - run_time)
121
122pre-emption: With preemption, the existing processes may be removed immediately if a more preferred process is added to the ready queue.
123
124starvation: a process ready to run for CPU can wait indefinitely because of low priority.
125
126Scheduling policies that may result in starvation:
127
128shortest job first
129Which scheduling algorithm results the smallest average wait time?
130
131shortest job first (SJF)
132What scheduling algorithm has the longest average response time? shortest total wait time?
133
134Describe Round-Robin scheduling and its performance advantages and disadvantages.
135
136round robin: each process is allowed to run for a limited amount of time
137Advantages:
138
139Every Thread / Process gets a chance to run.
140CPU is shared between all processes.
141Threads with the same priority are handled perfectly with Round Robin.
142Disadvantages:
143
144Low Priority tasks may wait for more time if the many tasks are given high priority.
145High Priority tasks may not execute the full instruction given stipulated amount of time.
146Describe the First Come First Serve (FCFS) scheduling algorithm. Explain how it leads to the convoy effect.
147
148The 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.
149
150Describe the Pre-emptive and Non-preemptive SJF scheduling algorithms.
151non-preemptive SJF: the shortest job out of all currently available jobs runs first, and executes on the CPU until completion
152preemptive 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.
153How 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_____?
154if the quantum is too small, there is lots of context switching, which is expensive
155if the quantum is too large, the algorith is less effective ----> FCFS
156What reasons might cause a scheduler switch a process from the running to the ready state?
157Preemption brings the process back to the ready state
1585. Synchronization and Deadlock
159Define circular wait, mutual exclusion, hold and wait, and no-preemption. How are these related to deadlock?
160
161circular 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.
162mutual exclusion: A resource can be held by at most one process.
163hold and wait: Processes that already hold resources can wait for another resource.
164no-preemption: A resource, once granted, cannot be taken away.
165What problem does the Banker's Algorithm solve?
166
167deadlock!! specifically it checks if the a resource allocation is safe before proceeding
168What is the difference between Deadlock Prevention, Deadlock Detection and Deadlock Avoidance?
169
170Deadlock detection allows the system to enter a deadlocked state. After entering, the system uses the information to break deadlock
171Deadlock 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.
172Deadlock avoidance: e.g. Banker's algorithm, checks whether deadlock will occur for a change in state before proceeding
173Sketch 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.
174
175Implement a producer-consumer fixed sized array using condition variables and mutex lock.
176
177Create an incorrect solution to the CSP for 2 processes that breaks: i) Mutual exclusion. ii) Bounded wait.
178
179Create a reader-writer implementation that suffers from a subtle problem. Explain your subtle bug.
180
1816. IPC and signals
182Write brief code to redirect future standard output to a file.
183
184Write a brief code example that uses dup2 and fork to redirect a child process output to a pipe
185
186Give an example of kernel generated signal. List 2 calls that can a process can use to generate a SIGUSR1.
187
188e.g. SIGINT, SIGQUIT
189to generate SIGUSR1: kill() or raise()
190What signals can be caught or ignored?
191
192signals such as SIGINT and SIGTERM can be caught/ignored
193What signals cannot be caught? What is signal disposition?
194
195SIGKILL cannot be caught
196The 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.
197Write code that uses sigaction and a signal set to create a SIGALRM handler.
198
199Why is it unsafe to call printf, and malloc inside a signal handler?
200
201they use a lock, but signal handlers are called asynchronously. therefore deadlock may occur
2027. Networking
203Explain the purpose of socket, bind, listen, and accept functions
204
205want to set up a TCP server
206
207socket: creates an endpoint for communication and returns a file descriptor that refers to that endpoint
208
209bind: assigns the address specified by addr to the socket referred to by the file descriptor sockfd
210
211listen: marks the socket referred to by sockfd as a passive socket
212
213connect: connects the socket referred to by the file descriptor sockfd to the address specified by addr
214
215Write 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.
216
217Write 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.
218
219Explain the main differences between using select and epoll. What are edge- and level-triggered epoll modes?
220
221Describe the services provided by TCP but not UDP.
222
223resend dropped packets
224orders packets correctly
225How does TCP connection establishment work? And how does it affect latency in HTTP1.0 vs HTTP1.1?
226
227Wrap 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).
228
229How is Domain Name System (DNS) related to IP and UDP? When does host resolution not cause traffic?
230
231What is NAT and where and why is it used?
232
2338. Files
234Write code that uses fseek, ftell, read and write to copy the second half of the contents of a file to a pipe.
235
236Write code that uses open, fstat, mmap to print in reverse the contents of a file to stderr.
237
238Write brief code to create a symbolic link and hard link to the file /etc/password
239
240"Creating a symlink in my home directory to the file /secret.txt succeeds but creating a hard link fails" Why?
241
242Briefly explain permission bits (including sticky and setuid bits) for files and directories.
243
244read
245write
246execute
247sticky: 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.
248setuid: 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).
249Write 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); }
250
251Write 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.
252
253The 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.
254
2559. File system
256Assume 10 direct blocks, a pointer to an indirect block, double-indirect, and triple indirect block, and block size 4KB.
257
258A 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.
259
260How 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?
261
262What 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.
263
264Using 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.
265
266int is_directory(const char *path) { struct stat path_stat; fstat(path, &path_stat); if (S_ISDIR(path_stat.st_mode)) { return -1; }
267
268    if (S_LNK(path_stat.st_mode)) {
269        return -3;
270    }
271
272    return -1;
273}
274If 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.
275
276When would fstat(open(path,O_RDONLY),&s) return different information in s than lstat(path,&s)?
277
27810. "I know the answer to one exam question because I helped write it"
279Create a hard but fair 'spot the lie/mistake' multiple choice or short-answer question. Ideally, 50% can get it correct.