CS330

Introduction to Operating Systems

Final Examination Preparation

QUESTIONS GIVEN FOR MIDTERM EXAMINATION PREPARATION ARE EQUALLY RELEVANT TO FINAL EXAMINATION. QUESTIONS FOR SECOND HALF OF COURSE ARE GIVEN HERE.

To prepare for the final exam, read:

· your notes; if you are missing any notes, see the course website and follow the link to the notes.

· Silberschatz, Galvin, and Gagne, Operating Systems Concepts, Seventh Edition or Eighth Edition (SGG78), chapters 1-3 and 5-11, 14, and 18 with emphasis on Sec. 2.1-2.4, 3.1-3.3, 3.4, 5.1-5.3, 5.6-5.7, 6.1-6.5, 7.1-7.4, 7.7, chapter 8 (all), Sec. 9.1-9.4, chapter 10 (all), Sec. 11.1-11.5, 14.1-14.5~~, 18.5-18.7~~.

· Silberschatz, Galvin, and Gagne, Operating Systems Concepts, Sixth Edition (SGG6), chapters 1-4 and 5-10, 12, 17-18, with emphasis on Sec. 3.1-3.4, 4.1-4.3, 4.5.1-4.5.4, 6.1-6.3, 6.6-6.7, 7.1-7.5, 8.1-8.4, 8.7, chapter 9 (all), Sec. 10.1-10.4, chapter 11 (all), Sec. 12.1-12.5, 18.1-18.5, ~~17.5-17.7~~.

