Introduction to Computer Systems

These notes are for a version of the class taught by Prof. Maria Striki in the Spring of 2017.

The textbook for this course is: Silberschatz, Galvin, and Gagne. Operating System Concepts. John Wiley & Sons

Reading assignments are based off of the 9th edition. Any of the 6th, 7th, or 8th edition should be okay.

Grading:

Lecture 1 - 1/17/17

Goals of this course:

This course covers:

Programming Assignments (tentative)

What is an operating system?

Lecture 2 - 1/19/2017

We’re going to look at a computer from an OS designer perspective

Hopefully we will be able to familiarize ourselves with

Topics:

The simple conceptual model of a computer we tend to look at the memory one giant byte array. The CPU is the place where calculations are performed.

All Von Neumann computers follow the same loop:

Instructions are simple. Ex:

How can we represent instructions as numbers?

In a 32-bit architecture you might get 8 bits to store the operator, 8 bits for the operands, and 8 bits for the destination location. Where each 8 bit location can represent a range of 256 values to represent different locations, registers, operations, etc..

First assume a memory cell is 8 bits (1 byte) wide. With this simplified 32-bit architecture we get a maximum total memory size of 256 bytes because we are only allowed \(2^8\) different memory locations. Thus 256 bytes of memory can be accessed. We used 4 bytes per instruction.

The Program Counter

In a naive fetch cycle, we increment the PC by the instruction length (4) after each execute when we assume all instructions are the same length.

Memory Indirection

We can efficiently access array elements by using LOAD instructions which allow us to move data between memory cells.

Conditionals + Looping

These are instructions which modify the program counter

Registers

Architecture ule: large memories are slow. Small ones are fast.

Lecture 3 - 1/24/2017

Symmetric Multiprocessing Architecture

Typically in a multi-CPU architecture there are multiple CPU cores which each have their own registers and own cache, but all share the same main memory

Clustered Systems

Operating System Structure

Transition from User to Kernel Mode

Example

User process executing –> System call –> transfer to kernel mode (trap, mode bit = 0) –> execute system call in kernel mode –> return mode bit = 1 –> return from system call

Process Management

The OS is responsible for:

Memory Management

The operating system is responsible for the following activities in connection with memory management:

Simple Protection Scheme for Memory

All addresses < 100 are reserved for operating system use

Mode register is also provided

Hardware check

Fetch-Decode-Execute Revisited

Fetch

if (PC < 100 && mode_reg == 1) then
    ERROR - user tried to access OS
else
    fetch instruction @ PC

Decode

if (destination_reg == mode && mode_reg == 1) then
    ERROR - user tried to set mode register
....

Execute

if (operand < 100 && mode_reg = 1) then
    ERROR - user tried to access OS
else
    execute instruction

Exceptions

Exceptions occur when the CPU encounters and instruction which cannot be executed (as seen in the example above)

Access Violations

Notice both instruction fetch from memory and data access must be checked.

Recovering From Exceptions

The OS can figure out what caused the exception from the entry point.

Solution: add another register - the PC’. When an exception occurs, save the current PC to PC’ before loading the PC with a new value. Then jump back to the old PC after finished recovering.

Traps

How does a user program legitimately access OS services?

A trap is a special instruction that forces the PC to a known address and sets the mode into system mode.

Unlike exceptions, traps carry a couple arguments to the OS. They are the foundation of the system call

Ex. The machine could include the trap ID in the instruction itself.

Most real CPUs have a convention for passing the trap code in a set of registers.

Lecture 4 - 1/26/2017

Switching from User to Kernel Mode

After a trap it is necessary for the OS to transfer control back from kernel to user mode.

Most machines have a “return from exception” instruction

Interrupts

Interrupts are signals sent to the CPU by external devices - normally IO. They tell the CPU to stop its activities and execute appropriate part of the operating system

The three main types are:

Every OS or machine has a set of code (PC value) set where the code to handle the logic for exceptions/interrupts/traps

I/O

I/O or input output devices are hardware devices that the user can typically use to send signals into the system (to perform an action) or out of the system to perform actions such as notifying a user, or writing to a file.

Keyboards, mice, and monitors are all examples of I/O devices.

A Simple IO Device

How can the CPU access those registers?

Why do we use memory-mapped registers?

Questions to ask:

Q: When does the processor check whether an interrupt has occurred
A: Processor checks for hardware interrupts every cycle (on the fetch stage)

Q How does the OS know if a new byte has arrived? Or how does the OS know when the last byte has been transmitted?

A: Status registers. A status register holds the state of the last IO operation. Our network card has 1 status register.

To transmit, the OS writes a byte into the TX register and sets bit 9 of the status register to 1. When the card successfully transmitted a byte it will set the bit 0 of the status register back to 0.

interrupt Driven IO

Solution: Use interrupts!

Why Poll at All?

The main thing we should worry about is the frequency at which IO is occurring vs the amount of overhead per interrupt.

Direct Memory Access (DMA)

The problem with programmed IO: CPU must load and store all the data into device registers

The data is usually in memory anyways. To address this we need more hardware which allows the device to read and write memory like the CPU.

Programmed IO vs DMA (PIO vs DMA)

Overhead for PIO is less than DMA

Lecture 5 - 1/31/17

Clarifying Interrupts

We can break interrupts into three categories:

Practicality: How to Boot:

Boot protocol:

The boot protocol:

The CPU is hard-wired to begin executing from a known address in memory. This execution in the CPU then loads the BIOS, sometimes referred to as the bootloader. The bootloader is typically stored in EEPROM, a form of electrically erasable ROM. From here it is able to then decide which location in memory (HDD/SSD) to boot from.

