CSE4001 Fall 2005 Exam #3, open book, open notes. Name ___________________ Each question is 10 points. 1. What are the 3 memory segments allocated to each process? ANSWER: code, data, stack. 2. What is the difference between a process and a thread? ANSWER: threads share memory (code and data), processes do not. 3. List the 4 states that a running UNIX process may transition to. For each state, what event will cause it to transition to that state? ANSWER ready or runnable - timeout suspended - SIGSTOP signal sleeping - wait for event (such as I/O) zombie - exit or killed 4. What effect does total CPU usage have on process priority? ANSWER: It decreases priority (to favor interactive processes). 5. Why is the following software implementation of a semaphore faulty? Describe how it could fail in a multithreaded application. What hardware support is required to implement a semaphore? class Semaphore { int available; // in shared memory public: Semaphore() {available=1;} int wait() { while (available < 1) sleep(1); --available; } int signal() {++available;} }; ANSWER: wait() is a critical area. It is possible for another thread to change 'available' in between the test (available < 1) and the set (--available). These two operations must be indivisible, either bu a special instruction (most processors have a "test and set" instruction) or by disabling interrupts between these two operations. 6. What is a deadlock? Give an example of two deadlocked processes waiting on semaphores. ANSWER: A deadlock is when two or more processes or threads are each holding a resource and waiting for the other to release their resource. For example, a resource could be a critical area controlled by a semaphore. Thread 1 Thread 2 --------- --------- Semaphore s1, s2; s1.wait(); s2.wait(); // both proceed s2.wait(); s1.wait(); // both wait - deadlock s2.signal(); s1.signal(); // these statements never reached s1.signal(); s2.signal(); 7. What information is stored in an inode? ANSWER: pointers to disk blocks, plus all information returned by stat() (i.e. everything except the filename): file type, real and effective owner and group ID, permissions, hard link count, last accessed/modified/changed time. 8. Under what two conditions does a page fault occur? ANSWER 1. when accessing a page not in memory (valid bit not set), 2. when writing to a page with the copy-on-write bit set. 9. Which component of a virtual memory system is responsible for making free pages available? ANSWER: the page daemon (a background process that updates the ages of pages and frees the oldest ones). 10. A computer has 4GB of virtual memory and 256MB of physical memory and a page size of 4KB. A small (one page) program at address 0x10000 copies a 1GB array starting at address 0x20000000 to a 1 GB array starting at 0x60000000. The page replacement algorithm is LRU. Assume that all pages are initially free, that pages are not freed until needed, and that no other processes run. a. How many page faults are there? b. How many pages were written to disk? ANSWER. a. Each array is 256K pages (1GB/4KB), so a total of 512K pages must be brought into memory. Also, the program is 1 page, so the total is 512K + 1 = 524,289. (You may express your answers in K or give an approximate answer). b. There are 64K pages of memory (256MB/4KB). These will be filled with the 64K most recently accessed pages, which will be the program (1 page), the last 32K pages of the destination array, and last 32K - 1 pages of the source array. Only the destination array pages need to be written to disk, since the other pages are not modified. The pages still in memory are not written. Each array has 1GB/4KB = 256K pages. Therefore 256K - 32K = 224K = 229,376 pages of the destination array are written to disk.