CPSC 3220 Final Exam

Quiz 1

In which role does an OS manage resources, protect users and applications, and facilitate sharing?

Referee

Quiz 1

In which role does an OS provide common services?

Glue

Quiz 1

What is virtualization?

Providing an application with the illusion of resources that are not physically present

Quiz 1

What is the design goal for virtual machines?

High efficiency

Quiz 1

Consider a system call that does not access disk and that does not block further progress of an application, e.g., get_process_id(). Approximately how long does such a system call take?

On the order of 25 ns

in-class 1

1. Circle the relevant role of an operating system as R, I, or G (i.e., acting as a Referee, Illusionist, or Glue):

(a) R / I / G Physical details of a disk, such as sector size, are hidden.

(b) R / I / G Cut and paste commands work across different applications.

(c) R / I / G Prevent users from accessing each other's files without permission.

a.) I

b.) G

c.) R

in-class 2

2. Match these three terms to the appropriate blanks below: efficiency, response time, throughput

(a) The design goal for batch operating systems was high throughput.

(b) The design goal for time-sharing operating systems was low response times.

(c) The design goal for virtual machines is high efficiency.

a.) throughput

b.) response times

c.) efficiency

in-class 1

3. Operating systems can support communication between applications in multiple ways:

· Through the file system on secondary storage, using open(), read(), write(), close(), etc. system calls.

· With messages passed between the applications, using connect(), send(), receive(), disconnect() system calls.

· Through regions of memory shared between the applications, using load and store instructions.

Which method is likely the most efficient? Use the chart below to help explain why.

Notes: 1 ns = 10-9 seconds

1 µs = 10-6 seconds = 1,000 ns

1 ms = 10-3 seconds = 1,000 µs = 1,000,000 ns

Want to communicate at memory speeds but we have to take into account protection. So, some communication will only be done at the system call (call-passing) speed.

in-class 1

4. Consider this statement (from Wikipedia):

In early versions of DOS, printing was accomplished using the copy command: the file to be printed was "copied" to the file representing the print device. Control returned to the user when the print job completed.

Can an OS support printing in the background and thereby allow control to return to a user almost immediately after he or she issues a print command (or to an application after a system call to print is made) rather than waiting until the printing is complete? If so, suggest a way in which this can be done.

Multiprogramming/multitasking - multiple processes

For printing the term is spooling

Quiz 2

The OS kernel executes with full access to all the capabilities of the hardware.

True

Quiz 2

A user process executes with full access to all the capabilities of the hardware.

False

Quiz 2

The two modes of execution are called kernel mode and executive mode.

False

Quiz 2

Executable file formats like ELF contain initialized data that will be placed in the heap when the program is loaded.

False

Quiz 2

If a computer system is executing multiple processes, then each process must be an instance of a different program.

False

in-class 2

1. What is a program?

A set or sequence of instructions in a programming language for the computer to execute.

in-class 2

2. Identify at least three stages that a program goes through in-between (and exclusive of) editing source code and execution.

1.) Compilation

2.) Linking

3.) Loading

in-class 2

3. Why does an executable file not have a stack or heap?

Those two regions are not needed until execution so we shouldn't waste disk space on them in the executable.

in-class 2

Consider the three command lines:

% gcc my_prog.c

% ./a.out < in1 > out1 & ./a.out < in2 > out2

% ./a.out < in3 | ./a.out > out3

4. In response to the second command line, are there one or two programs running? Are there one or two processes running?

One program, two processes. The processes are independent.

in-class 2

5. In response to the third command line, are there one or two programs running? Are there one or two processes running?

One program, two processes. The processes are dependent: one-way communication from the first to the second using UNIX piping.

in-class 2

6. What is the difference between the second and third command lines?

Third command line allows the two processes to communicate.

in-class 2

Kernel mode / User mode. Circle one or both of K and U, as applies.

7. K / U In this mode add instructions can be executed.

8. K / U In this mode only a subset of the instructions can be executed.

9. K / U In this mode only a subset of the physical memory addresses can be accessed.

7.) K & U

8.) U

9.) U

in-class 2

10. What should happen if a user program attempts to execute a privileged instruction?

Stop the application and alert the OS.

11. Consider the changes in the memory image of a process during a buffer overflow attack, as illustrated below. Identify a way in which the attack can be prevented using a memory protection scheme that differentiates instruction fetches from data reads and writes. (diagram source: stack exchange)

Prevent instruction fetch from the stack region. (AMD NX bit for page protections)

Quiz 3

A power failure alert is recognized by a computer system as which type of interrupt?

Asynchronous interrupt

Quiz 3

