-
Notifications
You must be signed in to change notification settings - Fork 85
Review
A non-comprehensive list of topics is below.
2
CSP (critical section problems)
HTTP
SIGINT
TCP
TLB
Virtual Memory
arrays
barrier
c strings
chmod
client/server
coffman conditions
condition variables
context switch
deadlock
dining philosophers
epoll
exit
file I/O
file system representation
fork/exec/wait
fprintf
free
heap allocator
heap/stack
inode vs name
malloc
mkfifo
mmap
mutexes
network ports
open/close
operating system terms
page fault
page tables
pipes
pointer arithmetic
pointers
printing (printf)
producer/consumer
progress/mutex
race conditions
read/write
reader/writer
resource allocation graphs
ring buffer
scanf
buffering
scheduling
select
semaphores
signals
sizeof
stat
stderr/stdout
symlinks
thread control (_create, _join, _exit)
variable initializers
variable scope
vm thrashing
wait macros
write/read with errno, EINTR and partial data
In the example below, which variables are guaranteed to print the value of zero?
[language=C] int a; static int b;
void func() static int c; int d; printf("
In the example below, which variables are guaranteed to print the value of zero?
[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("
Explain the error in the following attempt to copy a string.
[language=C] char* copy(char*src) char*result = malloc( strlen(src) ); strcpy(result, src); return result;
Why does the following attempt to copy a string sometimes work and sometimes fail?
[language=C] char* copy(char*src) char*result = malloc( strlen(src) +1 ); strcat(result, src); return result;
Explain the two errors in the following code that attempts to copy a string.
[language=C] char* copy(char*src) char result[sizeof(src)]; strcpy(result, src); return result;
Which of the following is legal?
[language=C] char a[] = “Hello”; strcpy(a, “World”); char b[] = “Hello”; strcpy(b, “World12345”, b); char* c = “Hello”; strcpy(c, “World”);
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’
[language=C] typedef ______________________;
In addition to the function arguments what else is stored on a thread’s stack?
Implement a version of char* strcat(char*dest, const char*src) using
only strcpy strlen and pointer arithmetic
[language=C] char* mystrcat(char*dest, const char*src)
? Use strcpy strlen here
return dest;
Implement version of size_t strlen(const char*) using a loop and no function calls.
[language=C] size_t mystrlen(const char*s)
Identify the three bugs in the following implementation of strcpy.
[language=C] char* strcpy(const char* dest, const char* src) while(*src) *dest++ = *src++; return dest;
Spot the two errors!
[language=C] fprintf("You scored 100
Complete the following code to print to a file. Print the name, a comma and the score to the file ‘result.txt’
[language=C] char* name = .....; int score = ...... FILE *f = fopen(“result.txt”,_____); if(f) _____ fclose(f);
How would you print the values of variables a,mesg,val and 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(<50 characters). Bonus: How would you make this code more robust or able to cope with?
[language=C] char* toString(int a, char*mesg, double val, void* ptr) char* result = malloc( strlen(mesg) + 50); _____ return result;
Why should you check the return value of sscanf and scanf? ## Q 5.2 Why is ‘gets’ dangerous?
Write a complete program that uses getline. Ensure your program has no
memory leaks.
When would you use calloc not malloc? When would realloc be useful?
(Todo - move this question to another page) 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?
[language=C] static int id;
char* next_ticket() id ++; char result[20]; sprintf(result," return result;
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.
[language=C] static char message[20]; pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void *format(int v) pthread_mutex_lock(&mutex); sprintf(message, ": pthread_mutex_unlock(&mutex); return message;
Which one of the following does not cause a process to exit? *
Returning from the pthread’s starting function in the last running
thread. * The original thread returning from main. * Any thread
causing a segmentation fault. * Any thread calling exit. * Calling
pthread_exit in the main thread with other threads still running.
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.
[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 */
Complete the following code. The following code is supposed to print
alternating A and B. It represents two threads that take turns to
execute. Add condition variable calls to func so that the waiting
thread does not need to continually check the turn variable. Q: Is
pthread_cond_broadcast necessary or is pthread_cond_signal
sufficient?
[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 - just use the main thread return 0;
Identify the critical sections in the given code. Add mutex locking to
make the code thread safe. Add condition variable calls so that total
never becomes negative or above 1000. Instead the call should block
until it is safe to proceed. Explain why pthread_cond_broadcast is
necessary.
[language=C] int total; void add(int value) if(value < 1) return; total += value; void sub(int value) if(value <
- return; total -= value;
A non-threadsafe data structure has size() enq and deq methods.
Use condition variable and mutex lock to complete the thread-safe,
blocking versions.
[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();
Your startup offers path planning using latest traffic information. Your
overpaid intern has created a non-threadsafe data structure with two
functions: shortest (which uses but does not modify the graph) and
set_edge (which modifies the graph).
[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);
For performance, multiple threads must be able to call shortest at the
same time but the graph can only be modified by one thread when no
threads other are executing inside shortest or set_edge.
Use mutex lock and condition variables to implement a reader-writer
solution. An incomplete attempt is shown below. Though this attempt is
threadsafe (thus sufficient for demo day!), it does not allow multiple
threads to calculate shortest path at the same time and will not have
sufficient throughput.
[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);
Note thread-programming synchronization problems are on a separate wiki page. This page focuses on conceptual topics. Question numbers subject to change
What do each of the Coffman conditions mean? (e.g. can you provide a definition of each one) * Hold and wait * Circular wait * No pre-emption * Mutual exclusion
Give a real life example of breaking each Coffman condition in turn. A situation to consider: Painters, paint and paint brushes. Hold and wait Circular wait No pre-emption Mutual exclusion
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?
[language=C] // Get both locks or none. pthread_mutex_lock( a ); if( pthread_mutex_trylock( b ) ) /*failed*/ pthread_mutex_unlock( a ); ...
How many processes are blocked?
-
P1 acquires R1
-
P2 acquires R2
-
P1 acquires R3
-
P2 waits for R3
-
P3 acquires R5
-
P1 acquires R4
-
P3 waits for R1
-
P4 waits for R5
-
P5 waits for R1
How many of the following statements are true for the reader-writer problem?
-
There can be multiple active readers
-
There can be multiple active writers
-
When there is an active writer the number of active readers must be zero
-
If there is an active reader the number of active writers must be zero
-
A writer must wait until the current active readers have finished
What are the following and what is their purpose? * Translation Lookaside Buffer * Physical Address * Memory Management Unit * The dirty bit
How do you determine how many bits are used in the page offset?
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?
Explain why the TLB must be flushed when a context switch occurs (i.e. the CPU is assigned to work on a different process).
Question numbers subject to change
Fill in the blanks to make the following program print 123456789. If
cat is given no arguments it simply prints its input until EOF. Bonus:
Explain why the close call below is necessary.
[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;
Use POSIX calls fork pipe dup2 and close to implement an
autograding program. Capture the standard output of a child process into
a pipe. The child process should exec the program ./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
This advanced challenge uses pipes to get an “AI player” to play itself
until the game is complete. The program tictactoe 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 B2A1A3 is a game of 3 turns/plys. A valid response is
B2A1A3C1 (the C1 response blocks the diagonal B2 A3 threat). The
output line may also include a suffix -I win -You win -invalid or
-draw Use pipes to control the input and output of each child process
created. When the output contains a -, print the final output line
(the entire game sequence and the result) and exit.
Write a function that uses fseek and ftell to replace the middle character of a file with an ‘X’
[language=C] void xout(char* filename)
FILE *f = fopen(filename, ____ );
In an ext2 filesystem how many inodes are read from disk to access the
first byte of the file /dir1/subdirA/notes.txt ? Assume the directory
names and inode numbers in the root directory (but not the inodes
themselves) are already in memory.
In an ext2 filesystem what is the minimum number of disk blocks that
must be read from disk to access the first byte of the file
/dir1/subdirA/notes.txt ? Assume the directory names and inode numbers
in the root directory and all inodes are already in memory.
In an ext2 filesystem with 32 bit addresses and 4KB disk blocks, an
inodes that can store 10 direct disk block numbers. What is the minimum
file size required to require an single indirection table? ii) a double
direction table?
Fix the shell command chmod below to set the permission of a file
secret.txt so that the owner can read,write,and execute permissions
the group can read and everyone else has no access.
[language=C] chmod 000 secret.txt
-
See
-
See
What is a socket?
What is special about listening on port 1000 vs port 2000?
-
Port 2000 is twice as slow as port 1000
-
Port 2000 is twice as fast as port 1000
-
Port 1000 requires root privileges
-
Nothing
Describe one significant difference between IPv4 and IPv6
When and why would you use ntohs?
If a host address is 32 bits which IP scheme am I most likely using? 128 bits?
Which common network protocol is packet based and may not successfully deliver the data?
Which common protocol is stream-based and will resend data if packets are lost?
What is the SYN ACK ACK-SYN handshake?
Which one of the following is NOT a feature of TCP? - Packet re-ordering
- Flow control - Packet re-tranmission - Simple error detection - Encryption
What protocol uses sequence numbers? What is their initial value? And why?
What are the minimum network calls are required to build a TCP server? What is their correct order?
What are the minimum network calls are required to build a TCP client? What is their correct order?
When would you call bind on a TCP client?
What is the purpose of socket bind listen accept ?
Which of the above calls can block, waiting for a new client to connect?
What is DNS? What does it do for you? Which of the CS241 network calls will use it for you?
For getaddrinfo, how do you specify a server socket?
Why may getaddrinfo generate network packets?
Which network call specifies the size of the allowed backlog?
Which network call returns a new file descriptor?
When are passive sockets used?
When is epoll a better choice than select? When is select a better choice than epoll?
Will write(fd, data, 5000) always send 5000 bytes of data? When can it
fail?
How does Network Address Translation (NAT) work?
@MCQ Assuming a network has a 20ms Transmit Time between Client and Server, how much time would it take to establish a TCP Connection? 20 ms 40 ms 100 ms 60 ms @ANS 3 Way Handshake @EXP @END
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?
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 write to
implement write_all that will repeatedly call write with any
remaining data. If write returns -1 then immediately return -1 unless
the errno is EINTR - in which case repeat the last write attempt.
You will need to use pointer arithmetic.
[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;
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.
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.
Why is it unsafe to call any function (something that it is not signal handler safe) in a signal handler?
Coding Questions
Write brief code that uses SIGACTION and a SIGNALSET to create a SIGALRM handler.
Please do not edit this wiki
This content is licensed under the coursebook licensing scheme. If you find any typos. Please file an issue or make a PR. Thank you!