Communicator

Posted on May 1, 2024 in Computers

Overview

● ●What are privileged instructions? Also known as protected instructions, they are a subset of instructions restricted to use only by the OS. They directly control hardware. Only the operating system can directly access I/O devices such as disks, printers, keyboard, etc.. (for security and fairness), manipulate memory management state (page table pointers, page protection, TLB management, etc..), manipulate protected control registers (kernel mode, interrupt level), and issue the halt (shutdown) instruction.

◆Who gets to execute them? Operating system in kernel mode

◆How does the CPU know whether they can be executed? they can only be executed in kernel mode. This is indicated by a status bit in a protected control register. This status bit will indicate whether the operating system is in user mode or if it in kernel mode. User mode cannot communicate directly with hardware. Setting this bit is a protected instruction. When a protected instruction is attempted, the bit is observed. If it is not set in protected mode, the instruction is prevented.

◆Difference between user and kernel mode

Kernel Mode: the executing code has complete and unrestricted access to the underlying hardware. It can execute any CPU instruction and reference any memory address. Kernel mode is generally reserved for the lowest-level, most trusted functions of the operating system. Crashes in kernel mode are catastrophic; they will halt the entire system.

User mode: The executing code has no ability to directly access hardware or reference memory. Code running in user mode must delegate to system APIs to access hardware or memory. Due to the protection afforded by this sort of isolation, crashes in user mode are always recoverable. Most of the code running on your computer will execute in user mode. User programs execute in user mode.

●Why do they need to be privileged?

To protect the operating system from itself

Prevent malicious user level programs from taking control mwhahahha

●What do they manipulate?

◆Protected control registers

◆Memory management

◆I/O devices

Events

●Events: an “unnatural” change in control flow. They immediately stop current execution. They also change the operating system mode (user mode, kernel mode), context (machine state), or both. They are handled by the kernel; the kernel defines a handler for each event type. Event handlers always execute in kernel mode. The specific types of events are defined by the machine. Once the system is booted, all entry to the kernel occurs as the result of an event (the operating system can be thought of as one big event handler). There are two kinds of events – interrupts and exceptions.

◆Synchronous:fault (exceptions), system calls

◆Asynchronous: interrupts, software interrupt

What are faults, and how are they handled? The hardware detects and reports “exceptional” conditions (page fault, unaligned access, divide by zero). When this happens, the hardware “faults”. The system will save the state (program counter, registers, mode, etc..) so that the faulting process can be restarted. Fault exceptions are a performance optimization; Faults could be detected through the insertion of extra instructions into code at the cost of performance.

Some faults are handled by “fixing” the exceptional condition and returning to the faulting context (exception handling). Example is page faults and the operating system placing the missing page into memory as a response. Other faults are handled by notifying the process, an example being the fault handler changes the saved context to transfer control to a user-mode handler on return from fault (Handler must be registered -+with OS).

The kernel may handle unrecoverable faults by killing the user process. A program faults with no registered handler, also the halt (shutdown) process are examples. Faults within the kernel itself are through the dereferencing NULL, dividing by zero, or an undefined instruction are considered to be fatal (Unix panic, Windows blue screen).

●What are system calls, and how are they handled? They allow a user program to do something “privileged”, also referred to as crossing the protection boundary, or protected procedure call, or protected control transfer.

The CPU ISA (Instruction Set Architecture) provides a system call instruction that causes an exception which vectors to a kernel handler. This passes a parameter which determines the system routine to call. The caller state (program counter, registers, mode) is saved so that it can be restored. Returning from the system call restores this state.

Requirements: requires architectural support to Verify input parameters (e.G., valid addresses for buffers). Also to restore saved state, reset mode, resume execution.

/*somebody answer these questions please this slide got me confused***/

What would happen if the kernel did not save state?

It couldn’t return to the previous process after the system call

Otherwise when return to the user mode it cannot be restored correctly?

essentially yes. “saving the state” will save things like the stack pointer and the program counter and the registers values being used by that program. When you do a context switch to the -previous- program, but don’t know the values that these things had, the program doesn’t have any of the data or even know what the next instruction is supposed to be

What if the kernel executes a system call?

The kernel is running in privileged mode so it can make system calls

What if a user program returns from a system call?

when a user program wants to do something privileged, like I/O, it sends a request to the OS to do it for them. When the OS finishes, it sends the output or response or confirmation (if any) to the program so it can continue running. I think this is what you meant by “returning” from a system call.

How to reference kernel objects as arguments or results to/from system calls?

●What are interrupts, and how are they handled?

Interrupts are asynchronous events. They consist of I/O hardware interrupts, also software and hardware timers. There are two types – precise and imprecise.

