Operating Systems

In the computer memory hierarchy, the two fastest layers are on a processor. What are they?

CPU Register, CPU Cache

In our lecture, we discussed a web browser and its practice of opening each new website in a separate process. Would the same benefits have been achieved if instead a browser app had been designed to open each new website in a separate thread?

No. If one thread has a bug in it, it renders the whole process unusable

Describe the actions taken by a kernel to context-switch between processes.

1. Store context of current process into its PCB

2. The scheduler picks a process in ready list

3. Use the PCB of picked core to restore the contents of CPU registers

What is PIC short for?

Programmable interrupt controller

What happens upon a keystroke?

1. Interrupt Occurs

2. On the hardware part the CPU indexes the IDT with interrupt_vector to locate the handler

3. In software, the handler is executed according to the interrupt number

If a user application wants to do an operation involving a privileged instruction, it only can do it via system call. Describe the entire procedures of invoking a system call in your own words.

1. From a library function call, an interrupt instruction is generated

2. The CPU registers for the processes that are saved.

3. The CPU interrupts the kernel.

4. Mode switch from user to kernel mode.

5. Interrupt instruction used to look up an interrupt descriptor in the IDT.

6. System call corresponding to the IDT entry is picked to handle the interrupt.

7. When work is done, kernel switches back to user mode

In a good design for implementing mutex, CAN we allow different processes to share an identical key to the critical section?

No. If anything happens to the process inside the critical section that results in it not leaving, deadlock will occur, blocking other processes from accessing resources

Illustrate how a binary semaphore can be used to implement mutual exclusion among n processes.

do

{

wait(semaphore)

//Critical section

singal(semaphore)

} while(true)

Why does the token drawing procedure in Lamport’s bakery algorithm need to be done atomically?

So that every process has a unique token.

How to implement CPU Modes?

Implemented through protection rings with lower rings having higher privileges.

Why are protection rings needed?

- Fault Isolation

- Privileged Instructions

- Privileged Memory Space

Which chip is responsible for handling higher performance-related communications?

Northbridge

What is a controller?

A hardware module that controls/interfaces with a peripheral component or device.

When using “time” command in shell to time any command, you may get the results,

for example, as below:

real 0m1.735s

user 0m0.017s

sys 0m0.040s

where real is the wall clock time (from start to finish);

user is the CPU time spent in user mode;

sys is the CPU time spent in kernel mode;

So, the actual CPU time is user + sys

Why does real ≠ user + sys? Please explain.

Because CPU usage is shared between processes.

There are multiple processes running on the CPU, the time process alternates with other processes so there is downtime that the time command does not account for.

In a command-line window (shell in Linux) consider the following input:

cat local_txt | sort

1) What is “|” called>

2) Is there a mode switch that happens? Why?

3) Is there a task switch/process switch that happens? Why?

1) Pipe

2) Yes, kernel mode will be necessary for the I/O procedures.

3) Yes, the computer will need to switch between the sort process and the process displaying the contents of the text file.

What are the three basic process states

Blocked, Running, Ready

What does the execution context mean? Please provide two examples

An execution context is the content of the CPU registers at a specific point in time. Two examples of an execution context are the program counter, and a call stack pointer.

Why does Linux have zombie processes?

It allows the parent process to read its child’s exit status

Which IPC method is usually the most efficient one? Why?

Shared Memory, because it doesn’t need to access kernel mode.

Is Round Robin always fair?

No, because a task gets a resource for a fixed period of time.

Why is Resource Numbering able to prevent deadlocks?

By allocating resources to processes in an even order, so the processes will never wait for a process that is also waiting on a process.

For the producer-consumer problem, if there is only one slot, what problem can this case actually be seen as? Please explain your answer.

If we have a FULL_SLOT then we must consume, produce, consume, produce.

If we have an EMPTY_SLOT then we must produce, consume, produce, consume

When does a process switch occur? Write down at least 2 reasons.

1) A process blocks

2) A process exits

3) CPU time slice is used up

Why do we need Zombie processes in Linux?

So the parent process can read the child’s exit status.

Name at least 4 IPC methods for data passing.

1. Pipe: Can only be used between parent and child.

2. FIFO: A named pipe, which doesn’t have the same limitation as pipe.

3. Message Queues: Supports boundary and message types.

4. Shared Memory: Usually the most efficient, because it does not need to access kernel mode.

Northbridge and Southbridge are two chips on the motherboard, what are the differences?

- Northbridge is higher performance than Southbridge. Both deal with communication.

Registers in a Controller can be used for various purposes. Please list one.

It can be used as data storage.

What is IPI

Inter-Processor Interrupt.

System call

In the C/C++ source code, a libc function (i.e. printf) is invoked. After being compiled, this source code is translated into a piece of machine code (aka, assembly code), which is executable. In Step 1, you see the assembly code includes two instructions:

EAX = sys_write

int 0x80

