Midterm Exam & Solutions

CS354 Spring 2000

1. (4 pts.) What is a real-time system, a hard real-time system, and a soft real-time system?

A real-time system is used when there is a rigid time requirement in the operation. For example, for medical equipment, traffic lights, computer systems for cars, etc. There are two types of real-time systems. A hard real-time systems deal with critical tasks that should be completed on time while soft real-time systems deal with critical tasks that get the highest priority until completion.

2. (4 pts.) What are the differences between kernel and user mode?

In kernel mode, the system has access to an extended set of instructions; it can modify the interrupt vector, and can modify any section of memory. In user mode, the system has access to only a restricted set of instructions, cannot modify the interrupt vector, and has access to a restricted range of memory.

3. (4 pts.) Why modern CPU's have kernel and user mode?

Modern CPU's have kernel and user mode because of reliability and security. Reliability because the user program can crash without crashing other programs. Security because different user processes are kept separate, and resources can be protected by unwanted users.

4. (4 pts.) Why system calls use software interrupts?

System calls use software interrupts because software interrupts allow switching from user to kernel mode. System calls is the way to access operating system services and need to run in kernel mode. In kernel mode, the system will have access to the interrupt vector and the memory it will need to perform its operations.


5. (4 pts.) What are the steps for servicing an interrupt? 

Steps for servicing an interrupt
a. interrupt
b. save registers, program counter, return address, etc.
c. go to interrupt vector and jump to address corresponding to that interrupt
d. execute driver
e. restore all registers and other memory saved in b.
f. return to place in code where interrupt was executed -> to return address

6. (4 pts.) How many program counters and sets of registers are stored in a single process table entry?

There is one program counter and one set of registers for each thread in the process.

7. (4 pts.) In which state processes are most of the time and in what kind of programs this is not true?

Processes are in the "waiting" state most of the time. The exception are numerical analysis programs and screen-savers that are CPU intensive and do not require to wait for input.

8. (4 pts.) What are the advantages and disadvantages of using threads vs. using processes?

The advantages of using threads are that process creation is more expensive than thread creation and context switch among threads are less expensive. The communication among threads are also very fast. The disadvantages of threads vs. processes are that with threads there is more chance for a deadlock and that multiple threads are less robust than multiple processes. If one thread crashes, the entire process and all the threads will have to exit.

9. (4 pts.) What factors have to be considered when choosing the length of a quantum time?

When choosing a quantum, you have to consider whether you want a short quantum or a long quantum. A short quantum produces a short response time, a high context switch overhead, is good for interactive programs, and produces longer total time for programs. A long quantum produces longer response time, lower context switch overhead, is good for batch programs, and produces shorter total time for programs. 

10. (4 pts.) What are the advantages and disadvantages of using spinlocks vs. disable/enable interrupts?

The advantages of using spinlock vs. disable/enable interrupts are that the CPU does not need to disable interrupts and that spinlocks can be done in user space. Disable interrupts is a privileged command done in the kernel. The disadvantage of spinlock include the CPU being consumed by spinning.

11. (6 pts.) Write down the code for spinlock() and spinunlock() and explain briefly how it works.

Int test_and_set ( int *v )
{
int oldval = *v;
*v = 1;
return oldval;
}

void spinlock ( int *lock )
{
while (test_and_set(lock));
}

void spinunlock ( int *lock )
{
*lock = 0;
}

This works because lock is initially set to 0. When the first process calls spinlock, test_and_set will set lock to 1 and cause the while loop to terminate. Then, when another process calls spinlock, the lock is already taken and the new process will continue "spinning" in the while loop until the first process calls spinunlock which will reset lock to 0.

12. (6 pts.) Assume that a computer executes the following jobs: 

 

Process
Time needed for completion (ms)
P1
40
P2
5
P3
30
Compute the average waiting time if the following scheduling algorithms are used: 

FCFS:0 + 40 + 45 / 3 = 28.3 ms

SJF:0 + 5 + 35 / 3 = 13.3 ms

Round Robin (Quantum=10ms): 0 + 10 + 15 / 3 = 8.3 ms

13. (6 pts.) Mark the "C" expressions that are equivalent to a[i]. The type of a[i] is not necessarily char.
 
Expression
Mark
a + I
Not equivalent
*(a + i)
equivalent
*(a[0] + i)
Not equivalent
*(&a[0] + i)
equivalent
*(&a[i])
equivalent
&a[i]
Not equivalent
*((char *) &a[0] + i )
Not equivalent
*((char *)&a[0] + i * sizeof(a[0]))
equivalent


 
14. (6 pts.) Write a procedure arrayMapper() , that calls the function func in all the n elements of the array a. The size of each element in the array a is elementSize. The address of the array element is passed to func every time func is called.
Note: The code in red color is the solution. The rest was provided with the problem.

typedef void (*FuncPtr)(void * arg);

void arrayMapper( void * a, FuncPtr func, int n, int elementSize)
{
for ( int h = 0; h < n ; h++ )
{
(*func) ( (void*)( (char *) a + (h * elementSize)) );
}

}


 
15. (6 pts.) The following code implements a concurrent stack. The push() and pop() calls can be called simultaneously by different threads. The push() call blocks until space is available in the stack. The pop() call blocks until data is available in the stack. Insert the necessary semaphore calls to implement this behavior.  Remember to initialize the semaphores in main().
Note: The code in red color is the solution. The rest was provided with the problem.

 

