University of Illinois at Urbana-ChampaignDepartment of Computer ScienceFinal ExaminationCS 241 System ProgrammingFall 20058:00-11:00 am Thursday December 151304 Siebel CenterName:NetID:• Print your name and netid neatly in the space provided above; print your netid at the upperright corner of every page.• This is a closed book, closed notes exam. No electronic aids are allowed, either.• Eleven short answer, one implementation, one design essay; do all parts of every question.• This booklet should include this title page, plus pages 1-12. Do your work inside this booklet,using the backs of pages if needed.• Problems are of varying difficulty, hence if you don’t know the answer immediately, progressto the following problem and come back to the unsolved problem later.• Perfect syntax is not required, but any code you write must be understo od by the graders.A few reference functions are included on the last page.Problem(s) Points Score1-3 154-5 106 157-9 1010 1011 2012 1013 30Total 120CS 241 Final Exam 1 NetID:1. (5pts) What is the difference between a physical memory address and a virtual memoryaddress?2. (5pts) Explain the difference betwee n a library function and a system call.3. (5pts) Why is it generally bad practice to acquire a lock in a signal handler?CS 241 Final Exam 2 NetID:4. (5pts) Explain Best Fit, First Fit, and Worst Fit. Argue for the exclusive use of one in asystem.5. (5pts) Compare and contrast linked list allocation and indexed allocation in a file system.CS 241 Final Exam 3 NetID:6. On a particular 64bit system with a 60gb hard disk, I-nodes are 512 bytes and disk blocksare 8kb. The I-node status information takes up 232 bytes. There is an address for a singleindirect block, an address for a double indirect block, and an address for a triple indirectblock; the rest of the space is for direct address pointers.(a) (2pts) How many addresses are needed to address a 64 kilobyte (216) file?(b) (4pts) How large of a file can be addressed by the double indirect block alone?(c) (4pts) Does a 4 megabyte (222) file use all of the addresses on its I-node? Any addressesin the single indirect block? double indirect? triple indirect?(d) (5pts) How much disk space (including overhead) is used to store the addresses requiredto access a 4 megabyte file (the answer involves more than one calculation)?CS 241 Final Exam 4 NetID:7. (4pts) Give more than one situation where use of a FIFO would be more desirable than apipe.8. (3pts) What C function is used to redirect standard output to a file?9. (3pts) When is it proper to use select()?CS 241 Final Exam 5 NetID:10. (a) (2pts) How would the im plementation of a web server using threads differ from one usingprocesses?(b) (2pts) A web server is started listening on port 8080, receives 5 incoming connections,then properly and completely is shut down. How many close() system calls are there ona threaded implementation? How many on a multiprocessed implementation?(c) (6pts) Discuss how a multithreaded web server running on a single processor systemcould be optimized using the process scheduling methods discussed in class? Which doyou recommend?CS 241 Final Exam 6 NetID:11. (20pts) Oh no! Andrew just accidentally deleted restart.h and restart.c! He is in desperateneed of the copyfile() method. Complete the implementation below without using any restartlibrary function calls. Add any helper functions you want. Informal descriptions will earnonly partial credit.#define BLKSIZE 4096// int copyfile(int fromfd, int tofd)// Attempts to copy all readable bytes from file descriptor fromfd to file// descriptor tofd.// File descriptors are assumed opened before the call to copyfile(), and// shall not be closed by the function.// if successful returns the number of bytes copied from fromfd to tofd// in the event of an error other than EINTR (automatic restart on EINTR),// errno is set and -1 is returnedint copyfile(int fromfd, int tofd){CS 241 Final Exam 7 NetID:11. (continued.)CS 241 Final Exam 8 NetID:12. (10pts) For each set of threads below, determine if a deadlock s tate can be reached. If so, fixthe deadlock, if not, give sufficient proof the deadlock cannot occur. Assume that mutex_ashould be acquired before read and write on variable a, mutex_b for variable b, etc.(a) Thread 1 Thread 2lock(mutex_a) lock(mutex_b)lock(mutex_b) lock(mutex_c)b = a c = bunlock(mutex_a) unlock(mutex_b)lock(mutex_c) lock(mutex_a)b = b + c a = c * 2unlock(mutex_c) unlock(mutex_a)unlock(mutex_b) unlock(mutex_c)(b) Thread 1 Thread 2 Thread 3lock(mutex_d) lock(mutex_e) lock(mutex_f)lock(mutex_e) lock(mutex_f) lock(mutex_d)e = d * 2 f = f + e d = d * funlock(mutex_e) unlock(mutex_f) unlock(mutex_d)unlock(mutex_d) unlock(mutex_e) unlock(mutex_f)(c) Thread 1 Thread 2lock(mutex_h) lock(mutex_g)lock(mutex_i) lock(mutex_i)lock(mutex_j) i = g + gj = i + h unlock(mutex_i)unlock(mutex_j) unlock(mutex_g)unlock(mutex_h)lock(mutex_g)g = g + iunlock(mutex_g)unlock(mutex_i)CS 241 Final Exam 9 NetID:13. (30pts) CS 241 Industries wishes to design a network memory server. Our programmers aren’tvery good, but if we give them the algorithm to follow, we believe they can create a goodimplementation from it.We seek to have a server with a lot of fast memory (4 gigabytes), that is running a simplememoryServer program. Clients should be able to connect to it over a very fast networkconnection, and then request me mory that they can use to store and load data. The clientshave only 64kb of local memory to use, and no disk from which to swap virtual memory.The client will have an instantiation of a memoryClient class which can be used to allocatemore memory as needed, or transfer data to and from the server.Give all the details you can (network protocols, how and when to connect, if the applicationsare multithreaded, virtual memory sizes, how much memory to swap across the network fora “mapoffset()” call, etc) of how the algorithm should be structured to allow the serve r toservice numerous connecting clients. Be explicit and verbose in your response.Also be sure to address these 2 questions:- What kind of function calls will the server need to implement?- What accessor methods will the client need and how will it run those on the remotemachine?CS 241 Final Exam 10 NetID:13. (continued.)CS 241 Final Exam 11 NetID:(extra paper.)CS 241 Final Exam 12 NetID:Manual pagessize_t read(int fd, void *buf, size_t count);read() attempts to read up to count bytes from file descriptor fd
View Full Document
Unlocking...