precise interrupts: CPU transfers control only on instruction boundaries. Operating system designers prefer these. Why? I believe it is because the processor can recover from a precise interrupt (the model that the instructions were executed in is preserved). The processor would be able to go back to where it was before the interrupt.

imprecise interrupts: CPU transfers control in the middle of instruction execution (what does this mean? The instructions the CPU was processing isn’t finished; It jumps to a different instruction). CPU designers prefer these. Why? Don’t have to worry about whether the instruction does when it stops executing the program and lets the interrupt handler run

2◆How do I/O devices use interrupts?

Http://www.Tldp.Org/HOWTO/Unix-and-Internet-Fundamentals-HOWTO/devices.Html

●What is the difference between exceptions and interrupts?

Interrupts and Exceptions both alter program flow. The difference being, interrupts are used to handle external events (serial ports, keyboard) and exceptions are used to handle instruction faults, (division by zero, undefined opcode).

Interrupts are handled by the processor after finishing the current instruction, so they are asynchronous events

Exceptions on the other hand are divided into three kinds

Faults

Faults are detected and serviced by the processor before the faulting instructions

Traps

Traps are serviced after the instruction causing the trap. User defined interrupts go into this category and can be said to be traps.

Aborts

Aborts are used only to signal severe system problems, when operation is no longer possible

2) Interrupts are asynchronous events that are normally(not always) generated by hardware(Ex, I/O) not in sync with processor instruction execution.

2) Exceptions are synchronous events generated when processor detects any predefined condition while executing instructions.

Lastly, An interrupt handler may defer an exception handler, but an exception handler never defers an interrupt handler.

Interrupt Questions

Interrupts halt the execution of a process and transfer control (execution) to the operating system

Can the OS be interrupted? (Consider why there might be different IRQ levels)

Interrupts are used by devices to have the OS do stuff

What is an alternative approach to using interrupts?

What are the drawbacks of that approach?

Processes

●What is a process? sometimes called a job or a task or a sequential process, it is the unit of execution, scheduling, and dynamic execution context of a program. It has an execution state that indicated what it is currently doing – running (executing instructions on the CPU), ready (waiting to be assigned to the CPU), and waiting (waiting for an event). As a process executes, it moves from state to state.

●What resource does it virtualize? CPU

●What is the difference between a process and a program? A process is a sequential program in execution. It defines the sequential, instruction-at-a-time execution of a program. Programs are static entities with the potential for execution.

●What is contained in a process?

//I Think the PCB contains the PID and state, not process itself

A process contains the state for a program in execution and is named using its process ID (PID). It contains the following…

An address space

The code for the executing program

The data for the executing program

An execution stack encapsulating the state of procedure calls

The program counter (PC) indicating the next instruction

A set of general-purpose registers with current values

A set of operating system resources such as open files, network connections, etc

Process Data Structures

●Process Control Blocks (PCBs) OS data structures representing each process. They contain a huge amount of information in one large structure. It is a heavyweight abstraction.

Process ID (PID)

Execution state

Hardware state: program counter, stack pointer, registers

Memory management

Scheduling

Accounting

Pointers for state queues

Etc.

◆What information does it contain? It contains all of the info about a process, also is where the OS keeps all of a process’ hardware execution state (program counter, stack pointer, registers, etc.) when the process is not running. This state is everything that is needed to restore the hardware to the same configuration it was in when the process was switched out of the hardware.

◆How is it used in a context switch? The process of changing the CPU hardware state from one process to another is called a context switch. It can happen many times a second.

In order to switch processes, the PCB for the first process must be created and saved. The PCBs are sometimes stored upon a per-processstack in kernel memory (as opposed to the user-modecall stack), or there may be some specific operating system defined data structure for this information.

When the OS stops running a process, it saves the current values of the registers into the process’ PCB. When the OS is ready to start executing a new process, it loads the hardware registers from the values stored in that process’ PCB.

●State queues The OS maintains a collection of queues that represent the state of all processes in the system

◆What are process states? A process has an execution state that indicates what it is currently doing; running (executing instructions on the CPU), ready (waiting to be assigned to the CPU), and waiting (waiting for an event).

◆What is the process state graph? It is a DFA (deterministic finite automata) that expresses the life cycle that all processes go through.

◆When does a process change state? This depends on the state that the process is currently in

Running to Waiting: When the process is currently in the running state but discovers that it cannot continue, it will transition to the waiting state. A common case is if the process finishes its task before its allotted time expires. In this case it will voluntarily relinquish control of the CPU.

Running to Ready: The scheduler decides that the running process has run long enough and it is time to let another process have CPU time.

Ready to Running: When all other processes have had their share and it is time for the first process to run again