What bad thing could happen if the user had access to the PSR (processor status register) and could change the value?

The user could change the execution mode bit to kernel and gain full access to the system.

Quiz 3

Why should an OS kernel copy system call parameters before checking their validity?

This prevents a user from modifying the parameters after they are checked for validity but before the parameters are used in the implementation of the system call.

Quiz 3

When a computer system is powered on, the first code that is executed is the command interpreter (or shell).

False

Quiz 3

A user stack will always be in a valid state.

False

in-class 3

Asynchronous interrupt / Synchronous interrupt (i.e., exception/fault/trap). Circle only one of A or S.

1. A / S Divide by zero

2. A / S CPU timer interrupt

3. A / S Completion of I/O operation

4. A / S System call that invokes the kernel

5. A / S Response to attempted execution of privileged instruction in user mode

1.) S

2.) A

3.) A

4.) S

5.) S

in-class 3

True / false. Circle only one of T or F.

6. T / F A guest OS runs in a virtual machine provided by a host OS.

7. T / F On a multiprocessor, an interrupt causes all available processors to respond.

6.) T

7.) F

in-class 3

Fill in the blanks.

8. The generic response to an interrupt is:

save the ____PC____ and the ____PSR_____

change execution mode to ____kernel_____

disable or restrict further ____interrupts

load the new ______PC____ from the ____IVT (interrupt table)_____

in-class 3

9. An interrupt return (iret) instruction needs to restore the ____PSR___ and the ___PC___ to provide restartable execution.

in-class 3

10. What is the purpose of a hardware timer?

Periodically interrupt execution and return control to the OS kernel.

in-class 3

11. What bad thing could happen if the user had access to the hardware timer and could change the value?

Malware can keep adding time to the timer and prevent the processor from breaking out of an infinite loop in user code.

in-class 3

12. Why should the hardware allow the masking of interrupts?

The kernel will need to protect small sequences of code with interrupts off to prevent corruption of kernel data.

in-class 3

13. Identify the two major differences between a jump-to-subroutine instruction (i.e., procedure call instruction) and a syscall instruction (i.e., software interrupt or trap instruction).

1.) Syscall has to enter the OS kernel only at entry points defined in the IVT

2.)

in-class 3

14. Why would one process need both a user stack and a kernel stack?

1.) User stacks could be corrupted; kernel stack is guaranteed to be valid.

2.) User stack could be accessed by a companion user thread and thwart protection.

in-class 3

15. Why should the operating system copy the system call parameters before checking their validity?

To avoid TOCTOU attack

Quiz 4

What type of problems can occur if you place OS functionality in library routines?

Protection problems

Quiz 4

What type of problems can occur if you place OS functionality in standalone server processes?

Performance problems

Quiz 4

A simple system call interface limits the amount of innovation possible in user applications.

False

Quiz 4

The Unix system call exec() creates a new process to run a program.

False

Quiz 4

If there were separate UNIX system calls for exists(), create(), and open(), what is NOT true of the following code segment?

if (!exists(name))create(name);fd = open(name);

These statements will always be executed in sequence with no interference from other processes.

Quiz 4

Producer and consumer processes can execute load/store instructions that directly access a kernel buffer.

False

Quiz 4

Kernel buffering requires that a producer process and its corresponding consumer process perform their respective calls to write() and read() in strict alternation.

False

Quiz 4

Unix and Linux are both microkernel designs.

False

in-class 4

1. Add a second reason to locate functionality outside the kernel.

flexibility - easier to change without breaking the system call interface

reliability - less likely to have buggy code in the kernel that corrupts kernel or user data

in-class 4

2. Add a second reason to locate functionality inside the kernel.

safety - better protection because validity checks cannot be skipped

performance - better performance since fewer system calls are needed

in-class 4

3. Add a second benefit of a "thin waist" for the system call interface. ("Thin waist" describes the design principle of decreasing the points of contact between the inside of the OS and the outside. See Figure 3.2.)

· provides a simple, stable interface

o ease of understanding for programmer (including an easier learning curve)

o ease of portability

· decouples the innovations in applications from the innovations in hardware

