Midterm review PDF

Preview

Summary

Midterm Notes...

Description

CS354 Midterm Review FE Introduction: Overview of Operating Systems What is an Operating System (OS)? It is a system program that sits between the hardware and application programs The program starts running at boot time Who boots up the OS? BIOS self-check Determining boot device First Sector loaded and executed Partition-specific boot loader leaded and executed OS loaded and executed

What does an OS do? Provides common services to all applications: Program Execution Printing Windowing File Access Resource Allocation Mutlitasking: Multiple processes run at the same time Security: Integrity, Confidentiality, Availability Ex. a user cannot see files of other users Part of the "Trusted Computing Base"

What does an operating system offer? Reliability Each program runs inside a sandbox . If the process does something wrong like writing to an invalid memory, it recieves notification. Processess will not get out of the sandbox. The OS continues to run. Fairness Access to resources has to be fair across users with the same priority Support For Multiple Users It allows running multiple users in the same machine simultaneously

FF Architecture: Architecture of a computer ("CS250 in a nutshell") Processors Each CPU has a specifc set of instructions All CPUs Contain: General Registers inside to hold key variables and temporary results Special Registers visible to the programmer Program Counter contains the memory address of the next instruction to be fetched Stack Pointer points to the top of the current stack in memory Control Registers (Ex. CRO-CR4 in x86) PSW (Program Status Word) contains the condition code bits which are set by comparison instructions, the CPU priority, the mode (user and kernal) and various other control bits

How Processors Work (Execute Instructions) CPU Cycles Fetch (from mem) --> decode --> execute Program Counter (PC) When is PC changed? Pipeline: fetch n+2 while decode n+1 while execute n Two Modes of CPU (Why?) User mode (a subset of instructions) Priveleged Mode (All Instructions) Trap Special Instructions

Memory Access Memory Read: Assert address on address lines Wait until data appears on data line Much slower than CPU! How many mem access for one instruction? Fetch Instruction Featch Operand (0, 1, or 2) Write Results (0 or 1)

CPU Cache Cache Hit: no need to access memory Cache Miss: Data obtained from mem, possibly update cache

Memory Internal CPU Registers

As fast as CPU Cache Memory

Cache Hit and Miss RAM (Random Access Memory) Disk

Magnetic Disks, CD-ROM, DVD, etc Cylinder, track Non-Volatile Memory

ROM (Read Only Memory) Programmed at the factory and can't be changed EEPROM (Electrically Erasable ROM) Flash RAM Can be erased and re-written Volatile Memory

CMOS holds current time and date

I/O Devices Controller

Example: Disk Controller Controllers are complex converting OS request into device parameters Controllers are often small embedded computers

Device

Fairly simple interfaces and standardized IDE (Integrated Drive Electronics) - standard disk type on Pentiums and other computers Device Driver

Needed since each type of controller may be different Software that talks to a controller, giving it commands and accepting responses Each controller manufacturer supplies a driver for each OS it supports How Device Driver talks to controller Busy Wait Interrupt DMA (Direct Memory Access)

Bus Pentium Systems have eight buses: Cache VESA local (GPU) mem PCI (Peripheral Component Interconnect) SCSI (Small Computer System Interface) USB (Universal Serial Bus) IDE (Integrated Drive Electronics) ISA (Industry Standard Architecture)

00 Program structure Virtual Address Space of a Program A program sees virtual memory as an array of bytes that goes from address 0 to 232 - 1 (0 to 4GB - 1) That is assuming a 32-bit architecture

Memory Sections The virtual address space is organized into sections: Text

Instructions that the program runs Data

Initialized global variables BSS

Uninitialized global variables. They are initialized to zeroes (saving object file size) Heap

Memory returned when calling malloc/new It grows upwards (from low to high addr) Stack

It stores local variables and return address It grows downwards (from high to low addr) Each Section has different permissions: read/write/execute or a combination of them Dynamic Libraries

Libraries shared with other processes Each Dynamic library has its own text, data, and BSS Each run the of the program (process) has its own view of the memory that is independent of each other This view is called the Virtual Address Space of the process If a process modifies a byte in its own address space, it will not modify the address space of another process

