Category: Notes – 2017

One of the main job of an OS is managing the movement of data between input/output (I/O) devices.  This management is performed by the kernel’s  I/O subsystem.

Most I/O devices fit into the following categories:

• storage devices
• transmission devices (Bluetooth, network connections)
• human-interface devices

A controller is an electronic component (as simple as a chip or as complex as a circuit board (aka host adapter) that can operate a port, a bus, or a device.  They may contain a processor, registers, microcode, and private memory.

In order to support a plethora of devices the kernel uses device-driver modules.  The device drivers present a uniform interface between the I/O device controller and the kernel, just as system calls provide a standard interface between user applications and the kernel.

Busses

A device communicates with a computer system by sending signals and data over a wired bus or through the air.  A bus is a set of wires with a rigidly defined protocol that specifies a set of messages that can be sent over the bus.

The system bus connects the CPU with RAM and other busses.  Some of the wires on the system bus are used to send control signals, others send address information, and others send data as shown below.

The image below shows the bus configuration on a motherboard.

 Buses vary in their:

• protocol
• connection method
• signaling method
• signaling speed

A common bus found on many computers is the PCI bus.  It connects fast devices (IDE disk controllers, graphics controller) to the processor-memory subsystem.  Slower devices such as a keyboard, parallels port and serial ports are connected to an expansion bus that is connected to the PCI bus through an expansion bus controller or bridge.

A device connects to a bus through a connection point or port consisting of a set of wire endpoints.  Ports can be external (serial, keyboard) or be on internal component.

Communicating between the Processor and the Controllers

The processor communicates with controllers using one of the following:

1. using special I/O instructions and addresses that trigger the bus controller to select the proper device and to move bits into or out of a controller’s registers.
2. the controller’s device-control registers are mapped to main memory. The processor uses standard data-transfer read and write instructions to perform memory-mapped I/O.

The graphics controller usually uses both: I/O ports for control operations, and memory-mapped I/O for screen contents.

Interrupts

It is most efficient if the controller notifies the CPU when the device becomes ready for service.  An interrupt is the hardware mechanism that allows one component in the computer to notify another that an event has occurred.

Interrupts can be issued for the following events:

• system exception (divide by zero)
• accessing protected memory
• controller raised exceptions (ready for service, service complete, error)
• software interrupt or trap (via library functions to execute system calls)
• managing resources by the kernel (run process in waiting queue since device is now ready)

Essentially, the CPU has an input wire called the interrupt-request line that the CPU reads after every instruction.  When the CPU detects a signal on the line, it performs a state save and jumps to the interrupt-handler routine at a fixed address in memory.  The interrupt handler then

• determines the cause of the interrupt
• performs the necessary processing
• performs a state restore
• executes a return from interrupt instruction to return the CPU to state before the interrupt.

Hundreds of interrupts are sent per second and most computer systems have a more sophisticated interrupt handling mechanism to

• defer interrupt handling during critical processing
• distinguish between high and low priority interrupts

These features are provided by an interrupt-controller.  Most CPUs have two interrupt-request lines:

• unmaskable for high priority events
• maskable for low priority events. The CPU can wait on interrupts on this line.

Device controllers use the maskable line.

The interrupt controller accepts an address (offset) in an interrupt vector table which specifies the type of interrupt.  The table specifies a chain of addresses of interrupt handlers.  When an interrupt occurs, the interrupts in the chain are executed until one is found that can handle the interrupt.

At boot time, the operating system probes the hardware busses to determine which devices are present and installs the corresponding interrupt handlers into the interrupt vector.

A Partial Interrupt Vector Table

0	divide error (handler sends exception to user program)
5	bound range exception
14	page fault (page needed from virtual memory)
16	floating point error
32-255	maskable interrupts

 

Signals are software interrupts that are used to notify a running process that some extraordinary condition has occurred.

For example, if a process attempts to divide by zero, the CPU traps to the kernel with an interrupt and the kernel sends a signal (whose name is SIGFPE) to the process.

A process can handle a signal in 4 ways.  This is called the disposition of the signal.  The disposition can be to

1. Ignore the signal and continue running.
   1. Some signals cannot be ignored or caught.
2. Block the signal. Put signal in a waiting queue.
   1. Used to protect critical regions of the user code.
3. Let a default action defined by the kernel to occur.
   1. See default actions below. Most are terminate.
4. Provide a handler function that is called by the kernel when the signal occurs.
   1. This is called catching the signal.

Signal Generation

Signals can be generated by:

1. The Kernel: Hardware exceptions cause interrupts to the kernel. The kernel interrupt handler may generate a signal to the process that caused the exception.
2. Users: Users can generate signals using terminal keys to interrupt the running process. The default action is to terminate the process.
   • The interrupt key (often CTRL+C or the DELETE key) sends SIGINT
   • The quit key (often CTRL+Q or CTRL+\) sends SIGQUIT

3. Processes: Other processes can send signals from one process to anther by calling the kill function. One restriction is that both process must be owned by the same owner or the sender must be super-user.

Signal Names

Every Signal has a name.

• They all begin with SIG.
• Signal names are defined by positive integer constants in signal.h. or sys/signal.h.
• No signal has a value 0.

SIGABRT	Generated by calling the abort function
SIGALRM	Generated when a timer expired that was set with the alarm function
SIGCHLD	Child process terminates or stops
SIGFPE	Any arithmetic exception such as divide by 0
SIGINT	Generated by terminal driver when we type CTRL+C
SIGQUIT	Generated by terminal driver when we type CTRL+\
SIGKILL	Allows sys admin to terminate a process
SIGSEGV	Process has made an invalid memory reference
SIGTERM	Sent by kill command by default
SIGTRAP	Often used by implementations to transfer control to a debugger when a breakpoint is reached.
SIGUSR1	User defined signal
SIGUSR2	User defined signal
SIGXCPU	Process has exceeded its soft CPU time limit.  (OSX ignores, Linux terminates)

Signal Dispositions

When a program starts up, each signal is assigned a disposition: the action that occurs when it receives the signal.  The disposition can be the kernel’s default action, an action different than the kernel’s default action, or to execute a signal handler.

• A child process inherits its parent’s signal dispositions since it runs in the same address space.
• When a process calls exec, the new memory space does not have access to the parent’s signal handlers (if any), so new handers need to be established (if any).
• If signal handers are to be established they should be done immediately after the process begins running so uncaught signals do not occur.

Below are a list of signals and default actions.

Name	Description	ISO C	Default Action
SIGABRT	abnormal Termination	*	terminate + core
SIGALRM	timer expired		terminate
SIGCHLD	Child process terminate		ignore
SIGFPE	floating point exception	*	terminate + core
SIGINT	terminal interrupt character	*	terminate
SIGQUIT	Terminal quit character		terminate + core
SIGKILL	termination		terminate
SIGSEGV	invalid memory reference	*	terminate + core
SIGTERM	termination	*	terminate
SIGTRAP	hardware fault		terminate + core
SIGUSR1	User defined signal		terminate
SIGUSR2	User defined signal		terminate
SIGXCPU	CPU limit exceeded		terminate + core

Handling Signals

When a program is running and it is sent a signal the following occurs:

• The kernel sets a flag in the process’ state space.
• If the kernel is in an uninterruptable system call or the intended process is blocking the signal,
  • the signal is put in a pending queue.
  • If the signal is blocked, it remains in a pending queue until the signal is either unblocked or the disposition is changed to ignore.

• Else
  • the signal is delivered to the process and the process’ normal execution is temporarily halted and the signal handler (either default or set by the process) is run. After the signal handler is run, the process continues where it left off.

Note: UNIX systems divide system calls into two categories, slow (that can block forever – like waiting for keyboard input, pause, wait, etc.) and the others. Linux and OSX stop slow system calls and restart them after the signal is handled.

What if when the signal was delivered, the process was in the process of allocating memory with malloc?  And what if the signal handler called malloc?  Since malloc keeps a linked list of all of the memory that was allocated, if the process was in the middle of changing that list, then that list could be corrupted.

Unix provides a list of async-signal safe functions that can be used in signal handlers.  These functions don’t use static or global data and don’t call malloc or free.

Most system functions use errno for return values.  When using system functions in signal handlers we should first save errno, use the system functions, then reset errno before exiting the signal handler.

Kill and Raise –

#include <signal.h>
int kill(pid_t pid, int signo)
int raise(int signo)

The kill() function sends a named signal to a process or group of processes.

• if pid > 0, the signal is sent to the process whose process id is pid.
• if pid ==0, the signal is sent to all the processes whose process group id equals the process group ID of the sender and for which the process has permission to send the signal.
• if pid == 1, the signal is sent to all processes on the system for which the sender has permission to send the signal.
• if pid < 0, the signal is sent to all processes whose group ID equals the absolute value of pid and for which the sender has permission to send the signal.

To print the group id of every process running on the system we can use the following command:

$ ps –eo pid,gid

The raise() function sends a signal to itself.  That is, raise(signo) is the same as kill(getpid(), signo)

Alarm and Pause

#include <unistd.h>
unsigned int alarm(unsigned int seconds)
int pause(void)

The alarm() function sets a timer to expire at a future time. When it expires, SIGALRM is generated and sent to the process that calls alarm(). If the program ignores the signal, the default action is to terminate the process.

• Only one alarm exists per process. Subsequent calls reset the timer.
• alarm(0) cancels a previous alarm.

The pause() function suspends the calling process until a signal (any signal) is caught. The only time pause() returns is if a signal handler is executed and that handler returns.

Signal Sets

We need a data type to represent multiple signals.  We’ll use this, for example, to tell the kernel to ignore all the signals in the set.

POSIX.1 defines sigset_t to hold a set of signals and the following functions to initialize the set.

#include <signal.h>
//initialize the set so that all signals are excluded.
int sigemptyset(sigset_t *set)

// initialize the set so that all signals are included.
int sigfillset(sigset_t *set)

All programs that use a signal set must call one of the above functions before using the set.  We can then add and delete individual signals using the following functions.

int sigaddset(sigset_t *set, int signo)
int sigdelset(sigset_t *set, int signo)

We can check if a signal is in a signal set by using the following function.

int sigismember(const sigset_t *set, int signo)

The function sigismember() returns 1 if true, 0 if false, -1 on error.

Signal Masks (Blocked Signals)

A signal mask is a set of signals that are currently blocked by the process.

We can use sigprocmask() to get the current signal mask and modify it.

#include <signal.h>
int sigprocmask(int how, const sigset_t *nset, const sigset_t *oset);

• defined for single threaded processes
• if oset (original set) is non_null, the original signal set (before modification) is returned in oset.
• how values:
  • SIG_BLOCK (curset = oset union nset)
  • SIG_UNBLOCK (curset = oset – nset)
  • SIG_SETMASK (curset = nset)

Pending Signals

#include <signal.h>
int sigpending(sigset_t *set);

sigpending() returns the set of signals that are blocked and pending for the calling process.

Signal Handlers

We can examine and modify a signal action associated with a particular signal with sigaction().

#include <signal.h>
int sigaction(int signo, const struct sigaction *act, struct sigaction *oact);

• signo is the signal number whose action we’re examining or modifying.
• if the act pointer is non-null, we are modifying the action.
• if the oact pointer is non-null, the previous action is returned to oact.

struct sigaction {
      // address of handler or SIG_IGN or SIG_DFL
      void (*sa_handler) (int);

      // more signals to block while running handler 
      sigset_t sa_mask;

      // signal options 
      int sa_flags;        
        
      //alternate handler
      void (*sa_sigaction) (int, siginfo_t *, void *);
};

Example

#include <stdio.h>
#include <signal.h>

static void foo (int signo) {
       printf("Can not terminiate with SIGTERM: permission denied\n");
       return;
}

int main(int argc, char* argv[])
{
       struct sigaction act, oact;
       act.sa_handler = foo;
       sigemptyset(&act.sa_mask);
       act.sa_flags = 0;

       if (sigaction(SIGTERM, &act, &oact) < 0) {
             printf("Error registering signal handler: %s\n", strerror(errno));
             return 1;
       }

       while (1) {
             pause();
       }

       return 0;
}

We can test the handler by running the program in one terminal window and issuing the following command in a second terminal window.

//To test handler
$kill -15 PID

//To kill
$kill -9 PID

SIGUSR1 and SIGUSR2

SIGUSR1 and SIGUSR2 are signals that are not used by the kernel.  When programs want to send signals to one another they often use these signals.  On cs.bridgewater.edu SIGUSR1 has a value of 10 and SIGUSR2 has a value of 12.

 

Basic Hardware –

Registers built into the CPU are generally accessible in one CPU clock tick.  CPU’s can often perform operations on register contents at a rate of one or more per clock tick.

The same can not be said for RAM which is transferred to the CPU registers via the memory bus. Completing a RAM access may take more than one clock tick. This is intolerable since the CPU accesses memory so frequently.  The solution is use cache memory, memory that resides between the CPU and RAM. Here, hardware components fetch blocks of data automatically from RAM and put it in cache for quicker access by the CPU.

To benefit from multi-processing, we need to have code and data for multiple processes loaded in RAM at the same time.

Although RAM is not physically manufactured as a linear array of bytes, the operating system views it as such. The smallest unit of RAM that can be addressed is the byte and each byte in RAM has a unique address, starting with address 0.

Memory (RAM) Access

For the rest of this lecture, when we refer to memory we’ll be referring to RAM.

The OS, operating in kernel-mode, is given unrestricted access to all memory. This allows the OS to

• load a user’s program
• dump a program in case of errors
• perform I/O to and from user memory
• store the process’ states in memory during a context switches
• restore a process’ state during a context switch

For the most part, user-mode processes are not allowed to access memory that was not allocated for it..

Symbolic, Virtual and Physical Addresses

Usually a program resides on a disk as a binary file. When a program is slated to be executed, it is put in a queue. When the kernel finds space for it in memory, a process is create and its code is loaded into memory. It is then put on the scheduler’s ready queue.

Most systems allow a user process to reside in any unused area of the physical memory. So, although the address space of memory starts at address 0, the process will most likely not be loaded at memory address 0.  So, the question is: since the compiler will have no idea where in RAM the code will be loaded, how can it specify an address (e.g. an address for a jump instruction) in the compiled code?

The name of a function in source code can be thought of as an symbolic address – it indicates where the start of a block of code begins.  Since at compile time, the compiler doesn’t know where the process will reside when it is run, the compiler typically binds the symbolic addresses to relocatable virtual address (aka logical addresses), starting at 0 which denotes the beginning of the module. It compiles the code as if the code will be loaded in RAM starting at address 0.  For example, the symbolic address for a function named foo may be at virtual address 14, 14 bytes from the beginning of the code block, wherever that may be. For the time being, let’s assume that the code is loaded in a contiguous block of memory.

When an address in a program is loaded into the CPU, the virtual address must be bound to the physical address space.  The runtime mapping from the virtual address space to the physical address space is performed by the memory-management unit (MMU).

One way to handle this is to store the starting address of the code block for the process. We call this the base address and store it in a register.   For example, suppose the base address for a process is 11,000 and the virtual address for a function named getAddress is 140. Then the physical address of getAddress is computed by:

physical address = base address + virtual address 
10140 = 10000 + 140;

In other words, the value of the base address is added to every virtual address to get a physical address.

Paging

One way to allocate memory is to give a process contiguous memory.  However, as processes terminate and others replace them, memory develops holes. This is called fragmentation.  One way to avoid fragmentation is to use Paging.  Paging is used in most OSs on various hardware devices from mainframes to mobile devices.

To implement paging, physical memory is partitioned into fixed-size blocks called frames.  All frames having the same size (a power of 2) typically between 4 and 8K bytes.  When the kernel allocates memory for a process, it reserves a set of frames for the process to use.  It is possible that this set of frames does not make up a single contiguous area of memory.  The OS keeps track of which frames are allocated to which processes in a frame table.

We previously stated that a compiler can assign virtual addresses in a virtual address space with addresses from 0 to some max value.  With paging, the compiler partitions the virtual address space into segments called blocks, with each block having the the same size as a frame.  Each virtual address created by the compiler is then written as a pair (p, o) where p is the page number and o is the offset from its page boundry.  Each page that an executable has defined is mapped to a physical address frame in a page table.

When the CPU needs to compute a physical address given of a virtual address (p, o) the following occurs:

1. The frame number associated with the page (p) is determined by querying the page table.
2. The frame boundary is computed by multiplying the frame number by the size of each frame.
3. The physical address associated with (p,o) is computed by adding o to the frame boundary.

Example

• Suppose a function named getAddress() has a virtual address given by (7, 100),
• Assume page 7 is mapped to frame 2 in the process’ page table
• Assume also that the frame size is 1024 bytes.

Then the physical address of getAddress is:

(2 * 1024) + 100 = 2048 +100 = 2148

Dynamic Linking

Dynamically linked libraries are system libraries that linked to user programs when the programs are run. This feature is usually used with system libraries that are called frequently.

When a program is loaded, a stub of each dynamically linked library routine is included in the loaded user image. The stub is a small piece of code that indicates how to locate the routine in memory if it already in memory or how to load the routine if it is not in memory.  If the stub indicates that the routine is already in the process’ memory space, it is executed. If the stub indicates the routine is in another program’s address space, the OS will update the processes’ memory address table to allow the routine access to it so it can run.

Notice, that here, a process may in fact, to run a dynamically linked library that is already being stored in memory, share another process’ memory space,  Thus, only one copy of the routine is ever in memory at a given time giving rise to the term shared libraries.

Swapping

A process must be in memory to be executed. Since there may not be enough memory to hold all the currently running processes, a process may be swapped out of memory to a backing store (e.g. a swap partition on a hard drive) and be brought back into memory for continued execution when the CPU is ready for it.

As we mentioned last time, the kernel maintains a ready queue for processes that are ready to run and the scheduler chooses a process to run. The dispatcher then checks to see if the process is in memory or is in the backing store. If in the backing store, the dispatcher swaps out a process in memory for the process in the backing store. It then restores the state of the registers and transfers control to the selected process.

The time to swap out a process can be costly. (2 sec per 100 MB).

What if a process was allocated 1GB of memory?
What if a process that is waiting on I/O that is mapped to the process’s memory is swapped out?

How does an operating system deal with these issues?

• Most OSs only swap if the amount of free memory is below a threshold.
• Swapping is halted when free memory increases.
• Some swap out only a portion of memory, leaving some of the outgoing process’ data in memory
• Mobile devices do not support swapping.  If a user clicks on a new app and there is no memory available, an old app is terminated.