Midterm Exam

CS354 Fall 1999

1. (6 pts.) Assume the following program. Write the memory section in the program that corresponds to each of the following memory addresses:

Memory Address Memory Section

&a BSS

&b DATA

&c STACK

&d STACK

&e STACK

e HEAP

&main TEXT

&printf SHARED LIBARY or TEXT

int a[300];
int b = 25;
void foo()
{
    int d;
}
int
main()(
    int c;
    int * e = new int;
}

2. (4 pts.) Describe the steps of an interrupt routine

   1. Save registers and return address
   2. Jump to the address in the interrupt vector that corresponds to this interrupt
   3. Service the interrupt
   4. Retry the offending instruction if necessary
   5. Restore the registers and return to the saved return address.

3. (4 pts.) What is protected and unprotected CPU mode?

In the CPU protected mode (kernel mode) the CPU is able to execute an extended set of instructions, such as writing to devices. In this mode the CPU is also able to write to any address in physical memory and to change the interrupt vector.
In unprotected mode (user mode), the CPU is able to execute a reduced set of instructions and it is only allowed to acces a restricted range of memory.

4. (4 pts.) Which CPU mode do interrupts run in and why?

Interrupts run in protected mode (kernel mode) to be able to access device registers and kernel memory.

5. (4 pts.) Why do system calls use software interrupts instead of procedure calls?

System calls is the way to access operating system services and need to run in kernel mode. Software interrupts allow to switch from user to kernel mode.

6. (4 pts.) Why do modern operating systems use preemptive scheduling?

A non-preemptive operating system has the danger of being hang if one of the applications never gives up the processor. Modern operating systems have preemptive scheduling to prevent this problem, giving a fair share of time to each ready process.

7. (4 pts.) How many processes can be in running state at any given time?

One for each CPU in the system.

8. (4 pts.) Describe how a small quantum affects the response time and the total execution time.

The shorter the quantum, the faster the response time. But also the shorter the quantum the longer the execution time due to excesive context switching.

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

Process	Estimated Time (ms)
P1	80
P2	40
P3	20

Compute the average waiting time if the following scheduling algorithms are used:

FCFS:

(80+120)/3 = 200/3 = 66.67ms

SJF:

(20 + 60)/3 = 80/3 = 26.67ms

Round Robin (Quantum=10ms):

(10 + 20)/3 = 10ms

10. (4 pts.) What are the differences between a thread and a process.

A thread is a path of execution. A process can have multiple threads but not vice versa. A process has at least one thread. Multiple threads may share the same address space, but each process will have its own independent address space.

11. (4 pts.) What are the differences between a user-level thread and a kernel thread.

The context switch between two user level threads is performed entirely in user space. If one use-level thread has to wait inside the kernel, other user-level threads that run on top of the same kernel thread will block as well. Multiple user level threads can run on top of one kernel-level thread but not vice versa. The management of kernel-level threads is done by the kernel. The management of user-level threads is done by the user-level thread library.

12. (7 pts.) The following multi-threaded circular queue implementation has a serious flaw. Explain what is the flaw and the repercussion.

      const int MAXQUEUE = 10;
      int queue[ MAXQUEUE ];
      int tail = 0;
      int head = 0;
      sem_t empty, full;
      mutex_t mutex;

      void enqueue( int a )
      {
          lock( mutex );
          wait( full );
          queue[tail] = a;
          tail = (tail + 1)%MAXQUEUE;
          post( empty );
          unlock( mutex );
      }

      int dequeue()
      {
          lock( mutex );
          wait(empty)
          tmp = queue[ head ];
          head = (head + 1)% MAXQUEUE;
          post( full );
          unlock(mutex);
          return tmp;
      }

      main()
      {
          init_sem( empty, 0 );
          init_sem( full, MAXQUEUE);
          init_mutex( mutex );
          // Run producer consumer threads using queue calls
     }

