NAME:_____Answer Sheet__________________________

 

Answer all questions. (There are a total of 122 possible points.)

 

This is a closed-book exam. Use separate paper for your answers, as needed. If you have a problem understanding a question please either (1) raise your hand to ask me for clarification, or (2) write a note pointing out how you interpreted the question, and then answer the question according to your interpretation.

 

Budget your time accordingly! I strongly recommend that you read through the entire exam before starting.

 

TRUE/FALSE (2 points each; 20 total)

 

__T__ (AM) A rendezvous can be between any number of processes.

 

__T__ (PM) Signaling is always between exactly two processes.

 

__F__ (AM) The operating system switches processes by switching process Ids.

 

__F__ (PM) Processes all share the system stack when they are in user mode.

 

__F__ (AM) SOS always uses the disk interrupt handler when reading the disk drive.

 

__F__ (PM) The disk interrupt handler is always called when disk I/O is performed.

 

__T__ (AM) Messages are buffered in SOS so that they can be sent before received.

 

__F__ (PM) Messages in SOS are buffered so they can be received before being sent.

 

__F__ (AM) A shell converts all user input into system calls.

 

__F__ (PM) SOS uses the UNIX fork()/execv() method of process creation.

 

__T__ (AM) A process has at least one thread.

 

__T__ (PM) Threads permit asynchronous I/O within a process.

 

__T__ (AM) The Java Vector class implements an array of objects that grows in size as necessary.

 

__F__ (PM) JavaSOS permits the loading and execution of process binaries from disk.

 

__F__ (AM) Enabling disk interrupts in a SOS CreateProcess() system call is easier to handle than disabling disk interrupts.

__F__ (PM) The overhead of executing a system call is less than the overhead of a function call.

 

__T__ (AM) The Producer-Consumer IPC pattern is a variant of signaling.

 

__F__ (PM) A race condition is won by the first process performing the update on the shared resource.

__F__ (AM) Race conditions can be safely ignored.

 

__T__ (PM) A sequence of actions that must be done one at a time is called a critical section.

 

Short Answer (5 points each; 25 total)

 

  1. (AM) Name the four types of interrupts on the CRA-1. System call, timer, disk and program error.

 

  1. (PM) Name four types of IPC patterns. Any four of: mutual exclusion, signaling, rendezvous, producer/consumer, client-server, multiple servers and clients, database access and update.

    2.  

  2. (AM ) Discuss what is too simplistic about the disk I/O primitives in SOS. It assumes that the disk drive never fails (reads and writes always work); a real operating system must handle media failures.

 

  1. (PM) Discuss what is too simplistic in the Program Error interrupt handler for SOS. It doesn’t indicate the type of error nor where the error might have occurred within the program’s execution (such as is done with UNIX’es core file).

    2.  

  2. (AM) Discuss the difference between the command sequences "ls –l > ls.out ; sort < ls.out" and "ls –l | sort". The first one is an example of I/O redirection. The first command sends the output of the "ls" command to a file named "ls.out"; the second redirects the standard input of the "sort" command from the file "ls.out". The second one avoids the use of an intermediate file by directly piping the standard output of the "ls" command to the "sort" command. The second one uses less resources (no intermediate disk file and both processes are started together, increasing potential execution overlap and decreasing overall runtime).

    3.  

    3. (PM) Explain the relationship between pipes and standard input/standard output. A pipe is a natural structure for connecting the standard output of one program to the standard input of another. A shell, such as any UNIX shell, will automatically create a pipe based on the presence of a metacharacter (such as the "|" symbol) and connect the standard output of the first process to the standard input of the second.

     

  3. (AM) Distinguish between the UNIX wait() system call and the SOS/JavaSOS Wait() system call. The UNIX wait() system call will unblock whenever ANY child of the parent executes an exit() system call; the SOS/JavaSOS Wait() system call will only unblock the parent when a particular child executes a SOS/JavaSOS Exit().

    4. 4. (PM) Name three fields you would expect the stat() call to return. Any three of the following: file owner, file permissions, file creation date, file last modification date, file last access (read) date, file length.

     

  4. (AM) What JavaSOS data structures does the DestroyMessageQueueSystemCall modify? It modifies the SOSProcessManager process descriptors (SIM.sosData.pd[]), the message queue allocated array (SIM.sosData.message_queue_allocated[]), the message queue array (SIM.sosData.message_queue[]), the message wait queue (SIM.sosData.wait_queue[]) and the message buffer area (SIM.MessageBufferArea). Note that the actual data structure names are not required but at least the data structure name or description of the data structure is required.

 