Waiting to Ready: When the external event for which a process was waiting (such as arrival of input) happens

New to Ready: When the process is created

Running to Terminated: When the process has finished execution

Http://www.Personal.Kent.Edu/~rmuhamma/OpSystems/Myos/processOperate.Htm

◆How does the OS use queues to keep track of processes? The OS maintains a collection of queues that represent the state of all processes in the system. Typically, the OS has one queue for each state (running, ready, waiting). Each process control block (PCB) is queued on a state queue according to its current state. As a process changes state, its PCB is unlinked from one queue and linked into another

Process Manipulation

●What does CreateProcess on NT do?

Creates and initializes a new PCB (process control block)

Creates and initializes a new address space

Loads the program specified by “prog” into the address space

Copies “args” into memory allocated in address space

Initializes the saved hardware context to start execution at main (or wherever specified in the file)

Places the PCB on the ready queue

●What does fork() on Unix do?

Creates and initializes a new PCB

Creates a new address space

Initializes the address space with a copy of the entire contents of the address space of the parent

Initializes the kernel resources to point to the resources used by parent (e.G., open files)

Places the PCB on the ready queue

◆What does it mean for it to “return twice”? Returns the child’s PID to the parent, “0” to the child

●What does exec() on Unix  do?

Stops the current process

Loads the program “prog” into the process’ address space

Initializes hardware context and args for the new program

Places the PCB onto the ready queue

Note: It does not create a new process

Question on slide: What does it mean for exec to return?

An error had occured (source: man: http://man7.Org/linux/man-pages/man3/exec.3.Html). Normally exec should have replaced the old process with a whole new program, thus the code of the old code should have been lost, forbidding a meaningful return.

◆How is it different from fork? fork() is used to create a new process, exec is used to load a program into the address space.

●How are fork and exec used to implement shells? The shell creates a child process from a command. Shell is returned when the process exits. (expand on this)

The shell forks a child process and exec the command on the child. Meanwhile, the parent wait()/waitpid() (Note: not to be confused with join for threads) till the child process finishes and reprompt.

(Source:
process slide p. 29: http://cseweb.Ucsd.Edu/classes/fa15/cse120-a/lectures/proc.Pdf)

 ● ●What are privileged instructions? Also known as protected instructions, they are a subset of instructions restricted to use only by the OS. They directly control hardware. Only the operating system can directly access I/O devices such as disks, printers, keyboard, etc.. (for security and fairness), manipulate memory management state (page table pointers, page protection, TLB management, etc..), manipulate protected control registers (kernel mode, interrupt level), and issue the halt (shutdown)

Instruction

◆Who gets to execute them? Operating system in kernel mode

◆How does the CPU know whether they can be executed? They can only be executed in kernel mode. This is indicated by a status bit in a protected control register. This status bit will indicate whether the operating system is in user mode or if it in kernel mode. User mode cannot communicate directly with hardware. Setting this bit is a protected instruction. When a protected instruction is attempted, the bit is observed. If it is not set in protected mode, the instruction is prevented.

◆Difference between user and kernel mode

Kernel Mode: the executing code has complete and unrestricted access to the underlying hardware. It can execute any CPU instruction and reference any memory address. Kernel mode is generally reserved for the lowest-level, most trusted functions of the operating system. Crashes in kernel mode are catastrophic; they will halt the entire system.

User mode: The executing code has no ability to directly access hardware or reference memory. Code running in user mode must delegate to system APIs to access hardware or memory. Due to the protection afforded by this sort of isolation, crashes in user mode are always recoverable. Most of the code running on your computer will execute in user mode. User programs execute in user mode.

●What do they manipulate?

◆Protected control registers

◆Memory management

◆I/O devices

Events

●Events: an “unnatural” change in control flow. They immediately stop current execution. They also change the operating system mode (user mode, kernel mode), context (machine state), or both. They are handled by the kernel; the kernel defines a handler for each event type. Event handlers always execute in kernel mode. The specific types of events are defined by the machine. Once the system is booted, all entry to the kernel occurs as the result of an event (the operating system can be thought of as one big event handler). There are two kinds of events – interrupts and exceptions.

◆Synchronous: fault (exceptions), system calls

◆Asynchronous: interrupts, software interrupt

What are faults, and how are they handled? The hardware detects and reports “exceptional” conditions (page fault, unaligned access, divide by zero). When this happens, the hardware “faults”. The system will save the state (program counter, registers, mode, etc..) so that the faulting process can be restarted. Fault exceptions are a performance optimization; Faults could be detected through the insertion of extra instructions into code at the cost of performance.

Some faults are handled by “fixing” the exceptional condition and returning to the faulting context (exception handling). Example is page faults and the operating system placing the missing page into memory as a response. Other faults are handled by notifying the process, an example being the fault handler changes the saved context to transfer control to a user-mode handler on return from fault (Handler must be registered -+with OS).

What are system calls, and how are they handled? They allow a user program to do something “privileged”, also referred to as crossing the protection boundary, or protected procedure call, or protected control transfer.

The CPU ISA (Instruction Set Architecture) provides a system call instruction that causes an exception which vectors to a kernel handler. This passes a parameter which determines the system routine to call. The caller state (program counter, registers, mode) is saved so that it can be restored. Returning from the system call restores this state.

Requirements: requires architectural support to Verify input parameters (e.G., valid addresses for buffers). Also to restore saved state, reset mode, resume execution.

Otherwise when return to the user mode it cannot be restored correctly?

essentially yes. “saving the state” will save things like the stack pointer and the program counter and the registers values being used by that program. When you do a context switch to the -previous- program, but don’t know the values that these things had, the program doesn’t have any of the data or even know what the next instruction is supposed to be

What if the kernel executes a system call?

The kernel is running in privileged mode so it can make system calls

What if a user program returns from a system call?

when a user program wants to do something privileged, like I/O, it sends a request to the OS to do it for them. When the OS finishes, it sends the output or response or confirmation (if any) to the program so it can continue running. I think this is what you meant by “returning” from a system call.

How to reference kernel objects as arguments or results to/from system calls?

●What are interrupts, and how are they handled?

Interrupts are asynchronous events. They consist of I/O hardware interrupts, also software and hardware timers. There are two types – precise and imprecise.

precise interrupts: CPU transfers control only on instruction boundaries. Operating system designers prefer these. Why? I believe it is because the processor can recover from a precise interrupt (the model that the instructions were executed in is preserved). The processor would be able to go back to where it was before the interrupt.

imprecise interrupts: CPU transfers control in the middle of instruction execution (what does this mean? The instructions the CPU was processing isn’t finished; It jumps to a different instruction). CPU designers prefer these. Why? Don’t have to worry about whether the instruction does when it stops executing the program and lets the interrupt handler run

●What is the difference between exceptions and interrupts?

Interrupts and Exceptions both alter program flow. The difference being, interrupts are used to handle external events (serial ports, keyboard) and exceptions are used to handle instruction faults, (division by zero, undefined opcode).

Interrupts are handled by the processor after finishing the current instruction, so they are asynchronous events.

Exceptions on the other hand are divided into three kinds.

Faults

Faults are detected and serviced by the processor before the faulting instructions.

Traps

Traps are serviced after the instruction causing the trap. User defined interrupts go into this category and can be said to be traps.

Aborts

Aborts are used only to signal severe system problems, when operation is no longer possible.

2) Interrupts are asynchronous events that are normally(not always) generated by hardware(Ex, I/O) not in sync with processor instruction execution.

2) Exceptions are synchronous events generated when processor detects any predefined condition while executing instructions.