The flaw is that lock() is called before wait() in both enqueue and dequeue. The repercusion is that if the queue is full and enqueue() is called, wait(full) will block while holding the mutex lock. This will cause that any other thread that calls dequeue() will block when calling lock() and the queue will remain full, causing the threads to deadlock.
The same happens in the queue is empty and dequeue() is called.

13. (15 pts.) Complete the following procedures. sendBroadcast() sends a message to N threads that will call receiveBroadcast(). sendBroadcast() will block until the N threads have called receiveBroadcast(). receiveBroadcast() will block until a thread has called sendBroadcast() and the variable theMessage has a valid value.

const int N = 5;
int theMessage;

void sendBroadcast( int msg )
{

theMessage = msg;

for ( int i = 0; i < N; i++ ) signal( sem-wakeup-receiver );

for (int i = 0; i < N; i++) wait( sem-wait-until-all-received );
}

int receiveBroadcast()
{

wait( sem-wakeup-receiver )

int tmp = theMessage;

signal( sem-wait-until-all-received );

return tmp;
}

      main()
      {
          // Initialization goes here
                    init_sem( &sem-wakeup-receiver , 0 );
                    init_sem( &sem-wait-until-all-received , 0 );

}

14. (15 pts.) Complete the procedure redirectStdout( fileName ) to redirect the standard output to a file fileName. The procedure will return -1 if any error occurrs or 0 if it succeeds. Look at main() to see how redirectStdout( ) is used. NOTE: ERROR CHECKING IS IMPORTANT.

int redirectStdout( char * fileName )
{
int fd = open( filenam, O_CREATE | O_RDWR|O_TRUNC, 0644 );
if ( fd < 0 ) return -1;

// Redirect standard out to fle
int err = dup2( fd, 1);

// We don't need fd anymore
close( fd );

if ( err ) return -1;

return 0;
}

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

// "Hello world" will be written to "myfile"
printf("Hello world\n ");
}

15. (15 pts.) Complete the procedure redirectStdoutToPipe( command, arg1) that will 1.redirect the standard output to a pipe. 2. fork a process that will execute a command with argument arg1 that will read the input from the pipe. redirectStdoutToPipe() will return -1 if an error occurrs or 0 if it succeeds. Look at main() to see how redirectStdoutToPipe( ) is used. NOTE: ERROR CHECKING IS IMPORTANT.

int
redirectStdoutToPipe( char * command, char * arg1)
{
int fdpipe[2];

     // Create pipe
     int err = pipe( fdpipe);
     if ( err < 0 ) return -1;

//Create child process
int pid = fork();

     if ( pid < 0 ) {
        // If error creating child
        close (fdpipe[0]);
        close (fdpipe[1]);
        return -1;
     }

if ( pid == 0 ) {
// In the child

// Redirect the standard input to come from pipe
dup2( fdpipe[1], 0);

        // Close file descriptors
        close( fdpipe[ 0 ]);
        close( fdpipe[ 1 ]);

        //Execute command
        char * args[ 3 ];
        args[ 0 ] = command;
        args[ 1 ] = arg1;
        args[ 2 ] = 0;
        execvp( command, args );

       // If returns, something went wrong
        exit( -1 );
    }

     // This is the parent
    // Redirect the output to the pipe
    dup2( fdpipe[ 0 ], 1);

    // Close pipe
    close( fdpipe[0]);
    close(fdpipe[1]);

return 0;
}

int
main()
{
    // "hello world" is piped to the command "lpr -PMuir"
    if ( redirectStdoutToPipe( "lpr", "-Pmuir" ) {
      perror("redirectStdoutToPipe");
      exit(-1);
    }

printf("Hello world\n");
}

Memory Address	Memory Section
&a	BSS
&b	DATA
&c	STACK
&d	STACK
&e	STACK
e	HEAP
&main	TEXT
&printf	SHARED LIBARY or TEXT