CS330
Introduction to Operating Systems
To prepare for the midterm 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, 2, 3, 5, and 10, with emphasis on Sec. 1.1, 1.4-1.7, 2.1-2.4, 2.6-2.8, 3.1-3.3, 5.1-5.3, 10.1-10.3.
· your laboratory assignments 1-4
· Gray, Interprocess Communication in UNX, chapters 1-4, 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), Sec. 4.4 (signals concept, kill system call), p.90 (sleep system call). If you don't have access to a copy of Gray's book, review the concepts mentioned here from other sources. Relevant material on using system calls for file operations is NOT given in Gray, but should be studied.
The following questions may help you prepare for the midterm 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.
INTRODUCTION:
1. (11 marks)
By consulting with the on-line notes or the textbook, define the following terms clearly and concisely. Use at most two sentences for each:
(a) operating system
(b) program counter
(c) multiprogramming (use the definition given in online notes rather than the one in the textbook)
(d) time sharing
(e) multiprocessing
(f) tightly coupled system
(g) loosely coupled system (clustered system)
(h) symmetric multiprocessing
(i) asymmetric multiprocessing
2. (18 marks)
By consulting with the on-line notes or the textbook, define the following terms clearly and concisely. Use at most two sentences for each:
(a) system call
(b) caching
(c) interrupt (define as occurring from hardware only)
(d) interrupt vector
(e) interrupt service routine (interrupt handler)
(f) trap
(g) direct memory access (DMA)
(h) dual-mode operation
(i) mode bit
(j) privileged instruction
(k) I/O protection
(l) memory protection
(m) base register
(n) limit register
(o) cpu protection
(p) timer interrupt
(q) halt instruction
3. (6 marks)
Draw the onion-skin diagram of an operating system. Briefly explain the purpose of each layer of the operating system.
(Hint for exam preparation: see lecture notes.)
4. (6 marks)
Suppose that the UNIX command
ls
is entered. It lists the names of the files in the current working directory. Based on the onion-skin diagram of an operating system, what part(s) of the operating system are involved in receiving this command and responding to it.
5. (3 marks)
What is a command interpreter? What is its main purpose?
6. (3 marks)
What are the four main functions of the nucleus of the operating system?
(Hint for exam preparation: see lecture notes.)
7. (8 marks)
Protecting the operating system is crucial to ensuring that the computer system operates correctly. To allow maximum flexibility, however, we would also like to place minimal constraints on the user. The following is a list of operations that are normally performed using privileged instructions. What is the minimal set of instructions that must be privileged?
(a) Change to monitor mode (system mode).
(b) Change to user mode.
(c) Turn on the timer (clock) interrupt.
(d) Turn off the timer (clock) interrupt.
(e) Set the value of the timer (clock).
(f) Read a value from monitor memory (i.e., OS’s private area of memory).
(g) Read an instruction from monitor memory (i.e., OS’s private area of memory).
(h) Write a value into monitor memory (i.e., OS’s private area of memory).
Explain why or why not each operation should be privileged. (SGG78, chapter 1; SGG6, chapter 2)
8. (6 marks)
Explain the concept of an interrupt-driven operating system. What types of events occur in the hardware and software that affect the operating system? In each case, what steps occur when such an event occurs? (SGG78, chapter 1; SGG6, chapter 2)
9. (6 marks)
Explain how dual-mode operation forms the basis for (a) input output protection, (b) memory protection, and (c) cpu protection. For each of these three types of protection, explain whether or not they require the use of privileged instructions. (SGG78, chapter 1; SGG6, chapter 2)
10. (10 marks)
Five major categories of operations provided by an operating system are process management, main-memory management, file management, I/O system management, and mass storage (secondary-storage) management. Draw a table that shows two activities in each category. (SGG78, chapter 2; SGG6, chapter 3)
11. (10 marks)
System calls can be grouped in five major categories: process control, file manipulation, device manipulation, information maintenance, and communication. Identify two system calls in each category by giving either the purpose of the system call or the name of the system call in UNIX. (SGG78, chapter 2; SGG6, chapter 3; Gray)
12. (5 marks)
Explain the difference between a system call and a system program. System programs are also called utility programs. Explain how in UNIX there could be a system call and a system program both called chmod. When would each be used? Explain. (SGG78, chapter 2; SGG6, chapter 3)
13. (5 marks)
What is a layered approach to operating system design? What is the relationship between a layer and other contiguous layers? What are the advantages and disadvantages of a layered design? (SGG78, chapter 2; SGG6, chapter 3)
14. (4 marks)
What is a virtual machine? (use the definition given in online notes). Explain, with regard to virtual Intel processors and Java virtual machines, what are the main advantages to the user of using a virtual-machine architecture. (SGG78, chapter 2; SGG6, chapter 3)
PROCESS MANAGEMENT:
P1. (1 marks)
Give a simple definition for a process? (SGG78, chapter 1; SGG6, chapter 3).
P2. (4 marks)
Draw a process state diagram giving names to the nodes and links. (SGG78, chapter 3; SGG6, chapter 4).
P3. (5 marks)
What is the difference between the process table and a process control block? What information is stored for each process? (SGG78, chapter 3; SGG6, chapter 4).
P4. (4 marks)
Describe the actions taken by the OS nucleus to perform a context switch among processes. A context switch is also called a process switch. (SGG78, chapter 3; SGG6, chapter 4).
P5. (5 marks)
Give three (3) examples of resources needed by a process. In some operating systems, a child process is restricted to a subset of its parent process’s resources. Explain, using an example, why an operating system might have this restriction.
FILE-SYSTEM INTERFACE:
F1.
F2. (4 marks)
Suppose an operating system is defined so that processes are organized in a tree of processes (called a process tree) such that all the descendants of a process are given resources (objects) and access rights by their ancestors only. Thus, a descendant can never have the ability to do anything that its ancestors cannot do. The root of the tree is the operating system, which has the ability to do anything. Assume the set of access rights was represented by an access matrix, A. A(x, y) defines the access rights of process x to object y. If x is a descendant of z, what is the relationship between A(x, y) and A(z, y) for an arbitrary object y?
F3. (4 marks)
Some systems automatically open a file when it is referenced for the first time, and close the file when the process that did the open terminates. This is referred to an implict opening/closing. Discuss the advantages and disadvantages of this scheme as compared to the more traditional one where the user has to open and close the file explicitly using open and close system calls.
F4. (4 marks)
Consider a system that supports 5000 users. Suppose that you want to allow 4990 of these users to be able to access on file.
(a) How would you specify this protection scheme in UNIX?
(b) Can you suggest another protection scheme that could be used more effectively for this purpose than the scheme provided by UNIX.
F5. (8 marks)
For each file or directory, an access-control list (or access list) specifies a list of user names (or groups of users) and the types of access allowed for each user. For each user or group of users, a user-control list (or capability list) specifies a list of files (or directories) and the types of access allowed to each file.
(a) Suppose we have 10 well-defined groups of users, where all users in a group should have the same privileges, and 1000 files organized in no particular fashion. Draw a diagram representing this situation with access lists, then draw a diagram representing this situation with capability lists. Which representation will allow faster checking of privileges for a particular (user, file) combination? Explain why.
(b) Suppose we have 1000 users, organized in no particular fashion, and 10 directories of files, where a user should have the same access rights to every file in a directory. Draw a diagram representing this situation with access lists, then draw a diagram representing this situation with capability lists. Which representation will allow faster checking of privileges for a particular (user, file) combination? Explain why.
SCHEDULING (SGG78, chapter 5; SGG6, chapter 6):
S1. (4 marks)
Explain the purpose of each of the long-term scheduler, medium-term scheduler, and short-term scheduler. (SGG78, chapter 3; SGG6, chapter 4).
S2. (6 marks)
Classify each of the following scheduling algorithms as preemptive or nonpreemptive:
(a) round robin,
(b) shortest job first -- as defined in lectures,
(c) shortest remaining time -- as defined in lectures,
(d) multi-level feedback queues,
(e) first come first served, and
(f) priority.
Explain why in each case.
S3. (18 marks)
Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:
|
ProcessID |
Arrival Time |
Burst Length |
Priority |
|
P1 |
0 |
8 |
0 |
|
P2 |
2 |
5 |
1 |
|
P3 |
4 |
1 |
0 |
|
P4 |
6 |
3 |
2 |
|
P5 |
8 |
2 |
1 |
Ignore the priorities for algorithms other than priority scheduling. For priority scheduling, assume that priority 0 is the highest priority. Also, if two processes have the same priority, choose the one that arrived first.
Consider the following scheduling algorithms:
(a) first come first served (FCFS),
(b) round robin (RR), with a quantum of 1 millisecond
(c) shortest job first (SJF) -- as defined in class,
(d) shortest remaining time (SRT) -- as defined in class,
(e) a nonpreemptive priority algorithm, based on the given priorities.
(f) a preemptive priority algorithm, based on the given priorities.
(g) feedback with multi-level queues (FB) algorithm, with a quantum of 1 millisecond at each of 3 queues.
For each of the above algorithms, do the following:
(i) draw a Gantt chart,
(ii) calculate the turnaround time for each process, which was referred to as the elapsed time (T) in lectures,
(iii) calculate the missed (or waiting) time (M) for each process.
Which of the algorithms gives the minimal average missed time (or waiting time)?
Hint for exam preparation: For each algorithm, determine the average missed time over all processes. Then find the one (or ones) with the minimal average missed time.
S4. (3 marks)
Give a formula that can be used to predict burst length:
e(t+1) = _____________________________
Assuming a default estimate of e(1) = 5, and actual burst lengths of
1 10
show the estimated burst lengths e(2) and e(3)
|
t |
1 |
2 |
3 |
|
a(t)
|
1 |
10 |
---- |
|
e(t)
|
5 |
|
|
(h) S5. Consider the Multi-Level Feedback (FB) scheduling algorithm with:
- three queues, Q0 with a quantum size of 2, Q1 with a quantum size of 2 and Q2 with a quantum size of 3. Q0, the top queue, is the highest priority queue.
- Queue Q2 is managed in a RR fashion.
- The processor continually removes a process from the front of the highest-priority non-empty queue and runs in for the quantum for that queue. A process is NOT interrupted by the arrival of a higher priority process.
- If the process from the top two queues does not complete in this quantum, it is moved to the next queue.
- If the process does complete in the quantum, the next process is scheduled immediately and it is given a full quantum.
- New arrivals are placed at the back of the highest-priority queue; this is done before dealing with a process whose quantum has expired.
Show the Gantt chart for the schedule (execution-over-time graph) for the following processes if the Multi-Level Feedback scheduling algorithm is used. Show the contents of each queue during each time-interval (e.g., the interval of time between time 0 and time 1, the interval of time between time1 and time2, etc.). These are the time intervals after a scheduling decision has been made while a process is running on the processor. Do not show the running process in any queue.
|
ProcessID |
Arrival Time |
Burst Time |
|
P1 |
0 |
3 |
|
P2 |
0 |
9 |
|
P3 |
2 |
3 |
|
P4 |
3 |
1 |
|
P5 |
6 |
5 |
|
P6 |
10 |
1 |
|
P7 |
17 |
4 |
GANTT CHART (running process):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
QUEUES:
Q0:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Q1.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Q2.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S6. (18 marks)
(a) Do the following for each algorithm:
(i) draw a Gantt chart,
(ii) calculate the turnaround time for each process,
(iii) calculate the missed (waiting) time for each process.
The algorithms are:
(i) FCFS, (ii) SJF, (iii) SRT, (iv) nonpreemptive priority, (v) preemptive priority, and (vi) round robin (with quantum = 1 millisecond).
|
ProcessID |
Burst Time (ms) |
Priority |
|
P1 |
3 |
3 |
|
P2 |
2 |
1 |
|
P3 |
9 |
2 |
|
P4 |
1 |
1 |
|
P5 |
4 |
3 |
Assume that priority 1 is the highest priority. Ignore the priority values except for the priority algorithm.
The processes are assumed to have arrived in the order p1, p2, p3, p4, p5, all at time 0.
Assume also that SJF and SRT use the burst times shown rather than estimating burst times. (In an implementation, they would have to estimate the times. We will assume for the purpose of this question that the estimates are available and 100% correct.)
(b) Which algorithm(s) has the shortest average waiting (missed) time?
(c) Which algorithms behave identically to other algorithms on this example? Explain why.
S7. (10 marks)
Draw a Gantt chart illustrating the execution of the following processes with the multilevel feedback queue algorithm and the following processes:
|
ProcessID |
Arrival Time |
Burst Time |
|
P1 |
0 |
2 |
|
P2 |
0 |
9 |
|
P3 |
2 |
3 |
|
P4 |
3 |
1 |
|
P5 |
6 |
5 |
|
P6 |
10 |
1 |
|
P7 |
17 |
4 |
Assume that there are 3 queues (Q0, Q1, Q2) and a quantum q0 = 1 (for queue Q0), q1 = 2 (for queue Q1), and q2 = 3 (for queue Q2). A process is given one quantum in queue Q0 and one quantum in queue Q1. Queue Q2 is managed in a round robin fashion. Show the contents of each queue during each time interval (e.g., the interval between time 0 and time 1, between time 1 and time 2, etc.). Once a process starts executing, it cannot be preempted until it terminates or finishes its current quantum. If a process terminates before the end of its quantum, scheduling is done immediately and the newly scheduled process is given a full quantum. Newly arriving processes are placed at the end of queue Q0 (the insertion is done before dealing with the process that finished its quantum at this time point and before any scheduling decision at that time point is made).
GANTT CHART (running process):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
QUEUES:
Q0:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Q1.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Q2.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S8. (4 marks)
Explain why disabling interrupts frequently could affect the system's clock. Also explain how such effects could be minimized.
S9. (4 marks)
Assume that an operating system uses multilevel feedback queue scheduling. It is observed that when process P356, which frequently disables interrupts, is run, interactive users complain about the computer being slow. Other large processes are not observed to cause the same problem as P356. Explain.
LABORATORY WORK AND UNIX SYSTEM CALLS:
L1. (10 marks)
Using the programming language of your choice, write a complete short program that uses the appropriate UNIX system call(s) to:
· create three (3) child processes,
· execute the programs prog1, prog2, and prog3 (assume these programs are stored in the /usr/bin/local directory),
· wait for all 3 processes to finish execution, and
· print a message indicating completion.
(Gray, chapters 1-3; hint for exam preparation: use fork, execl/execlp, wait/waitpid)
L2. (6 marks)
Using the programming language of your choice, write a complete short program that uses the appropriate UNIX system call(s) to:
· determine its own process id
· determine the process id of its parent process
· display this information in a message
(Gray, chapter 2; hint for exam preparation: use getpid, getppid)
L3. (6 marks)
L4. (6 marks)
Using the programming language of your choice, write a complete short program called changemode that uses the appropriate UNIX system call(s) to change the mode of a file. For example:
changemode 0755 myfile
should cause the mode of the file to be changed to the permissions corresponding to octal 0755. You do not have to check the command-line arguments, but use perror to report an error message if the user’s request is invalid.
(Gray, chapters 1-2; hint for exam preparation: use argv, chmod, perror)
L5. (6 marks)
Using the programming language of your choice, write a complete short program called sendsignal that uses the appropriate UNIX system call(s) to send a specific signal to a specific process. For example:
sendsignal 8 2340
should cause signal number 8 to be sent to process 2340. You do not have to check the command-line arguments, but use perror to report an error message if the user’s request is invalid.
(Gray, chapters 1-2, 4; hint for exam preparation: use argv, kill, perror)