Building a Program The programmer writes a program hello.c The preprocessor exapnds #define, #include, #ifdef etc preprocessor statements and generates a hello.i file The compiler compiles hello.i, optimizrs it and generates an assembly instruction listing hello.s The assembler (as) assembles hello.s and generates an object file hello.o The linker puts together all object files as well as the object files in static libraries The compiler (cc, gcc, or llvm) by defualt hides all intermediate steps. Use compiler options to run each step independtly The linker takes the definitions in shared libraries and verifies that all required symbold (functions and variables) are completly satisfied If a symbol is not defined in either the executable or shared libraries, the linker gives and error Static Libraries (.a files) are added to the executable. Shared Libraries (.so files) are not added to the executable file

Loading a Program The loader is part of the OS to prepare a process for an executable program Reads the executable file header to determine size of text and data segments Creates address space large enough for text and data Copies instructions and data from executable file into memory Copies parameters to the main program (argc, argv) onto the stack Initialize to a startup routine __start that in turn calls the main() routine. When the main routine returns, the startup routine terminates the program by making system call (executed by the OS) exit()

Static and Shared Libraries Shared Libraries are shared across different processes There is only one instance of each shared library for the entire system Static Libraries are not shared There is an instance of a static library for each process

01 OS Interface Kernal and User Mode Kernal Mode When the CPU runs in this mode: It can execute any machine instructions such as: LMSW, SMSW (load/store Machine Status Word register) MOV DBn, MOV CRn (move to debug/control registers) LSL (load stack limit, adjusting stack space available to a process) HLT (halt the CPU) It can access/modify any location in memory It can access and modify any register in the CPU and any device The OS kernal instructions run in kernal mode User Mode When the CPU runs in this mode: The CPU can use a limited set of instructions The CPU can only modify the sections of memory assigned to the process running the program The CPU can access only a subset of registers in the CPU and it cannot access registers in devices There is a limited access to the resources of the computer The user processes run in user mode When the OS boots, it starts in kernal mode In Kernal mode, the OS sets up all the interrupt vectors and initializes all the devices Then it starts the first process and switches to user mode In user mode, it runs all the background system processes (daemons or services)

Then it runs the user shell/window manager User programs run in User mode The programs switch to kernal mode to request OS services (through the sytem call interface) Also user programs switch to kernal mode when an interrupt is raised They switch back to user mode when interrupt returns The interrupt handling code (part of OS) is executed in kernal mode The interrupt vector can be modified only in kernal mode Most of the CPU time is spend in User mode (overhead of mode switch and context switch)

UNIX Interface

UNIX Kernal

Seperation of user/kernal mode is used for: Security The OS calls in kernal mode make sure that the user has enough privileges to run that call Robustness If a process writes to an invalid memory location, the OS will kill the program, but the OS continues to run. A process crash will not crash the OS A bug in user mode causes program to crash, but the OS still runs. A bug in the the kernal mode may cause OS and system to crash Fairness OS enforces fair access among user processes

Interrupts An interrupt is an event that requires immediate attention. In hardware, a device sets the interrupt line to high When an interrupt is recieved, the CPU stops whatever it is doing and it jumps to the inturrupt handler for the specific interrupt After executing the handler, it returns to the same place where the interrupt happened and the program continues Examples: Mouse, Key Press, Network Packet Interrupt Vector : Array of pointers that point to the different interrupt handlers for each type of interrupt

Steps of Handling an Interrupt 1. 2. 3. 4.

The CPUT saves the program counter and registers in execution stack CPU looks up the corresponding interrupt handler in the interrupt vector CPU jumps to interrupt handler and runs it CPU restores the registers and return back to the place in a program that was previously interrupted. The program continues execution as if nothing happened 5. In some cases it retries the instruction that was interrupted (E.g., Virtual memory page fault handlers)

Interrupts and Kernal Mode Interrupt must be handled in kernal mode. Why? An interrupt handler must read device/CPU registers and execute instructions only available in kernal mode Interrupt vector can be modified only in kernal mode (security) Interrupt vector initialized during boot time; modified when drivers added to system

Types of Interrupts 1. Device Interrupts Generated by devices when a request is complete or an event that requires CPU attention happens 2. Math Exceptions Generated by the CPU when there is a math error Divide by zero 3. Page Faults Generated by the MMU (Memory Management Unit) that converts Virtual memory addresses to physical memory addresses Invalid address: interrupt prompts a SEGV signal to the process Access to a valid address but the page is not mapped. This causes the CPU to load the page from disk Invalid permission (i.e. writing on a read only page) causes a SEGV signal to the process 4. Software Interrupt Generated by software with a special assembly instruction. This is how a program running in user mode requests operating systems services

