This is an introductory course on operating systems. The topics will include the basic concepts of operating systems, process and threads, inter-process communications, process synchronization, scheduling, memory allocation, page and segmentation, secondary storage, I/O systems, file systems, and protection. It contains the key concepts as well as examples drawn from a variety of real systems such as Microsoft Windows and Linux.

• Introduction

  • learning goals
    • fundamental principles, strategies, and algorithms
      • for design & implementation of operating systems
    • analyze & evaluate OS functions
    • understand basic structure of OS kernel
      • and identify relationship between various subsystems
    • identify typical events / alerts / symptoms
      • indicating potential OS problems
    • design & implement programs for basic OS functions and algorithms
  • course overview
    • overview (4)
      • basic OS concept (2)
      • system architecture (2)
    • process and thread (12)
      • process and thread (4)
      • CPU scheduling (4)
      • synchronization and synchronization example (2)
      • deadlock (2)
    • memory and storage (8)
      • memory management (2)
      • virtual memory (3)
      • secondary storage (1)
      • file systems and implementation (2)
    • protection (1)
      • protection (1)
      • security - optional

• Operating system components

  • users: people, machine, other computers / devices
  • application programs: defining ways how system resources are used
    • to solve user problems
    • e.g. editors, compilers, web browsers, video games, etc.
  • operating system: controls & coordinates use of computing resources
    • among various application & different users
  • hardware: basic computing resources: CPU, memory, IO devices

• Operating system introduction

  • OS: a (complex) program working as intermediary between: user-applications and hardware
    • iOS, MS Window, Android, Linux, etc.
  • OS goals:
    • execute user programs & solve user problems easier
    • make computer system: convenient to use
    • manage & use computer hardware efficiently
  • user view:
    • convenience, easy of use, good performance & utility
    • user: doesn't care about resource utilization & efficiency
  • system view:
    • OS: resource allocator & control program
  • no universally accepted definition, but:
    • "everything vendors ships when you order an OS"
  • OS as a resource allocator
    • managing both SW & HW resources
    • decides among conflicting requests: for efficient & fair resource use
  • OS as a control program
    • controls: execution of programs, prevent errors & improper use of computer
  • OS: manages & controls hardware
    • helps to facilitate (user) programs to run

• OS breakdown

  • kernel: one program always running on computer
    • provides essential functionalities
  • middleware: set of SW frameworks: provide additional services to app dev
    • e.g. DB, multimedia, graphics
    • popular in mobile OS
  • all else:
    • system programs
    • application programs
  • OS includes:
    • always running kernel
    • middleware frameworks: for easy app development & additional feature
    • system programs: aid in managing system while running

• Operating system tasks

  • depends on: PoV (user vs. system) and target devices
  • shared computers (mainframe, minicomputer)
    • OS: need to keep all users satisfied
    • performance vs. fairness
  • individual systems (e.g. workstations) with dedicate resources
    • performance > fairness; may use shared resource from servers
  • mobile devices: resource constrained
    • target specific user interfaces (touch screen, voice detection)
    • optimized for usability & battery life
  • computers / computing devices w/ little-no UI
    • embedded systems: present within home devices, automobiles, etc.
      • run real-time OS
    • design: run primarily without user intervention

• Computer system organization

  • one or more CPU cores & device controllers: connected through common bus
    • providing access to shared memory
  • goal: concurrent execution of CPUs and devices
    • compete for memory cycles w/ shared bus

• Von Neumann architecture: composition

  

  • CPU: contains ALU & processor registers
    • programmer counter (PC)
    • accumulator (AC)
    • memory address register (MAR)
    • memory data register (MDR)
  • control unit: contains
    • instruction register (IR)
    • program counter (PC)
  • memory: w/ data and instructions
    • as well as caches
  • external mass storage / secondary storage for more space
  • input-output mechanism

• Von Neumann architecture

  • steps
    • fetch instruction
    • decode instruction
    • fetch data
    • execute instruction
    • write back (if any)
  diagrams

  • 
  • 

• IO

  • IO device & CPU: execute concurrently & asynchronously
    • ~= event driven?
  • each device controller: in charge of a particular device
    • w/ local buffer
    • responsible for moving data between:
      • peripheral devices it control
      • & local buffer storage
    • IO operation: from device -> local buffer of controller
  • CPU: moves data from/to main memory $\rightleftarrows$ local buffers
    • typically: for slow devices (keyboard, mouse)
  • DMA controller: to move data for fast devices (e.g. disks)
  • device controller: informs CPU operation termination (completion / fail) by: interrupt
    • i.e. requires CPU attention
    • for input: i.e. data is available in local buffer
    • for output: i.e. IO operation has been completed

• Interrupt cycle

  • 

• Interrupt timeline

  • CPU & device: execute concurrently
  • IO device: may trigger interrupt by sending CPU a signal
  • CPU handles interrupt (i.e. transfer control to interrupt handler)
    • then returns to interrupted instruction
  • 

• Interrupt functions

  • interrupts: widely used in modern OS systems
    • for asynchronous event handling
    • e.g. device controllers hardware faults
    • all modern OS: interrupt-driven
      • hundreds of interrupts occur per sec
        • CPU: extremely fast ($<1\text{ns}$)
  • interrupt: transfers control to:
    • interrupt service routine / interrupt handler
    • part of kernel code; OS runs to handle a specific interrupt
  • also: implements a interrupt priority levels
    • high-priority interrupt: can preempt execution of low-priority
  • trap / exception: SW-generated interrupt caused either by:
    • error (e.g. div by 0) / user request (e.g. some syscall)

• Bits & Units

  • bit: basic unit of computer storage (0/1)
  • byte: 8 bits
    • smallest chunk of storage from most computers
  • word: computer architecture's native unit of data
    • nowadays: mostly 1 word = 8 byte = 64 bits
  • larger units
    • kilobyte $\text{KB}=2^{10}\approx 10^3$ bytes
    • megabyte $\text{MB}=2^{20}\approx 10^6$ bytes
    • gigabyte $\text{GB}=2^{30}\approx 10^9$ bytes
    • terabyte $\text{TB}=2^{40}\approx 10^{12}$ bytes
    • petabyte $\text{PB}=2^{50}\approx 10^{15}$ bytes
  • often rounded up in $10^x$ for computer manufacturers
    • however, network measurements: given in bits, not bytes

• Storage hierarchy

  • storage systems: organized in hierarchy
    • w/ speed, cost / unit, capacity, and volatility (non-volatile vs. volatile)
    • usually, higher: faster & more expensive, but smaller & more volatile
  • 

• Memory

  • main memory: directly accessible by CPU
    • only large storage media to be so
    • volatile, often random-access memory
      • in the form of: dynamic ram (DRAM)
    • basic operations: load & store to specific memory address
      • that is: byte addressable
      • each addr: refers to 1 byte in memory
  • computers: also use other forms of memory

• Second storage

  • i.e. extension of main memory
  • w/ non-volatile storage capacity
    • data: stored permanently
  • most common such storage:
    • hard disk drives (HDD)
    • nonvolatile memory (NVM) devices
    • provides storage for both programs & data
  • generally: two types
    • mechanical
      • HDDs, optical disks, holographic storage, magnetic tape
      • generally larger & less expensive
    • electrical
      • flash memory, SDD, FRAM, NRAM
      • electrical: often referred as NVM
      • typically costly, smaller, more reliable & faster

• Caching

  • important: performed at many levels in computers
    • for memory, address translation, file blocks, file names (freq. used), file dir, network routes, etc.
  • ⭐ fundamental idea: a subset of information: copied from slower to a faster storage temporarily
    • i.e. make freq. used case: faster
  • access: first check whether information is inside cache
    • hit: inside cache; information can be directly retrieved (fast)
    • miss: not inside cache; data copied from slower storage to cache, then used (slow)
  • cache: usually much smaller than storage (memory) being cached
    • cache management: cache size & replacement policy
    • major criteria: cache hit ratio; percentage of hit per access
  • important measurement
    • $\text{average access time}=(\text{hit rate}\times \text{hit time})+(\text{miss rate}\times \text{miss time})$

• Locality: principle below caching

  • temporal locality (in time)
    • recently accessed items: likely to be accessed again
  • spatial locality (in space)
    • contiguous blocks (i.e. neighbor of recently accessed): likely to be accessed shortly
  • without locality pattern (i.e. all item: accessed w/ equal prob): cache can't work
  • 

• Cache levels

  

  • range of timescales

    name	time (ns)
    L1 cache reference	0.5
    branch mispredict	5
    L2 cache reference	7
    mutex lock/unlock	25
    main memory reference	100
    compress 1K bytes w/ Zippy	3,000
    send 2K bytes w/ 1 Gbps net	20,000
    read 1 MB sequentially from memory	250,000
    round trip within same data center	500,000
    disk seek	10,000,000
    read 1 MB sequentially from disk	20,000,000
    send packet CA->Netherlands->CA	150,000,000

• IO subsystem

  • OS: accommodate wide variety of devices
    • w/ different capabilities, control-bit def., protocol to interact
  • OS: enables standard, uniform way of interaction w/ IO
    • involving abstraction, encapsulation, and software layering
  • encapsulate device behavior in generic classes
    • each: accessed through interface: standardized set of functions
  • one purpose of OS: hide gap between hardware devices from users
    • abstraction & encapsulation!
  • IO subsystem: responsible for
    • memory management of IO
      • buffering: storing data temporarily while being transferred
      • caching: storing parts of data in faster storage for performance
      • spooling: overlapping / queuing of one job's output as input of other jobs
        • typically: printers
    • general device-driver interface
    • driver for specific hardware devices

• Direct memory access

  • programmed IO: CPU running special IO instructions
    • moving byte one-by-one
    • between memory & slow devices (keyboard & mouse)
  • for fast devices: programmed IO must be avoided
    • instead, use direct memory access (DMA) controller
    • idea: let IO device and memory transfer data directly
      • bypass CPU!
    • CPU / OS initialize DMA controller, and it's now responsible for moving data
  • benefit: CPU freed from slow IO operations
  • OS writes DMA command block into memory
    • preparation
      • source & destination addresses
      • read || write mode
      • no. of bytes to be transferred
    • execution
      • write location of command block to DMA controller
      • bus mastering of DMA controller
        • i.e. grab bus from CPA
    • send interrupt to CPU for signaling completion
  DMA transfer diagram

  

• Single processor system

  • traditionally: most system w/ single processor, single CPU, single processing core
    • core: executes instructions & registers for storing data locally
    • processing core / CPU: capable of executing a general-purpose instruction set
  • such systems: w/ other special-purpose processors
    • e.g. device-specific processors (for disk) and graphic controllers (GPU)
    • those: w/ limited instruction set
      • not executing instructions from user processes

• Multiprocessor system

  • modern computer (mobile to servers): dominated by multiprocessors system
    • traditionally: 2+ processors and each w/ single-core CPU
    • speedup ratio: less than no. of processors
      • due to overhead - contention for shared resources
      • e.g. bus / memory
  • multiprocessor advantage
    • increased throughput: more computing capability
    • economy of scale: share other devices (e.g. IO devices)
    • increased reliability: graceful degradation / fault tolerance
  • two types of multiprocessor systems
    • asymmetric multiprocessing
      • master-slave manner
      • master processor: assign specific tasks to slaves
        • master: handles IO
    • symmetric multiprocessing
      • each processor: performs all tasks
        • including OS functions & user processes
      • aka SMP
      • each processor: w/ own set of registers and private || local cache
        • but all processors: share physical memory via system bus
      • 
  • multicore: multiple computing cores inside a single physical chip
    • faster intra-chip communication than inter-chip
    • using significantly less power: important for mobile / laptops
    • 

• Non-Uniform Memory Access (NUMA)

  • 
  • adding more CPU to multiprocessor: may not scale / help
    • as system bus can be a bottleneck
  • alternative: provide each CPU local memory
    • accessed via small & fast local bus
  • CPUs: connected by shared system interconnect
    • all CPU: share one physical memory address space
  • such approach: non-uniform memory access (NUMA)
  • potential drawback
    • increased latency when CPU must access remote memory across system interconnect
      • e.g. memory of another CPU?
    • scheduling & memory management implication

• Computer system component

  • CPU: hardware executing instructions
  • processor: physical chip containing one or more CPUs
  • core: basic computation unit of CPU
    • or: component executing instructions / registers for storing data locally
  • multicore: including multiple computing cores on a single physical processor chip
  • multiprocessor system: including multiple processors

• OS structure

  • 2 common characteristics exist in all modern OS
  • multiprogramming: for efficiency
    • aka batch system
    • single program: can't keep CPU & I/O busy
      • thus multi-program: organize multiple jobs
      • s.t. CPU will not stay idle
    • in mainframe PC: jobs being submitted remotely & queued
      • selected & ran via jab scheduling: load into the memory
  • timesharing: logical extension of multiprogramming
    • aka multitasking
    • CPU: switches frequently between jobs
      • s.t. users: can interact w/ each job while running
      • enables: interactive computing
    • characteristics
      • response time: $<1s$
      • each user: w/ at least one program executing in memory (= process)
      • if several jobs ready to run: CPU scheduling needed
      • if: processes don't fit in memory
        • swapping technique required
        • moving some program in and out of memory during execution
      • virtual memory: allows execution of processes that are not completely in memory

• Virtualization

  • virtualization: abstracts hardware of a single computer
    • into multiple different execution environments
      • creating illusion: each user / program is running on their "private computer"
      • creates: virtual system = virtual machine (VM) to run OS / applications over
        • allows: an OS to run as an app within another OS
          • 👨‍🏫 growing industry!
  • components
    • host: underlying hardware system
    • virtual machine manager (VMM): creates & runs VM by providing interface
      • s.t. it's identical to the host
      • aka hypervisor
    • guest: process provided w/ virtual copy of host
      • i.e. program. often: an OS (guest OS)
  • allows: a single physical machine to run multiple OS concurrently
    • each on their own VM
  system models

  

• Virtualization history

  • virtualization: OS natively compiled for CPU, running guest OSes
    • originally: designed in IBM mainframes (1972)
      • for: allowing multiple users to run tasks concurrently
        • under: system designed for a single use
      • or: sharing batch-oriented system
    • VMware: runs one or more guest copies of Windows on Intel x86 CPU
    • virtual machine manager (VMM): provides environment for programs
      • that is: essentially identical to original machine (interface)
    • programs on such environment: only experience minor performance decrease (due to extra layers)
    • VMM: in complete control of system resources
  • by late 1990s: Intel CPUs on general purpose PCs: fast enough for virtualization
    • technology: treated by $Xen,VMware$, which are still relevant today
    • virtualization: expended to many OSes, CPUs, VMMs

• Cloud computing & virtualization

  • delivers: computing, storage, or apps as a service over a network
  • logical extension of virtualization: combination of virtualization & communication
    • Amazon EC2: w/ millions of servers, and tens of millions of VMs
      • petabytes of storage available across the Internet
      • payment: based on usage
    • 