· Gray, Interprocess Communication in UNIX, chapters 1-5 (with emphasis on chap.1 (perror, fork, many general concepts), sec 2.2 (getpid system call), 2.3 (getppid system call), 2.8 (chmod system call), 2.10 (signals concepts), 2.11 (argc/argv), 3.1-3.2 (fork system call), 3.3 (exec concepts, execl or execlp system call), 3.4 (fork/exec together, exit library function, _exit system call), 3.6 (wait and waitpid system calls), p.90 (sleep system call), 4.4 (signals concept, kill system call), 4.5 (signal system call). If you don't have access to a copy of Gray's book, review the concepts mentioned here from other sources.

· The Linix/Unix semaphore functions will not be tested on the final examination.

· your laboratory assignments, especially with regard to the use of the open, close, read, write, lseek, and stat system calls.

· your project

DESCRIPTION OF FINAL EXAM:

The final exam is 3 hours (180 minutes long) and is marked out of 120 marks, which means that you can allocate your time as one mark per minute. The actual exam contains 7 questions (7 pages) for 20 marks each and you are to do SIX (6) out of 7 questions. Place a large X on the page not to be marked. If no page is blank or X'd, I will mark the first 6 questions.

The exam is intended to be comprehensive, i.e., test your understanding of all aspects of the course material. The exam will feature both memory-testing questions (define, describe, compare and contrast, give examples) and problem-solving questions. Problem-solving questions will be directed towards material covered in lectures, assignments, and labs. Some questions will refer to material in the listed chapters, that has not otherwise been covered, but these questions will be memory-testing questions and will be less than 10% of the exam.

SAMPLE QUESTIONS:

The following questions may help you prepare for the final examination. I have estimated the number of marks that such a question, in its entirety, would be assigned in an exam. In general, these are NOT the questions that will appear on the examination, but by doing them you will increase your familiarity with the relevant concepts. During the exam you will be provided with concise documentation on the UNIX system calls relevant to any programming question.

CONCURRENT PROCESSES AND DEADLOCK:

C1. (10 marks)

The following is the correct code for Peterson's solution (Figure 6.2 in the text) for process i, given one other concurrent process named j:

1. do {

2. flag[i] = TRUE;

3. turn = j;

4. while (flag[j] and turn = j)

5. ; /* no-op */

6. ** CRITICAL SECTION **

7. flag[i] = FALSE;

8. ** REMAINDER SECTION **

9. } while (TRUE);

Note: the same code is used for the other process, with the meaning of i and j reversed

Note: the complete content of the while loop is the no-op statement.

(a) Show that if lines 2 and 3 were reversed that the code fails to solve the mutual exclusion problem. To do so, find some sequence of execution and preemption between two processes such that both processes end up in the critical section at the same time. The revised lines of the algorithm are:

2. turn = j;

3. flag[i] = TRUE;

(b) Explain step by step how Peterson's algorithm handles the same case.

C2. (9 marks)

Explain how to use the following to solve the mutual exclusion problem, and discuss whether each uses busy waiting:

(a) interrupts

(b) test-and-set instruction

C3. (5 marks)

Show using an example that, if the semaphore operations called wait and signal are not executed atomically, then mutual exclusion may be violated.

C4. (6 marks)

With regard to the semaphore solution to the bounded buffer problem (the producer-consumer problem):

(a) Explain the purpose of each of the three semaphores.

(b) Explain why the order of calls to wait and signal is different between the producer and the consumer.

C5a. (10 marks)

How can semaphores be used to solve the first reader-writer problem (such that no reader be kept waiting unless a writer has already obtained permission to use the shared object)? Give pseudocode for the reader process and a writer process. Describe the purposes and initial values of the semaphores used.

(Hint for exam preparation: see SGG78, section 6.6.2 or SGG6, section 7.5.2 or SG5, section 6.5.2; write your pseudocode in the same style as the textbook examples).

C6. (10 marks)

Disabling interrupts frequently can affect the system’s clock. Explain why it can, and how such effects can be minimized.

(Hint for exam preparation: see background material in SGG78, section 6.2 or SGG6, section 7.3 or SG5, section 6.3)

C7a. (10 marks)

[Equivalent to the second reader-writer problem in textbook]

Two types of concurrent processes require access to a shared variable (called RESTRICTED_VAR) containing an integer value. Note, these are concurrent processes that share memory (unlike UNIX processes) and might be better called threads.

- Checker processes simply check whether the value in RESTRICTED_VAR is zero.

- Updater processes update the value in RESTRICTED_VAR from time to time.

The checker processes may share access to RESTRICTED_VAR, but when an updater process is updating RESTRICTED_VAR, no other process is allowed access to RESTRICTED_VAR. Whenever an updater process is ready to update RESTRICTED_VAR, any checker processes that later request access to RESTRICTED_VAR, will not have access granted until the updating is done. Assume that many separate updater and checker processes are run at various times.

You are to devise a pseudocode solution to this problem using semaphores. You should also specify initial values for all semaphores used in your programs. Your solution need not avoid starvation. Your solution should consist of two pieces of code (written in a style of pseudocode similar to the examples given in SGG7, section 6.6, SGG6, section 7.5 or SG5, section 6.5):

(1) code for a checker process and

(2) code for an updater process.

C7b. (7 marks)

(a) Draw the resource-allocation graph when the sets P, R, and E are:

· P = {P1; P2; P3; P4; P5}

· R = {R1; R2; R3; R4; R5}

· E = {P2 → R1, P2 → R5, P3 → R3, P4 → R1, P4 → R3, P4 → R4, P5 → R2, R1 → P3, R2 → P2, R3 → P5, R4 → P2, R5 → P1}

Assume there exists one instance of each resource type. As well, assume resources R1, R2, R3, R4, and R5 are nonpreemptive and cannot be shared.

(b) Could a deadlock exist in the system described in part a)? Explain why or why not making reference to the necessary conditions for deadlock.

C8. (7 marks)

(a) Draw the resource-allocation graph when the sets P, R, and E are:

P = {P1, P2, P3}
R = {R1, R2, R3, R4}
E = {P1 -->R1, P2 -->R1, P2 -->R2, P3 -->R4, R2 -->P3, R3 -->P1, and R4 -->P2}

Assume there exists one instance of each resource type. As well, assume resources R1, R2, R3, and R4 are nonpreemptive and cannot be shared.

(b) Could a deadlock exist in the system described in part a)? Explain why or why not making reference to the necessary conditions for deadlock.

C9. (11 marks)

In the Dining Philosophers problem, 5 philosophers sit around a table with 5 chopsticks located one between each pair of philosophers. To eat, a philosopher must have two chopsticks.

(a) Explain how each of the following methods prevent deadlock in this problem:

(i) one-shot algorithm

(ii) repeated one-shot (multishot) algorithm

(iii) hierarchical algorithm

