Computer Architecture: Core Components

Computer Components

• Central Processing Unit (CPU)
• Random Access Memory (RAM)
• Input/Output (I/O) Devices

Actual Physical Memory Organization

• "Zero Page" contains the interrupt vector, I/O, and BIOS/ROMs if present
• Has an address range from 0x00...00
• RAM has an address range Ox??...??

Hardware Architecture Tools

• Program Counter (PC) tracks current instruction
• Stack Pointer/Frame Pointer
• Processor Status Register
• General Purpose Registers
• Memory Management Unit (MMU), for mapping and protection
• Kernel/User Mode
• Interrupts and interrupt vector

Interrupt Vector Function

• Links devices with service routines using function addresses
• Example devices: disk, CD, mouse, keyboard

Basic Instruction Cycle

• Fetch instruction pointed to by the PC
• Increment the PC
• Execute the instruction
• Process repeats

Processor Status

• User mode can execute most instructions, excluding I/O operations
• Kernel mode can execute all user instructions, as well as special instructions and registers for I/O and memory access
• Kernel mode called supervisor mode

Interrupt Vector

• Allocates a special range of locations in RAM
• Links hardware interrupts with interrupt service routines

Processes in Memory

• Consists of a process table entry, hardware kernel space and user space
• Shared memory is accessible from the user space and kernel space
• Requires interrupt signal

Program Execution

• Assembler translates code to machine code and designates a memory address
• Assembler, Machine Code and virtual memory addresses are used
• Registers include R0, R1, R2, R3, SP, and PC
• Op Codes dictate Load, Store, Increment, Decrement, Jump, Jump to Subroutine, Reserve Storage Bytes, and Zero

Context Switch Definition

• Process of changing from one running program to another "on the fly"
• Involves saving the "program state," mainly the program counter, general purpose registers, status register, and stack pointer
• Each program must reside indifferent parts of the memory

Time Chart

• Can be used to visualize context switching
• Program represented by a line
• Interrupts (disk or mouse) represented by vertical bars during the interrupt
• Context switches occur at points where programs switch due to interrupts

Interrupts Explained

• Trigger a hardware-generated jump to a subroutine (JSR)
• Initiated by an external hardware device, not the CPU
• Defined by an interrupt vector, which resides in physical memory as an array of function pointers
• Can be delayed via masking off

Interrupt Steps

• Saves Program Counter (PC) on the stack
• Switches the CPU to kernel (supervisor) mode
• Loads PC from a vector utilizing a hardware ID
• Vector contains the start address of the interrupt service routine
• Saves all registers and continues execution

Return from Interrupt (RTI) Steps

• Restore registers
• Restore saved PC value
• Set CPU to the previous mode

Critical Section Definition

• A code segment that references data shared among multiple "threads of control"
• Threads may include interrupts, processes, or multiple conventional threads
• Data must be managed so all parties can rely on its value
• Failure to manage could lead to incorrect or corrupted data

Critical Section Example

• i++ gets compiled to load R1, #i; incr R1; store R1, #i
• Interrupts must be managed

Device Drivers

• Enable communication between hardware and the operating system
• Divided into three primary types in modern UNIX-like systems: BLOCK, NETWORK, and CHARACTER

Types of Device Drivers

• BLOCK: manage devices that read/write blocks, like disks and tapes
• NETWORK: handle local and remote network communications, such as Ethernet and PPP
• CHARACTER: manage devices that don't fit into the BLOCK or NETWORK categories (serial ports)

Device Driver Top Half Functions

• Interface with user and kernel level processes
• Primary operations include:
• Probe: Checks for hardware during boot time
• Open: Initialized when a process opens a device file
• Generates a file descriptor in user space.
• Close: Called when a process closes a device file to deallocate
• Read function copies data from device to process
• Write function queues the data for the device to output.

Device Driver Bottom Half Functions

• Focuses on event handling
• Manages interrupt service routines triggered when a device generates an interrupt, handling I/O on the hardware

Mutual Exclusion

• Must block interrupt signal to prevent conflicts in updating
• Uses spltty() to prevent the second interrupt from overwriting the first.
• splx(int prev State) returns to a previous interrupt mask
• Processes can be put to sleep if a buffer is full using tsleep() and awoken using wakeup()

Device Driver Skeleton - read

• Character variable Q is declared with a variable size QSIZE
• Sets starting variables for number in queue, start and end position in the queue
• Enters the spltty() critical section to check that a device can be read
• Enters a while loop conditioned upon the list being empty
• Enters an sleept() critical section and then loop back to a new spltty() to check the device again
• Copies the first character from the read queue into a variable and iterates the pointer
• Exits the sleept() critical section

Device Driver Skeleton - intr

• Enters the spltty() critical section to ensure nothing else reads at the same time
• Conditional statement checks that the queue is not full
• Exits the spltty() critical section and exits
• If the queue isn't full it adds the first available character from the specified device
• Iterates the end of the queue
• Exits the critical section
• Signals to wakeup that data has been receieved