Lastly, An interrupt handler may defer an exception handler, but an exception handler never defers an interrupt handler.

Interrupt Questions

Interrupts halt the execution of a process and transfer control (execution) to the operating system

Can the OS be interrupted? (Consider why there might be different IRQ levels)

Interrupts are used by devices to have the OS do stuff

What is an alternative approach to using interrupts?

What are the drawbacks of that approach?

Processes

●What is a process? Sometimes called a job or a task or a sequential process, it is the unit of execution, scheduling, and dynamic execution context of a program. It has an execution state that indicated what it is currently doing – running (executing instructions on the CPU), ready (waiting to be assigned to the CPU), and waiting (waiting for an event). As a process executes, it moves from state to state.

●What resource does it virtualize? CPU

●What is the difference between a process and a program? A process is a sequential program in execution. It defines the sequential, instruction-at-a-time execution of a program. Programs are static entities with the potential for execution.

●What is contained in a process?

//I Think the PCB contains the PID and state, not process itself

A process contains the state for a program in execution and is named using its process ID (PID). It contains the following…

An address space

The code for the executing program

The data for the executing program

An execution stack encapsulating the state of procedure calls

The program counter (PC) indicating the next instruction

A set of general-purpose registers with current values

A set of operating system resources such as open files, network connections, etc.

Process Data Structures

◆What information does it contain? It contains all of the info about a process, also is where the OS keeps all of a process’ hardware execution state (program counter, stack pointer, registers, etc.) when the process is not running. This state is everything that is needed to restore the hardware to the same configuration it was in when the process was switched out of the hardware.

◆How is it used in a context switch? The process of changing the CPU hardware state from one process to another is called a context switch. It can happen many times a second.