(b) Do any of these solutions prevent starvation? Explain.

C10. (4 marks)

In the hierarchical algorithm for preventing deadlock, each resource type is assigned a unique integer as a priority, with 5 as lowest priority and 0 as highest priority. Suppose

resource R1 has priority 3,
resource R2 has priority 5,
resource R3 has priority 0.

Given this sequence of requests and frees:

P1 requests R1,
P3 requests R3,
P1 requests R2,
P1 frees R2,
P2 requests R2,
P2 frees R2,
P3 requests R2,
P3 frees R2

which of the above REQUESTS will be REFUSED by the hierarchical algorithm?

MEMORY MANAGEMENT:

M1. (8 marks)

Draw a picture and describe a four-level storage hierarchy. Give the sizes, prices, and speeds of typical current hardware for each level of the storage hierarchy.

M2. (6 marks)

What are the three segments of a UNIX process? What software determines where they are located in the virtual address space? the physical address space?

M3. (9 marks)

Given memory partitions (holes) of 1Mb, 4Mb, 3Mb, 2Mb, and 6Mb (in order), how would each of the First-fit, Best-fit, and Worst-fit algorithms place processes if the requests for space were received in the order:

process 1 of size 2.12Mb,
process 2 of size 4.17Mb,
process 3 of size 1.12Mb, and
process 4 of size 4.26Mb?

In this case, which algorithm makes the least efficient use of memory?

M4. (15 marks)

Consider virtual address translation in a paged system, based on byte-addressable memory.

Suppose that:

the size of the virtual address space is 32M bytes,

· the size of a page is 512 bytes,

the size of the real address space is 256K bytes.

a) What is the length (in bits) of the virtual address?

b) What is the length (in bits) of the physical address?

c) What is the length (in bits) of the displacement (or offset) field?

d) What is the length (in bits) of the page number field?

e) How many page frames are there in main memory?

Show your work or explain each result in a few words.

M5. (15 marks)

(a) Using a picture, explain the procedure for translating virtual addresses into physical addresses for a paging system. Assume a 32 bit virtual address, a 24 bit physical address, and a page size of 256 bytes (i.e., 2^8).

(b) Given a virtual address written in binary as 0000 0000 1111 1111 1001 1001 1000 1000 or in hex as 00ff9988, and a page size of 256 (i.e., 2^8), what is the corresponding 24 bit physical address?

M6. (10 marks): not relevant for 201030.

Describe an inverted page table. What is its purpose in an operating system? What type of page replacement algorithm might consult the inverted page table?

M7. (8 marks)

Assume that we have a paged memory system with associative registers to hold the most active page-table entries and all of page-table entries in main memory. (The associative registers are also called the translation lookaside buffer.) Access time is 8 nanoseconds for the associative registers and 80 nanoseconds for the main memory. When a page is referenced, a search is first made of the associative registers and if that fails, main memory is then accessed.

(a) What is the effective access time for a page-table entry if 90% of all memory references find their entries in the associative registers? Note: consider the time required to access the page table, but not the time required for the subsequent access to the page itself.

(b) Repeat part (a) for 50%.

(c) What do the results from parts (a) and (b) suggest about the usefulness of associate registers for storing page-table entries?

(Note for exam preparation: here the time is for finding the page table entry rather than the value from main memory.)

M8, M9: not relevant for 201030.

M10. (40 marks)

Assume that main memory contains 3 page frames with pages 3, 1, and 4 in them (from the sequence of page references 3 1 4). Suppose that the sequence of page references continues:

5 2 4 1 4 3 5 2 4 1.

(a) Give a trace of the contents of main memory, showing the contents after each page reference, using Belady's optimal (MIN or OPT) algorithm. Also give the total number of page faults.

OPT:

3
1
4

What is the number of page faults? _____________

(b) Repeat part (a) using theFIFO algorithm and the same page reference string:

5 2 4 1 4 3 5 2 4 1.

FIFO:

3
1
4

What is the number of page faults? ______________

5 2 4 1 4 3 5 2 4 1.

LRU:

3
1
4

What is the number of page faults? _________________

(d) Repeat part (a) using the NRU Linear Scanning algorithm and the same page reference string:

5 2 4 1 4 3 5 2 4 1.