• Cloud types

  • public cloud: available vis Internet to anyone willing to pay
  • private: run by company for internal use
  • hybrid cloud: includes both public & private components
  • software as a service (SaaS): provides one / more apps via Internet (web based application)
    • no installation required
  • platform as a service (PaaS): provides SW stack ready for application via Internet
    • e.g. database server, Google Apps Engine, Heroku
  • infrastructure as a service (IaaS): provides servers / storage over Internet
    • e.g. VM instances, cloud bucket
  • other services: also appearing
    • e.g. machine learning as a service (MaaS)

• Free and open source OS

  • OS: often made available in source code, rather than just binary
    • yet: MS Windows: closed source
  • idea: started by Free Software Foundation (FSF) w/ "copyleft" GNU Public License (GPL)
    • free software != open-source software
    • free software: licensed to allow no-cost use, redistribution, modification
      • in addition to public source
    • open source: not necessarily w/ such license
  • popular examples:
    • GNU / Linux
    • FreeBSD UNIX (and core of MAx OS X - Darwin)
    • Solaris
  • open source code: arguable more secure
    • more programmers to contribute & check
    • a better learning tool for us

• OS services

  • OS: provides environment for execution of programs
    • and other services to programs & users
  • set of OS services (OS functions) helpful to user
    • user interface: almost all OS has a user interface (UI)
      • command line (CLU), graphics (GUI), touch-screen
    • program execution: system: must be able to load program into memory
      • and run the program & end execution
        • either normally or abnormally (= error)
    • IO operations: running program: may require IO
      • might involve: files / IO device
    • ⭐ file-system manipulation: programs: need to read & write files and directories
      • in additions to: search, create, and delete
      • and further: listing file information / permission management
    • communications: processes: may exchange information (on same computer, or over a network)
      • via: shared memory or through message passing (packets: moved by the OS)
    • error detections: OS needs to be constantly aware of possible errors
      • may occur in CPU, memory, IO devices, user programs
      • for each error type: OS must take appropriate actions
        • to ensure: correct & consistent computing
      • debugging facilities: can greatly enhance the user's and programmer's abilities
        • to efficiently use the system
  • other set of OS services: ensures efficient operation of system (via resource sharing)
    • resource allocation: within multiple concurrent users & jobs
      • resources: must be allocate to each of them
        • e.g. CPU cycles, memory, file storage, IO devices
    • logging: keep track of: which users use how much
      • and what kinds of computer resources
    • protection, security: owners of information stored in multi-user / networked system: might want control on information use
      • e.g. permission control
      • concurrent processes: should not interfere with each other
      • protection: involving ensuring that all accesses to system resources: controlled
      • security of the system from outsiders: requires user authentication
        • extends to: defending external IO devices from invalid access attempts
  • 

• User OS interface: CLI

  • generally: three approaches for UI exists
    • CLI / command interpreter - directly enters commands to OS
    • GUI / touch screen: allows user to interface w/ the OS
  • CLI: allows direct command entry
    • sometimes: implemented in kernel
      • sometimes by system programs
    • sometimes: multiple flavors implemented: shells in Unix / Linux
    • primary functionality of shell:
      1. fetching command from user
      2. interpreting it
      3. executing it
    • UNIX and Linux systems: provide different version of shells
      • e.g. C shell, Bourne-Again, Korn, et.

• User OS interface: GUI

  • user-friendly desktop metaphor interface
    • usually: mouse, keyboard, and monitor
    • icons representing files, programs, directories, system functions, etc.
    • various mouse buttons over objects: cause various actions
      • e.g. provide information, execute function, open directory, etc.
      • invented at: Xerox PARC earlier 1970s (near Stanford)
        • first wide use: in Apple Macintosh (1984)
  • many systems now: provide both CLI and GUI interfaces
    • MS Windows: using GUI w/ CLI command shell
    • Apple Max OS X: Aqua GUI interface
      • w/ UNIX kernel underneath, as well as shells
    • Unix and Linux: w/ CLI and optional GUI interfaces (KDE, GNOME)

• User OS interface: touchscreen

  • touch screen requires: new interfaces
    • mouse: not feasible / desired
    • actions & selection: based on gestures (no mouse move)
    • virtual (on-screen) keyboard for text
  • voice command: iPhone's Siri, etc.

• Syscall

  • system call: programming interface to the services provided by the OS
  • syscall: generally available as functions, written in a high-level language (C/C++)
    • certain low-level tasks: written in assembly languages (accessing hardware)
  • e.g.: cp in.txt out.txt involves multiple syscall
    • input file name, accept input, open input file, create out file, etc.

• API

  • application program interface (API): specifying a set of functions, available for app programmers to use
    • including: parameters passed to functions
      • and expected return values
  • function making up API: typically invoke actual syscalls, on behalf of programmer
  • programmer: access APIs via library provided by the OS
    • in UNIX / Linux: libc for C programs
  • three most common APIs:
    • Win32 API for Windows systems
    • POSIX API for POSIX-based systems (UNIX, Linux, and Mac OS X)
    • Java API for JVM
  • standard API example
    • 
    • parameters
      • int fd: file descriptor to be read
      • void *buf: buffer the data will be read into
      • size_t count: maximum number of bytes to be read: into the buffer
    • return value
      • 0: indicating end of file
      • -1: indicating error
  • advantages: why use API over syscall?
    • program portability: programmer w/ API: expect program to run on any system supporting same API
      • syscall implementation: might vary from machine to machine
    • abstraction: hiding complex details of the syscall from users
      • actual syscall: often more details / difficult to work with
      • caller of API: doesn't need to know implementation of syscall
      • caller: simply obey API format / understand what does API do

• Syscall implementation

  • for most programming languages: run-time environment (RTE) provides syscall interface
    • serving as link to syscalls, made available by OS
    • RTE: set of functions built into libraries
  • each syscall: associated w/ identity number
    • syscall interface: maintains a table indexed according to these numbers
  • syscall interface: functions
    • intercept: function calls in API
    • invoke: necessary syscall within OS
    • return: status of syscall / return values if any
  • API-syscall-OS relationship
    • 

• Syscall parameter passing

  • often: more info than just syscall identity is needed
    • exact type / amount of information: vary for OS / call
    • 👨‍🏫 although we will spend some time on a syscall without parameter (fork())
  • three general methods used to pass parameters from user programs to OS
    • simplest: pass parameters in registers
    • block method: parameters stored in block / table / memory
      • and address of block: passed as a parameter in a register
    • stack method: parameters placed / pushed onto stack by the program
      • popped off the stack by the OS
    • block & stack: no limitation on number / length of parameters!
  • parameter passing: via table
    • 

• Types of syscalls

  • process control
    • create / terminate process
    • end, abort
    • load, execute
    • get / set process attributes
    • wait for time
    • wait even, signal event
    • allocate / free memory
    • dump memory if error
    • debugger for determining bugs, single step execution
    • locks for managing access to shared data between processes
  • file management
    • create / delete file
    • open / close file
    • read, write, reposition
    • get & set file attributes
  • device management
    • request / release device
    • read, write, reposition
    • get / set device attributes
    • logically attach / detach devices
  • information maintenance
    • get & set time / data
    • get & set system data
    • get & set process, file, device attributes
  • communications
    • create, delete communication connection
    • send, receive messages: to host name / process name
      • if message parsing model
    • shared memory model: create & gain access to memory regions
    • transfer status information
    • attach & detach remote devices
  • protection
    • control access to resources / get and set permissions
    • allow / deny user access

• Examples

  task	Windows	Unix
  process control	CreateProcess()	fork()
  	ExitProcess()	exit()
  	WaitForSingleObject()	wait()
  file management	CreateFile()	open()
  	ReadFile()	read()
  	WriteFile()	write()
  	CloseHandle()	close()
  device management	SetConsoleMode()	ioctl()
  	ReadConsole()	read()
  	WriteConsole()	write()
  information maintenance	GetCurrentProcessID()	getpid()
  	SetTimer()	alarm()
  	Sleep()	sleep()
  communications	CreatePipe()	pipe()
  	CreateFileMapping()	shm_open()
  	MapViewOfFile()	mmap()
  protection	SetFileSecurity()	chmod()
  	InitializeSecurityDescriptor()	umask()
  	SetSecurityDescriptorGroup()	chown()

  • standard C library example
    • program invoking printf() library call
      • leads to write() syscall, etc.
      • 

• MS-DOS example

  • characteristics
    • single tasking
    • shell invoked when system booted
    • simple to run a program
      • no process created
    • single memory space
    • loads program into memory
      • overwriting all: but the kernel
    • program exit => shell reloaded
  • 

• System programs

  • another aspect of modern computer system: collection of system services
  • system services: provide convenient environment for program development / execution
    • aka system programs / utilities
    • some: simply user interface to syscalls
      • others: considerably more complex
    • view of OS seen by most users: defined by application & system programs
      • not the actual syscalls
      • e.g. GUI featuring mouse-and-windows interface vs. UNIX shell
        • same set of system calls
        • yet, syscalls appear very differently & act in different way (from user)

• List of system programs

  • file management
    • create, delete, copy, rename, print, dump, list
    • and generally manipulate files & directories
  • status information
    • some: ask system for data, time, amount of available memory, disk space, number of users, etc.
    • others: provide detailed performance, logging, debugging information
  • file modification
    • text editors to create & modify files
    • special commands to search file contents / perform transformation of the text
  • program-language support
    • compilers, assemblers, debuggers, and interpreters
      • for common programming languages (C, C++, Java, Python)
      • often provided
  • program loading & execution
    • absolute loaders, relocatable loaders, linkage editors, overlay-loaders, debugging systems
      • for higher-level and machine language
  • communications: providing mechanism for creating virtual connections
    • among processes, users, and computer systems
    • allowing users to:
      • send messages to one another's screens
      • browse web pages
      • send electronic-mail messages
      • log in remotely
      • transfer files from one machine to another
  • background services
    • launch at boot time
      • some: terminate after completing task
      • some: continue to run until system terminates
        • aka: services, subsystems, daemons
    • provide: facilities like disk checking, process scheduling, error logging
  • application programs
    • not part of the OS
    • launched by command line, mouse click, finger poke, etc.
    • examples: web browsers, word processors, text formatters, spreadsheet, DB systems, games ...

• Linkers and loaders

  • source codes: compiled into object files
    • designed to be loaded into any physical memory location
    • relocatable object files
  • linker: combines object files into a single binary executable file
  • programs: reside on secondary storage as binary executable
    • must be brought into memory by loader to be executed
    • relocation: assigns final addresses to program parts
    • adjusts code & data in program to match those addresses
  • modern general purpose OS: don't link libraries into executables statically
    • instead: using dynamically linked libraries (aka DLLs in Windows)
      • loaded when needed, and shared by all programs using the same version of that library
        • loaded only once!
    • object files / executable files: often w/ standard formats
      • machine codes, symbolic tables
      • thus: OS knows how to load & start them
  • role of the linker and loader
    • 

• Protection

  • protection: internal problem
    • security: considering both the system & surrounding environment of is
  • OS: must protect itself from user programs
    • Reliability: compromising the OS: generally causes it to crash
    • Security: limit the scope of what processes can do
    • Privacy: limit each process to the data it has access permission
    • Fairness: each user / process: should be limited to its "appropriate share" of system resources
  • system protection features: guided by
    • principle of need-to-know
    • implement mechanisms to enforce: principle of least privilege
      • minimum possible permission to do the job!
    • computer systems contain object that must be protected from misuse
      • hardware: memory, CPU time, IO devices
      • software: files, programs, semaphores

• Design and implementation of OS

  • not solvable / no optimal solution
  • characteristics
    • internal structure: varies widely
    • even at high level: design affected by choice of hardware / system type, etc.
      • desktop / laptop / mobile / distributed / real- tie
    • design: starts with specifying goals & specifications
      • user goals: OS being convenient to use
        • and ease to learn & use
        • reliable, safe, fast
      • system goals: easy to design, implement, and maintain
        • and flexible, reliable (hopefully) error-free & efficient
    • highly creative task of SWE

• Important principle ⭐

  • separation of policy & mechanism
    • policy: what will be done
    • mechanism: how to do it?
      • e.g. time construct, mechanism for ensuring CPU protection
        • deciding how long the timer will be: policy decision
  • 👨‍🏫 policy: often changes
  • separation of policy from mechanism: allows flexibility even policies change
    • w/ proper separation: mechanism can be used to policy decision for
      • prioritizing IO-intensive program
      • as well as vice versa
  • OS: designed w/ specific goals in mind
    • which: determine OS policies
    • OS: implements policies through specific mechanisms

• Implementation

  • early OSes: written in assembly (~= 50 yrs a go)
  • modern OS: written in higher level language
    • for some special device/ function: assembly might still be used
    • but general system: written in C/C++
    • frameworks: in Java, mostly
  • w/ higher level language: it can be easily ported
    • also, code can be write faster, compact, and easier to maintain
  • speed / increased storage requirement: not a concern now
    • technology advances!

• OS structure

  • general purpose OS: very large program
  • various ways to structure one
    • monolithic structure
    • layered - specific type of modular approach
    • microkernel - mach OS
    • loadable kernel modules (LKMs) - modular approach

• Simple structure

  
  • the simplest possible
  • structure not well-defined; started as a small / simple / limited system
  • MS-DOS: written for maximum functionalist in minimum space
    • not carefully divided into modules
  • doesn't separate between user & os problem
    • 👨‍🏫 NOT a dual system
    • can cause many trouble nowadays (all user: can do sudo and all)

• Monolithic structure: original linux

  • kernel: consists of everything below the syscall interface
    • and above the physical hardware
  • employees multiprogramming
  • 👨‍🏫 quite simple considering having to allocate stacks, etc.
  • user: can't directly hardware
    • kernel is underneath
  • 
  • UNIX: initially limited by hardware functionality => limited structuring
    • 👨‍🏫 still, it is a single program!
      • a single, static binary file running in a single address space
    • monolithic structure!
  • UNIX: made of two separable parts
    • kernel: further separated into interfaces & device drivers
      • expanded as UNIX evolves
    • system programs
  • drawback: enormous functionality: combined to one level
    • difficult to implement, debug & maintain
  • advantage: distinct performance!
    • no need to pass parameter, etc.
    • very little overhead in syscall interface and communication, etc.

• Linux system structure

  • i.e. modular design
    • allows kernel to be modified during run time
  • based on UNIT
  • still, monolithic:runs entirely in kernel mode w/ single address space

• Modular design

  • monolithic approach: too compact and tight interaction
  • why not make the tie looser?
    • so that change in one module / functionality does not affect the others parts!
    • 👨‍🏫 ideally, and hopefully!
  • one method: layered approach
    • e.g. file system: located above hardware

• Layered approach

  • OS: divided into no. of layers
    • each built on top of lower layers
    • layer $0$: hardware
    • layer $N$: user interface
  • each layer: made of data structure & set of functions
    • that can be invoked by higher level layers
  • each layer: utilized the services from a lower layer, provides a set of functions
    • and offers certain services for a higher layer
  • 
  • 👨‍🎓 linux: all in 1 layer
  • information higher: layer not needing to know lower-layer's implementation
    • each layers: hides existence of its own data structures / operations to higher levels
  • main advantage: simplification of construction & debugging
    • layered system: successfully used in other areas too
    • like TCP/IP vs. hardware (networking system)
  • few systems tue pure layered approach though
    • overall performance will be affected
  • trend: fewer layers w/ more functionality & modularization
    • while avoiding complex layer definition & interactions