int stackPointer;
int stack [ MaxStack ];
sema_t full, empty;
mutex_t mutex;

void push (int a)
{
sema_wait (&empty);
mutex_lock (&mutex);

stack[ stackPointer ] = a;
stackPointer++;

mutex_unlock (&mutex);
sema_post (&full);
}

int pop()
{
sema_wait (&full);
mutex_lock (&mutex);

stackPointer--;
int tmp = stack[ stackPointer ];

mutex_unlock (&mutex);
sema_post (&empty);

return tmp;
}

main()
{
sema_init ( full, 0 );
sema_init ( empty, MaxStack );
} 


 
16. (6 pts.) The following program consists of two threads: a client thread and a server thread. First the client thread reads the numbers a and b, wakes up the server thread, and then blocks until c is ready. When the server thread wakes up, it adds a and b, assigns the result to c, wakes up the client thread, and then goes to sleep. When the client wakes up, prints the value of c and starts all over again. Complete the following code and insert semaphore calls where necessary.  Remember to initialize the semaphores in main().
Note: The code in red color is the solution. The rest was provided with the problem.

client_thread()
{
while(1) {
a = input();
b = input();
sema_post(&input);
sema_wait(&print);
print c;
}
}
server_thread()
{
while(1) {
sema_wait(&input);
c = a + b;
sema_post(&print);
}
}

main( )
{
sema_init( input, 0 );
sema_init( print, 0 );
}


 
17. (6 pts.) Complete the procedure redirectStdin( fileName ) to redirect the standard input from file fileName. The procedure will return -1 if any error occurrs or 0 if it succeeds. Look at main() to see how redirectStdin( ) is used. NOTE: ERROR CHECKING IS IMPORTANT. Also notice that the procedure is called redirectStdin and not redirectStdout.
Note: The code in red color is the solution. The rest was provided with the problem.

int redirectStdin ( char *filename)
{
int fd = open (filename, O_RDONLY, 0666);
if ( fd < 0 )
{
return -1;
}

int err = dup2 ( fd, 0 );
close( fd );

if (err)
{
return -1;
}

return 0;
}

main()
{
if (redirectStdin ("myfile") < 0 ) {
perror ( "redirectStdout" );
exit (-1);
}

int n = scanf ( "%d", &j );
if ( n == 1 ) {
printf ( "Read j = %d from myfile\n");
}
else {
printf ( "Error reading j from myfile\n");
}
}


 
18. (6 pts.) Complete the procedure redirectStdinFromPipe( command, arg1) that creates a pipe, redirects stdin from the pipe, forks a child process that redirects its output to the pipe, and then executes a command with argument arg1. redirectStdinFromPipe() will return -1 if an error occurrs or 0 if it succeeds.  Look at main() to see how redirectStdinFromPipe( ) is used. NOTE: ERROR CHECKING IS IMPORTANT. Also see that the procedure is called redirectStdinFromPipe and not redirectStdoutToPipe.
Note: The code in red color is the solution. The rest was provided with the problem.

int redirectStdinFromPipe ( char *command, char *arg1)
{
int fdpipe[2];
pipe(fdpipe);
int pid = fork();
if (pid < 0 ) {
close(fdpipe[0]);
close(fdpipe[1]);
return -1;
}

if ( pid == 0 ) {
dup2(fdpipe[0],1);// redirects output to the
// pipe
close(fdpipe[0]);
close(fdpipe[1]);

// execute commands
char *args[3];
args[0] = command;
args[1] = arg1;
args[2] = 0;
execvp(command, args);
return -1;
}

// redirects stdin from the pipe

dup2(fdpipe[1],0);
close(fdpipe[0]);
close(fdpipe[1]);

return 0;
}

int main()
{
if (redirectStdinFromPipe ( "ls", "/") {
perror( "redirectStdinFromPipe");
exit(-1);
}

const int bufferSize = 1024;
char buffer[bufferSize];
read ( 1, buffer, bufferSize );
}


 
19. (6 pts.) Write the instructions necessary to eliminate zombie processes. Your code should print "Child exited" when a child exits.
Note: The code in red color is the solution. The rest was provided with the problem.

void zombie_process(int x)
{
int killed_process;
killed_process = wait3(NULL, 0, NULL);
if (BACKGROUND == 1)
{
printf("%d Child Exited...\n", killed_process);
BACKGROUND = 0;
}
}

struct sigaction z;

int main()
{
 sigignore(SIGINT);
z.sa_handler = zombie_process;
sigemtypset(&z.sa_mask);
z.sa_flags = SA_RESTART;
sigaction(SIGCHLD, &z, NULL);
}


 
20. (6 pts.) Write the code for the function strcpy().
Note: The code in red color is the solution. The rest was provided with the problem.

char *strcpy ( char *dest, char *src )
{
char *tmp = dest;

while (*src)
{
*dest = *src;
dest++;
src++;
}

*dest = 0;

return(tmp);

}