NRU LINEAR SCANNING ALGORITHM (asterisk shows location of search pointer):

P	U
*3	1
1	1
4	1

What is the number of page faults? _________________

(e) Repeat using the NRU Additional Reference Bits algorithm and the same page reference string with bit shift to the right each time there is a T: 5 2 4 T 1 4 3 T 5 2 4 1 T 4 2 4.

NRU ADDITIONAL REFERENCE BITS ALGORITHM:

What is the number of page faults? _________________

FILE-SYSTEM IMPLEMENTATION

F6. (15 marks)

Consider a file currently consisting of 600 blocks. Assume that the file control block (and the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level) allocation strategies, if, for one block, the following conditions hold. In the contiguous-allocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added is stored in memory.

(a) The block is added at the beginning.

(b) The block is added after block 200.

(d) The 200th block is removed.

(e) The block is removed from the end.

F7. (18 marks) – another question similar to F6.

Consider a file currently consisting of 400 blocks. Assume that the file control block is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed allocation strategies, if, for one block, the following conditions hold. In the contiguous-allocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added is stored in memory. For the indexed allocation scheme, assume that the index is all stored in one index block and that this index block is already in memory.

(a) The block is added at the beginning.

(b) The block is added after block 206.

(d) The 9^th block is removed.

(e) The 303^rd block is removed.

(f) The last block is removed from the end.

F8. (6 marks)

Consider a file system on a disk that has both logical and physical block sizes of 512 bytes. Assume that the information about each file is already in memory. For each of the linked and indexed strategies, answer these questions:

(a) How is the logical-to-physical address mapping accomplished in this system? (For the indexed allocation, assume that a file is always less than 512 blocks long.)

(b) If we are currently at logical block 10 (the last block accessed was block 10) and want to access logical block 4, how many physical blocks must be read from the disk? Explain your reasoning for each strategy.

(Question 12.6 in SGG.)

F9. (9 marks)

For the contiguous strategy, given free areas on disk of 1Mb, 4Mb, 3Mb, 2Mb, and 6Mb (in order), how would each of the First-fit, Best-fit, and Worst-fit algorithms place files of 2.12Mb, 4.17Mb, 1.12Mb, and 4.26Mb (in order)? Which algorithm makes the least efficient use of disk space?

F10. Omitted

F11. Omitted

LABORATORY WORK / SYSTEM CALLS

L11. (15 marks)

Using the programming language of your choice, write a complete program that provides a simple shell for UNIX. Prompt the user with a "%" symbol and then read the command (a string). Assume that the command consists of a single word. If the command isn't "stop", then create a child process and have this child process load the executable file corresponding to the command. For example, if the command is "ls", then run /bin/ls, and if the command is "pwd", then run "/bin/pwd". If the child process can't find the executable file to execute in /bin, it should print a message saying "Unknown command". In the meantime, the parent process should wait until the child process terminates. Then the parent process should prompt the user again and read the next command. This procedure should be followed until the word "stop" is entered.

L12. (15 marks)

(a) Using the programming language of your choice, write a complete program that displays information about its address space on UNIX. Display the addresses of some key identifiers:

· a global variable,

an automatic local variable,
the address of a function,
a static local variable, and
a variable on the heap (you will have to allocate one with malloc or new).

To show the addresses, use regular print statements, such as printf or cout.

(b) not provided

L13. Not provided.

L14. (15 marks)

Using the programming language of your choice, write a complete program that uses UNIX system calls to perform the following:

create two child processes,
run the “cat” program in the first process with arguments myfile1 myfile2, and myfile3,
run the “wc” program in the second process with no arguments,
use an unnamed pipe to transfer the output of the first process to the second process,
have the parent wait until both child processes are done.

Assume the executable for “cat” and “pwd” can be found in “/bin/cat” and “/usr/local/bin/pwd”, respectively.

L15. (10 marks)

Using the programming language of your choice, write a complete program that uses UNIX system calls to create a binary file, write the integer 47, the double value 93.6, and the four characters ‘r’, ‘a’, ‘t’, and ‘s’ to it, then close it. Report an error with a standardized system error message if the file cannot be opened or if any of the writes fails.

Project: P1, P2, P3, P4 - omitted