• Mixed kernel system structure

  • kernel: became large & difficult to manage
  • some people: wanted to make OS a core
    • and store all other nonessential parts outside
    • mainstream (OS): expansion
    • result: much smaller kernel
  • Mach: developed at CMU in mid-1980s
    • modularized the kernel w/ microkernel approach
    • best-known microkernel OS: Darwin, used in Mac OS X, iOS
      • consisting of 2 kernels, one being Mach microkernel
    • UNIX / IBM, etc. thought it's desirable
  • 👨‍🏫 but no general consensus on what's nonessential
    • but generally: minimal process, memory management and communication facility: must be in kernel
  • some of the essential functions
    • provide communications between programs / services in user address space
      • through message passing
    • problem: if app wants to access file
      • it must interact w/ file server through kernel, not directly to file / file manager
    • 
  • advantage
    • easier to extend microkernel system (without modifying the kernel)
    • minimal change to kernel
    • easier to post OS to ner architectures
    • more secure
  • drawbacks: performance
    • increased system overhead
    • copying & storing messages during communication => makes it slow!
  • not done by the mainstream
  • Window NT: w/ layered microkernel
    • much worse performance thantWindow 95 / Window XP

• Modular approach: current methodology

  • best current practice: involving loadable kernel modules (LKMs)
    • i.e. programs can be added to kernel without rebooting
  • once added, become a part of kernel, not user program!
  • kernel: supports link to additional services
    • services: can be implements & added dynamically while kernel is running
    • dynamic linking: preferred to adding new features directly to kernel
      • as it doesn't require recompiling kernel per every change
  • resembles layer : as it has well-defined & protected interfaced
    • yet, it's much more flexible
  • also resembles microkernel: as primary module is only core functions and linkers
    • more efficient that pure microkernel though
  • linux: w/ LKMs, primarily for supporting device drivers & file systems
  • LKMs: can be inserted into kernel during booting & runtime
    • also can be removed during runtime!
  • dynamic & modular kernel, while maintaining performance of monolithic system

• Case study: Solaris

  • 👨‍🏫 in my days... Solaris was a dominant workstation provider
    • PC wasn't a things... and we CS people used Linux
    • now, the company is not computer system program though
  • it worked with modular system
  • 

• Hybrid system

  • most OS: combines benefit of different structures
  • Linux: monolithic (in single address space), but also modular
    • new functionality can be dynamically added
  • windows: largely monolithic, with some microkernel behavior
    • also provide support for dynamically loadable kernel modules

• macOS & iOS structure

  • in architecture: mcOS & iOS: have much in common
    • UI, programming support, graphics, media, and even kernel environment
  • Darwin: includes Mach microkernel and BSD UNIX kernel
    • with dual base programs
  • 
  • higher level structure
  • Max OS X: hybrid, layered, Aqua UI (mouse / trackpad)
    • w/ Cocoa programming environment: API for Objective-C
    • core frameworks: support graphics and media
      • including Quicktime & OpenGL
    • kernel environment (Darwin) includes Mach microkernel & BSD
    • 
  • iOS
    • structured on Mac OS; added C functionality
    • does not run applications natively; runs on different CPU architectures too (ARM & Intel)
      • core OS: based on Mac OS X kernel, but with optimized battery
    • 
    • Springboard UI: designed for touch devices
    • Cocoa Touch: Object-C API for mobile app development (touch screen)
    • Media services: layer for graphics, audio, video, quicktime, OpenGL
    • Core services: providing cloud computing & data bases
    • Core OS: based on Max OS X kernel
  • Darwin
    • layered system consisting of Mach microkernel & BSD UNIX kernel
      • hybrid system
    • two syscall interfaces: Mach syscalls (aka traps) and BSD syscalls (POSIX functionality)
    • interface: rich set of libraries - standard C, networking, security, programming languages..
    • Mach: providing fundamental OS services
      • memory management, CPU scheduling, IPC facilities
    • kernel: provide IO kit for device drivers
      • dynamically loadable modules: aka kernel extensions (kexts)
    • BSD: THE first implementation supporting TCP/IP, etc.
    • 

• Android

  • developed by Open Handset Alliance (led by GOogle)
  • runs on a variety of mobile platforms
    • open-source, unlike Apple's closed-sources
  • similar to OS: layered system providing rich set of frameworks
  • for graphics, audio, and hardware
  • using a separate Android API for Java development (not standard Java)
    • Java app: execute on Android Run Time (ART)
    • VM: optimized for mobile devices w/ limited memory & CPU
  • Java native interface (JNI): allows developers to bypass CM
    • and access: specific hardware features
    • programs written in JNI: generally not portable in terms of hardware
  • libraries: include framework for:
    • Webkit: web browser dev
    • SQLite: DB support
    • SSLs: network support (secure sockets)
  • hardware abstract layer (HAL): abstracts all hardware
    • providing applications w/ consistent view
      • independent of hardware
  • uses Bionic standard C library by google, instead of GNU C library for Linux systems
  • 

• Introduction to processes

  • 👨‍🏫 a real thing! no more high level!
  • objectives:
    • identify components of process, representation, and scheduling
    • describe creation & termination using appropriate syscalls
    • describe and contrast inter-process communication w/ shared memory
      • and message passing methods

• Four fundamental OS concepts

  • process
    • instance of an executing program
    • made of address space & more than 1 thread of control
  • thread (continues in Ch. 4)
    • single unique execution context
    • full description of program stated
      • captured by program counter, registers, execution flags, and stack
    • for parallel operations..?
  • address space (w/ address translation)
    • programs: execute in address space
      • != memory space of physical machine
    • each program: starts w/ address 0
  • dual mode operation (= Basic protection)
    • user program / kernel: runs in different modes
    • different permissions per programs
    • OS & hardware: protected from user programs
    • user programs: protected & isolated from one another

• Process concept

  • OS: executes a variety of programs: each runs as process
  • process: captures a program execution, in a sequential manner
    • von Neumann architecture
  • process: contains multiple parts
    • program code: aka text section
    • current activities or state: program counter / processor registers
    • stack: temporary data storage when invoking functions
      • e.g. for function parameters, return addresses, etc.
    • data section: containing global variables
    • heap: w/ dynamically allocated memory during run time
    • 👨‍🏫 stack & heap can grow dynamically: during execution
  • program: passively stored on disk
    • process: active entity, w/ PC specifying next instruction to fetch & execute
  • process: with life cycle: from execution to termination
  • program: becomes a process
    • when executable file is loaded into main memory & get ready to run
  • executes in address space, different from actual main memory location
  • one program: can be executed by multiple processes
  • a program: can be an execution environment for others (e.g. JVM)

• Loading program into memory

  • program: must be loaded to memory before execution
  1. load its code & static data into memory / address space
  2. some memory: allocated for program's runtime stack
     • for C: stack used for local variables, function parameters, return addresses
     • fill in: parameters for main(): e.g. argc,argv
  3. OS: may allocate memory for program's heap
     • programs: request & returns it explicitly
  4. dO: also d some initialization tasks
     • esp. relating to IO
       • e.g. UNIX: each process w/ 3 open file descriptors
       • standard input / output / error

• Memory layout of a program

  • global data: divided into initialized data and uninitialized data
  • separate section for argc,argv parameters
  • 

• Process state

  • traditional Unix: each process = 1 thread
    • process state $\ni$ current activity of that process
  • as process executes: it changes states
    • new: process being created / allocating resource
    • ready: process waiting to be assigned to CPU
      • 👨‍🏫 remember ready queue and CPU core!
    • running: instructions being fetched & executed
    • waiting: process waiting for event to occur
    • terminated: process finished execution / deallocating resource
    • ❓ how do process manager work? how much CPU resource does it take?
      • 👨‍🏫 will be discussed later (whole chapter)
  • 
  • different things might happen in running state
    • exit: finished all tasks
    • interrupt: after each line of instruction: checks interrupt signal
      • if detected: add interrupt routine to process queue
    • I/O || event: I/O service, etc: are much slower than CPU
      • so the process gives up CPU itself, and waits for signal (from IO / etc.)

• Process control block (PCB)

  • each process: corresponds to 1 PCB
    • i.e. info. associated w/ each process
    • aka: task control block
  • includes following info:
    • process state: running / waiting, etc.
    • program counter: location of instruction to be fetched next
    • CPU registers: accumulators, index resisters, stack pointers, general-purpose registers, condition-code information
    • CPU scheduling info.: priorities, pointers to scheduling queue, scheduling parameters
    • memory-management info.: memory allocated to the process
      • complicated data structure: paging & segmentation tables
      • 👨‍🏫 for now, consider it as a pointer to program data structure
      • 👨‍🏫 program: simple binary; process: dynamic!
    • accounting info.: CPU used, clock time elapsed, time limits
      • simple statistics
    • IO status info.: IO devices allocated to process
      • e.g. list of open files
  • 

• Threads

  • we assumed: a process w/ single thread of execution
    • thread: represented by: PC, registers, execution flags, stack
  • modern OS: allow a process w/ multiple threads
    • thus can perform parallel execution
    • e.g. browsers: contacting web server vs. displaying image, etc.
    • w/ multi-core systems: multiple threads of process: can run in parallel
  • process: can consist of 1 / multiple threads
    • running within the same address space (e.g. sharing code & data)
    • each thread: w/ its own, unique state
  • multi-threads: process providing concurrency & active components
    • 

• Process representation in Linux

  • Linux: storing list of processes in circular doubly LL
    • aka task list
    • each element in task list: of type struct task_struct
      • i.e. PCB

  pid t_pid;
  long state;
  unsigned int time_slice;
  struct task_struct *parent /* TBD */
  struct list_head children /* TBD */
  struct files_struct *files /* TBD */
  struct task_struct *parent /* TBD */
  

• Process schedule

  • primary object of multiprogramming: keep CPU busy
    • as it's a scars resource
  • process scheduler: OS mechanism selecting a process
    • from available processes inside main memory
    • scheduling criteria: CPU utilization, job response time, fairness, real-time guarantee, latency optimization...
  • degree of multiprogramming: no. of processes currently residing in memory
    • determines resource consumption
  • processes: roughly either:
    • I/O bound process: spends more time w/ IO than computations
      • many short CPU bursts
    • CPU bound process: generates IO requests infrequently
      • more time doing computations; few, very long CPU bursts

• Scheduling queue

  • OS: maintains different scheduling queues of processes
    • ready queue: set of processes in main memory;
      • ready & waiting to execute
    • wait queue: set of processes waiting for an event
  • processes: migrate among various queues during lifetime

• Representation of process scheduling

  • 

• Schedulers

  • long-term scheduler (job scheduler)
    • for scientific & heavy computation
    • selects which processes to be brought to memory
    • for mainframe minicomputers (not PC)
      • made of job queue: hosts job submitted to mainframe computers
  • short-term scheduler (CPU scheduler)
    • selects a process from a ready queue to be executed next & allocate CPU for it
  • short-term scheduler: invoked frequently (μs, must be fast)
  • long-term scheduler: invoked infrequently (s,min, may be slow)
  • long term scheduler: dictates degree of multiprogramming
  • mainframe computer system:

• Medium term scheduling

  • if you underestimated the program resource:
    • swap out (not terminating) some programs
      • entire process information (not just PCB)
    • and use the freed up resource to accelerate & give more space
  • for PC: you can simply kill the resources
    • for mainstream: it's all services that's paid
    • mostly not implemented for PC

• Inter-process CPU switch

  • context switch: when CPU switches from one process to another
    • sample OS task
      • save state into PCB-0
      • reload state from PCB-1
      • save state into PCB-1
      • reload from PCB-0
      • ...
  • context: must be saved (in PCB / in each thread of process)
    • typically: including registers, PC, stack pointer
  • context-switch time: an overhead
    • system: doesn't do useful work during it
    • takes longer if OS & PCBs are complex
  • switching speed: depends on
    • memory speed
    • no. of registers copied
    • existence of a special instructions to load & store all registers
  • speed: highly dependent on underlying hardware
    • e.g. some processors: provide multiple sets of registers
    • context switch: simply changing the pointer to a different register set

• Dual mode operation

  • allows OS to protect itself & other system components
  • 👨‍🏫 MS-DOS didn't have it; Windows have
  • user mode: has less access / permission to hardware than the kernel mode
  • can be easily extended to multiple modes!
  • ❓ sudo = executing as the lowermost user?
  • dual-mode operation provides: basic means of OS protection & users
    • from errant / bad users
  • all access: must be strictly controlled by well-defined OS API
  • switching between modes: constant
    • e.g. (user) API call to open -> (kernel) open -> (user) displays

• Three types of mode transfer

  • 3 common ways to access kernel mode from user mode
  • system call:
  • interrupt:
  • trap / exception:

• Operations on processes

  • processes in most systems: execute concurrently;
  • created & deleted dynamically; thus OS must support
    • process creation: running a new program
    • process termination: program execute completes / terminate
  • parent process: can create children processes
    • children: can create other child processes
    • tree of processes!
  • 👨‍🏫 shell: also a process!
    • waiting for your input
    • all commands running on it: children process of shell
  • desktop: can be a parent process
    • process started on it (e.g. by double click): its children process
  • the grandpa: root process

• Tree of processes on Linux system

  • 

• Process creation

  • most OS: identify process according to unique process identifier
    • or: pid, usually an integer
  • child process: needs certain resources
    • CPU time, memory, files, IO devices to accomplish task
    • parent process: also pass along initialization dat (input)
      • to child process
  • parent & children: share "almost" all resources
  • three choices possible on how to share the resource
    1. parent & children: share almost all resources: fork()
    2. children: share only subset of parent's resources: clone()
    3. parent & children: share no resources
  • two options for execution after process creation
    1. parent: continues to execute concurrently with its children
    2. parent: wait until some / all its children to terminate
  • again, two choices of address space for a new child process
    • child process: duplicates of parent (same program & data) - Unix/Linux
    • child process: has a new program loaded into it (different program & data) - Windows
  • UNIX examples
    • fork(): creates a new process; duplicates entire address space of the parent
      • both processes: continue execution at the next instruction after fork()
    • exec(): maybe used after fork(): to replace child process's address space w/ a new program
      • loading a new program
    • parent: can call wait() to wait for a child to finish
  • 