OS Human Computer Interaction

The common ways to interact with an OS is either at the command-line or with a visual GUI. Typically OSs are written in C or C++ because of the wide support for C and its history with writing operating systems.

The linux operating system also provides a wide set of libraries which allow programmers and developers to use some of the same system calls that the kernel uses.

Microkernel System Structure

OS Modules

Most modern operating systems implement loadable kernel modules

Layered Systems

A layered system is asystem which is designed such that the lowest layer (layer 0) consists of the hardware. Layers are built on top of one another which use the libraries and calls used by the layers below and grows outwards toward the user interface.

Hybrid Systems

Most modern OSs are not purely modular by design. This is due to challenges faecs by performance security and usability needs. Many designers collaborate together on these systems which results in these hybrid OS architectures.

Runtime Storage Organization

Each variable must be assigned to a storage class. The hierarchy is described below.

  1. Code
  2. Global (static) variables
  3. Stack(Method variables and parameters allocated dynamically)
  4. Dynamically created objects (using the new keyword in OOP)

Lecture 6 - 2/02/2017

Operating Systems Structures

System calls are calls supplied by the OS to interact with the computer hardware. This includes (but is not limited to) file I/O or networking tasks.

Three general methods used to pass parameters to OS system calls

Difference between Program and Process

Runetime Storage Organization

Process Control Block

Each process has per-process state maintained by the OS

Process Creation

Create processes from system calls

The process which creates the new process is called the parent and the new process is the child.

Parent and child processes run in two different memory address spaces

In unix exec() is provided for the new process to run a different program other than a parent (this runs a different set of instructions which may be stored on disk)

Process Death

You can force a process to wait (stop executing instructions using wait() system call)

In Unix you can wait for any process by passing its PID to wait().

Signals

Signals are a type of software interrupt which is provided as OS system calls to programs in order to interrupt programs from running their instruction and run a different set of instructions to handle the signals.

These signals can be used to kill a program, notify the program of message arrival, or of a certain type of event occurring.

Programs can specify handler functions for certain types of signals. When the OS receives a signal intended for a certain process it will check if the process has a hanler function for the signal. If so it will interrupt the program and run the interrupt handler method instructions with the signal parameters.

In this process the CPU has to switch the stack variables because switching to running the handler function requires a context switch into kernel mode to load the instructions, then back to kernel mode to notify the signal has been handled, then back to the user mode instructions.

Processes Summary

OS process management:

Lecture 7 - 2/7/2017

Chapter 3 - Processes

Processes at a minimum contain a single thread which the main program code will run on. Many modern operating systems will allow a single program to run on many different threads under a single process. This information is all tracked by the operating system.

With respect to processes, an operating system is responsible for:

The Process Control Block

Every process is represented in the OS by the process control block (PCB) sometimes it is called a task control block.

It includes the following pieces of information:

Process Switching

The OS must schedule when processes get to execute on certain CPU cores. In a typical system you might have tens or hundreds of processes running at the same time. In order to be able to allow the system to run and respond with as little delay as possible, the OS must constantly switch executing many different processes.

Given a process \(P_0\) running on CPU core 0, the process to switch to another process \(P_1\) is as follows:

  1. Save the state of \(P_0\) to \(PCB_0\) (PCB stands for Process-Control-Block)
  2. Load/Reload the state of \(P_1\) from \(PCB_1\).
    • After some time we switch back
  3. Save state of \(P_1\) into \(PCB_1\)
  4. Reload the state of \(P_0\) from \(PCB_0\)

Sometimes this is referred to as a context switch

Process States

A process can have multiple states:

A process is represented in Unix/Linux by a struct in C

(The book calls it a task_struct )

struct task_struct {
  long state; /* state of the process */
  struct sched entity se; /* scheduling information */
  struct task struct *parent; /* this process’s parent */
  struct list head children; /* this process’s children */
  struct files struct *files; /* list of open files */
  struct mm struct *mm; /* address space of this process */
}

Process Scheduling

A process scheduler will assign available processes to individual CPU cores at a fast rate in order to keep the system executing instructions in order to stay responsive.

When a processes is created it is put into the job queue which is a queue of all process currently running in the system. The processes which reside in main memory and are ready to execute are kept in the ready queue.

There are other queues as well such as the device queue: The list of processes waiting for a particular I/O device.

There are actually two schedulers which are typically used called the long-term scheduler and short-term scheduler or job scheduler and CPU scheduler respectively.

The CPU scheduler will select available processes and place them on the CPU. The long term scheduler will load processes from a disk to main memory where they can then be added to the CPU scheduler.

Process Termination

You can stop a process by using the exit command if on the main thread of a program. Otherwise you should use kill to stop a process with a given PID.

see man kill and man exit on GNU/Linux systems for more detail.

Interprocess Communication

We can uses pipes to allow two processes to communicate between one another.

Issues which we must think about with pipes:

There are ordinary pipes which cannot be accessed from outside the process that created it. Typically, a parent process creates a pipe and uses it to communicate with a child process that it created.

There are also named pipes which can be accessed without having a parent-child relationship.

CPU Scheduling

Processes are scheduled with combinations of CPU bursts and I/O bursts.

IO bound programs are typically composed of many short CPU bursts due to the I/O waiting that needs to occur.

4 possible conditions for a new process to be scheduled

In the 1st and 4th case a new process MUST be scheduled.

Dispatch latency is the time is takes to switch processes. i.e. the time between ending one and starting another

Scheduling Algorithms

NP Complete Problems

CNF, 3-CNF, CLique, Knapsack, Vertex-Cover, Hamiltonian Cycle, Independent Sets

Introduction to Computer Systems - zac blanco