Operating Systems Concepts

Parts of a computer

• RAM, CPU, and I/O Devices are basic parts of a computer.
• The "Zero Page" in RAM contains the interrupt vector, I/O, and BIOS/ROMs if present and starts at memory address 0x00...00.
• The other end of the RAM ends at memory address 0x??...??.

Tools at the Hardware Architecture Level

• The program counter (PC), stack pointer/frame pointer, processor status register, general purpose registers, memory management unit, kernel/user mode, and interrupts/interrupt vector are tools at the hardware architecture level.

Interrupt Vector and Service Routines

• An interrupt vector links devices to service routines.
• A basic instruction cycle of the ALU of the CPU includes fetching the instruction pointed to by the PC, incrementing the PC, and executing the instruction, repeating the cycle.
• The processor status is stored in a special register on each CPU.
• User mode can execute most instructions but not I/O, while kernel mode can execute all user instructions, access special instructions, and control I/O and memory access, also called supervisor mode.
• The interrupt vector in RAM links hardware interrupts with interrupt service routines.

Processes and Memory

• User Space contains processes P1, P2, P3 and P4 and shared memory.
• Interrupts or traps link User Space to Kernel Space
• Kernel Space includes the process table entry, run queue, interrupt service routines, and hardware.

Program Example (Machine Code)

• Assembler code can include instructions like load, incr, store, jmp, decr, rsb, and zero.
• Op Codes include load (0x1), store (0x2), incr (0x3), decr (0x4), jmp (0x5), jsr (0x6), rsb (0x7), and zero (0x8).
• Example Registers: R0, R1, R2, R3, SP, PC

Context Switch and Memory Residence

• A context switch changes from one running program to another "on the fly" and makes sure you change back later.
• To make a context switch the "program state" must be saved and involves saving program counter, general purpose registers, status register and stack pointer
• Each program must be resident in different parts of memory.

Interrupts

• An interrupt includes hardware-generated jump to subroutine (JSR) from external hardware.
• Interrupts are defined through interrupt vector, which resides in physical memory and is an array of function pointers.
• Interrupts may be delayed by masking off.

Interrupt Steps

• During an interrupt, the PC is saved on the stack, the CPU switches to Kernel mode, and the PC is loaded from the vector using hardware ID.
• All registers should be saved during an interrupt and execution continues.
• To return from interrupt, registers must be restored, saved PC value should be restored, and CPU is set to its previous mode.

Critical Sections

• A critical section contains references to data shared between two or more "threads of control".
• One may be an interrupt, there may be two or more processes, and there may be two or more threads
• Must manage the data so all parties can rely on its value and if it is not data may be wrong or corrupted.

Device Drivers

• Modern UNIX-type systems have block, network, and character device drivers.
• Block device drivers read/write blocks (disc, tapes, SD cards, CD-ROM/DVD)
• Network device drivers are local area network (Ethernet, token ring)
• Character device drivers includes serial ports, display/keyboard, mouse, joystick, touchscreen.

Device Driver Functions

• Top Half device driver functions communicate with user and kernel, includes probe, open, close, read and write.
• probe checks for hardware at boot time.
• open is called when a process does an open of a device file.
• close is called when a process does a close() of the file descriptor.
• read transfers data from device to process.
• write queues data for device to output.
• Bottom Half device driver functions handle events using an interrupt service routine which when device generates an interrupt and does the I/O on the hardware.

Circular Queue

• A circular Queue or Ring buffer can have multiple char values in its array.

Critical Sections in Device Drivers

• Interrupts can be masked off to prevent second interrupt from over-writing the first using the spltty() function.
• splx(int prevState) returns the interrupt mask to the previous mask.
• A process can be “put to sleep" until there is space in a buffer using tsleep() for thread
• wakeup() un-blocks all threads that are asleep and have have the given identifier.

Process Execution and Environment