• Process creation

  • fork()

    • parent & child: can be added to ready queue parallelly
      • behavior: cannot be determined by code only
    • parent & child: resumes execution after fork w/ the same PC
      • i.e. the return of fork() call
    • after
    • return values of fork()
      • each process: receives exactly one return value
      • -1: unsuccessful (to parent)
      • 0: successful (to child)
      • >0: successful (to parent)
        • returned value: child's PID
        • 👨‍🏫 losing track of PID / etc.: not discussed here
      • 👨‍🏫 this value: used to distinguish post-fork behavior of process
    • almost everything of the parent gets copied
      • memory / file descriptors / etc.
      • i.e. such copy of everything: very costly & time consuming
        • parent can't access child's cloned memory
        • nor the child access parent's original memory

  • UNIX fork

    • create & initialize process control block (PCB) in kernel
    • create new address space / allocate memory
    • initialize address space w/ the copy of entire contents
      • time consuming!
    • inherit the execution context of the parent (e.g. open files)
      • i.e. all stack and etc. information
    • inform the CPU scheduler: child process is ready to run

  • parent & child comparison

    • after fork()

    Duplicated	Different
    address space	PID
    global-local var	fork() return
    current working dir	running time
    root dir	running state
    process resources
    resource limits
    program counter
    ...

    example

    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <unistd.h>
    #include <sys/types.h>
    
    #define BUFSIZE 1024
    int main(int argc, char *argv[]) {
        char bug[BUFSIZE];
        size_t readlen, writelen, slen;
        pid_t cpid, mypid;
        pit_t pid = getpid();
        printf("Parent pid: %d\n", pid);
        cpid = fork(); // branch
        if (cpid > 0) {
            mypid = getpid(); // parent
            printf("[%d] parent of [%d]\n", mypid, cpid);
        } else if (cpid == 0) {
            mypid = getpid(); // child
            printf("[%d] child\n", mypid);
        } else {
            perror("Fork failed");
            exit(1);
        }
    }
    

    • note that
      • output after printing (i.e. within control flow) has undetermined order
        • depending on CPU scheduler

• system calls

  • exec(), execlp(): syscall to change program in current process

    • creates a new process image from: regular executable file
    • 👨‍🎓 ~= j to another program?
      • ⭐ no return to original process!

  • wait(): syscall to wait for child process to finish

    • or: on general wait for event
    • 👨‍🏫 enter waiting stage & give up CPU
      • 👨‍🎓 if parent keep occupying CPU: then a single-core won't be able to be execute a fork w/ wait()
      • ⭐ very very important!

  • exit(): syscall to terminate current process

    • • free all resources

  • signal(): syscall to send notification to another process

  • implementing a shell

    char *prog, **args;
    int child_pid;
    
    while (readAndParseCmdLine(&prog, &args)) {
        child_pid = fork();
        if (child_pid == 0) {
            exec(prog, args); // run command in child
            // cannot be reached
        } else {
            wait(child_pid);
            return 0;
        }
    }
    

  • fork tracing

    • to trace forks in loops, try to expand the loop
      • e.g. for (int i=0; i < 10; ++i) fork(); into fork(); fork(); fork();...
    fork diagrams (credit: IA Peter)

---
    title: fork()
    ---
    flowchart LR
        p0((p0)) --> f1{fork 1}
        f1 --> p0_2((p0))
        f1 --0--> p1((p1))

---
    title: fork(); fork()
    ---
    flowchart LR
        p0((p0)) --> f1{fork 1}
        f1 --> p0_2((p0))
        f1 --0--> p1((p1))
        p0_2 --> f2{fork 2}
        f2 --> p0_3((p0))
        f2 --0--> p2((p2))
        p1 --> f3{fork 3}
        f3 --> p1_2((p1))
        f3 --0--> p3((p3))

---
    title: fork()&&fork()
    ---
    flowchart LR
        p0((p0)) --> f1{fork 1}
        f1 --> p0_2((p0))
        f1 --0--> p1((p1))
        p0_2 --> f2{fork 2}
        f2 --> p0_3((p0))
        f2 --0--> p2((p2))

---
    title: fork()||fork()
    ---
    flowchart LR
        p0((p0)) --> f1{fork 1}
        f1 --> p0_2((p0))
        f1 --0--> p1((p1))
        p1 --> f2{fork 2}
        f2 --> p1_2((p1))
        f2 --0--> p2((p2))

</details>

• Final notes on fork

  • process creation is unix: unique (no pun)
    • most os: create a process in new address space & read in an executable file and execute
    • Unix: separating it into fork() and exec()
  • linux: fork(): implemented via copy-on-write
    • as usually: we don't need the entire copy
      • thus we can delay / prevent copying the data
        • until content is changes / written to
        • improves speed a lot!
    • child process: points to parent process's address space
  • linux also implements fork() via clone() (more general)
    • clone(): uses a series of flags allow to specify which set of resources should be shared by parent & child

• Process termination

  • termination
    • after process executes the last statement
      • exit syscall: used to ask OS to delete it
  • some os: do not allow child to exist if parent has terminated
    • i.e. all children are to be terminated after parents
      • cascading termination by the OS
  • process termination:
    • deallocation: must involve the OS
    • e.g. kernel data, etc.: cannot be accessed / modified by the user application
  • concepts
    • zombie process: process terminated, but wait not called on parents yet
      • e.g. corresponding entry in the process table / PID, and PCB
      • 👨‍🏫 every process enters this stage, at least for a moment after termination
        • nothing wrong. It's just "we are almost over"
      • but zombies can be accumulated, and wit as a problem back then
        • because the memory restriction was very tight ~=30 years ago
      • once parent calls wait: PID of zombie process and other corresponding entry: released
      • such design: enables parent inform the OS termination of the child
        • 👨‍🏫 not the best design, nor the only. but the design of Unix
    • if parent terminates without invoking wait()
      • child becomes an orphan
      • without cascading, the process might be still runnable
      • or become a zombie
        • which, will never be released, as no parent exist
      • thus: all process (except root or so): must have a parent
        • (or kill them all using cascading)
        • 👨‍🎓 can we assign
    • 👨‍🏫 this is the design chosen by UNIX
      • 👨‍🎓 can't we ensure the child to call OS and take care of themselves?
        • maybe we can, but this is choice or trade-off made by the unix
      • 👨‍🏫&👨‍🎓 parent has ability to track all its children, but it is not required.

• General

• Communication models

  • producer-consumer problem
    • represents common type of inter-process cooperation
    • producer: produces information (& puts into buffer)
    • consumer: consumes information (e.g. display)
  • unbounded buffer: places no practical limit on the size of the buffer
  • bounded buffer: assumes: fixed puffer size

• Shared memory

  • shared data

    • bounded buffer: pseudocode

      #define BUFFER_SIZE 10
      typedef struct {
        ...
      } item;
      item buffer[BUFFER_SIZE];
      int in = 0;
      int out = 0;
      

    • allows at most BUFFER_SIZE-1 items in buffer at same time
      • "one" of the common communication method
      • different implementations: can use all BUFFER_SIZE items
    Pseudocode

    s
    

• Message passing

  • mechanism for communication & synchronization
  • without sharing the same address
  • particularly useful: in distributed environment
  • IPC facility: provides
    • send (message)
    • receive (message)
  • message size: can be either fixed / variable
  • in order to processes to communicate, they need to
    • establish a communication link between them
      • 👨‍🏫 need to know somehow each other's identity!
      • such processes can eue either direct / indirect communication
    • exchange messages visa primitives: send(), receive()
  • different methods exist

• Direct communication

  • processes: must name each other explicitly
    • usually: PID, but can be acronyms, etc.
    • send(P,m)
  • d

• Indirect Communication

  • messages: sent to and received from mailboxes
    • each mailbox: w/ unique id
    • processes: can communicate only if they share a mailbox
  • properties of communication link
    • link: established written a pair of processes
      • only if both members of pair: w/ shared mailbox
    • d
  • basic mechanism to support:
    • create a new mailbox
    • send & receive messages through the mailbox
    • destroy the mailbox
  • primitives: defined as
    • send(A,message): send message to mailbox: $A$
    • send(A,message): receive message from mailbox: $A$
  • mailbox sharing
    • $P_1,P_2,P_3$: shares mailbox
    • can $P_2,P_3$ receive message from $P_1$?

    • solutions

• Synchronization

  • message passing: either blocking / non-blocking
    • or: synchronous - asynchronous
  • 4 possibilities
    • status of sender & receiver
  • blocking: considered synchronous
    • blocking send: sending process: blocked until message is received
      • i.e. I'll until you confirm
    • blocking receive: receiver blocks until a message is available
      • i.e. give me message! give me message! give me message!
  • non-blocking: considered asynchronous
    • non-blocking send: sending process: sends message & resumes operation
    • not waiting for message reception
    • non-blocking receive: receiver: retrieve either a valid message / null
  • rendezvous: when send() and receive() are both blocking
    • i.e. common place
    • pseudocode

    • producer-consumer: becomes trivial

• Buffering

  • either direct / indirect, messages exchange by communicating processes reside in a temporary queue
  • queue: either in three ways
    1. zero capacity: no messages are queued on a link
       • sender: must wait for receiver
    2. zero capacity: no messages are queued on a link
       • sender: must wait if link is full
    3. unbounded capacity: infinite length
       • sender never waits

• Pipes

  • piped: one of the first IPC mechanism in early UNIX systems
    • is communication: unidirectional / bidirectional?
    • must there exists a relationship between processes?
      • e.g. parent-child
    • can the pipes:used over a network?
      • or only on the same machine?
  • ordinary pipes: cannot be accessed from outside the process that created it
    • typically: parent process creates a pipe
    • and uses it to communicate with child, made by fork()
  • names pipes: can be accessed without a parent-child relationship
    • destroyed by the OS upon process termination

• Ordinary pipes

  • communicates in a standard producer-consumer fashion
  • pipe(int fd[]) in unix: unidirectional
    • producer: writes to one end (write end, fd[1])
    • producer: reads from end (read end, fd[0])
  • requires parent-child relationship
  • cannot be accessed from outside the process created them
    • cease to exist after processes finish communication & terminated
  • 
  • unix: treats pipe as a special type of file
    • standard read(), write(), and the child: inherits pipe from parent process
    • parent process: use pipe() to create pipe
      • then use fork to create a child process
        • child: inherits pipe as well
        • 👨‍🏫 inherited fo one child only, in original UNIX
  • example code

• Names pipes

  • more powerful than ordinary pipes!
    • bidirectional
    • no parent-child relationship required
    • multiple process can use it (w/ several writers)
  • names pipes: continues to exist after processes terminate
    • must be explicitly deleted
  • names

• Client-server communication

  • sockets
    • defined as: endpoint for communication
      • pair of process communicating over a network:
      • employs a pair of socket
    • uniquely identified by an IP address and a port number
      • port: specifies process / application on client / server side
    • server: waits for incoming client requests
      • by listening to a specified port (well-knowns)
      • once received: server can choose to accept the request
        • to establish a socket connection
      • port number: different for different process
        • although they are the same application
        • e.g. two tabs of chrome browser: separate process & separate port number!
  • remote procedure calls (RPC)
    • one of the most common forms of remote services
      • procedure-call mechanism: for use between systems w/ network connections
    • RPC: commonly used for implementing distributed file systems

• Sockets

  • servers: listen to well-known ports (SSH-22; FTP-21; HTTP-80)
    • all ports below 1024: well-known and reserved for standard services
    • server: always running & with well-known IP address & IP
  • only client: can initialize communication
  • when client initiate a request:
    • it should know its OP address
    • and select a client port number not in use ($1024$)
    • 4-tuple: uniquely determines a pair of communication
      • source IP address
      • source port number
      • destination IP address
      • destination port number
    • 👨‍🏫 even only 1/4 are different: they are different pair!
  • ⭐⭐ requirements for communication to occur
    1. server: MUST BE ALWAYS RUNNING
    2. server address & port: MUST BE KNOWN
       • server side port: the same
         • HTTP: 80
       • IP address: known by domain naming system (DNS)
         • original idea: having a gigantic machine with single IP address
         • however: cannot handle world-size traffic like Google
       • professor: has a 1999 paper on how to allocate replica
         • which server to access (i.e. nearby / quickest)
         • which IP to access (relating to DNS)

• Thread

  • many app / programs: multithreads
    • e.g. web browser: some displaying images, some retrieving data from internet
      • or: each tabs in a browser
    • to perform tasks efficiently
  • most OS kernels: multithreads
    • e.g. multiple kernel threads created Linux system boot time
  • motivation: can take advantage of processing capabilities on multicore systems
    • i.e. parallel programming: often in data mining, graphics, AI
  • process creation: time consuming and resource intensive
    • thread creation: light-weight
    • as thread shares code, data, and others within the process

• Multithreaded program examples

  • embedded systems
    • elevators, planes, medical systems, etc.
    • single program on concurrent operations
  • most modern OS kernels
    • internally concurrent: to deal w/ concurrent requests by multiple users
    • no internal protection needed in kernel
  • DB servers
    • access to shared data of many current users
    • background utility processing: must be done
  • network servers
    • concurrent requests from network
    • file server / web server / airline reservation systems
  • parallel programming
    • split program & data into multiple threads for parallelism

• Single & multithreaded processes

  • thread: basic unit of CPU utilization
    • independently scheduled & run - instance of execution
    • represented by
      • thread ID
      • program counter
      • register set
      • stack
    • shares code, data, and OS resources: e.g. open files & signals
    • efficiency: depends on no. of cores allocated to the process
  • benefits
    • responsiveness
    • resource sharing
      • threads: share process resource by default
      • easier than inter-process shared memory / message passing
        • as: threads run within the same address space
    • economy
      • thread creation: cheaper than process creation
      • context switch: faster intra-process (thread) than inter-process
    • scalability
      • processes: can take advantage of multicore architecture

• Multicore design

  • multithreaded programming: provides mechanism for more eff. use of multi-cores
    • and improves concurrency in multicore systems
  • ⭐👨‍🏫 L2 cache / memory are shared by cores

• Multicore programming

  • significant new challenges in multicore/multiprocess programming design
    • dividing tasks: how to divide into separate / concurrent tasks
    • balance: each task performing equal amount of work
    • data splitting: data used by tasks: divided to run on separate cores
      • 👨‍🎓 dividing seed among farmers to work concurrently
    • data dependency: synchronization required if data dependency exist
      • e.g. operation B: requiring completion of operation A
    • testing and debuggingL different path of executions: makes debugging difficult
  • parallelism != concurrency
  • parallelism: system can perform more than one task simultaneously
  • concurrency: supporting more than one task for making progress
    • i.e. doing more than one job over a time
    • when multiplexed over time: single process core, scheduler provides concurrency
  • advent of multicore: requires new approach in software system design

• Concurrency vs. parallelism

  • concurrent: single core multiplexing over time
    • 
  • parallel: execution on a multi-core system
    • 
  • 👨‍🏫 rigorously, parallelism only exists in multicore
    • but many literatures don't differentiate them

• Data & task parallelism

  • data parallelism: distribute subset of data across multiple cores
    • same operation on each core
    • common: in distributed machine learning tasks
    • 
  • task parallelism: distribute: threads across core
    • each thread: performing unique operation
    • 
  • data & task: not mutually exclusive: could be used at the same time!