(e.g., we wouldn't change the system call interface

in-class 4

4. Add a second advantage of the "open before use" approach to file I/O. (In networking this design approach is called a connection-oriented interface. This is when we expect multiple interactions and thus initially establish a connection to reduce the overhead on each of those interactions.)

· check permissions once for the series of transactions rather than repeating the same check on each transaction

· allocate and set up internal data structures (such as control blocks and data buffers) once at the start of the series of transactions, rather than repeatedly having to do so on each transaction

in-class 4

5. What does an explicit call to the close() function accomplish?

decrements the reference count on the file and then garbage collects the internal data structures when the reference count reaches zero

in-class 4

6. If there were separate UNIX system calls for exists(), create(), and open(), what could go wrong with

the following code?

if (!exists(name))

create(name);

fd = open(name);

another process could run just after exists() returns false and then create the non-existing file

another process could run just before the call to open() and delete the existing file

in-class 4

7. Explain how kernel buffering decouples the execution of a producer and consumer process.

· each process can run at its own pace

· strict alternation of reads and writes is unnecessary, and this can reduce the number and costs of context switches (since each process can operate on a buffer multiple times before a process switch)

in-class 4

8. What is the purpose of the select() system call?

allows a server process to wait for requests from any of a set of file descriptors

in-class 4

9. Identify a pro and a con of microkernel design.

pro: simpler and likely more reliable

con: worse performance because of all the message passing communication

in-class 4

10. What three functions does the seL4 system implement in the microkernel?

interrupt handling, message passing, and scheduling

in-class 4

11. What does Linus think of microkernels?

He thinks they are stupid because they push the problem space into communication, which is actually a much bigger and fundamental problem.

in-class 4

12. What is the benefit of having device drivers run in user mode?

A buggy driver affects only its own data structures and not the rest of the kernel. (Thus, if the driver crashes, the kernel is not affected.)

Quiz 5

Threads created by a single process share the same memory address space.

True

Quiz 5

Threads created by a single process share the same memory stack.

False

Quiz 5

Threads created by a single process share the same scheduling state (e.g., Ready, Waiting).

False

Quiz 5

Threads created by a single process share the same open files.

True

Quiz 5

A thread enters the Running state when the thread scheduler resumes it.

True

Quiz 5

The thread_exit() call can immediately garbage collect the exited thread's resources and destroy the exited thread's thread control block.

False

Quiz 5

Threads are less expensive to create and destroy than processes.

True

Quiz 5

It is correct programming logic to assume that, once resumed, a thread will run without interruption up to the point of its next system call.

False

Quiz 5

It is correct programming logic to assume that the thread scheduling pattern will be the same on each run when the same program is executed multiple times with the same data and the same command line arguments.

False

Quiz 5

The Unix fork() system call is used to create a new process, and the Unix exec() system call is used to create an additional thread for the current process.

False

in-class 5

Process/Thread. Circle one or both of P or T, as applies.

1. P / T Has an associated control block.

2. P / T Has an associated data segment.

3. P / T Has an associated SP (stack pointer).

4. P / T Has an associated PC (program counter).

5. P / T Is created in response to the UNIX system call fork().

6. P / T The abstraction for protection provided by the OS kernel.

7. P / T A single execution sequence that represents a separately schedulable task.

8. P / T Is associated with an open file.

1.) P & T

2.) P

3.) T

4.) T

5.) P

6.) P

7.) T

8.) P

in-class 5

9. Identify four reasons to use threads within a single process.

express natural concurrency of application by writing each concurrent task as a separate thread

shift work to run in the background

exploit multiple processors

manage I/O devices

1.) express natural concurrency of application by writing each concurrent task as a separate thread

2.) shift work to run in the background

3.) exploit multiple processors

4.) manage I/O devices

in-class 5

10. Are threads considered more efficient than processes? If so, why? If not, why not?

yes, threads are:

● easier to create and destroy

● easier to communicate through shared memory (as opposed to needing system calls like send() receive())

● easier to switch between (there is no need to change the memory map/page table since they use the same address space)

in-class 5

11. What thread scheduling pattern should you base your program design upon?

none, each thread runs with unpredictable and variable speed

in-class 5

12. Is a kernel interrupt handler a thread?

no, an interrupt handler is not independently scheduled but is instead triggered by a hardware event

13. Can two threads be executing at the same time? Explain your answer.

yes, if there are multiple processors / multiple cores

in-class 5

15. Consider the following program using the thread library from ospp.cs.washington.edu.

#include

#include

#include

#include "thread.h"

#define NTHREADS 2

void go (void vp);

double x;

int main(int argc, char **argv) {

int i;

thread_t threads[NTHREADS];

for (i = 0; i < NTHREADS; i++) {

thread_create_p(&(threads[i]), &go, NULL);

}

for (i = 0; i < NTHREADS; i++) {

thread_join(threads[i]);

}

return 0;

}

void go (void vp) {

double y;

printf( "address of x is %p, address of y is %p\n", &x, &y );

thread_exit(0);

// Not reached

return NULL;

}

1.) How many different copies of the variable x are there?

2.) How many different copies of the variable y are there?

1.) 1

2.) 2

