CS372: Solutions for Homework 1

Problem 1:

Explain the steps that an operating system goes through when the CPU receives an interrupt.

First, the hardware switches the machine to supervisor mode and causes control to transfer to a routine at a pre-specified
address. The operating system has already loaded that address with a pointer to a function that handles the interrupt. The
function starts by saving all registers, possibly setting the allowed interrupts to a level that guarantees correct execution of the
operating system, and then executes the code to serve the interrupt. When the operating system is done, it restores the
registers again and calls the "reti" to return to the user program that was running when the interrupt occurred. If there is no
runnable program, the operating system jumps to the idle loop and waits for an interrupt. Finally, if the interrupt occurred
while the operating system was running, then the OS simply restores the registers and jumps to the instruction following the
one at which the interrupt occurred.

Problem 2:

Define three styles of switching from user mode to supervisor mode.

Interrupts, when a device sends an interrupt to the CPU.
When a program executes a system call, which is usually implemented by a trap instruction.
When a program performs an operation that causes a hardware exception, such as divide by zero, illegal memory access or execution of an illegal opcode.

Problem 3

A typical hardware architecture provides an instruction called "return from interrupt", and abbreviated by something like "reti". This instruction switches the mode of operation from supervisor mode to user mode. This instruction is usually only available while the machine is running in supervisor mode.

Explain where in the operating system this instruction would be used.
What happens if an application program executes this instruction?

The operating system calls "reti" whenever it wants to give control to a user program. This happens at the end of a contextswitch, or when an interrupt service routine is finished.
Since the "reti" instruction is usually a privileged instruction, an application program trying to execute it will cause a hardware exception, because it is illegal for user programs to execute privileged opcodes.

Problem 4

System Calls vs. Procedure Calls: How much more expensive is a system call than a procedure call? Write a simple test program to compare the cost of a simple procedure call to a simple system call ("getpid()" is a good candidate on UNIX; see the man page.) (Note: be careful to prevent the optimizing compiler from "optimizing out" your procedure calls. Do not compile with optimization on.)

Run your experiment on two different hardware architectures and report the results.
Explain the difference (if any) between the time required by your simple procedure call and simple system call by discussing what work each call must do (be specific). [Note: Do not provide the source code for your program, just the results].

Hint: You should use system calls such as gethrtime() or gettimeofday() for time measurements. Design your code such that the measurement overhead is negligible. Also, be aware that timer values in some systems have limited resolution (e.g., millisecond resolution).

Solution : A system call is expected to be significantly more expensive than a procedure call (provided that both perform very little actual computation). A system call involves the following actions, which do not occur during a simple procedure call, and thus entails a high overhead:

A context switch
A trap to a specific location in the interrupt vector
Control passes to a service routine, which runs in 'monitor' mode
The monitor determines what system call has occurred
Monitor verifies that the parameters passed are correct and legal

For your experiment, you should measure the total time for a large number of system/function calls, and then find the average time per call in order to overcome the course resolution of your timing functions. For example, here's a sample code for measuring the time taken for a simple system call and a simple function call:

#include <sys/time.h>
#include <unistd.h>
#include <assert.h>

int foo(){
return(10);
}

long nanosec(struct timeval t){ /* Calculate nanoseconds in a timeval structure */
return((t.tv_sec*1000000+t.tv_usec)*1000);
}

main(){
int i,j,res;
long N_iterations=1000000; /* A million iterations */
float avgTimeSysCall, avgTimeFuncCall;
struct timeval t1, t2;

/* Find average time for System call */
res=gettimeofday(&t1,NULL); assert(res==0);
for (i=0;i<N_iterations; i++){
j=getpid();
}
res=gettimeofday(&t2,NULL); assert(res==0);
avgTimeSysCall = (nanosec(t2) - nanosec(t1))/(N_iterations*1.0);

/* Find average time for Function call */
res=gettimeofday(&t1,NULL); assert(res==0);
for (i=0;i<N_iterations; i++){
j=foo();
}
res=gettimeofday(&t2,NULL); assert(res==0);
avgTimeFuncCall = (nanosec(t2) - nanosec(t1))/(N_iterations*1.0);

printf("Average time for System call getpid : %f\n",avgTimeSysCall);
printf("Average time for Function call : %f\n",avgTimeFuncCall);
}

Sample output on a linux machine :

> gcc -O0 testtime.c -o testtime
> ./testtime
Average time for System call getpid : 394.778015
Average time for Function call : 15.080000

Problem 5

When an operating system receives a system call from a program, a switch to the operating system code occurs with the help of the hardware. In such a switch, the hardware sets the mode of operation to supervisor mode, calls the operating system trap handler at a location specified by the operating system, and allows the operating system to return back to user mode after it finishes its trap handling. Now, consider the stack on which the operating system must run when it receives the system call. Should this be a different stack from the one that the application uses, or could it use the same stack as the application program? Assume that the application program is blocked while the system call runs.

Most compilers set the stack pointer to be at the beginning of the stack area when a function is called. Thus, automatic
variables are found underneath the location to which the stack pointer is pointing to (except for the HP PA-RISC, in which
the stack grows upward). Thus,

When an interrupt occurs, the kernel has no idea as to how many automatic variables the user program has allocated on the stack Therefore, it cannot just set the stack pointer past the current call frame of the use program, because it does not know where are the call frame limits. As such, the kernel must use a different stack to execute the interrupt handling routine.
On a multiprocessor, executing on the user stack allows another active user thread (on a different processor) to modify the stack and forcing the kernel to fail (maliciously, or unintentionally).
If the current stack is allocated on the user program's heap (such as in user-level thread packages), then the kernel code can cause a stack overflow and start destroying data in the user's address space.