• Amdahl's law

  • designs performance gain from additional cores to an application
    • w/ both serial and parallel components
  • $S$: serial portion
  • $1-S$: parallel portion
  • $N$: processing cores
  • speedup $\le \frac{1}{S+\frac{1-S}{N}}$
    • as $N$ approaches infinity: speedup approaches $1/S$
    • serial portion of application: disproportionate effect
      • on performance gained by adding additional cores
  • e.g. if application if 75% parallel, 25% serial
    • then moving from 1 to 2 cores: give speedup of
    • $\frac{1}{0.25+\frac{0.75}{2}}=\frac{1}{0.625}\approx 1.6$
  • 👨‍🏫 even if you have 5% of serial portion: speedup decreases significantly
  • 

• Multithreaded processes

  • multithreaded process: more than one instance of execution (i.e. threads)
  • thread: similar to process, but shares the same address space
  • state of each thread: similar to process
    • with its of program counter and private set of register for execution
  • two thread running on single process: switching from threads requires context switch, too
    • register state of a thread: saved, and another thread's is loaded / restored
    • address space: remains the same - much smaller context switch
      • and thus much small overhead
  • thus parallelism is supported
    • enables overlap of IO with other each activities within a single program
    • one thread: running on CPU; another thread doing IO

• Thread

  • thread: single unique execution context: lightweight process
    • program counter, registers, execution flags, stack
    • thread: executing on processor when it resides i registers
    • PC register: holds address of currently executing instruction
    • register: holds root state of the thread (other state in memory)
  • each thread: w/ thread control block (TCB)
    • execution state: CPU registers, program counter, pointer to stack
    • scheduling info: state, priority CPU time
    • accounting info
    • various pointers: for implementing scheduling queues
    • pointer to enclosing process: PCB of belonging process

• Thread state

  • thread: encapsulates concurrency - active component of a process
  • address space: encapsulates protection - passive part of process
    • one program's address space: different from another's
    • i.e. keeping buggy program from thrashing entire system
  • state shared by all threads in a process / address space
    • contents onf emory (global variables, heap)
    • IO state (file descriptors, network connections, etc.)
  • state not shared / private to each thread
    • kept in TCB: thread control block
    • CPU registers (including PC)
    • execution stack: parameters, temporary variables, PC saved

• Lifecycle of a thread

  • 
  • change of state
    • new: thread being created
    • ready thread waiting to run
    • running: instructions being executed
    • waiting: thread waiting for event to occur
    • terminated: thread finished execution
      • or: killed by OS / user
  • active threads: represented by TCBs
    • TCBs: organized into queues based on states

• Ready queue and IO device queues

  • thread not running: TCB is in some queue
    • queue for each device / signal / condition: w/ their own scheduling policy
  • more accurate visualization of ready queue (instead of PCB, w/ TCB)
  • 

• User threads and kernel threads

  • user threads: independently executable entity within a program
    • created & managed by user-level threads library
    • users: only visible to programmers
  • kernel threads: can be scheduled & executed on a CPU
    • supported & managed by OS
    • users: only visible to OS
  • example: virtually all-general purpose OS
    • Windows, Linux, Max OS X iOS, Android
  • 

• Multithreading models

  • as user threads: invisible to kernel
    • => cannot be scheduled to run on a CPU
    • OS: only manages & schedules kernel threads
  • thread libraries: provide API for creating & managing user threads
    • primary libraries
      • POSIX Pthreads - POSIX API
      • Windows threads - Win32 API
      • Java threads - Java API
  • user-level thread: providing concurrent & modular entities
    • in a program that OS can take advantage of
      • 👨‍🎓 here! this can be done in parallel manner!
    • if no user threads defined: kernel threads can't be scheduled either
    • ❓ are kernel threads assigned on runtime?
      • 👨‍🏫 yes; user threads are static though
      • cycles of threads / control / etc.: applies to kernel threads
  • example

    pthread_t tid;
    /* creating thread */
    pthread_create(&tid, 0, worker, NULL)
    

  • ultimately: mapping must exist for user-kernel threads
    • common ways:
    • many-to-one: many user-level thread to one kernel thread
    • one-to-one: one user-level thread for a kernel thread
      • most common in modern OS
    • many-to-many: many user-level thread to many (usually smaller no. of) kernel thread

• Multithreading models (cont.)

• Multithreading: many-to-one

  • many user thread: mapped to single kernel thread
  • only one user thread mapped to kernel thread at execution time
    • which user thread is mapped: scheduling problem
  • one thread blocking (of thread): causes
    • cases all
  • m
  • no performance benefit
    • still, structure-wise works like multithreading
    • cannot run in parallel on multicore system
      • as one kernel thread: can be active at a time
  • examples
    • Solaris Green Threads
    • GNU Portable Threads
  • 👨‍🏫 used in the past due to resource limitation
    • kernel thread: requires resource
    • user thread: piece of code waiting for execution
  • few systems currently use this model
  • 

• Multithreading: one-to-one

  • each user-level thread: maps to one kernel threads
  • maximum concurrency: allows multiple threads to run in parallel
    • having more kernel threads than user threads: meaningless
  • i.e. creation of user thread: mandates kernel thread creation
    • max no. of threads / process: might be restricted due to overhead
    • could have been problematic in the past
      • as kernel thread consumes resources: memory, IO, etc.
  • examples
    • Windows
    • Linux
  • 

• Multithreading: many-to-many

  • multiplexing many user=level
  • in-between
  • process-contention scope: to be discussed later (Ch. 5)
    • 👨‍🏫 similar to many-to-one mapping
    • we have scheduling problem
  • 

• Multithreading: two-level

  • similar to many-to-many
  • but: it allows user thread to be bound to kernel thread
    • e.g. some user thread: significant, and requires set kernel thread
  • 

• Multithreading mapping models

  • many-to-many: most flexible
  • but difficult ti implement in practice
  • in modern computer: limiting no. of kernel threads: less of a problem
    • thanks to multi core

• fork(), exec() semantics

  • does fork() by thread: duplicate only the calling thread?
    • or all threads of a process?
  • some UNIX versions: chosen two versions of fork()
    • if exec() called immediately after forking: duplicate only calling thread
    • exec(): works as normal - replacing the entire process (although only calling thread is copied)
    • 👨‍🏫 'one' of the improvement case
  • different improvements exist!

• Signal handling

  • signals: notify a process that a particular event has occurred
    • can be receives synchronously / asynchronously
    • based on source / reason
  • synchronous signals: delivered to same process performing operation causing signal
    • d.g. illegal memory access / division by 0
  • signals: handled in different ways
    • some signals: ignored
    • some: handled by terminating program
      • e.g. illegal memory access
  • signal handler: process signal
    • signal: generated by a particular event
    • delivered to a process
    • handled by one of two signal handlers
      • default vs. user defined
  • every signal: w/ default handler that kernel users
  • where signal shall be delivered for a multi-thread process?
    • deliver: signal to thread to signal applies
    • deliver: signal to every thread in process
    • deliver: signal to certain thread in process
    • assign a specific thread to receive all signals
  • method of delivering signal: depends on signal type
    • synchronous signal: delivered to thread causing the signal (not other threads)
    • asynchronous signals (e.g. termination process): sent to all threads
  • UNIX function for delivering kill signal: send to all thread of the process
    • s
    • specifies pid
  • POSIX Pthread function: allows signal to be delivered to a specified thread
    • specifies tid
  • d

• Thread cancellation

  • terminating thread before finishing

    • thread to be cancelled: target thread

  • cancellation scenario

    • asynchronous cancellation: terminate target thread immediately
    • deferred cancellation: target thread: periodically check if it should terminate
      • allows termination in orderly fashion
      • e.g. when modifying an inter-process variable / in critical point, target thread shouldn't be terminated

  • invoking thread cancellation: requests cancellation

    • actual cancellation: depending on thread state / type

  • w/ Pthreads:

  • by nature: cancellation of a thread affects other threads within the same process

    mode	state	type
    off	disabled
    deferred	enabled	deferred
    asynchronous	enabled	asynchronous

    Pthread code for created cancel of a thread

    #include <pthread.h>
    #pthread_t tid
    
    /* create the thread */
    pthread_create(&tid, 0, worker, NULL);
    // worker: a start routine / function call
    
    /* cancel the thread */ 
    pthread_cancel(tid);
    
    /* wait for the thread to terminate */
    pthread_join(tid, NULL);
    

• OS example: Windows

  • Windows application: runs as a separate process
  • Windows API: primary API for Windows app
  • w/ one-to-one mapping
  • general components of a Window thread
    • tid
    • register set
    • PC
    • separate user / kernel stacks
  • context of a thread: register set, stacks, and private storage areas
  • primary data structures of a thread
    • ethread
    • kthread
    • TEB (thread environment block)
    • 

• OS example: Linux

  • Linux: does not differentiate threads & process
    • special kind of process: task
  • thread in Linux: process that (may) share certain resource w/ other thread
    • each thread: w/ unique task_struct and appears as a normal process
    • threads in Linux: happens to share everything (except context)
      • e.g. address space
      • then they behave like threads
    • ⭐👨‍🏫 Linux approach: provides much flexibility
      • e.g. sharing program, but not data
      • or sharing data, but program
      • or sharing file, but nothing else
      • impossible with traditional approach
  • contracts greatly w/ Windows / Sun Solaris
    • w/ explicit kernel support for threads / lightweight processes
  • if a process: consist of two threads
    • in Windows
    • in Linux: simply 2 tasks w/ normal task_struct structure
      • that are set up to share resources
  • threads: created just like normal tasks
    • except: clone() syscall used to pass flag
    • clone(): allows a child task to share part of execution context w/ parent
    • clone(): specifies what to share
    • 👨‍🏫 fork / clone: creates a new task
      • clone(): only in Linux
    • flags control behavior
  • instead of copying all data structures
    • new task points to data structures of parent task
  • normal fork(): can be implemented as
    • clone(SIGCHLD, 0);

• Basic concepts

  • objective of multiprogramming: have process running at all time
    • i.e. maximize CPU utilization
  • process execution: made of cycles of CPU execution & IO wait
    • ask CPU burst and IO burst
    • 👨‍🏫 based on what you are doing at the point
    • 
  • when CPU idle:
    • OS try to select one process on ready queue & execute
    • unless ready queue is empty = no process in ready state
  • selection of process: done by CPU scheduler
    • aka process scheduler, short-term scheduler

• History of CPU-burst times

  • majority of CPU burst time: very short
    • but very few CPU extensive jobs exist
    • aka: long-tail distribution
  • typically
    • d
  • distribution: matters when we design a CPU-scheduling algorithm
  • 

• CPU scheduler

  • CPU scheduler: selects on process thread on ready queue
    • i.e. what to be executed next?
    • queue
  • CPU scheduling: may take place in following 4 conditions (when scheduling must be done)
    1. switching from running -> waiting state (e.g. IO request / wait)
    2. process terminates
       • giving up CPU voluntarily
    3. switching from running to ready state
       • i.e. interrupt
    4. switching from waiting to ready / new to ready
       • e.g. completion of IO
       • new process arrives on ready queue w/ higher priority
         • if it is priority-based scheduling
  • case 1 & 2: non-preemptive
    • giving up CPU voluntarily
  • case 3 & 4: preemptive
    • OS: forces to give up CPU
    • consider access to: shared data

• Dispatcher

  • dispatcher module: allocates CPU to process selected by scheduler
  • involves:
  • no. of context switches:
    • can be obtained by vmstat on Linux
    • ~= hundred context switches / sec usually

• Scheduling criteria

  • CPU utilization: fraction of the time that CPU is busy
    • as long as ready queue is not empty: CPU must not be idle
    • 👨‍🏫 priority no matter what scheduler you use
  • throughput: no. of process / job completed per time
  • response time: only matters for robin-round
  • fairness
  • computation of each: will be explained later
  • generally: desirable to optimize all criteria
    • but there might be conflict, which different considerations in practice
  • mostly
  • in practice: we prefer to optimize minimum / maximum values rather than average
    • and there are many things to be considered
  • 👨‍🏫 interactive
    • interactive: CPU
    • non-interactive: does not require sCU attention until termination
      • e.g. ML communication

• 👨‍🏫 assume: all under single processor system

• First-Come First-Served: FCFS

  • if $P_1,P_2,P_3$ arrives in respective order
  • waiting time: each process in "ready stage"
    • time joining CPU burst - arrival time
    • ⭐⭐ = turn-around time - CPU burst time
  • turn-around time: total time to execute a particular process
    • ⭐⭐ = completion time - arrival time
    • (for single process system)
  • 👨‍🏫 waiting & turn around time: must be computed manually
  • earlier system: FCFS = one program is scheduled to run until completion
  • in multiprogramming systems: process finishes its current CPU time
  • example
    • 
    • waiting time: $P_1=0;P_2=24;P+3=27$
    • avg.waiting time: $(0+24+27)/3=17$
    • avg. turn-around time: $(24+27+30)/3=27$
      • or: $(27+(24+3+3))/3=27$
  • example 2
    • 
    • waiting time: $P_1=6;P_2=0;P+3=3$
    • avg.waiting time: $(6+0+3)/3=3$
    • avg. turn-around time: $(9+30)/3=13$
    • Convoy effect: short process: stuck behind a long process
      • bad for short jobs, depending purely on arrival order
      • e.g. one CPU -bund & many IO-bound processes
        • FCFS: result in low IO device utilization
  • problem: you can't know execution time of the program beforehand!

• Round Robin (RR)

  • straightforward solution
    • if process takes longer than expectation (e.g. found from the curve)
  • FCFS: non-preemptive
    • once CPU core allocated process, process keeps it until release
  • RR: preemptive
    • each process w/ small unit of CPU time (time quantum $q$)
      • 10-100 ms
    • after time elapse: process is preempted and added to the end of ready queue
  • given $n$ long process, each process: gets $1/n$ portion of CPU time
    • $q$ per each round
    • (ignoring context switching)
    • waiting time: always less than $(n-1)q$ time units
  • timer: interrupt every quantum to schedule next process / process blocks
    • upon completing current CPU burst time
    • when its CPU burst time / remaining CPU time $<q$
      • i.e. quicker than expectation?
  • example: w/ $q=4$
    • 
    • waiting time: $P_1=6;P_2=4;P_3=7$
    • avg. waiting time: $(6+4+7)/3=5.67$
    • avg. turn-around time: $(6+4+7+30)/3=15.67$
    • response time: $P_1=4;P_2=7;P_3=10$
      • average: 7
      • i.e. first response time - request time
      • 👨‍🏫 same as turn-around for FCFS/FIFO
    • remaining CPU burst time
  • average waiting time: can be long
    • but inherently "fairer" than FCFS
    • offers better average response time: important for interactive jobs

• Time quantum and context switch time

  • performance of RR: depends heavily on $q$ choice
    • large $q$: FCFS
    • small $q$: interleaved, but high overhead from context switch time
      • context switch time: $<10$ micro sec