• The execution of a program (an "image") is a process.
• The O/S provides the process with an simplified environment or pseudo-computer.
• The UNIX/Mach process environment includes virtual address space, process context with no direct access to I/O ports

Process Context

• The process table contains an entry for each current process with usually one process table entry per thread.
• Each entry holds information about a process, including process (thread) context, program counter, registers, stack pointer, virtual address space reference, and scheduling information consisting of blocked, runnable, and running states, plus priority and time used.

Synchronization Primitives

• Shared data can be used between processes/threads, requiring critical sections management.
• The two most popular synchronization primitives are mutexes where a critical section only allows 1 process at a time and semaphores which allow N-at-a-time

Mutex Implementation

• Mutexes bracket a critical section so only one process is allowed at a time, using critical_begin() and critical_end()
• Semaphores allow N-at-a-time to section code using signal increments an internal counter and wait until the internal counter > 0.
• Commercial/professional implementations use tsleep() to block processes instead of busy-loops.

Semaphore Producer/Consumer

• Available_sem = QSIZE
• Used_sem = 0
• critical_sem = 1
• Can use SEM_WAIT(&sem) and SEM_SIGNAL(&sem)

Dekker's Algorithm

• Dekker's Algorithm can implement mutual exclusion (in Hardware)

Semaphore Hints

• Semaphores must be properly initialized and must have wait_sem() and signal_sem() defined, generally on the same semaphore.
• The order of wait_sem() operations is important; the order of signal is less so.

Deadlock Condition

• Deadlock happens when processes hold resources then require resources that other processes hold, shown by a cycle in request allocation graph.

Java and Synchronization

• The synchronized keyword can be used on a whole method or a block to provide a critical section.
• The synchronized keyword enables Method locking and block locking.

Interprocess Communication (IPC)

• IPC uses shared memory, semaphores/mutexes, signals, and pipes.
• Shared Memory are blocks of shared process image
• Semaphores/Mutexes are integer data values for flow control
• Signals are a software “interrupt"
• Pipes are an imitation file shared by two processes

Signals

• Signals indicate an important event has happened and include a sequence of events like process A running performing some task when process B sends a signal to process A which interrupts whatever A is doing for signal handler, returning it was doing before
• There is no direct notification to process B that anything has been done

Signals Values

• Signals are integer valued actions similar to interrupts.
• Common signals include:
  • 1 HUP hangup
  • 2 INT interrupt
  • 3 QUIT quit
  • 4 ILL illegal instruction
  • 5 TRAP trace trap
  • 9 KILL kill process
  • 7 BUS bus error
  • 11 SEGV segmentation violation
  • 30 PWR power failure
  • 15 TERM terminate process
  • 10 USR1 user defined #1
  • 12 USR2 user defined #2
• Numbers vary between platform.

Pipes

• A pipe is a file descriptor created between processes.

Scheduling

• The basic process scheduler loop happens when a process exits, waits for I/O, or finishes a time slice.
• The mark process is either runnable or blocked and records why processes get blocked and saves context in the process table entry.
• The scheduler then searches the process table for another runnable process, marking it "running" the restoring context from the table and CPU starts executing the the process from where it left off

Scheduling Algorithms

• Scheduling algorithms include FIFO and SJF.
• FIFO has jobs/es/...repeatedly join the queue this is typically called "round robin" which is usually preemptive.
• SJF uses the shortest job first which is not preemptive.

Scheduling Algorithm Evaluation

• FIFO and round robin are fair since jobs avoid waiting forever.
• SJF is optimal for throughput, will finish more jobs and is run in the shortest time.
• SJF is unfair and impractical for processes and is approximated in processes

Scheduling Algorithms/Queuing Disciplines

• Preemptive schedulers will perform better for interactive systems than non-preemptive schedulers
• Schedulers will bias towards short jobs like updating an editor keystroke
• Operators/users will be able to set/adjust priorities for jobs
• Dynamic priority is updated is updated during context switch
• There's always a tradeoff between the coarse and fine granularity of the time-slices.
  • Coarse gives low overhead/poor interactive response
  • Fine gives higher overhead/better interactive response