Running Programs in UNIX/Mach

• Execution of a program (image) is a process
• O/S provides a simplified pseudo-computer environment for program execution
• Process runs without direct access to I/O Ports
• Access through kernel calls
• Process has a virtual (simplified) address space and a process context
• UNIX/Mach process environment consists of registers, stack and other data
• Managed through process table entry

Process Table Contains

• Context (thread)
• Program counter
• Registers for general/special purposes
• Stack pointer
• Virtual address space reference
• Scheduling information, like blocked, runnable, or running status, priority and time used

Synchronization Primitives

• Handle data shared between processes/threads
• Manages critical sections that prevent data conflicts.
• Two main are mutex and semaphores

Mutex Definition

• Brackets a critical section to allow only one process at a time
• Prevents race conditions and ensures data integrity

Semaphore Definition

• Allows "N" processes to access a critical section at once
• Used to control access to resources

Semaphores: "signal" function

• Increments the internal counter of the semaphore

Semaphores: "wait" function

• Waits until the internal counter is greater than zero, and then decrements the counter

Mutex Synchronization

• Producer adds entries to the queue, and consumer removes them
• Ensures that two processes aren't writing to the same memory at the same time

Implementing Mutual Exclusion

• Achieved in hardware using special instructions like TEST_AND_SET
• These ensure indivisible operations, preventing race conditions
• Critical_begin sets the mutexFlag, and the critical_end resets it

Dekker's Algorithm

• A software approach to mutual exclusion for two processes
• Uses "need" flags and a "turn" variable to decide which process can enter the critical section

Semaphore Implementation with Mutexes

• Critical sections are used with signal and wait
• Professional implementations use tsleep() to block busy loops

Semaphore Producer/Consumer Example

• Uses two semaphores, available_sem and used_sem, to manage the buffer
• Critical sections are protected with semaphore to avoid race conditions

Co-Operating Sequential Processes

• Semaphores can be used to coordinate two sequential streams
• Semaphore_t U and Semaphore_t D
• SEM_WAIT and SEM_SIGNAL are used

Semaphore Hints

• Semaphores must be properly initialized
• Always work from the definitions of wait_sem() and signal_sem()
• A wait_sem should have a corresponding signal_sem on the same semaphore
• The order of wait_sem operations is important, but the order of signal is less so

Deadlock Cause

• Occurs when processes hold resources and require resources already held by other processes
• Can be detected by the presence of a cycle in the resource allocation graph

Java synchronized Keyword

• Is used on a whole method or code block to provide a critical section
• Ensures that only one thread can access the synchronized section at a time

Inter-Process Communication (IPC) Mechanisms

• Shared Memory: Shared process image
• Semaphores/Mutexes: Integer values for flow control
• Signals: Software "interrupts"
• Pipes: Imitation file shared by processes

Signals Explained

• Signals can indicate an important event
• Process A runs, and Process B sends a signal
• Process A suspends and calls a signal handler
• Process A returns
• Process B sees no direct notification

Signal Values

• Represented by integers, similar to interrupts
• Include HUP (hangup), INT (interrupt), QUIT (quit), ILL (illegal instruction), TRAP (trace trap), and KILL (kill process)
• Some signals may vary between platforms
• Can use kill -l command to know current configuration

Signal Example

• Example uses #include <signal.h>
• signalHandler gets defined
• signal command registers the handler

Pipes Explained

• A pair of file descriptors shared between processes
• Buffer is common to both processes
• Buffer not stored in the filesystem but in memory

Basic Process Scheduler Loop

• When a process can no longer run, it is marked Runnable or Blocked
• Save process context in the process table entry
• A new process is then found to be Runnable and is executed
• The state is then restored

Scheduling Algorithms

• Queuing Discipline
• Determines the order in which processes are executed

FIFO (First-In-First-Out)

• If processses repeatedly join the queue its called "round robin"
• Process is typically preemptive
• Processes handled in order of arrival.

SJF (Shortest Job First)

• Prioritizes the shortest jobs first
• May jump to the head of the queue
• It is nonpreemptive

Scheduling Algorithm Considerations

• FIFO & round robin are generally considered fair
• This is due being incapable of being stuck waiting forever
• SJF provides the largest throughput due to always running the fastest task
• SJF may be considered unfair due to processes being starved though

Scheduling In General

• Preemptive schedulers will perform better than non-preemptive and are required for interactive systems
• Schedulers will normally bias towards short jobs
• Operators/users can manually change by using the command nice(1)
• Always a trade-off between coarse and fine granularity

Scheduling Implementations

• Preemption occurs frequently results in 'processor sharing'
• The discipline is therefore FIFO

Batch Task

• Insensitive to runtime gaps
• Seeks overall task completion

Interactive Task

• Sensitive to runtime gaps
• Contains many I/O operations

Real-time Task

• Critically sensitive to runtime gaps
• Has a fixed fraction of CPU/unit requirements

Priority Queues

• VMS/Windows
• Some systems vary the priority dynamically; others do not