In order to switch processes, the PCB for the first process must be created and saved. The PCBs are sometimes stored upon a per-process stack in kernel memory (as opposed to the user-mode call stack), or there may be some specific operating system defined data structure for this information.

When the OS stops running a process, it saves the current values of the registers into the process’ PCB. When the OS is ready to start executing a new process, it loads the hardware registers from the values stored in that process’ PCB.

●State queues The OS maintains a collection of queues that represent the state of all processes in the system.

◆What are process states? A process has an execution state that indicates what it is currently doing; running (executing instructions on the CPU), ready (waiting to be assigned to the CPU), and waiting (waiting for an event).

◆What is the process state graph? It is a DFA (deterministic finite automata) that expresses the life cycle that all processes go through.

◆When does a process change state? This depends on the state that the process is currently in.

Running to Waiting: When the process is currently in the running state but discovers that it cannot continue, it will transition to the waiting state. A common case is if the process finishes its task before its allotted time expires. In this case it will voluntarily relinquish control of the CPU.

Running to Ready: The scheduler decides that the running process has run long enough and it is time to let another process have CPU time.

Ready to Running: When all other processes have had their share and it is time for the first process to run again.

Waiting to Ready: When the external event for which a process was waiting (such as arrival of input) happens.

New to Ready: When the process is created.

◆How does the OS use queues to keep track of processes? The OS maintains a collection of queues that represent the state of all processes in the system. Typically, the OS has one queue for each state (running, ready, waiting). Each process control block (PCB) is queued on a state queue according to its current state. As a process changes state, its PCB is unlinked from one queue and linked into another

Process Manipulation

●What does CreateProcess on NT do?

Creates and initializes a new PCB (process control block).

Creates and initializes a new address space.

Loads the program specified by “prog” into the address space.

Copies “args” into memory allocated in address space.

Initializes the saved hardware context to start execution at main (or wherever specified in the file).

Places the PCB on the ready queue.

●What does fork() on Unix do?

Creates and initializes a new PCB.

Creates a new address space.

Initializes the address space with a copy of the entire contents of the address space of the parent.

Initializes the kernel resources to point to the resources used by parent (e.G., open files).

Places the PCB on the ready queue.

●What does exec() on Unix  do?

Stops the current process

Loads the program “prog” into the process’ address space

Initializes hardware context and args for the new program

Places the PCB onto the ready queue

Note: It does not create a new process

question on slide: What does it mean for exec to return?

◆How is it different from fork? Fork() is used to create a new process, exec is used to load a program into the address space.

●How are fork and exec used to implement shells? The shell creates a child process from a command. Shell is returned when the process exits. (expand on this)

The shell forks a child process and exec the command on the child. Meanwhile, the parent wait()/waitpid() (Note: not to be confused with join for threads) till the child process finishes and reprompt.

Threads

●What is a thread?
A sequential execution stream within a process (program counter, stack pointer, registers). Each thread is much like a separate process, except that they share the same address space and thus can access the same data.

◆What is the difference between a thread and a process?

A thread defines a sequential execution stream within a process (program counter, stack pointer, registers) while a process defines the address space and general process attributes (everything but threads of execution). A thread is also bound to a single process, while processes can have multiple threads. A process has more overhead and is more resource-intensive than a thread.

◆How are they related? Processes are now the containers in which threads execute. Processes become static, threads are the dynamic entities.

●Why are threads useful? Separating threads and processes makes it easier to support multithreaded applications; Concurrency does not require creating new processes, it also improves program structure, handling concurrent events, and writing parallel programs. Concurrency is thus cheaper with threads than it is with processes.

●What is the difference between user-level and kernel- level threads?

Kernel-level: Integrated with OS (informed scheduling). Slower to create, manipulate, synchronize.

User-level: Faster to create, manipulate, synchronize. Not integrated with OS (uninformed scheduling)

Understanding the differences between kernel and user-level threads is important for programming (correctness, performance) and test-taking.

◆What are the advantages/disadvantages of one over another?

Kernel-level threads are implemented in the kernel and the operating system schedules them. Although kernel-level threads are cheaper and more efficient than processes, they are less efficient than user-level threads (slower to create, manipulate, synchronize), which are managed entirely by  the run-time system (user-level library). User-level threads are small and fast, and creating them, switching between them, and synchronizing them are done via procedure call, all without kernel involvement. User-level thread operations 100x faster than kernel threads. Unfortunately since they are not managed directly by the operating system like kernel-level threads, they can be prone to poor scheduling decisions. Solving this requires communication between the kernel and the user-level thread manager. Kernel-level threads are more efficiently scheduled by the operating system since they are directly managed by it.