5. (PM) On the CRA-1 how is the rti instruction used? The rti instruction (return from interrupt) is used to return control back to the point prior to an interrupt occurring. It is typically the last instruction in an interrupt handler.

 

Definitions (4 points each; 32 total) - Define the following terms.

 

  1. (AM) Non-preemptive scheduling – process scheduling where a process once in the run state will not be interrupted (preempted) by a timer interrupt. In effect, the program has control over the CPU since it will not be involuntarily preempted.

    2. 1. (PM) ½ of a context switch – The steps necessary to either save the state of a process (the half of a context switch that occurs at each interrupt) or restore the state of another (possibly the same) process (the half of a context switch that occurs at the end of the Dispatcher()).

  2. (AM) saveArea – Part of the SOS process descriptor that contains the hardware state of a process (the CRA-1 general-purpose registers, as well as the relevant control registers, such as ia, psw, base and bound). SOS keeps one saveArea per process.
  1. 2. (PM) pd[] – The SOS process descriptor array, used to keep track of processes within SOS.

    2. 3. (AM) iva – the interrupt vector address register of the CRA-1, a control register that points to the location in memory where the interrupt vector table resides.

    3. (PM) time quantum – value loaded into the CRA-1 timer register that controls the maximum amount of time that a process will be allowed to run in the run state before the timer interrupt causes a context switch. In other words, the maximum amount of CPU time that a process may use before being context switched (also known as a time slice).

  2. 4. (AM) system stack – runtime stack used to keep a record of the procedure calls and stack-based variables made while in the kernel; unlike a user stack this stack is reset and reused at the beginning of each system call/interrupt.

    3. 4. (PM) "friendly" non-preemption – a form of non-preemptive CPU scheduling where a program is expected to occasionally "give up" the CPU. This is typically done in event-based windows programming, where a program will call a routine that will block waiting for the next window/mouse/keyboard event.

  3. 5. (AM) loadall – a CRA-1 instruction that will load all 32 general-purpose registers from a memory address in one instruction. Typically used by operating system code when restoring the context of a process to be run next.
  1. (PM) SIM.hw.SetCellUnmapped() – the JavaSOS method used to write a memory object back to an absolute memory address.
  2. (AM) Client-server – an IPC pattern where a server provides one or more services to a number of clients. Usually recognized by the existence of a "public" address for client requests and the absence of explicit client addresses in the server. Client programs typically make a request and then leave while the server typically loops indefinitely, handling requests. Client/server is a variation of the producer/consumer IPC pattern.
  1. (PM) Rendezvous – an IPC pattern used when two or more processes want to synchronize in time by use of two-way signals.

    2. 7. (AM) Critical Section - A sequence of actions that must be done one at a time.

  2. (PM) Device independence – mapping of devices within the file name space (file hierarchy) such that programs can perform I/O using standard file system I/O calls (like open, read, write & close). The operating system manages the different types of devices below these system calls, meaning that application programs do not have to be specially coded to write to non-file types of "files", such as tape drives, video memory, etc.
  3. (AM & PM) Memory-mapped I/O – use of a machine’s memory address space as a method for communicating with I/O devices, such as disk controllers on the CRA-1. Specific addresses or a range of addresses are not actually stored into or read from memory but are instead interpreted by the I/O device assigned to these specific addresses.

 

Problem Solving (15 points each; 45 total)

 

1. Given the following JavaSOS definitions:

 

class SOSProcessDescriptor {

public boolean slotAllocated;

public int timeLeft;

public int state;

public int base_register;

public int limit_register;

}

 

(AM) Extend JavaSOS by adding a system call that returns the process ID to the calling process, modeled after the UNIX getpid() system call. Here is an example of how it would be used in, say, AppTests.java:

 