System Calls System calls are the way user programs request services from the OS System calls use software interrupts Examples: open() read() write() fork() execve() System calls define the OS's API from the user program's point of view Only operations that need to be executed by the OS in kernal mode are part of the system calls Functions like sin(x), cos(x) are not system calls Somce C function like printf(s) run mainly in user mode but call write() to flush buffers malloc(size) runs mostly in user mode but calls sbrk() or mmap() to extend the heap libc() provides wrappers for the system calls that eventually generate the system calls

02 OS Organization, Xinu lists and queues Interface to System Services Appears to operate like a function call mechanism OS makes set of "functions" available to applications Application supplies arguments using standard mechanism Application "calls" one of the OS functions Control transfers to OS code that implements the function Control returns to caller wehen function completes Requires special instruction to invoke OS function Moves from application address space to OS Changes from application mode to privilege level to OS Terminology used by various vendors: System Call

Trap Supervisor Call

Concurrent Processing Fundemental concept that dominates OS design Real concurrency achieved by hardware I/O devices operate at same time as processor Multiple processors/cores each operate at the same time Apparent concurrency achieved with multitasking (multiprogramming) Multiple programs appear to operate simultaneuosly Operating system provides the illusion Each process requires its own: Runtime stack for function calls Storage for local variables Copy of arguments A process may have private heap storage as well

Multilevel Vs. Multilayered Organization Multilayer Structure Visible to user as well as designer Each layer uses layer directly beneath Involves protection as well as data abstraction Examples: Internet Protocal Layering MULTICS layered security structure Can be inefficient Multilevel Structure Form of data abstraction Used during system construction Helps designer focus on one aspect at a time Keeps policy decisions independent Allows given level to use all lower levels Efficient

Unified List Storage in Xinu All lists are doubly-linked Each node stores a key as well as the process ID, even though the key is not used in a FIFO list Each list has a head and tail, the head and tail nodes have the same shape as other nodes Non-FIFO lists are ordered in descending order

- They key value in a head node is the maximum integer used as a key, and the key value in the tail node is the minumum integer used as a key 03 Runtime system General and Special Purpose Registers General-Purpose Registers Local storage inside processor Hold active values during computation Saved and restored during subprogram invocation

Special-Purpose Registers Located inside the processor Values control processor actions

Bus Operations Only two basic operations supported Fetch Store Fetch

Processor places address on bus Processor uses control line to signal fetch request Device senses its address Device puts specified data on bus Device uses control line to signal response Store

Processor places data and address on bus Processor uses control line to signal store request Device senses its address Device extracts data from bus Device uses control line to signal data extracted

Transfer Size and Interrupts Transfer size depends on device Serial Device transfers one character Disk Controller transfers one block (e.x. 512 bytes) Network interface transfers one packet Large transfers use Direct Memory Access (DMA)

Runtime Storage Model in Xinu Single shared copy of: Text segment Data Segment BSS Segment One Stack segment per process Allocated when process created Each process has its own stack pointer

04 Process scheduling and management Information Kept In Process Table For each process: Unique process identifier Owner Scheduling Priority Location of code and all data (including stack) Status of completion Current Program Counter Current values of registers If a heavyweight process contains multiple threads, keep for each thread: Owning process Thread's scheduling priority

Location of the thread's stack Status of completion Current Program counter Current values of registers

Xinu Process Model Simplest possible scheme Single-user system One global context Once global address space No boundary between OS and applications All Xinu processes can share data

Process States Current Ready Waiting Recieving Sleeping Suspended

Schedular Key part of the process manager Chooses next process to execute Implements a scheduling policy Changes information in the process table Calls context switch to change from one process to another Usually optimized for high speed

05 Process synchronization Interrupt Mask Hardware mechanism that controls interrupts Internal machine register OS Can: Examine current interrupt mask Set interrupt mask to prevent interrupts Clear interrupt mask to allow interrupts

06 Inter Process Communication Synchronous vs. Asynchronous Interface Synchronous Interface Blocks until the operation is performed Easy to understand and program Extra processes can be used to obtain asynchrony Asynchronous Interface Process starts an operation Initiating process continues execution Notification arrives when operation completes

Polling can be used to determine status...