Thread Implementation

●How are threads managed by the run-time system? Thread control blocks, thread queues. How is this different from process management? Threads reside within processes, so process management is therefore thread management.

●What operations do threads support?

Fork, yield, sleep, join, etc.

◆What does thread yield do?

It gives up the CPU to another thread. In other words, it context switches to another thread.

●What is a context switch?

A context switch (also sometimes referred to as a process switch or a task switch) is the switching of the CPU (central processing unit) from one process or thread to another. Saves context of the currently running thread (old_thread) by pushing all machine state onto its stack. Restores context of the next thread by pooping (LOL) all machine state from the next thread’s stack. The next thread becomes the current thread. Return to caller as new thread. This is all done in assembly language; It works at the level of the procedure calling convention, so it cannot be implemented using procedure calls.

●What is the difference between non-preemptive scheduling and preemptive thread scheduling?

◆Voluntary and involuntary context switches

voluntary: non-preemptive, must voluntarily give up CPU. A long-running thread will take over the machine. Only voluntary calls to thread_yield(), thread_stop(), or thread_exit() causes a context switch.

involuntary: preemptive, need to regain control of processor asynchronously. Uses a timer interrupt. Timer interrupt handler forces current thread to “call” thread_yield. How is this done?Ynchronization

●Why do we need synchronization?Coordinate access to shared data structures and coordinate thread/process execution.

●What can happen to shared data structures if synchronization is not used? Race condition, corruption, bank account example (http://cseweb.Ucsd.Edu/classes/fa15/cse120-a/lectures/synch.Pdf p.6/7)

●When are resources shared? Global variables, static objects, and heap objects.

Mutual Exclusion

●What is mutual exclusion? Synchronizes access to shared resources, preventing simultaneous access to those shared resources.

●What is a critical section? Code that uses mutual exclusion to synchronize its execution is called a critical section. The section of code that is being synchronized is the critical section.

◆What guarantees do critical sections provide? Only one thread at a time can execute in the critical section. All other threads are forced to wait on entry. When a thread leaves a critical section, another can enter.

◆What are the requirements of critical sections?

1) Mutual exclusion (mutex): If one thread is in the critical section, then no other is

2) Progress: If some thread is not in the critical section, then it cannot prevent some other threads from entering the critical section. A thread in the critical section will eventually leave it.

3) Bounded waiting (no starvation): If some thread is waiting on the critical section, then it will eventually enter the critical section.

4) Performance: The overhead of entering and exiting the critical section is small with respect to the work being done within it.

●How does mutual exclusion relate to critical sections? Mutual exclusion regulates the critical section by permitting only one thread at a time to be within it.

●What are the mechanisms for building critical sections?

Locks: Primitive, minimal semantics, used to build others.

Semaphores: Basic, easy to get the hang of, but hard to program with.

Monitors: High-level, requires language support, operations implicit.

Messages: Simple model of communication and synchronization based on atomic transfer of data across a channel. Direct application to distributed systems. Messages for synchronization are straightforward (once we see how the others work).

Locks

A lock is an object in memory providing two operations.

●What does Acquire do? Prepares to enter a critical section.

●What does Release do? Prepares to leave a critical section.

●What does it mean for Acquire/Release to be atomic? An atomic operation is one which executes as though it could not be interrupted.

●How can locks be implemented?

◆Spinlocks (a thread spins waiting for the lock to be released)

The problem with spinlocks is that they are wasteful. If a thread is spinning on a lock, then the thread holding the lock cannot make progress (on a uniprocessor). How did the lock holder give up the CPU in the first place? Lock holder calls yield or sleep for an involuntary context switch. You only want to use spinlocks as primitives to build higher-level synchronization constructs.

◆Disable/enable interrupts (there is no state associated with the lock)

Like spinlocks, only want to disable interrupts to implement higher-level synchronization primitives. Don’t want interrupts disabled between acquire and release.

Can two threads disable interrupts simultaneously?

◆Blocking (Nachos)

●How does test-and-set work?

◆What kind of lock does it implement? Atomic

●What are the limitations of using spinlocks, interrupts? Spinlocks and disabling interrupts are useful only for very short and simple critical sections.

Spinlocks: Threads waiting to acquire lock spin in test-and-set loop. Wastes CPU cycles. Longer the critical section, the longer the spin. Greater the chance for lock holder to be interrupted.

Interrupts: Should not disable interrupts for long periods of time. Can miss or delay important events (e.G., timer, I/O).Semaphores

●What is a semaphore?

Dijkstra: Semaphores are an abstract data type that provide mutual exclusion to critical sections.

◆What does Wait/P/Decrement do? Block until semaphore is open.