• FCFS - RR comparison

  • is RR: always better than FCFS?

  • extreme example: quantum = 1

    • and 10 jobs starting same time, with 100 CPU burst time

    Job #	FIFO	RR
    1	100	991
    2	200	992
    $\dots$	$\dots$	$\dots$
    9	900	999
    10	1000	1000

  • average job turn-around time: much worse

    • albeit with two extreme conditions
      • very small quantum size
      • all jobs with same length
    • yet: average response time: much better

  • example

    process	time
    $P_1$	6
    $P_2$	3
    $P_3$	1
    $P_4$	6

    • 

  • turnaround time: varies with time quantum

    • average turnaround time: not necessarily improve when quantum increases
    • it can be, generally, when most processes finish current CPU bursts within a single quantum
    • yet: large quantum leads to FCFS

  • ⭐ rule of thumb: 80% of CPU bursts: should be shorter than the time quantum $q$

    • quantum: should be enough to produce meaningful result for most cases

  • 👨‍🏫 $q$ can be adjusted on the way

    • actually... we have better algorithms than pure RR

• Short-Job-First (SJF)

  • what if: we know next CPU burst time of each process?
  • then, we can process the shorted job first
    • for given set of processes, this is optimal (i.e. min avg. waiting time)
  • difficulty: knowing length of next CPU request
  • big effect on short jobs, rather than long ones
  • more precise name: shortest-next-CPU-burst
  • can be applied to entire program / current CPU burst only
  • response time: not concerned now
    • 👨‍🏫 as this is introduction of concepts
  • example

    process	time
    $P_1$	6
    $P_2$	8
    $P_3$	7
    $P_4$	3

    • 
    • average waiting time: $(3+16+9+0)/4=7$
    • best FCFS = case of SJF
    • actually,

• Determining length of next CPU burst

  • estimation: done by exponential average (again :p)

    • $t_n$: average length of $n$-th burst
    • ${\tau }_{n+1}$: predicted value for next CPU burst
    • $\alpha ,0\le \alpha \le 1$
      • larger $\alpha$: weight / portion of the most recent data
    • define: ${\tau }_{n+1}=\alpha t_n+(1-\alpha ){\tau }_n$

  • commonly: $\alpha =0.5$

  • preemptive version: called shorted-remaining-time-first (SRTF)

    diagram

    

    • $\alpha =1/2;{\tau }_0=10$

  • examples of EMA

    • $\alpha =0$: ${\tau }_{n+1}={\tau }_n$
      • first estimation lasts forever
    • $\alpha =1$: ${\tau }_{n+1}=t_n$
      • only last CPU burst counts $$\begin{array}{rl}{\tau }_{n+1}& =\alpha t_n+(1-\alpha ){\tau }_n\\ & =\alpha t_n+(1-\alpha )(\alpha t_{n-1}+(1-\alpha ){\tau }_{n-1})\\ & =\alpha t_n+(1-\alpha )\alpha t_{n-1}+(1-\alpha {)}^2{\tau }_{n-1}\\ & =\alpha t_n+(1-\alpha )\alpha t_{n-1}+(1-\alpha {)}^2\alpha t_{n-1}+(1-\alpha {)}^3{\tau }_{n-2}\\ & =(1-\alpha {)}^{n+1}{\tau }_0+\alpha \sum _{k=0}^{n-1}(1-\alpha {)}^k{t}_{n-k}\end{array}$$
    • current prediction: dependent on all of past data
      • yet, the effect of past exponentially reduces

• Shortest Remaining Time First

gantt
    A task          :a1, 1, 30s
    Another task    :a2, after a1, 20s
    Another task    :a3, after a2, 20s
    Another task    :a4, after a3, 20s
    axisFormat %S

• SJF: can either be preemptive / non=preemptive

• what if: new process arrives while another is executing?

  • CPU: might switch to new process (if w/ shorter remaining time)

• SRJF: SJF, but preemptive

• example

  process	arrival	burst
  $P_1$	0	8
  $P_2$	1	4
  $P_3$	2	9
  $P_4$	3	5

  • 
  • average waiting time:
    • $[(10-1)+(1-1)+(17-2)+(5-3)]/4=26/4=6.5$

• SJF/SRTF and FCFS comparison

  • possible: results in starving
    • process w/ long burst time might keep delayed

  - 
  

• Priority scheduling

  • priority no.: associated w each process
  • CPU: allocated to process w/ highest priority (= smallest integer)
    • preemptive
    • non-preemptive
  • equal-priority process: scheduled in FCFS
  • SJF: special case of priority scheduling algorithm
    • priority: inverse of predicted next CPU burst
  • problem: starvation: low priority process never executing
  • solution: aging: as time progresses, priority process
    • other solutions exist
    • 👨‍🏫 or: periodically update the priority
  • example

    process	burst	priority
    $P_1$	10	3
    $P_2$	1	1
    $P_3$	2	4
    $P_4$	1	5
    $P_5$	5	2

    • 
    • average waiting time: 8.2 msec
    • when 2 ms quantum applied, w/ RR:
      • 👨‍🏫 combination between priority and RR!
      • 

• Multilevel queue

  • multilevel queue scheduling: can be extension of priority scheduling
    • e.g. priority assigned statically
    • process: remains in the same queue for duration of runtime
    • 
  • partition processes: depending on process type
    • scheduling among queues: commonly implemented w/ fixed priority preemptive scheduling
      • each queue w/ certain CPU time / time-slice

• Multilevel feedback queue (MLFQ)

  • process: move between various guess
    • aging: implemented this way
    • supports flexibility
  • following parameters
    • no. of queues
    • scheduling algorithms for each queue
    • method to determine when to upgrade / demote a process
    • method to determining which queue to enqueue process
  • example
    • three queues
      • $Q_0$: RR w/ $q=8$ ms
      • $Q_1$: RR w/ $q=16$ ms
      • $Q_2$: FCFS
    • scheduling
      • new job entering $Q_0$: served FCFS
        • preempts jobs from $Q_1,Q_2$ if they are running
        • if it doesn't finish in 8 ms: enqueue process to $Q_1$
      • $Q_1$: served FCFS and receives 16 ms
        • if it doesn't complete: enqueue process to $Q_2$
      • if: a job from $Q_1,Q_2$: preemptive by a new job of higher queue
        • remains at the front of that queue (w/ remaining quantum)
    • approximates SRTF
      • CPU bound jobs: drop quickly
      • short-running IO bound: stays near top
    • 👨‍🏫 running on a CPU: means that queues above are empty
      • upon preemption: interrupted process still stays front of the queue
      • when prioritized process ends: (i.e. priority returns to second queue)
        • then the interrupted process continues its remaining time quantum

• Computation

  • turnaround time: termination time - arrival time
  • waiting time: turnaround time - CPU burst time

---
  displayMode: compact
  ---
  gantt
      axisFormat  %S
      Requirements  :a1, 1, 4s
      Design  :a2, after a1, 4s
      Development  :a3, after a2, 4s
      Test  :a4, after a3, 4s

• MLFQ: Remarks

  • MLFQ: commonly used in many systems (unix, Solaris, Windows, etc.)
  • w/ distinctive advantages
    • no need for prediction of CPU burst time
    • handles interactive jobs well
      • better than RR in terms of response time
      • i.e. first quantum
    • produces similar performance w/ SJF / SRTF
      • short jobs: finish at Q0
      • SJF / SRTF: theoretical & optimal
        • MLFQ: practical & approximates
      • fair: on performance for CPU-bound jobs
        • no "complete" starvation
    • possible starvation: handled by reshuffling jobs to different queues
      • e.g. after some period: move all jobs to top queue
      • 👨‍🎓 shake!
    • 👨‍🏫 wonderful (& best) principle!
      • no, or very little overhead!
  • ❓ is there any criteria for quantum 1, 2, etc. in MLFQ?
    • first quantum: 7-80%
    • second: somewhat of a buffering - until it goes to FCFS
    • design: must be considered carefully
      • 2 level: may be better than 3-4
      • CPU intensive environment, e.g. ML, has different consideration w/ DB query handler

• Thread scheduling

  • user thread: handled by programs
  • no scheduler needed for on-to-one mapping
  • yet: many-to-one or many-to-(smaller) many: requires scheduling on thread
    • i.e. which task is mapped to thread currently?
  • OS: uses intermediate data structure: lightweight process (LWP)
    • between user threads & kernel threads
  • programmer: assigns thread priority in program

• Multiple-processor scheduling

  • asymmetric: not to be discussed
    • i.e. when one processor acts as a master
  • symmetric multiprocessing (SMP)
    • each processor: either self-scheduling or w/ one common ready queue
      • e.g. one line for all counter (airport) / each counter (supermarket)
      • both are common for SMP
    • 

• ❓ if one process happens to miss deadline once in a cycle, will it miss deadline again in the next cycle?
  • 👨‍🏫 maybe, maybe not! depends on arrival, deadline, etc.
• ❓ what if: we know in prior that a process will miss deadline?
  • depends on whether the deadline is soft or hard
  • also, different mechanism handles it differently
    • for hard deadline, you may ignore the step in some cases
  • if the workload is >100% (impossible), it's not scheduler's problem!

• Multicore processor

  • recent trend: multiple processor cores on same physical chip
    • faster & consumes less power
    • but: complicate scheduling design
  • memory stall: waits long time waiting for memory / cache to respond
    • as processors are much faster than memory
    • 👨‍🏫 inherent problem of Von-Neumann architecture
  • solution: having multiple hardware threads per core
    • each hardware thread: w/ own state, PC, register set
      • appearing as a logical CPU: running a software thread
    • chip multithreading (CMT)
    • 👨‍🏫 dealing with two program, without idle state!
    • ideal case
      • 
      • 👨‍🏫 in reality: memory operation might be much longer than CPU operation
      • then, we can have more hardware threads than just 2
  • scheduling: can take advantage of memory stall
    • to make progress on another hardware thread, while another doing memory task
    • core: switching to another thread - dual-thread processor core
  • 👨‍🏫 there is no software overhead, as it's hardware
    • thus, it's very fast
  • dual-threaded, dual-core system: presents 4 logical processors to OS!
    • e.g. UltraSPARC T3 CPU: w/ 16 cores / chip and 8 hardware threads per core
      • appearing to be 128 logical processors

• Multithreaded multicore system

  • from OS view: each hardware thread maintains its architecture state
    • thus: appears as a logical CPU
  • CMT: assigns each core multiple hardware threads
    • Intel term: hyperthreading
  • 👨‍🏫 logical != physical
    • you can't simultaneously run all those jobs
  • two levels of scheduling exist
    • OS: decide which SW thread to run on a logical CPU (in CPU scheduling)
    • each core: decide which hardware to run on physical core
      • possible: RR scheduling
    • 

• Multithreaded multicore scheduling

  • user-level thread: schedule to LWP / kernel-level thread
    • for many-to-one or many-to-many: thread library schedules user-level threads
      • such threads: process contention scope (PCS)
      • typically: based on priority (set by programmers)
  • software thread (=kernel thread): scheduled on logical CPU = hardware thread
    • 👨‍🏫 OS is responsible for this only
  • hardware thread: scheduled to run on a CPU core
    • each CPU core: decides scheduling, often using RR

• Processor affinity

  • process: has affinity for a processor on which it runs
    • cache contents of processor: stores on memory accesses by that thread
      • called as processor affinity
  • high cost of invalidating in repopulating caches
    • most SMP: try to avoid migration!
  • essentially: per-processor ready queues: provide processor affinity for free
  • soft affinity: OS: attempts to keep process running on same processor (no guarantee)
    • possible for process to migrate: during load balancing
  • hard affinity: allow a process to specify: subset of processors it may run
    • 👨‍🎓 I want this, that, and this only!
  • many systems: provide both soft & hard affinity
    • e.g. Linux implements soft affinity, yet also provides syscall sched_setaffinity() for hard affinity

• Load balancing

  • 👨‍🏫 only focusing on load balancing: common queue for all cores are good
    • same for separate queue and affinity
    • everything comes at a cost!
  • load balancing: attempts to keep workload evenly distributed
  • two general approaches to load balancing
    • push migration: specific task: periodically check load on each processor
      • if imbalance found: pushes overloaded CPU's task to less-busy CPUs
    • pull migration: idle processors: pull waiting tasks from a busy processor
    • not mutually exclusive: can be both implemented in parallel on load-balancers
      • e.g. Linux CFS implements both
  • load balancing: often counteracts benefits of processor affinity
    • natural tension between load balancing & minimizing memory access times
    • scheduling algorithms for modern multicore NUMA systems: quite complex

• Real-time CPU scheduling

  • demands: performance guarantee - predictability
  • especially in embedded control, etc.
    • e.g. spaceship must respond within certain time
  • hard real-time systems: with stricter requirements
    • task: must be serviced by deadline
    • service after deadline: expired, and meaningless
  • soft real-time systems
    • provides: no guarantee to when critical real-time process will be scheduled
    • guarantee tha real-time process: given preference over noncritical process
    • 👨‍🏫 we will be discussing this now!
  • must support: priority-based algorithm w/ preemption

• Priority-based scheduling

  • processes: w/ periodic characteristic: requires CPU at constant intervals (periods)
    • has: processing time $t$, deadline $d$, period $p$: $0\le t\le d\le p$
      • 👨‍🏫 if $t=d=p$: CPU must always be working on this
    • rate of periodic task: $1/p$
  • process: must announce its deadline requirements
    • scheduler: decides whether to admit process or not
  • 

• Rate monotonic scheduling

  • static priority: assigned based on inverse of period
    • shorter period: higher priority
    • rationale: assign priority to frequent (CPU) visitor
  • suppose:
    • $P_1$ w/ period=deadline 50, processing time 20
    • $P_2$ w/ period=deadline 100, processing time 35
    • as $50<100$: $P_1$ w/ higher priority than $P_2$
    • $P_1$: occupied $20/50=40\%$ time
    • $P_2$: occupied $35/100=35\%$ time
    • 👨‍🏫 75% utility if both can be scheduled!
      • if the sum is more than 100%: can't be scheduled at all
    • schedule example
      • 
  • 👨‍🏫 is tricky - it's preemptive!
  • missing deadline
    • $P_1$ w/ period=deadline 50, processing time 25
    • $P_2$ w/ period=deadline 70, processing time 35
    • as $50<80$: $P_1$ w/ higher priority than $P_2$
    • $P_1$: occupied $25/50=50\%$ time
    • $P_2$: occupied $35/80=44\%$ time
    • 👨‍🏫 94% utility if both can be scheduled!
    • P2: missing deadline by finishing at time 85
    • 

• Earliest deadline first scheduling (EDF)

  • Earliest deadline first: assigns priorities dynamically according to deadline
    • earlier the deadline: higher the priority
  • e.g. w/ same case as above:
    • 
    • 👨‍🏫 "first" $P_1$ has higher priority than "first" $P_2$
      • but second $P_1$ has lower priority than first $P_2$
      • no preemption of first $P_1$ by second $P_2$!
      • notably: first $P_1$ ($d=150$) preempts second $P_2$ ($d=160$)
      • 👨‍🏫 logically equivalent to SRTF