Processor Sharing vs FIFO

• If preemption occurs extremely frequently such that each job gets an infinitesimally small time each time it runs, the discipline is called "processor sharing”.
• If the preemption time is infinitely large, the discipline is called FIFO.

Types of tasks

• Batch tasks are insensitive to gaps in runtime.
• Interactive tasks are sensitive to runtime gaps and have lots of I/O.
• Real-time is critical and requires a fixed fraction of CPU/unit time.

Priority Queues

• Priority queues can range from 1 to 3, where 1 is the highest queue
• Some systems vary the priority dynamically, others do not

Unix Process Image

• stack grows downward and is at 0xFFFFFFFF
• text contains executable code
• data contains static data
• symbol table lists symbols, text, constants
• shared with other processes
• text segment.
• dynamic data and bss grows upward
• at 0x00000000

Process Image

• Process image is unique to process.
• Processes can clone using fork(), which copies data, the pointer to shared libs, readonly portions, and text.
• Threads can be created using POSIX which shares most data, copies the stack, and uses local variables.
• threads use co-operative multitasking instead of preemptive multitasking.

Protected Virtual Addressing

• Programs sees its own only virtual addresses, while the kernel sees/manages all address spaces.
• One program cannot interfere with other memory programs.
• Protected virtual addressing avoids large space requirement, divides programs into pages only needed pages are kept in real memory

Process image and logical page

• Process image is sliced into pages independent of data arrangement
• The "page + offset" relates to the logical position of a byte.
• The MMU translates virtual to physical addresses

MMU Address Translation

• Processes are divided into pages (which are like slices of bread)
• VirtualAddress/PageSize = VirtualPageNumber
• VirtualAddress%PageSize = PageOffset Number
• Use virtual page number to look up the frame number for the page number in the page table.
• (FrameNumber x PageSize) + Offset = PhysicalAddress

MMU and Memory

• CPU to MMU to Memory.
• The CPU sends a virtual address to the MMU, which translates it into a physical address and accesses the correct location in memory.

Valid and Invalid Memory

• The hardware page table contains information per page, with page frame number, whether page is "valid", writeability bits R/O or W, and other used bits.
• The in-memory page table contains a disk address if page is out.
• A valid bit indicates whether the page is in memory.
• The top of the stack indicate process stack, bottom of the heap

Paing Disk

• The main memory, physical address, and paging disk also includes hex addresses describing the data stored there.

Examples

• The slide deck goes into multiple examples demonstrating how paged memory works, and the specific steps the operating system goes through to find data using hex.

Page Fault Handling

• "If address is invalid terminate process
• Else If page frame isn't valid, use the frame
• Else choose a page to be replaced
  • If page modified save page on disk
• If required page is saved, read the page in
• Else text or intialized data, read from executable file
• Else initialize to Zeros (Security)
• Set up page table
• Mark RUNNABLE process

Page Fault Timeline

if address mapping fails and causes a page fault, process must be blocked and wait.

• Other processes can run if they can use runnable.
• The page faults need to be managed, as they increase the overall number.
• Faults will always cause some major interruption.
• If no processes are runnable, the CPU will become idle

Virtual Memory

• Paged Virtual Memory depends on the locality principle:
  • Locality principle enables programs to only use a small portion of the total address space needed.
• The set of pages that make up this portion is called the working set.
• The pages that are actually on real memory are called the resident set.

Page Replacement Policy

• The ideal policy to decide which one to remove the page from real memory is the page replacement policy
• The goal of the policy is to ensure the working set is in the resident set.
• The best of deciding and finding the perfect policy is using process strings on a real program to find a process that causes a [page fault](page fault).

This quiz covers fundamental concepts in operating systems, including the instruction cycle, kernel mode, interrupt vectors, user and kernel space interaction, machine code interpretation, and process synchronization using semaphores. It tests understanding of system architecture and resource management.