◆What does Signal/V/Increment do? Allow another thread to enter.

◆How does a semaphore differ from a lock? A lock allows only one thread to enter the critical section at a time. A semaphore allows a specified maximum number of threads to be within the critical section at any one time.

◆What is the difference between a binary semaphore and a counting semaphore?

Binary Semaphore (or Mutex Semaphore): Represents single access to a resource. Guarantees mutual exclusion to a critical section.

Counting Semaphore (or General Semaphore): Represents a resource with many units available, or a resource that allows certain kinds of unsynchronized concurrent access (e.G., reading). Multiple threads can pass the semaphore. Number of threads determined by the semaphore “count” (mutex has count = 1, counting has count = N).

●When do threads block on semaphores? When the semaphore is closed as a result of the maximum threads allowed to enter it has been reached.

●When are they woken up again? When the semaphore is open as a result of the amount of threads inside is less than the maximum amount allowed to enter.

●Using semaphores to solve synchronization problems

◆Readers/Writers problem: provides mutex between readers and writers. When a writer has submitted something, all readers can read it.

◆Bounded Buffers problem: There is a set of resource buffers shared by producer and consumer threads.

Monitors

●What is a monitor? A monitor is a programming language construct that controls access to shared data. It is a module that encapsulates the following…

Shared data structures.

Procedures that operate on the shared data structures.

Synchronization between concurrent threads that invoke the procedures

Queues for the condition variables.

A lock for mutual exclusion to procedures (w/ a queue).

Synchronizes execution within procedures that manipulate encapsulated data shared among procedures; Only one thread can execute within a monitor at a time. Relies upon high-level language support

●In what way does a monitor provide mutual exclusion? It protects its data from unstructured access, guaranteeing that threads accessing its data through its procedures interact only in legitimate ways. Only one thread can execute any monitor procedure at any time (the thread is “in the monitor”). If a second thread invokes a monitor procedure when a first thread is already executing one, it blocks, so the monitor has to have a wait queue.

What are the implications in terms of parallelism in monitor?

●How does a monitor differ from a semaphore?

A monitor only allows one thread at a time to act on an object via mutual exclusion. A semaphore can do this as well if it is a binary semaphore. If it is a counting semaphore, then a specified maximum number of threads may act on the critical section.

●How does a monitor differ from a lock?

Lock is used for implementing monitor. Therefore, monitor is of a higher level of abstraction from lock with added capabilities that allow for more control over how threads interact with the resources that the monitor is “locking”. Monitors also provide cooperation; threads cooperate with each other towards a common goal.

http://howtodoinjava.Com/2015/10/21/multithreading-difference-between-lock-and-monitor/

●What kind of support do monitors require?

Language, run-time support.

Condition Variables

●What is a condition variable used for? A condition variable is associated with a condition needed for a thread to make progress once it is in the monitor. Coordinates the execution of threads. Not involved in mutual exclusion. They are not boolean objects, and they are not semaphores. Used by threads as a synchronization point to wait for events. Found inside monitors, or outside with locks.

●Operations

◆What are the semantics of Wait? To release monitor lock, wait for C/V to be signaled. Condition variables have wait queues, too.

◆What are the semantics of Signal? Wake up one waiting thread.

◆What are the semantics of Broadcast? Wake up all waiting threads.

●How are condition variables different from semaphores? Condition variables are stateless (they have no history) and are used to wait for a particular condition to become true. Semaphores are stateful. Both have a wait() and signal(), but are implemented differently.

condition variables:

                    wait(): the thread that is currently in the monitor is blocked. The thread has to have the lock.

                    signal(): if there is a thread waiting, then it will be allowed to enter the critical section. If there is no thread waiting, then nothing will happen.

semaphore:

                    wait(): blocks the thread on the queue. This is after the semaphore has reached its limit in terms of the amount of threads allowed inside.

                    signal(): it has a counter that is used for keeping track of the amount of threads currently in the critical section. It will still increment even if no thread is waiting.

Scheduling

The decision process of choosing a thread from the ready queue.

●What kinds of scheduling is there?

◆Long-term scheduling: Long-term scheduling happens relatively infrequently due to significant overhead in swapping a process out to disk.

◆Short-term scheduling: Short-term scheduling happens relatively frequently. It achieves the goal of minimizing the overhead of scheduling, resulting in fast context switches, fast queue manipulation.

●Components

◆Scheduler (dispatcher): the module that manipulates the queues, moving jobs around from place to place. It is the module that gets invoked when a context switch needs to happen.

●When does scheduling happen?

◆When a job switches from running to waiting.

◆When an interrupt or exception occurs (e.G., I/O completes).

◆When a job is created or terminated.