• Rate-monotonic vs. EDF scheduling

  • rate-monotonic: schedules periodic tasks w/ static priority w/ preemption
    • considered optimal among static priority-based algorithm
  • EDF: does not require process to be periodic, nor constant CPU burst time
    • only requirement: process announce deadline when it becomes runnable
  • EDF: theoretically optimal
    • schedule processes s.t. each process: meet deadline requirements
    • and CPU utilization will be 100 percent
    • in practice: impossible to achieve such level
      • as: cost of context switching & interrupt handling, etc.
    • optimal: cannot find a better scheduler w/ smaller number of deadline misses

• Algorithm evaluation

  • selecting CPU scheduling algorithm: might be difficult
    • different algorithms: w/ own set of parameters

• Deterministic modeling

  • takes: particular predetermined workload
  • and define: performance of each algorithm for that workload

• Queueing analysis

  • through actual numbers (arrival time, CPU bursts, etc.)
  • 👨‍🏫 there can be 2 PG courses on this!
  • Queueing models
    • mathematical approach for stochastic workload handling
    • $n$: average queue length
    • $W$: average queue length
    • $\lambda$: average arrival rate into queue
      • usually given
    • Little's formula: $n=\lambda \times W$
    • 👨‍🏫 my PhD thesis owa on this :p
    • more details: Poisson and Markov chain...
    • 👨‍🏫 $\lambda <\mu$
      • $1/\mu$: CPU burst time
      • unless: overload :p

• Simulations

  • queueing models: not "very" practical, but interesting mathematical models
    • restricted to few known distributions
  • more accurate: simulations involving program of a computer system model:

• Simulation implementation

  • even simulations: w/ limited accuracy
  • build a system: allowing actual algorithms to run w/ real data set
    • more flexible & general
  • 👨‍🏫: no true optimal solution exists

• Background

  • processes: execute concurrently
    • might be interrupted at any time, for many possible reasons
  • concurrent access to any shared data: may result in data inconsistency
  • maintaining data consistency: requires OS mechanism
    • to ensure orderly execution of cooperating processes

• Illustration of Problem

  • e.g. producer-consumer problem
  • integer counter: used to keep track of no. of buffers occupied
    • counter = 0 initially
    • incremented each time producer places item in buffer
    • decremented each time consumer consumes item in buffer
  • example code

    // producer
    while (true) {
        // produce an item
        while (counter == BUFFER_SIZE) ;
    
        buffer[in] = next_produced;
        in = (in + 1) % BUFFER_SIZE;
        counter++;
    }
    while (true) {
        while (counter == 0) ; // do nothing
    
        next_consumer = buffer[out];
        out = (out + 1) % BUFFER_SIZE;
        counter--;
        // consume an item
    }
    

  • race condition:
    • counter++ can be made as:

      register1 = counter
      register1 = register1 + 1
      counter = register1
      

    • counter-- can be made as:

      register2 = counter
      register2 = register2 - 1
      counter = register2
      

    • order of execution: cannot be determined
      • following scenario is possible, from counter = 5

      register1 = counter // 5
      register1 = register1 + 1 // 6
      register2 = counter // 5
      counter = register1 // counter = 6
      register2 = register2 - 1 // 4
      counter = register2 // counter = 4
      

    • expected result: counter = 5
      • but trouble happened!
    • only internal order of consumer / producer can be trusted, but not inter-process
      • 👨‍🏫 fundamental problem of sharing data
    • very hard to debug, and happens in small chance
      • individual code & logic: has no error!
  • similar case: fork() occurring at almost same time
    • resulting in: identical pid
  • must be: no interleave with another process sharing the variable

• Race condition

  • race condition: undesirable situation where several processes access / manipulate shared data concurrently
    • and outcome of executions: depend on particular order access / executions take place
      • which is not guaranteed
    • thus: resulting in non-deterministic result
  • critical section segment: during which
    • process / thread: changing shared var., updating a table, writing a file, etc.
    • must ensure: when one process is in critical section, no other can be in its critical section
    • mutual exclusion and critical section: implies the same
    • 👨‍🏫 can be long, can be short (= hundreds of lines)
  • critical section problem: to design a protocol to solve it
    • i.e. each process:
      • ask permission before entering a critical section (entry section)
      • notify exit (exit section)
      • and remainder section
  • general structure

    do {
        // entry section
        critical section // do something critical
        // exit section
        remainder section // others can access critical section
    
    } while (true);
    

• Solution of critical section problem

  • 3 solutions
    • mutual exclusion: if process $P_1$ is in its critical section
      • no other processes can be executing their critical section
    • progress: if a process wish to inter critical sections, it cannot de delayed / waited for indefinitely
      • i.e. must know no. of process in front of queue, etc. must be in $O(\cdot )$
    • bounded waiting: bound: must exist on no. of time processes are allowed to enter
      • 👨‍🎓 one shouldn't use toilet alone for too long
    • assume: each process execute at nonzero speed
      • and with no assumption on relative speed on individual process
  • critical section problem in kernel
    • kernel code: code OS is running
      • subject to: many possible race conditions
      • kernel data structure: keeps list of all open files
        • that can be updated by multiple kernel processes
      • other kernel DS: e.g. for maintaining memory allocation, process lists, interrupt handling, etc.
    • two general approaches
      • preemptive: let preemption of process running in kernel mode
        • possible race condition
          • more difficult to maintain in SMP architecture
        • 👨‍🏫 much more effective!
      • non-preemptive: runs until exiting kernel mode, blocks, or giving up CPU
        • free of race conditions in kernel mode
        • only possible in single-processor system

• Synchronization tools

  • many systems: provide hardware support on critical section code implementation
    • for uni-processor systems: simply disable interrupts
    • such approach: inefficient for multiprocessor
  • OS: provide hardware & high level API support for critical section code
  • example

    programs	share programs
    hardware	load / store, disable interrupts, test & set, compare & swap
    high level APIs	locks, semaphores

  • synchronization hardware
    • modern OS: provides atomic hardware instructions
      • atomic: non-interruptible
      • ensures: execution of atomic instruction: cannot be interrupted
        • => no race condition!
      • building blocks for more sophisticated mechanisms
    • two commonly used atomic hardware instructions
    • test a memory word & set a value: Test_and_Set()
    • swap contents of two memory words: Compare_and_Swap()
  • implementation
    • Test_and_Set()

      bool test_and_set(bool *target) {
        bool rv = *target;
        *target = true; // set here
        return rv;
      }
      

      • if target was initially true: than it returns true
        • i.e. we shouldn't interfere
      • integrated solution: let shared boolean var. lock, initially false

        do {
            while (test_and_set(&lock)) ;
            critical section // do something critical
            lock = false;
            remainder section // others can access critical section
        } while (true)
        

        • 👨‍🏫 this: only guarantees mutual exclusion!
      • dedicated data structure exist for those test variables
    • Compare_and_Swap()

      bool compare_and_swap(int *value, int expected, int new_value) {
        int temp = *value;
        if (*value == expected)
            *value = new_value;
        return temp;
      }
      

      • 👨‍🏫 return value: doesn't change
        • it only determines: whether I edit the variable or not
      • example

        do {
            while (compare_and_swap(&lock, 0, 1) != 0) ;
            critical section // !!!
            lock = 0;
            remainder section // !!!
        } while (true);
        

        • ❓ can we modify it a bit and
          • this function code can be used,
          • but use of more sophisticated tools built upon primitives: easier
      • direct use of primitive: for bounded-waiting mutual exclusion

        do {
            waiting[i] = true;
            key = true; // local variable
            while (waiting[i] && key)
                key = test_and_set(&lock);
            waiting[i] = false;
            
            critical section // !!!
        
            j = (i + 1) % n;
            while ((j != i) && !waiting[j])
                j = (j + 1) % n;
            if (j == i)
                lock = false; // no one waiting: release the lock
            else
                waiting[j] = false; // unblock process j
                // force process j to get out of waiting loop
        
            remainder section // !!!
        } while (true);
        

      • shared: lock & waiting; local: key
    • sketch proof
      • mutual exclusion: $P_i$: enters critical section only if:
        • either waiting[i]=false or key=false
          • key=false only if test_and_set is executed
          • only first process executing test_and_set find key==false
            • others: wait
        • waiting[i]: can become false only if another process leaves critical section
          • only one waiting[i] set to false
        • maintain: mutex requirement
      • progress: process exiting its section:
        • either set lock to false or waiting[j] to false
        • both: allow a waiting process to enter the critical section to proceed
      • bounded waiting: count in turns
        • when a process leaving critical section:
          • it scans array waiting in cyclic order
            • {i+1, i+2, ..., n-1, 0, 1, ..., i-1}
          • then designates: first process in the ordering w/ waiting[j]
            • as next one to enter critical section
        • 👨‍🏫 worst case: waiting n-1 processes in front of me

• Atomic variables

  • provides atomic updates on basic data types (integers & booleans)
  • e.g. increment() on atomic variable ensures increment without interruption

    void increment(atomic_int *v) {
        int temp;
        do {
            temp = *v;
        } while (temp !=
        (compare_and_swap(v, temp, temp+1))
        );
    }
    

    • supported by Linux

• Mutex locks

  • OS: builds a no. of SW tools to solve critical section problem
  • supported by most OS: mutex lock
  • to access a critical region: must ask acquire
    • use release() after use
  • calls to acquire(), release() - must be atomic
    • often implemented via hardware atomic instructions
  • however: solution requires busy waiting - must keep checking
    • thus: has a nickname: spinlock
    • wastes CPU cycles due to busy waiting
      • advantage: context switch is not required when process is waiting
        • context switch: might take long time
        • spinlock: thus useful when locks: expected to hold short
      • often used in multiprocessor systems
        • as one thread: spin on one processor
          • while another thread performs its critical section on another processor
  • acquire() and release()
    • solution: based on the idea of lock on protecting critical section
      • operations: atomic
      • lock before entering critical section (accessing shared data)
      • unlock upon departure from critical section after access
      • wait if locked: synchronization = involves busy waiting
        • "sleep" or "block" if waiting for a long time

    void acquire() {
      while (!available)
        ; /* busy wait */
      available = false;
    }
    void release() {
      available = true;
    }
    do {
      acquire lock
      // critical section
      release lock
      // remainder section
    } while (true);
    

• Semaphore

  • semaphore $S$: non-negative integer variable
    • a generalized lock
    • first defined by Dijkstra in late 1960s
      • can behave similarly to mutex lock, but has more sophisticated usage
      • min synchronization primitive used in original UNIX
  • two standard operations for modifying: wait() and signal()
    • originally P() and V() for proberen (test) and verhogen (increment) in Dutch
  • must be execute atomically s.t. no more than one process: execute wait() and signal() on same semaphore at the same time
    • idea: serialization
  • semaphore: only accessible by those two operations, except initialization

    void wait(S) {
      while (S <= 0)
        ; // busy wait
      S--;
    }
    void signal (S) {
      S++;
    }
    

• Semaphore usage

  • counting semaphore: integer value over unrestricted domain
    • can be used: for controlling access to given set of resources
    • of finite number of instances
    • initialized to: no. of resources available
  • binary semaphore: integer value, 0 or 1
    • can be hav like mutex locks
    • 👨‍🏫 but also can be used in different ways
  • can also: solve various synchronization problems
  • consider $P_1,P_2$: sharing a common semaphore synch - initialized to 0
    • following code: ensures that $P_1$ process executes $S_1$ before $P_2$ execute $S_2$

    P_1: 
      S_1;
      signal(synch);
    P_2: 
      wait(synch);
      S_2;
    

• Implementation with no busy waiting

  • each semaphore: associated w/ waiting queue
  • each entry in waiting queue: w/ two data ideas
    • value (in integer)
    • pointer to next record on queue
  • two operations
    • block: place process invoking operation to (appropriate) waiting queue
    • wakeup: remove one of process in waiting queue
      • place it on ready queue
  • semaphore: may be negative
    • w/ classical busy-waiting semaphore: impossible
  • if semaphore value = negative:
    • magnitude = no. of processes currently waiting on semaphore

• Signal semaphore

  • code

    typedef struct{
        int value; // if negative: processes being waiting
        struct process *list;
    } semaphore;
    wait(semaphore *S) {
        S->value--;
        if (S->value < 0) {
            add this process to S->list;
            block();
        }
    }
    // signal: has chance of changing condition
    signal(semaphore *S) {
        S->value++;
        if (S->value <= 0) {
            remove a process P from S->list;
            wakeup(P);
        }
    }
    

  • notice:
    • increment & decrement: done before checking semaphore value
    • block(): suspends the process & invokes it
    • wakeup(P): resumes execution of a suspended process $P$

• Deadlock and starvation

  • semaphore initialized w/ $1$ (binary semaphore)
    • forces atomic operation
  • deadlock: two / more processes: waiting indefinitely
    • for an event: that can be caused oy only one of waiting processes
    • e.g. $A,B$: with half-torn treasure map
      • each: request the other part of map
        • without giving up the piece they are holding
        • won't happen!
  • if $S,Q$: two semaphores initialized to $1$:

    $P_0$	$P_1$
    wait(S);	wait(Q);
    wait(Q);	wait(S);
    $\dots$	$\dots$
    signal(S);	signal(Q);
    signal(Q);	signal(S);

    • $P_0$: waiting for $P_1$ to execute signal(Q)
      • and $P_1$: waiting for $P_1$ to execute signal(S)
      • deadlock!
  • starvation: indefinite blocking
    • process: may never being removed from semaphore queue
      • then: suspended
    • e.g. removing process from queue using LIFO
      • w/ certain priorities

• Bounded-buffer problem

  • counting semaphore for solving a problem!
  • $n$ buffers, each holding one item
  • semaphore mutex initialized to 1
    • binary
  • semaphore full initialized to 0
    • no. of full slots in buffer
  • semaphore empty initialized to $n$
    • signal(mutex);
    • no. of empty slots in buffer
  • structure of the producer process

    do {
        // produce item
        wait(empty);
        wait(mutex); // guarantee mutual execution
        // add next produced to buffer
        signal(mutex);
        signal(full); // no. of items in buffer
    } while (true);
    

  • structure of the consumer process

    do {
        // remove item from budder to variable
        wait(full);
        wait(mutex); // guarantee mutual execution
        // consume next item from buffer
        signal(mutex);
        signal(empty);
    } while (true);
    

• Readers-writers problem

  • data set: shared among a no. of concurrent processes
    • readers: only read the data, without performing any updates
    • writers: can both read & write
  • problem: allow multiple readers to read the data set at the same time
    • however, at most one writer can access shared data at a time
  • several variations on treatment of readers & writers
    • w/ different priorities
  • simplest solution: requiring no reader be kept waiting
    • unless: writer as already gained access to shared data
      • shared data update by writers: can be delayed
        • as: people are reading (outdated) version
      • gives: readers priority in accessing shared data
  • shared data
    • data set
    • semaphore rw_mutex initialized to 1
    • semaphore mutex initialized to 1
    • semaphore read_count initialized to 0
  • for writer: guarantee mutual exclusion

    do {
        wait(rw_mutex);
        // writing
        signal(rw_mutex);
    } while (true);
    

  • for reader: first reader can take over $r{w}_{m}utex$
    • prevent another writer from reading it!

    do {
        wait(mutex); // exclusiveness of following snippet
        read_count++;
        if (read_count == 1)
            wait(rw_mutex);
        signal(mutex);
        // reading performed
        wait(mutex);
        read_count--;
        if (read_count == 0)
            signal(rw_mutex);
        signal(mutex);
    } while (true);
    

  • rw_mutex: controls access to shared data for writers & first reader
    • last reader leaving: release the lock (for potential writer)
  • mutex: controls the access of readers, to shared variable read_count
  • writers: wait on rw_mutex
    • first reader gain access to critical section: also waiting on rw_mutex
    • all subsequent readers: wait on mutex (held by the first reader)