Quiz 6

To avoid having to make a system call for every thread operation, some systems support a model where user-level thread operations are implemented entirely in a user-level thread library, without invoking the kernel.

True

Quiz 6

Identify the missing word: The last step in creating a thread is to set its state to ________ and put the new TCB on the ready list, enabling the thread to be scheduled.

READY

Quiz 6

Consider Figure 4.12 and the discussion in section 4.8.1. on implementing multithreaded processes. Is the following statement in this context true or false?

The ready list used by the scheduler contains a mix of both TCBs and PCBs.

False

Quiz 6

A limitation of green threads is that when a blocking call is made by a user-level thread, the kernel is unable to run a different user-level thread in that same process. Scheduler activations are an improvement over green threads since the scheduler activation for a process can inform the user-level thread scheduler that it should choose another user-level thread to run after a blocking call is made.

True

Quiz 6

Asynchronous I/O requires that a running thread must create a separate I/O thread whenever a read or write is made to a high-latency device.

False

in-class 6

1. Why would you disable interrupts while a thread context switch occurs?

could corrupt kernel data; the textbook uses an example of a high priority thread being selected for dispatching and removed from the ready queue, and then an interrupt occurs before the dispatch can complete.

in-class 6

2. Why would you use green threads?

Historically - when the OS doesn't support the threads.

Minimize dependency on the OS thread API and maximize portability.

in-class 6

3. Why would you use scheduler activations?

Thread management functions can be implemented as procedure calls rather than system calls, with the thread management system knowing exactly how many processors have been assigned by the OS

in-class 6

4. What are the three ways listed in the textbook in which an operating system can return results after a call to asynchronous I/O?

Calling a signal handler, placing the result in queue in the processes memory, strong result in kernel memory until the process makes another system call to retrieve it.

in-class 6

5. Give at least one argument in favor of event-driven programming as compared to threads.

better performance since the application knows exactly what needs to be saved/restored for each event handler

Will not bump up against a thread count limit

in-class 6

6. Give at least one argument in favor of threads as compared to event-driven programming.

threads allows the program to exploit multiple processors, threads allows both foreground and background processing, threads allows the programmer to express logically concurrent

tasks.

Quiz 7

For a given lock, at most one thread can hold the lock at a given time.

True

Quiz 7

A single thread can hold multiple different locks at one time.

True

Quiz 7

If a CV::signal() operation is executed when there are no threads in the condition variable's waiting list, it is essentially a no-op and there is no effect.

True

Quiz 7

A CV::signal() operation reacquires the lock associated with the condition variable and passes it to the thread that it wakes up.

False

Quiz 7

A CV::wait() operation must atomically (a) release the lock, and (b) add the current thread to the waiting list.

True

Quiz 7

What is the only assumption you should make on a return from a CV::wait() operation?

The current thread holds the lock

Quiz 7

When a shared object is properly coded, you can always convert any CV::signal() operations to CV::broadcast() operations without changing the semantics of the shared object. However, making those conversions may impact performance.

True

Quiz 7

A lock acquire operation performed on a busy lock puts the calling thread into the WAITING state.

Ture

Quiz 7

For ease in locating a waiting thread, each lock and each condition variable has its own waiting list.

True

Quiz 7

To improve the performance of your program, it is ok to sometimes avoid acquiring locks before accessing shared data. This is because it is quite simple for even novice programmers to reason about the execution and memory access interleavings among multiple threads and identify performance optimizations.

False

in-class 7

Fill in the last four rows of values in the middle three columns for the following trace table that reflects the lost update example in the slides. Each thread has its own copy of register r1 and is able to access the shared global variable x using load and store instructions. ('?' means unknown value.)

time thread A A's r1 x B's r1 thread B

0 ? 0 ? (initially)

1 load r1,x 0 0 ?

2 add r1,r1,#1 1 0 ?

3 _1_ _0_ _0_ load r1,x // B's r1 = memory[x];

4 _1_ _0_ _1_ add r1,r1,#1 // B's r1++;

5 _1_ _1_ _1_ store r1,x // memory[x] = B's r1;

6 store r1,x _1_ _1_ _1_

in-class 7

Suppose we add a method to ask if a lock is free. Suppose it returns true. Is the lock now free, busy, or do you no longer know?

You no longer know; an event could occur between the time of check and time of use

in-class 7

What is the difference between a condition variable signal and broadcast?

Signal wakes up at most one thread; broadcast will wake up all threads waiting on that CV.

in-class 7

What do we mean when we say a condition variable is memoryless?

CV has no state to remember that there was a signal operation prior to wait operation (this is the key difference between CV's and semaphores)