1) What does int 0x80 mean?

2) What is Step 2?

3) What is Step 3?

4) After finishing handling the syscall, we also need the last step.

1) Issues an interrupt because of a system call.

2) Mode switch from user to kernel.

3) An IDT Lookup

4) Mode switch back from kernel to user.

What is processor state? Please provide two examples.

The processor state, or execution context, is the content of the CPU registers at any given point in time. Examples: Program counter, call stack pointer, location of memory.

What is the content in an activation record in a call stack? Please list two examples.

- Arguments passed to the routine

- The return address

PCB is an abbreviation for ______________.

Process Control Block.

If a signal SIGFPE is received by kernel, what does this indicate?

Divide-by-zero

What are the requirements that a good solution to mutual exclusion should satisfy? Write down at least 3 items

1) Only one process allowed in the critical section at a time.

2) A process must not be denied entry to the critical section if there is no other process actively using it.

3) No deadlock

What are the three basic components of monitor?

1) Shared data.

2) Procedures, that operate on shared data.

3) Synchronization between concurrent procedures.

List four conditions of Deadlock

1) Circular Wait

2) No Pre-emption

3) Hold and Wait

4) Mutual Exclusion

What is the difference between “deadlock prevention” and “deadlock avoidance”?

Deadlock prevention breaks one of the deadlock conditions BEFORE execution.
Deadlock avoidance is enforced DURING execution.

MFQ is short for Multi-level Feedback Queue. Please explain how MFQ works

1) Has a set of Round Robin queues

2) High priority queues have short time slices while low priority queues has longer time slices.

3) Scheduler picks the first thread in highest priority, non-empty queue

4) When a process is scheduled out, it is inserted back into queues.

For contiguous allocation, what is updated at a process switch to assist address translation?

The base register + limit register

For segmentation, what is updated at a process switch to assist address translation?

The register points to the segmentation table.

What will happen if the total RAM is less than the total size of the working sets of processes?

Thrashing, which is continuous page swapping, eating up resources.

In CPU Scheduling, what is the difference between preemptive and nonpreemptive scheduling?

Preemptive scheduling can take resources away from the process Nonpreemptive scheduling occupies the resources until it voluntarily releases them.

What is the difference between a physical address and logical address? What are they used by?

Physical address is a physical location in main memory, used by memory bus.

Logical address is a reference to a memory location in logical memory, used by CPU and compiler

Logical view vs. Physical view

A compiler compiles a program based on the logical view.
The layout of processes in physical memory forms a physical view.

Why is non-contiguous allocation better?

Contiguous allocation does not exploit the working set theory while non-contiguous allocation does.

Does paging have internal fragmentation? Why?

Yes, paging can have internal fragmentation but only on the last page.

What is the main disadvantage of fixed partitioning?

Internal fragmentation.

What is the relation between 4G and 4GB in describing memory address/space?

4G is the number of memory addresses.

4GB is logical memory space size

What conditions can lead to a segmentation fault exception?

1) Reference to unallocated holes in memory.

2) Reference to freed heap buffers

3) Trying to access protected areas.

4) Try to write to read-only.

What command is used when debugging using gbd?

“bt” (backtrace)

Briefly describe the process of CoW, or Copy on Write.

- Copy page table of parent into child process.

- Mark all writable pages as read only

- Trap into kernel on write (child or parent)

What are the two types of memory reference locality? Give an example of each.

Temporal Locality (EX: instructions executed multiple times in a loop)

Spacial Locality (EX: array is scanned)

What is TLB, and how does it work?

Translation Lookaside Buffer: A cache specialized for speeding up address translation.

What is the content in one IDT entry?

A descriptor for an exception handler or interrupt.

Assuming "counter" is an integer variable shared by multiple processes. If it is incremented by multiple processes through "counter++" operation concurrently without any syncohnrization, what problem will happen? Please note you can and only can need to use a term to answer the question.

Race condition

enter_cs();

counter++;

leave_cs();

Given an X86 CPU, how do you tell whether the CPU is in the kernel mode or user mode

The lowest two bits in the CS register indicate the Current Privilege Level of the CPU.

What if the user mode code tries to execute privileged instructions?

CPU checks if it’s in the kernel mode. If not, exception gets triggered to end the current process

Given that I/O instructions can only be executed in the kernel mode, how does a user program perform I/O?

With system calls. When a system call is invoked, the CPU mode switches to kernel mode and CPU can thus execute privileged instructions, such as I/O instructions

Whats the difference between kernel mode and user mode?

- Faults in user space can be captured by the kernel

- Privileged instructions can only be issued in kernel mode

- Some memory space can only be accessed in kernel mode

What are examples of Privileged instructions

- I/O operations

- Switch page tables of processes: load cr3

- Enable/disable interrupts: sti/cli

- Change processor modes from kernel to user: iret

- Halt a processor to enter low-power stage: hlt

