Review O: Principles of operating systems
printable version
O1: [1] // O2: [1] [2] [3] [4] [5] [6] [7] [8] [9] // O3: [1] [2] [3] // O4: [1] [2] [3] [4] [5] [6] // O5: [1] [2] [3] [4] [5]
Problem O1.1
Name at least two generic purposes of an operating system.
There were three that we examined, but potentially there are others too.
- Abstract complex resources.
- Provide hardware compatibility.
- Protect the system from untrustworthy programs.
Problem O2.1
Because the disk takes quite some time to respond, the operating system cannot simply wait until the disk responds to any requests it makes of the disk. Instead, the operating system will send the request and proceed to other work. Nonetheless, when the disk's response is ready, the operating system must be able to respond quickly. How is this normally implemented?
The CPU is designed so that an electrical signal can be passed into it signaling a hardware interrupt. When the CPU receives a signal, it suspends the work on the current process and enters the OS interrupt handler so the OS can deal with the disk response promptly.
Problem O2.2
A CPU will interrupt the current program to enter an interrupt handler for three categories of reasons: hardware interrupts, software interrupts, and CPU exceptions. Describe two situations that lead to CPU exceptions.
The CPU reaches a division instruction that should be executed, and the divisor turns out to be 0.
The CPU reaches an instruction to be executed, but the value doesn't conform to any known machine language instruction.
While the CPU is in user mode, it reaches an instruction that asks to do something that can only be done in supervisor mode.
The CPU reaches an instruction accessing a memory address that is beyond the bounds of accessible memory.
The CPU reaches an instruction that accesses a virtual memory address, but the page containing that address is not in memory according to the page table.
Problem O2.3
Older operating systems provided a library of subroutines that a
program could call in order to interact with devices, using
instructions akin to the ARM's BL instruction. Why do
modern operating systems eschew this simple technique in favor
of the more complex system where system calls are made via
software interrupts? Explain your answer.
The primary reason is that calling a subroutine maintains the same
privileges; thus, with this technique, the operating system
would have to work at the same privilege level as regular
processes, and so regular processes would need access to all
facets of the system. This allows software (both malicious
software such as viruses, as well as trusted
programs that
simply have bugs) to wreak havoc on the system. In modern
systems, an interrupt provides a way to switch from the user
mode
of regular processes into the supervisor mode
used by the
operating system.
Problem O2.4
We saw that when asked to execute a program, the OS first configures the CPU to execute instructions in user mode, so that the CPU disallows communication with devices. The CPU cannot include an instruction simply to switch into supervisor mode, since a malicious program could use such an instruction to gain unfettered access. How does the CPU designer facilitate allowing programs to initiate device communication while guaranteeing that only OS code executes while in supervisor mode?
While in user mode, the only way the CPU will switch to supervisor mode
is in response to an interrupt. The CPU includes an instruction
(SWI) whereby a program can initiate an interrupt.
When the interrupt occurs, the CPU transfers control to the instruction
at memory address 0x8.
The operating system should have placed its own code at this
address and arranged memory permissions so that the code executing
in user mode cannot modify it this code.
Problem O2.5
Name two ways in which the ARM's CPSR (Current Program Status
Register) is used.
It contains the four flags that are set by the arithmetic instructions like
CMPorSUBS.It contains an indication of what mode the CPU is currently executing in (user versus supervisor mode).
It contains the interrupt flag, indicating whether the CPU should enter the interrupt handler for any hardware interrupts that are received.
Problem O2.6
Because other users' information is stored on the disk, a multiuser computer system cannot allow a process to access the disk directly. Yet programs often need to read from the disk. Explain how a computer system can allow this without compromising security.
The CPU implements two modes, supervisor mode and user mode, and prevents a process from accessing the disk directly while in user mode. The operating system enters user mode every time it exits into a user program, so that the user program runs in user mode and cannot access the disk. But the user program can initiate an interrupt using a CPU instruction, whereupon the CPU will switch into supervisor mode as part of the interrupt process and jump into the interrupt handler, implemented by the operating system. The operating system's handler, running in supervisor mode, can access the disk on the process's behalf (after it verifies that the request is legitimate) before returning back into the user program in user mode.
Problem O2.7
Explain the difference between user mode and supervisor mode, and explain why modern CPUs include the capability to run in either of these modes.
When in user mode, the CPU places many restrictions on its behavior (particularly restricting access to memory and to external devices); these restrictions do not apply when the CPU is executing in supervisor mode. Having multiple modes allows the operating system to maintain control over the computer, so that buggy or malevolent user software cannot damage its resources.
Problem O2.8
For each of the following CPU instructions, which of the following applies?
A. The instruction should be permitted whether the CPU is running in user mode or supervisor mode. B. The instruction should be allowed only when the CPU is running in supervisor mode.
| a. | Switch between modes (supervisor to user, or user to supervisor). |
| b. | Send a software-initiated interrupt to the CPU. |
| c. | Disable interrupts by clearing the interrupt flag. |
| d. | Send information to an I/O device. |
| e. | Call a subroutine. |
| a. | B. |
| b. | A. |
| c. | B. |
| d. | B. |
| e. | A. |
Problem O2.9
What distinguishes system calls (such as write)
from library functions (such as printf)? Given
that they are less efficient, why do programmers typically
prefer library functions?
Code for system calls are included in the operating system, while code for library functions are included with the running program. Thus, a system call's code runs in supervisor (unprotected) mode, while a library function's code runs in user mode. A program enters a system call by initiating a software interrupt, while a program enters a library function by calling a subroutine included with the program.
Programmers typically prefer library functions because
they are typically less platform-dependent (a program written
under Linux can more easily be ported to Windows) and provide more
convenient functionality (the OS system calls typically
provide bare minimum convenience — like
printf providing so many formatting options in contrast
to no formatting at al with write, its closest
system-call relative under Linux.
Problem O3.1
Consider the read system call in Unix/Linux.
a. How is the first parameter, an int, used?
b. How is the second parameter, a char*, used?
c. How is the third parameter, an int, used?
d. What does the return value, an int, represent?
a. The first parameter is a file descriptor, an integer that the operating system has allocated as corresponding to an opened file.
b. The second parameter is the pointer to the beginning of an array of characters where the OS may place the bytes read from the file.
c. The third parameter identifies how long this array is.
d. The system call returns the number of bytes it successfully read from the file and copied into the array; if it has reached the end of the file, it returns 0; and if there is an error, it returns −1.
Problem O3.2
Complete the following Linux program to count the number of bytes in
the file using no functions or system calls except
for the read system call.
int main() {
int fd;
int bytes_found;
char data[120];
fd = open("src.txt", O_RDONLY);
close(fd);
printf("%d\n", bytes_found);
return 0;
}
int main() {
int fd;
int bytes_found;
char data[120];
int nbytes; // added
bytes_found = 0; // added
fd = open("src.txt", O_RDONLY);
nbytes = read(fd, data, 120); // added
while (nbytes > 0) { // added
bytes_found += nbytes; // added
nbytes = read(fd, data, 120); // added
} // added
close(fd);
printf("%d\n", bytes_found);
return 0;
}
Problem O3.3
Explain what a Unix shell does so that the output of a process is redirected into a file instead of to the screen, as it is told to do in the following shell command.
unix% wc words > count
Since the wc command writes to file descriptor 1, the shell must insure that file descriptor 1 for the process running wc will refer to the count file. To accomplish this, it closes file descriptor 1 in the child process it creates for running wc and then designates descriptor 1 to refer to the count file instead. Thus, when wc runs and writes to file descriptor 1, the output will go into the file instead of to the screen.
Problem O4.1
List three categories of information found in an entry of the process table.
the process ID
the process's state (running, ready, blocked)
the last values observed in the process's registers
the last observed value of the process's program counter
information showing which memory is being occupied by the process
the process's file descriptor table
a pointer to the next ready process or the next process blocked on the same device
Problem O4.2
Explain why the operating system would move a process in the Running state to the Blocked state instead.
When a running process requests interaction with a device that cannot immediately respond, the operating system moves it into the Blocked state so that it will not occupy CPU time while the device is working.
Problem O4.3
Describe a situation where the operating system would move a process from the Blocked state to the Ready state.
A process is typically in the Blocked state when it is waiting for some response from a I/O device (such as the keyboard or hard drive). The operating system would move it into the Ready state when it has received a response for the I/O device for the blocked process.
Problem O4.4
In the following diagram illustrating the various states a process can be in, draw arrows connecting each pair of states that a preemptive operating system may move a process between. Label each arrow with a brief description of a situation where the operating system would move the process as indicated.
|
|
Running to Ready: process's time slice has expired. Ready to Running: CPU is idle, ready to work. Running to Blocked: processes makes request forcing communication with I/O device Blocked to Ready: I/O device has completed action necessitated by process |
Problem O4.5
As the OS executes, it sometimes decides that the CPU should resume its execution of a previously running process. List steps that the OS must perform before branching into the selected process's code.
- The OS restores the registers to the values saved in the selected process's entry of the process table.
- The OS switches into user mode.
- The OS restores the program counter to its last-observed value.
Problem O4.6
Because the CPU can run only one thread of execution at once, when a user program is running, the operating system cannot be. How, then, can the OS manage to preempt a running program that runs for a long period of time and attempts to run beyond its time slice?
Before beginning to run the user program, the OS schedules the clock device to send an interrupt. When this interrupt occurs, the CPU automatically jumps into the exception handler for the clock's interrupt, which would be code existing within the OS. The OS's handler can then preempt the process and schedule another to run.
Problem O5.1
Suppose we were to run the following program below.
#include <stdio.h>
int i = 1;
int main() {
while(i < 4 && fork() != 0) {
i++;
}
printf("%d ", i);
exit(0);
}
Which of the following outputs might occur?
| a. | 1 1 2 4 |
| b. | 1 2 3 |
| c. | 1 2 3 4 |
| d. | 1 2 4 |
| e. | 3 1 2 4 |
| f. | 4 |
| g. | 4 3 2 1 |
| h. | 4 4 4 4 |
The possible outputs are c., e., and g..
Problem O5.2
Suppose we were to run the following program.
#include <stdio.h>
int i = 0;
int arr[4] = { 2, 3, 5, 7 };
int main() {
while(i < 2 && fork() != 0) i++;
arr[i] = arr[i] + 1;
printf("%d ", arr[i + 1]);
exit(0);
}
Which of the following outputs might occur?
| a. | 2 3 5 | d. | 3 6 7 | g. | 7 4 6 | ||
| b. | 2 3 5 7 | e. | 4 6 7 | h. | 7 7 7 | ||
| c. | 3 5 7 | f. | 7 5 3 | i. | 7 7 7 7 |
c. and f.
Problem O5.3
Suppose we were to execute the following Linux program.
int arr[4] = { 2, 3, 5 };
int main() {
int i = 0;
while (i < 2 && fork() != 0) {
i++;
arr[i] = arr[i] + 1;
}
printf("%d ", arr[i]);
return 0;
}
Which of the following are possible outputs of this program?
| a. | 2 3 5 | d. | 3 4 6 | g. | 6 3 4 | ||
| b. | 2 4 6 | e. | 5 3 2 | h. | 6 4 2 | ||
| c. | 3 4 6 | f. | 5 5 5 | i. | 6 6 6 |
(b.) and (h.) are the possible outputs.
Problem O5.4
What might be displayed by the below program?
#include <stdio.h>
int main() {
int i = 1;
while(i < 3) {
fork();
i++;
}
printf("%d ", i);
exit(0);
}
3 3 3 3
Problem O5.5
What does Linux do when requested to perform the execvp
(or execve) system call?
It replaces the currently running process with the program specified in
the parameters to execvp.
The new process keeps the state of the replaced process, but its memory
changes to the memory image required by the program, and execution
enters the started program.
Execution will not return to the program calling execvp unless
an error prevents the OS from executing the request.