• Reader-writer problem variations

  • first variation: no reader kept waiting: unless writer gained access
    • simple, yet might result in starvation of writers
      • thus: potential & significant delay of the object's update
  • second variation: one writer is reader: 'needs' perform update first
    • when a writer: waiting for access (either another writer or readers occupying it)
    • no new readers: can start reading
  • either solution: may result in starvation
    • problem: can be solved partially by kernel's reader-writer locks
      • multiple processes: permitted to acquire lock in read mode
      • yet: only one permitted to acquire lock in write mode
    • i.e. specifying: the mode of the lock

• by: Solaris, Windows XP, Linux, Pthreads

• Solaris

  • implements: variety of locks for support multi-tasking, multi-threading, and multi-processing
  • uses: adaptive mutex for efficiency
    • when protecting data from short code segments (less than a few hundred instructions)
    • starts as: standard semaphore implemented as a spinlock in multiprocessor system
    • lock held by a thread running on another CPU: spins to wait for lock
    • if held by non-run-state thread: block & sleep waiting
      • for signal of lock being released
  • condition variables: to be discussed
    • wait until condition satisfies
    • uses: readers-writers locks when longer sections of code need access to data
      • used to protect frequently-accessed data
        • used in read-only manner
      • relatively expensive to implement

• Windows synchronization

  • kernel: using interrupt masks to protect: access to global resources in uni-processor systems
  • kernel: uses spinlocks for multi-processor systems
    • for efficiency: threads are never preempted when holding a spinlock
  • thread synchronization: outside the kernel (user mode)
    • Windows: provide dispatcher objects
    • threads: synchronize according to several different mechanism
      • mutex locks, semaphores, events, timers
  • events: similar to condition variables; notify waiting thread when condition occurs
  • timers: used to notify one / more thread that specific amount of time has expired
  • dispatcher objects: either signaled-state (object available) or non-signaled state (occupied & block / wait)

• Linux synchronization

  • prior to kernel 2.6: disables interrupts to implement short critical sections

    • 2.6 and later: fully preemptive kernel

  • provides:

    • semaphores
    • spinlocks (for multi-processor)
    • atomic integer, and math operations involving it
    • reader-writer locks

  • on single CPU: spinlocks replaced by enabling / disabling kernel preemption

  • atomic variables: like atomic_t

    • e.g. variable atomic_t counter; int value;

    atomic operation	effect
    atomic_set(&counter, 5);	counter = 5
    atomic_add(10, &counter);	counter = counter + 10
    atomic_sub(4, &counter);	counter = counter - 4
    atomic_inc(&counter);	counter = counter + 1
    value = atomic_read(&counter);	value = 12

• POSIX synchronization

  • POSIX API: provides
    • mutex locks
    • semaphores
    • condition variables
  • widely used on UNIX, Linux, an MAcOS
  • creating & initializing the lock

    #include <pthread.h>
    
    pthread_mutex_t mutex;
    
    /* create and initialize the mutex lock */
    pthread_mutex_init(&mutex, NULL);
    

  • acquiring and releasing the lock

    /* acquire the mutex lock */
    pthread_mutex_lock(&mutex);
    
    /* critical section */
    
    /* release the mutex lock */
    pthread_mutex_unlock(&mutex);
    

  • POSIX condition variables
    • associated w/ POSIX mutex lock to provide: mutual exclusion
    • 👨‍🏫 must be in combination
    • modification of condition variable itself: not guaranteed to be exclusive
      • mutex lock needed

    pthread_mutex_t mutex;
    pthread_cond_t cond_var;
    
    pthread_mutex_init(&mutex, NULL);
    pthread_cond_init(&cond_var, NULL);
    

    • waiting for condition a==b to be true:

      pthread_mutex_lock(&mutex);
      while (a != b)
        pthread_cond_wait(&cond_var, &mutex);
      
      pthread_mutex_unlock(&mutex);
      

      • pthread_cond_wait: in addition to putting the calling thread to sleep
        • release the lock when putting said caller to sleep
        • no other signal: can acquire lock / signal it to wake up
      • it also: release on mutex
        • thus: others can modify the condition..?

      pthread_mutex_lock(&mutex);
      a = b;
      pthread_cond_signal(&cond_var);
      pthread_mutex_unlock(&mutex);
      

      • when signalling: make sure to have the lock held
        • ensures: there is no race condition
      • before returning & being waked up: pthread_cond_wait re-acquires the lock
        • ensures: any time: waiting thread is running "between the lock acquired in the beginning"
        • lock: release at the end
  • 👨‍🏫 there are situation mutex can replace condition variable
    • but there are also situations it can't

• ❓ if we can analyze deadlock given RAG?
  • 👨‍🏫 yes, given particular RAG: we can identify the deadlock
  • then, is it possible to check all possible states of a program
    • 👨‍🏫 theoretically, yet not feasible
• ❓ in EVM / distributed system, how can we apply similar tactics?
  • e.g. smart contracts also apply similar idea (e.g. mutex) to prevent reentrancy
  • how can we coordinate it across multiple computers? Do we consider each computer as a core?
    • 👨‍🏫 we still consider each computer core as individual cores
  • 👨‍🏫 we can't even work it out for a single computer, how can we do so for entire network?
    • overhead will be too much: 10 ~ 20 times slower
    • we usually do something similar to deadlock detection
• ❓ Rust utilizes advanced compiler to ensure that there is no memory leak, runtime error, etc.
  • can we do similar to programs, so that there won't be issues?
  • 👨‍🏫 too complex, it won't be feasible
  • 👨‍🎓 it would be to compress all as a docker-like gigantic and atomic multi-core process
    • can we really call that as a single process at this point?
• ❓ Is deadlock detection somewhat similar to garbage collector?
  • in that they check problem regularly
  • 👨‍🏫 yes

• Deadlock in multi-threaded application

  • order of threads running: depending on CPU scheduler
    • identifying testing deadlocks: hard
    • as they may occur only under certain scheduling circumstances
  • example code

    code
    

  • deadlock with lock ordering

    void transaction(Account from, Account to, double amount) {
        mutex lock1, lock2;
        lock1 = get_lock(from);
        lock2 = get_lock(to);
        acquire(lock1);
            acquire(lock2);
                withdraw(from, amount);
                deposit(to, amount);
            release(lock2);
        release(lock1);
    }
    

    • transactions: execute concurrently
    • 1 transferring 25 from A to B, 2 transferring 50 from B to A
    • 👨‍🏫 we can have deadlock among any no. of processes (not just 2)

• System model

  • system:consist of resources
  • resource types: $R_1,R_2,\dots ,R_m$
    • $n$: no. of types of resources
      • not no. of resources
    • e.g. CPU cycles, memory spaces, files, IO devices, semaphores...
  • each resource type $R_i$: w/ $W_i$ instances
  • each process $P_i$: utilizes a resource as follows
    • request
    • use
    • release

• Deadlock characterization

  • deadlock involving multiple processes: arise if following 4 conditions hold simultaneously
    • necessary to not sufficient conditions
    • 👨‍🏫 sufficient condition not known
  • mutual exclusion: only ne process at a time: can use a resource
  • hold and wait: a process holding a resource, waiting to acquire additional resource (held by anther)
  • no preemption: resource: can be released only voluntarily by process holding it
  • circular wait: set of $n$ waiting process s.t.
    • $P_i$ waiting for resource held by $P_{i+1}$
    • and $P_n$ for $P_1$
  • if there is dead lock -> conditions hold
    • is any of the condition doesn't hold -> no dead lock

• Resource-allocation graph

  • let graph $G=(V,E)$
  • $V$: partitioned into two types
    • bipartite!
    • $P=\{P_1,P_2,\dots ,P_n\}$: set of all processes in system
    • $R=\{R_1,R_2,\dots ,R_n\}$: set of all resource types in system
  • request edge: directed edge $P_i\to R_j$
    • 👨‍🎓 please give me this resource!
  • assignment edge: directed edge $R_j\to P_i$
    • 👨‍🎓 this resource belong to xxx!
  • example
    • 
    • 1 instance of $R_1$
    • 2 instances of $R_2$
    • 1 instance of $R_3$
    • 3 instance of $R_4$
    • $T_1$: holds one $R_2$ and waiting for $R_1$
    • $T_2$: holds one $R_1$, one $R_2$, waiting for $R_3$
    • $T_3$: holding one $R_3$
    • 👨‍🏫 no circular wait: no deadlock (for this instance / snapshot)
  • example, with deadlock
    • 
    • cycles exist:
      • $P_1\to R_1\to P_2\to R_3\to P_3\to R_2\to P_1$
      • $P_2\to R_3\to P_3\to R_2\to P_2$
    • processes $P_1,P_2,P_3$: deadlocked
  • graph with a cycle, yet no deadlock
    • 
    • cycles exist, yet no deadlock
  • basic facts
    • if a graph has no cycle: no deadlock
    • if a graph contains a cycle: system may / may not be in a deadlocked state
      • if only one instance per resource type: then deadlock
      • if several instances per resource type: possibility of deadlock

• Methods for handling deadlocks

  • ensure that: system will never enter a deadlock state
    • deadlock prevention: ensure at least one of the necessary conditions cannot hold
    • deadlock avoidance: requires additional information
      • given in advance, concerning
  • deadlock detection: allow system to enter a deadlock state
    • periodically detect: if there is a deadlock & recover from it
    • 👨‍🎓 ~= garbage collector?

• Deadlock prevention

  • mutual exclusive: unavoidable
    • some resources: cannot be shared!
  • hold & wait: must guarantee: whenever a process request a resource, it doesn't hold any other resources
    • require: each process to request and allocated all its resources before execution
      • request resources only when process: has none
    • disadvantages: low resource utilization, possible starvation
  • no preemption:
    • preempt resource occupied by another resource
      • preempted resource: added to waiting resource
    • process: will be restarted only if all its old resources are regained
    • only for resources w/ state being easily saved & restored
      • e.g. registers, memory space, and DB transactions
      • cannot be generally applied ro resource (e.g. locks, semaphore)
  • circular wait: impose total ordering of all resource types
    • require: each process requests resources in an increasing order of enumeration
      • thus: must request $R_j$ before $R_i$ if $j>i$
    • can be proved by contradiction
      • let: set of processes involved in circular wait: $p=<P_0,P_1,\dots ,P_n>$
      • $P_i$: awaiting for $R_i$, held by process $P_{i+1}$
      • $P_n$: waiting for $R_n$ held by $P_0$
      • implies: $R_0<R_1<R_2\cdots <R_n<R_0$
      • $R_0<R_0$: impossible
        • thus, there can be no circular wait
    • 👨‍🏫 same problem as hold & wait: very slow
      • problem: request resource much earlier than needed / expected

• Circular wait example

  • invalidating circular wait condition: most common
    • assign each resource (i.e. mutex locks): unique number
    • resources: must be acquired in order
  • code

    first_mutex = 1
    second_mutex = 5
    

• Deadlock avoidance

  • requires: system w/ additional a priori information available
    • e.g. w/ knowledge of complete sqe. of request and release for each process
      • system: can decide for each request whether process should wait to avoid a possible future deadlock
    • simples & most useful model:
      • requiring each process declaration on max no. of resources of each type
      • that it might need (worst case)
    • deadlock avoidance algorithm: dynamically examining resource-allocation state
    • de ensure: circular-wait condition can never exist
  • resource allocation state: defined by
    1. available resources
    2. allocated resources
    3. max demand of processes

• ⭐⭐ Safe state

  • when a process: request an available resource
    • system: must decide whether allocation will leave system in safe state
  • system: in safe state if there exists a safe sequence $<P_1,P_2,\dots ,P_n>$ consisting all processes in systems
    • s.t. for each $P_i$, resource $P_i$ can still request:
      • can be satisfied by currently available resources + resources held by all $P_j$ for $j<i$
        • i.e. can be freed by execution of $P_i$
        • 👨‍🏫 $P_i$: not waiting for anybody
    • 👨‍🏫 procedure: find $P_1$ s.t. it can be executed w/o any need for waiting
  • i.e. if $P_i$: resource needs not immediately available:
    • $P_i$: can wait until all $P_j$ have finished
    • when $P_j$ finished: $P_i$ obtain needed resources, execute, return allocated resources & terminate
    • when $P_i$ terminates, $P_{i+1}$: obtain needed resources, and so on
  • if no such seq. exist: system state is unsafe
    • 👨‍🏫 not saying that there must be a deadlock
    • i.e. no immediate solution found!
  • ⭐ basic facts
    • if system is in safe state: no deadlocks
    • if a system is in unsafe state: possibility of deadlock
    • 

• Avoidance algorithms

  • single instance of a resource type
    • use resource allocation graph
  • multiple instances of a resource type
    • use Banker's algorithm

• Resource-allocation graph scheme

  • simply check: whether there exists a cycle
    • 👨‍🏫 if so: deadlock!

• Banker's algorithm

  • multiple instances
  • each process: must declare priori maximum usage
    • if resulting state is unsafe: don't allocate resource!
  • when process requests a resource: wait
  • check if: allocation result in a safe state / not
  • when process
  • similar to banking loan system

• Data structure for Banker's algorithm

  • $n$: no. of processes, $m$: no. of resources types
  • available: vector of length $m$
    • if available[j] = k, then $k$ instances of type $R_j$ available
  • max: $n\times m$ matrix
    • if Max[i,j] = k, then $P_i$ may request at most $k$ instances of $R_j$
  • allocation: $n\times m$ matrix
    • if Allocation[i,j] = k, $P_i$ currently allocated $k$ instance of $R_j$
  • need: $n\times m$ matrix
    • if Need[i,j] = k, then $P_i$ may need $k$ more instances of $R_j$ tom complete tasks
    • ⭐⭐ Need[i,j] = Max[i, k] - Allocation[i, j]
    • maximum s.t. process can request additionally
      • ensure: the accumulated request doesn't exceed maximum
        • i.e. check validity / legitimacy
  • 👨‍🏫 above properties: defines snapshot

• Safety algorithm

  • input: state
  1. let work & finish: vectors of length $m,n$
     • initialize:
       • Work = Available
       • Finish[i] = false for i ∈ [0, n-1]
  2. find $i$ s.t. both
     • Finish[i] = false
     • Need_i ≤ Work
  3. Work = Work + Allocation_i
     • Finish[i] = true
     • go to step 2
  4. if Finish[i] == true for all $i$: system is in a safe state
     • otherwise, unsafe

• Resource-request algorithm for process $P_i$

  • input: request
  • request: request vector for process $P_i$