- Load the Global Descriptor Table register in x86: lgdt

What are examples of Non Privileged instructions

add, sub

Does “root” refer to kernel mode?

No, Root User is always root user regardless of mode.

Can user code issue I/O calls directly?

No, I/O calls are done through system calls.

How does the kernel know when the CPU time slice of the current process is used up?

- Whenever a timer interrupt is issued, the interrupt handler in the kernel is invoked to determine whether scheduling should happen

- Timer interrupts ensure that the CPU time allocation is under the control of the kernel; i.e., no user process can occupy the CPU longer than it is supposed to

If the CPU time slice is 10ms, why not just set the timer interrupt frequency as 100 hz (ie. it occurs per 10ms)?

Because timer interrupts are not only used by the scheduler, but also for timing purposes

What is a Call Stack?

A stack data structure that stores the information for the active function calls

What is a Process Switch?

Suspending one process and resuming another. Also called task switch.

What does a mode switch mean?

program execution switches between different CPU modes

When does the user → kernel mode switch occur?

- System calls

- Interrupts

- Exceptions

What are examples of fault isolation?

- Divide by zero

- Exception occurs when doing the operation

- Mode swithc to kernel, a handler for exception is invoked

- Handler send a SIGFPE to faulty process

- Mode switch back to user space

What is the difference between interrupt entry and exception entry

- CPU will clear the IF flag to disable local interrupts upon handling of an interrupt

- IF flag will not be disabled when handling exceptions

What is a Monitor?

a language-assisted construct that encapsulates data, procedures, and synchronization. It also contains a mutex lock and a queue.

What does a system bus comprise of?

Control Bus, Address Bus, Data Bus

What are the 3 major subsystems of an OS Kernel?

Process Management, Memory Management, Device Management

What are the OS layers

- User Space: Application / Libraries

- Kernel: Process Management / Memory management / Device management

- Hardware: CPU / Memory / Device

What are the two forms of controllers?

- Controller Boards (network interface, graphics)

- Chips (north/south bridge, keyboard/interrupts)

Whats an example of IPI (Inter-Processor Interrupt).

The interruption of one processor when another processor is shutting the system down.

Why does a controller need registers?

A controller needs registers so it can create bridges between a device and the computer.

What’s an example of IPI

One process shutting down another.

Please provide 3 examples of signals.

SIGFPE, SIG_IGN, and SIGKILL

Provide 2 examples of hardware interrupts

Keystroke, Timer

Provide 1 example of software interrupt.

System call

How does non-contiguous allocation work?

During non-contiguous allocation, the memory needed by a process is cut into segments or pages, and swaps in the corresponding parts of current working set into memory, allowing more active processes.

For paging, what is updated at a process switch to assist address translation?

The register pointing to the page table.

For paging, what if the page size is very large?

Internal fragmentation, as we wont use all the space.

For paging, what if the page size is very small?

Many page table entries, which consumes resources.

For paging, can it share data with other processes?

Yes, different processes’ page tables can point to the same page frames.

In Linux, zombie processes occupy precious resources, so we need to clean them up. How to clean them up explicitly?

Its parent calls wait to retrieve the exit state or If the parent explicitly ignores the SIGCHILD by setting handler to SIG_IGN

What condition of Deadlock can’t be eliminated?

Mutual Exclusion, because mutex is needed to avoid race condition bugs.

For contiguous allocation, can it keep the program from accidentally overwriting it’s own code?

No.

For contiguous allocation, can it share data with other processes?

No, because different process occupy separate memory locations with no overlap.

What is the main disadvantage of dynamic partitioning?

External fragmentation.

How do we solve the problem of fragmentation in dynamic partitioning?

Paging

For segmentation, can it keep the program from accidentally overwriting it’s own code?

Yes, a code segment can be set as “read only”

For segmentation, can it share data with other processes?

Yes, a physical segment can be pointed to by many other processes.

How to use MFQ in a multi-processor computer?

Per-processor affinity scheduling

Busy-waiting synchronization has one advantage when comparing with non-busy-waiting synchronization. That is busy-waiting synchronization does not need _________________, while non-busy waiting does need.

Context Switch

In contrast, busy-waiting synchronization also has one disadvantage when comparing with non-busy-waiting synchronization. That is busy-waiting synchronization needs to consume ________________ resources because of this empty loops.

CPU Time

Busy-waiting synchronization does not need a context switch. That is, busy-waiting synchronization needs to consume CPU Time resources because of these empty loops Therefore, in practice, they are used in a ________________ way by many systems

Hybrid

In a non-preemptive scheduling assumption, there are the following five processes:

| Process | Time consumption (ms) |

| A | 5 |

| B | 15 |

| C | 20 | 

| D | 10 |

| E | 30 |

If SPF Scheduling is adopted, what will be the average wait time?

A + D + B + C + E
Average Time = (0 + 5 + 15 +30 + 50) / 5