●What is the goal of a batch system? Strive for job throughput, turnaround time (supercomputers).

●What is the goal of an interactive system? Strive to minimize response time for interactive jobs (program counter).Ath

Starvation

●Starvation: Starvation is a situation where a process is prevented from making progress because some other process has the resource it requires. Indefinite denial of a resource. Resource could be the CPU, or a lock (recall readers/writers).

●Causes

◆Starvation is usually a side effect of the scheduling algorithm. An example would be a high priority process always preventing a low priority process from running on the CPU, or one thread always beats another when acquiring a lock.

◆Starvation can be a side effect of synchronization as a result of a constant supply of readers always blocks out writers.

●Operating systems try to prevent starvation

Scheduling Algorithms

Scheduling algorithm determines which process runs, where processes are placed on queues for the purpose of utilization, throughput, wait time, response time, etc. Algorithms can be combined.

●What are the properties, advantages and disadvantages of the following scheduling algorithms?

◆First Come First Serve (FCFS)/First In First Out (FIFO):

                    advantages: Jobs are scheduled in order of arrival to ready queue, similar to “Real-world” scheduling of people in lines (e.G., supermarket). Typically non-preemptive (no context switching at market). Jobs treated equally, no starvation.

disadvantages: Average waiting time can be large if small jobs wait behind long ones (high turnaround time). You have a basket, but you’re stuck behind someone with bigger basket.

◆Shortest Job First (SJF)

                    advantages: Choose the job with the smallest expected CPU burst; Person with smallest number of items to buy. Provably optimal minimum average waiting time.

disadvantages: Impossible to know size of CPU burst; choosing person in line without looking inside basket/cart. Starvation could be triggered since you cannot make a reasonable guess.

◆Priority

                    advantages: Choose next job based on priority, similar to airline check in for first-class passengers. Can implement SJF, priority = 1/(expected CPU burst). Also can be either preemptive or non-preemptive.

                    disadvantages: Starvation as a result of low priority jobs waiting indefinitely.

◆Round Robin

                    advantages: Excellent for timesharing. Ready queue is treated as a circular queue (FIFO). Each job is given a time slice called a quantum. A job executes for the duration of the quantum, or until it blocks or is interrupted. No starvation. Can be preemptive or non-preemptive.

                    disadvantages: Context switches are frequent and need to be very fast.

◆Multilevel feedback queues (combined algorithm)

                    advantages: A multilevel feedback scheduler actively discriminates in favor of short processes by maintaining separate queues for short (“interactive”) processes and long-running (“CPU-bound”) processes. Jobs in the interactive queue always run first, so jobs in the CPU-bound queue get to run only when no interactive jobs are ready to run.

                    disadvantages: Moving the processes around the queues produce more CPU overhead.

●What scheduling algorithm does Unix use? Why? It uses a Multilevel feedback queue (MLFQ). Its goal is to reward interactive processes over CPU hogs. This minimizes response time of interactive events so that the operating system appears to be more responsive than it really is. This includes anything that is visual and interactive, such as keyboard interrupts. Anything that is CPU-intensive is delayed in favor of these events. They do not finish quantum before waiting for more input.

●What are the conditions for deadlock?

◆Mutual exclusion: At least one resource must be held in a non-sharable mode.

◆Hold and wait: There must be one process holding one resource and waiting for another resource.

◆No preemption: Resources cannot be preempted (critical sections cannot be aborted externally).

◆Circular wait: There must exist a set of processes [P1, P2, P3,…,Pn] such that P1 is waiting for P2, P2 for P3, etc.

●How to visualize, represent abstractly?

Deadlock

Approaches

●Dealing with deadlock

◆Ignore it.

◆Prevent it by making it impossible for it to happen. You must prevent one of the four conditions for deadlock. Scroll up to see these conditions (they are also mentioned below).

                    Mutual exclusion: Making resources sharable (not generally practical).

Hold and wait: Process cannot hold one resource when requesting another. Process requests, releases all needed resources at once.

Preemption: OS can preempt resource (costly).

Circular wait: Impose an ordering (numbering) on the resources and request them in order (popular implementation technique).

◆Avoid it through control over the allocation of resources (have tight control over resource allocation).

Provide information in advance about what resources will be needed by processes to guarantee that deadlock will not happen.

System only grants resource requests if it knows that the process can obtain all resources it needs in future requests.

Hard to determine all resources needed in advance.

Avoids circularities (wait dependencies)

◆Detect and recover from it.

If we don’t have deadlock prevention or avoidance, then deadlock may occur. In this case, we need to detect deadlock and recover from it. To do this, we need two algorithms: One to determine whether a deadlock has occurred, another to recover from the deadlock.