int myPID = MakeSystemCall((SOSSyscallIntHandler.GetPIDSystemCall, 0, 0);

SIM.Trace(SIM.TraceApp, "My Process ID = " + myPID);

 

Write the code for SOSSyscallIntHandler.java to add this new system call.

 

static final int GetPIDSystemCall = 9; // any value other than 1-8

.

. (anywhere within the switch statement of the HandleInterrupt() method):

.

case GetPIDSystemCall:

 

// Return the current processes PID

 

SIM.hw.SetCellUnmapped(addr + base_reg, cur_proc);

break;

 

NOTE: You will get near full credit for having the correct method name, even if you didn’t put down the full instance chain (in this case, SIM.hw). As long as you SetCellUnmapped() the value of cur_proc into cell 100 of the calling process.

 

(PM) Extend JavaSOS by adding a system call that returns the remaining CPU time left to the calling process. Here is an example of how it would be used in, say, AppTests.java:

 

int timeLeft = MakeSystemCall((SOSSyscallIntHandler.GetCPUTimeLeftSystemCall, 0, 0);

SIM.Trace(SIM.TraceApp, "I have " timeLeft + " milliseconds left in this time slice");

 

Write the code for SOSSyscallIntHandler.java to add this new system call.

 

static final int GetCPUTimeLeftSystemCall = 9; // any value other than 1-8

.

. (anywhere within the switch statement of the HandleInterrupt() method):

.

case GetCPUTimeLeftSystemCall:

 

// Return the current processes timeLeft

 

SIM.hw.SetCellUnmapped(addr + base_reg, SIM.sosData.pd[cur_proc].timeLeft);

break;

 

2. (AM) A SOS programmer attempted to write some code that is supposed to make two processes reach a common point in their code. Correct the problems in the code and state what type of IPC pattern this code is trying to achieve.

 

void main() { // process "A"

int queueA = AttachMessageQueue("/usr/queueb");

WaitForEmptyMsg(queueA);

int queueB = AttachMessageQueue("/user/queuea");

SendMsgTo(queueB);

}

 

void main() { // process "B"

int queueA = AttachMessageQueue("/usr/queueb");

WaitForEmptyMsg(queueA);

int queueB = AttachMessageQueue("/usr/queuea");

SendMsgTo(queueB);

}

 

This is the Two-process Rendezvous code found on page 243 of the book, with mistakes introduced:

 

    1. The WaitForEmptyMsg() and SendMsgTo() calls in process "A" are swapped (the SendMsgTo() should happen before the WaitForEmptyMsg()).
    2. The queues are swapped; process "A" should either Send() on queueA and wait on queueB while process "B" Send()s on queueB and Wait()s on queueA or vice versa (you can swap the QIDs on either the sends or the waits, but not both).
    3. The second AttachMessage() call in process "A" has a typo in the queue name; it should read "/usr/queuea" not "/user/queuea".
    4. The fact that the queue names don’t match the QID names (e.g., an attach on "/usr/queuea" is assigned to QID queueb) doesn’t matter, since the switching of the names is consistent between the two (no points deducted if the names are switched, as long as the end result satisfies condition # 2 above).

 

2.(PM) A SOS programmer attempts to write code that manages a resource potentially useful to other processes. Correct the problems in the code and state what type of IPC pattern this code is trying to achieve.

 

void main() { // process "A"

int msg[6];

int q1 = AttachMessageQueue("q1");

int q2 = AttachMessageQueue("q2");

SendMsgTo(q1, 3.14, q1);

ReceiveMessage(q2, msg);

}

 

void main() { // process "B"

int q3 = AttachMessageQueue("q2");

int msg[8];

while (1) {

SendMsgTo(msg[1], msg[0]/180);

ReceiveMessage(q3, msg);

}

}

 

This is the client/server code on page 251, with the "squaring" server now turned into a "divide by 180" server. Various mistakes have been introduced:

    1. The message buffer in process "A" (the client code) is two words too short (it should read "int msg[8]").
    2. The SendMsgTo() call in the client (process "A") should read: SendMsgTo(q2, 3.14, q1). That is, the server address is "q2" and the client’s response address is "q1". Msg[0] in the client contains the number to be "served upon" and msg[1] contains the QID of the client.
    3. The SendMsgTo() and ReceiveMessage() calls in the server (process "B") need to be swapped.
    4. The use of the name "q3" in the server code is not an error.

 

  1. 3. (AM & PM)

 

Fill in the missing labels of the diagram above.

 

The diagram is the process state diagram taken from page 128 of the textbook.

 

(AM)

    1. __create process_________
    2. __ready state____________
    3. __running state__________
    4. __clock (or timer)_interrupt
    5. __block for I/O or message

 

(PM)

    1. __ready state____________
    2. __running state__________
    3. __blocked state__________
    4. __process exit___________
    5. __dispatch process_______