OPERATING SYSTEMS
1 A MEMORY-CENTRIC SYSTEM MODEL 1 1 OVERVIEW 1 2 MODELING THE SYSTEM 1 2 1 THE SIMPLEST POSSIBLE MODEL 1 2 2 WHAT IS THIS ‘‘SYSTEM STATE’’? 1 2 3 REFINING NON-PROCESSOR ACTIONS 1 2 4 INTERRUPT REQUESTS 1 2 5 AN IMPORTANT PERIPHERAL: THE TIMER 1 3 BARE-BONES PROCESSOR MODEL 1 3 1 WHAT DOES THE PROCESSOR DO? 1 3 2 PROCESSOR INTERNAL STATE: REGISTERS 1 3 3 PROCESSOR INSTRUCTIONS 1 3 4 ASSEMBLY LANGUAGE 1 3 5 ARITHMETIC LOGIC UNIT 1 3 6 INSTRUCTION CYCLE 1 3 7 BARE BONES PROCESSOR MODEL 1 4 ADVANCED PROCESSOR MODEL 1 4 1 STACK SUPPORT 1 4 2 SUBROUTINE CALLS 1 4 3 INTERRUPT HANDLING 1 4 4 DIRECT MEMORY ACCESS 1 4 5 COMPLETE CYCLE-BASED PROCESSOR MODEL 1 4 6 CACHING 1 4 7 RUNNING A PROGRAM ON THE PROCESSOR 1 4 8 HIGH-LEVEL INSTRUCTIONS 1 5 BASIC OPERATING SYSTEM CONCEPTS 1 5 1 TASKS AND CONCURRENCY 1 5 2 THE REGISTER FILE 1 5 3 TIME SLICING AND SCHEDULING 1 5 4 PRIVILEGES CONTENTS 1 5 5 MEMORY MANAGEMENT 1 5 6 TRANSLATION LOOK-ASIDE BUFFER (TLB) 1 6 EXERCISES AND QUESTIONS 1 6 1 TASK SCHEDULING 1 6 2 TLB MODEL 1 6 3 MODELING THE SYSTEM 1 6 4 BARE-BONES PROCESSOR MODEL 1 6 5 ADVANCED PROCESSOR MODEL 1 6 6 BASIC OPERATING SYSTEM CONCEPTS 2 A PRACTICAL VIEW OF THE LINUX SYSTEM 2 1 OVERVIEW 2 2 BASIC CONCEPTS 2 2 1 OPERATING SYSTEM HIERARCHY 2 2 2 PROCESSES 2 2 3 USER SPACE AND KERNEL SPACE 2 2 4 DEVICE TREE AND ATAGS 2 2 5 FILES AND PERSISTENT STORAGE PARTITION FILE SYSTEM 2 2 6 ‘EVERYTHING IS A FILE’ 2 2 7 USERS 2 2 8 CREDENTIALS 2 2 9 PRIVILEGES AND USER ADMINISTRATION 2 3 BOOTING LINUX ON THE ARM (RASPBERRY PI 3) 2 3 1 BOOT PROCESS STAGE 1: FIND THE BOOTLOADER 2 3 2 BOOT PROCESS STAGE 2: ENABLE THE SDRAM 2 3 3 BOOT PROCESS STAGE 3: LOAD THE LINUX KERNEL INTO MEMORY 2 3 4 BOOT PROCESS STAGE 4: START THE LINUX KERNEL 2 3 4 BOOT PROCESS STAGE 5: RUN THE PROCESSOR-INDEPENDENT KERNEL CODE 2 3 5 INITIALIZATION 2 3 6 LOGIN 2 4 KERNEL ADMINISTRATION AND PROGRAMMING 2 4 1 LOADABLE KERNEL MODULES AND DEVICE DRIVERS 2 4 2 ANATOMY OF A LINUX KERNEL MODULE 2 4 3 BUILDING A CUSTOM KERNEL MODULE 2 4 4 BUILDING A CUSTOM KERNEL VII 2 5 KERNEL ADMINISTRATION AND PROGRAMMING 2 5 1 PROCESS MANAGEMENT 2 5 2 PROCESS SCHEDULING 2 5 3 MEMORY MANAGEMENT 2 5 4 CONCURRENCY AND PARALLELISM 2 5 5 INPUT/OUTPUT 2 5 6 PERSISTENT STORAGE 2 5 7 NETWORKING 2 6 SUMMARY 2 7 EXERCISES AND QUESTIONS 2 7 1 INSTALLING RASPBIAN ON THE RASPBERRY PI 2 7 2 SETTING UP SSH UNDER RASPBIAN 2 7 3 WRITING A KERNEL MODULE 2 7 4 BOOTING LINUX ON THE RASPBERRY PI 2 7 5 INITIALIZATION 2 7 6 LOGIN 2 7 7 ADMINISTRATION 3 HARDWARE ARCHITECTURE 3 1 OVERVIEW 3 2 ARM HARDWARE ARCHITECTURE 3 3 ARM CORTEX M0+ 3 3 1 INTERRUPT CONTROL 3 3 2 INSTRUCTION SET 3 3 3 SYSTEM TIMER 3 3 4 PROCESSOR MODE AND PRIVILEGES 3 3 5 MEMORY PROTECTION 3 4 1 INTERRUPT CONTROL 3 4 2 INSTRUCTION SET FLOATING-POINT AND SIMD SUPPORT 3 4 3 SYSTEM TIMER 3 4 4 PROCESSOR MODE AND PRIVILEGES 3 4 5 MEMORY MANAGEMENT UNIT TRANSLATION LOOK-ASIDE BUFFER ADDITIONAL CACHES 3 4 6 MEMORY SYSTEM L1 CACHE L2 CACHE DATA CACHE COHERENCY 3 5 ADDRESS MAP 3 6 DIRECT MEMORY ACCESS 3 7 SUMMARY 3 8 EXERCISES AND QUESTIONS 3 8 1 BARE-BONES PROGRAMMING 3 8 2 ARM HARDWARE ARCHITECTURE 3 8 3 ARM CORTEX M0+ 3 8 5 ADDRESS MAP 3 8 6 DIRECT MEMORY ACCESS 4 PROCESS MANAGEMENT 4 1 OVERVIEW 4 2 THE PROCESS ABSTRACTION 4 2 1 DISCOVERING PROCESSES 4 2 2 LAUNCHING A NEW PROCESS 4 2 3 DOING SOMETHING DIFFERENT 4 2 4 ENDING A PROCESS 4 3 PROCESS METADATA 4 3 1 THE /PROC FILE SYSTEM 4 3 2 LINUX KERNEL DATA STRUCTURES 4 3 3 PROCESS HIERARCHIES 4 4 PROCESS STATE TRANSITIONS 4 5 CONTEXT SWITCH 4 6 SIGNAL COMMUNICATIONS 4 6 1 SENDING SIGNALS 4 6 2 HANDLING SIGNALS 4 7 SUMMARY 4 8 FURTHER READING 4 9 EXERCISES AND QUESTIONS 4 9 1 MULTIPLE CHOICE QUIZ 4 9 2 METADATA MIX IX 4 9 3 RUSSIAN DOLL PROJECT 4 9 4 PROCESS OVERLOAD 4 9 5 SIGNAL FREQUENCY 4 9 6 ILLEGAL INSTRUCTIONS 5 PROCESS SCHEDULING 5 1 OVERVIEW 5 2 SCHEDULING OVERVIEW: WHAT, WHY, HOW? 5 2 1 DEFINITION 5 2 2 SCHEDULING FOR RESPONSIVENESS 5 2 3 SCHEDULING FOR PERFORMANCE 5 2 4 SCHEDULING POLICIES 5 3 RECAP: THE PROCESS LIFECYCLE 5 4 SYSTEM CALLS 5 4 1 THE LINUX SYSCALL(2) FUNCTION 5 4 2 THE IMPLICATIONS OF THE SYSTEM CALL MECHANISM 5 5 SCHEDULING PRINCIPLES 5 5 1 PREEMPTIVE VERSUS NON-PREEMPTIVE SCHEDULING 5 5 2 SCHEDULING POLICIES 5 5 3 TASK ATTRIBUTES 5 6 SCHEDULING CRITERIA 5 7 SCHEDULING POLICIES 5 7 1 FIRST-COME, FIRST-SERVED (FCFS) 5 7 2 ROUND-ROBIN (RR) 5 7 3 PRIORITY-DRIVEN SCHEDULING 5 7 4 SHORTEST JOB FIRST (SJF) AND SHORTEST REMAINING TIME FIRST (SRTF) 5 7 5 SHORTEST ELAPSED TIME FIRST (SETF) 5 7 6 PRIORITY SCHEDULING 5 7 7 REAL-TIME SCHEDULING 5 7 8 EARLIEST DEADLINE FIRST (EDF) 5 8 SCHEDULING IN THE LINUX KERNEL 5 8 1 USER PRIORITIES: NICENESS 5 8 2 SCHEDULING INFORMATION IN THE TASK CONTROL BLOCK (TCB) 5 8 3 PROCESS PRIORITIES IN THE LINUX KERNEL PRIORITY INFO IN TASK_STRUCT PRIORITY AND LOAD WEIGHT 5 8 4 NORMAL SCHEDULING POLICIES: THE COMPLETELY FAIR SCHEDULER (CFS) 5 8 5 SOFT REAL-TIME SCHEDULING POLICIES 5 8 6 HARD REAL-TIME SCHEDULING POLICY TIME BUDGET ALLOCATION 5 8 7 KERNEL PREEMPTION MODELS 5 8 8 THE RED-BLACK TREE IN THE LINUX KERNEL CREATING A NEW RBTREE SEARCHING FOR A VALUE IN A RBTREE INSERTING DATA INTO A RBTREE REMOVING OR REPLACING EXISTING DATA IN A RBTREE ITERATING THROUGH THE ELEMENTS STORED IN A RBTREE (IN SORT ORDER) CACHED RBTREES 5 8 9 LINUX SCHEDULING COMMANDS AND API NORMAL PROCESSES REAL-TIME PROCESSES 5 9 SUMMARY 5 10 EXERCISES AND QUESTIONS 5 10 1 WRITING A SCHEDULER 5 10 2 SCHEDULING 5 10 3 SYSTEM CALLS 5 10 4 SCHEDULING POLICIES 5 10 5 THE LINUX SCHEDULER 6 MEMORY MANAGEMENT 6 1 OVERVIEW 6 2 PHYSICAL MEMORY 6 3 VIRTUAL MEMORY 6 3 1 CONCEPTUAL VIEW OF MEMORY 6 3 2 VIRTUAL ADDRESSING 6 3 3 PAGING 6 4 PAGE TABLES 6 4 1 PAGE TABLE STRUCTURE 6 4 2 LINUX PAGE TABLES ON ARM 6 4 3 PAGE METADATA 6 4 4 FASTER TRANSLATION 6 4 5 ARCHITECTURAL DETAILS XI 6 5 MANAGING MEMORY OVER-COMMITMENT 6 5 1 SWAPPING 6 5 2 HANDLING PAGE FAULTS 6 5 3 WORKING SET SIZE 6 5 4 IN-MEMORY CACHES 6 5 5 PAGE REPLACEMENT POLICIES RANDOM NOT RECENTLY USED (NRU) CLOCK LEAST RECENTLY USED TUNING THE SYSTEM 6 5 6 DEMAND PAGING 6 5 7 COPY ON WRITE (COW) 6 5 8 OUT OF MEMORY KILLER 6 6 PROCESS VIEW OF MEMORY 6 7 ADVANCED TOPICS 6 8 FURTHER READING 6 9 EXERCISES AND QUESTIONS 6 9 1 HOW MUCH MEMORY? 6 9 2 HYPOTHETICAL ADDRESS SPACE 6 9 3 CUSTOM MEMORY PROTECTION 6 9 4 INVERTED PAGE TABLES 6 9 5 HOW MUCH MEMORY? 6 9 6 TINY VIRTUAL ADDRESS SPACE 6 9 7 DEFINITIONS QUIZ 7 CONCURRENCY AND PARALLELISM 7 1 OVERVIEW 7 2 CONCURRENCY AND PARALLELISM: DEFINITIONS 7 2 1 WHAT IS CONCURRENCY? 7 2 2 WHAT IS PARALLELISM? 7 2 3 PROGRAMMING MODEL VIEW 7 3 CONCURRENCY 7 3 1 WHAT ARE THE ISSUES WITH CONCURRENCY? SHARED RESOURCES EXCHANGE OF INFORMATION 7 3 2 CONCURRENCY TERMINOLOGY CRITICAL SECTION SYNCHRONIZATION DEADLOCK 7 3 3 SYNCHRONIZATION PRIMITIVES 7 3 4 ARM HARDWARE SUPPORT FOR SYNCHRONIZATION PRIMITIVES EXCLUSIVE OPERATIONS AND MONITORS SHAREABILITY DOMAINS 7 3 5 LINUX KERNEL SYNCHRONIZATION PRIMITIVES ATOMIC PRIMITIVES MEMORY OPERATION ORDERING MEMORY BARRIERS SPIN LOCKS FUTEXES KERNEL MUTEXES SEMAPHORES 7 3 6 POSIX SYNCHRONIZATION PRIMITIVES MUTEXES CONDITION VARIABLES 7 4 PARALLELISM 7 4 1 WHAT ARE THE CHALLENGES WITH PARALLELISM? 7 4 2 ARM HARDWARE SUPPORT FOR PARALLELISM 7 4 3 LINUX KERNEL SUPPORT FOR PARALLELISM SMP BOOT PROCESS LOAD BALANCING PROCESSOR AFFINITY CONTROL 7 5 DATA-PARALLEL AND TASK-PARALLEL PROGRAMMING MODELS 7 5 1 DATA PARALLEL PROGRAMMING FULL DATA PARALLELISM: MAP REDUCTION ASSOCIATIVITY BINARY TREE-BASED PARALLEL REDUCTION 7 5 2 TASK PARALLEL PROGRAMMING 7 6 PRACTICAL PARALLEL PROGRAMMING FRAMEWORKS 7 6 1 POSIX THREADS (PTHREADS) 7 6 2 OPENMP 7 6 3 MESSAGE PASSING INTERFACE (MPI) 7 6 4 OPENCL 7 6 5 INTEL THREADING BUILDING BLOCKS (TBB) 7 6 6 MAPREDUCE 7 7 SUMMARY 7 8 EXERCISES AND QUESTIONS 7 8 1 CONCURRENCY: SYNCHRONIZATION OF TASKS 7 8 1 PARALLELISM 8 INPUT/OUTPUT 8 1 OVERVIEW 8 2 THE DEVICE ZOO 8 2 1 INSPECT YOUR DEVICES 8 2 2 DEVICE CLASSES 8 2 3 TRIVIAL DEVICE DRIVER 8 3 CONNECTING DEVICES 8 3 1 BUS ARCHITECTURE 8 4 COMMUNICATING WITH DEVICES 8 4 1 DEVICE ABSTRACTIONS 8 4 2 BLOCKING VERSUS NON-BLOCKING IO 8 4 3 MANAGING IO INTERACTIONS POLLING INTERRUPTS DIRECT MEMORY ACCESS 8 5 INTERRUPT HANDLERS 8 5 1 SPECIFIC INTERRUPT HANDLING DETAILS 8 5 2 INSTALL AN INTERRUPT HANDLER 8 6 EFFICIENT IO 8 7 FURTHER READING 8 8 EXERCISES AND QUESTIONS 8 8 1 HOW MANY INTERRUPTS? 8 8 2 COMPARATIVE COMPLEXITY 8 8 3 ROLL YOUR OWN INTERRUPT HANDLER 8 8 4 MORSE CODE LED DEVICE 9 PERSISTENT STORAGE 9 1 OVERVIEW 9 2 USER PERSPECTIVE ON THE FILE SYSTEM 9 2 1 WHAT IS A FILE? 9 2 2 HOW ARE MULTIPLE FILES ORGANIZED? 9 3 OPERATIONS ON FILES 9 4 OPERATIONS ON DIRECTORIES 9 5 KEEPING TRACK OF OPEN FILES 9 6 CONCURRENT ACCESS TO FILES 9 7 FILE METADATA 9 8 BLOCK-STRUCTURED STORAGE 9 9 CONSTRUCTING A LOGICAL FILE SYSTEM 9 9 1 VIRTUAL FILE SYSTEM 9 10 INODES 9 10 1 MULTIPLE LINKS, SINGLE INODE 9 10 2 DIRECTORIES 9 11 1 LAYOUT ON DISK 9 11 2 INDEXING DATA BLOCKS 9 11 3 MULTIPLE LINKS, SINGLE INODE 9 11 4 CHECKSUMMING 9 11 5 ENCRYPTION 9 12 FAT 9 12 1 ADVANTAGES OF FAT 9 12 2 CONSTRUCT A MINI FILE SYSTEM USING FAT 9 13 LATENCY REDUCTION TECHNIQUES 9 14 FIXING UP BROKEN FILE SYSTEMS 9 15 ADVANCED TOPICS 9 16 FURTHER READING 9 17 EXERCISES AND QUESTIONS 9 17 1 HYBRID CONTIGUOUS AND LINKED FILE SYSTEM 9 17 2 EXTRA FAT FILE POINTERS 9 17 3 EXPECTED FILE SIZE 9 17 4 EXT4 EXTENTS 9 17 5 ACCESS TIMES 9 17 6 DATABASE DECISIONS XV 10 NETWORKING 10 1 OVERVIEW 10 2 WHAT IS NETWORKING 10 3 WHY IS NETWORKING PART OF THE KERNEL? 10 4 THE OSI LAYER MODEL 10 5 THE LINUX NETWORKING STACK 10 5 1 DEVICE DRIVERS 10 5 2 DEVICE-AGNOSTIC INTERFACE 10 5 3 NETWORK PROTOCOLS 10 5 4 PROTOCOL-AGNOSTIC INTERFACE 10 5 5 SYSTEM CALL INTERFACE 10 5 6 SOCKET BUFFERS 10 6 THE POSIX STANDARD SOCKET INTERFACE LIBRARY 10 6 1 STREAM SOCKET (TCP) COMMUNICATIONS FLOW 10 6 2 COMMON INTERNET DATA TYPES SOCKET ADDRESS DATA TYPE: STRUCT SOCKADDR INTERNET SOCKET ADDRESS DATA TYPE: STRUCT SOCKADDR_IN 10 6 3 COMMON POSIX SOCKET API FUNCTIONS CREATE A SOCKET DESCRIPTOR: SOCKET() BIND A SERVER SOCKET ADDRESS TO A SOCKET DESCRIPTOR: BIND() ENABLE SERVER SOCKET CONNECTION REQUESTS: LISTEN() ACCEPT A SERVER SOCKET CONNECTION REQUEST: ACCEPT() CLIENT CONNECTION REQUEST: ‘CONNECT()’ WRITE DATA TO A STREAM SOCKET: SEND() READ DATA FROM A STREAM SOCKET: RECV() SETTING SERVER SOCKET OPTIONS: SETSOCKOPT() 10 6 4 COMMON UTILITY FUNCTIONS INTERNET ADDRESS MANIPULATION FUNCTIONS INTERNET NETWORK/HOST BYTE ORDER MANIPULATION FUNCTIONS HOST TABLE ACCESS FUNCTIONS 10 6 5 BUILDING APPLICATIONS WITH TCP REQUEST/RESPONSE COMMUNICATION USING TCP TCP SERVER TCP CLIENT 10 6 6 BUILDING APPLICATIONS WITH UDP UDP SERVER UDP CLIENT UDP CLIENT USING CONNECT() 10 6 7 HANDLING MULTIPLE CLIENTS THE SELECT() SYSTEM CALL MULTIPLE SERVER PROCESSES: FORK() AND EXEC() MULTITHREADED SERVERS USING PTHREADS 10 7 SUMMARY 10 8 EXERCISES AND QUESTIONS 10 8 1 SIMPLE SOCIAL NETWORKING 10 8 2 THE LINUX NETWORKING STACK 10 8 3 THE POSIX SOCKET API 11 ADVANCED TOPICS 11 1 OVERVIEW 11 2 SCALING DOWN 11 3 SCALING UP 11 4 VIRTUALIZATION AND CONTAINERIZATION 11 5 SECURITY 11 5 1 ROWHAMMER, RAMPAGE, THROWHAMMER, AND NETHAMMER 11 5 2 SPECTRE, MELTDOWN, FORESHADOW 11 6 VERIFICATION AND CERTIFICATION 11 7 RECONFIGURABILITY 11 8 LINUX DEVELOPMENT ROADMAP 11 9 FURTHER READING 11 10 EXERCISES AND QUESTIONS 11 10 1 MAKE A MINIMAL KERNEL 11 10 2 VERIFY IMPORTANT PROPERTIES 11 10 3 COMMERCIAL COMPARISON 11 10 4 FOR OR AGAINST CERTIFICATION 11 10 5 DEVOLVED DECISIONS 11 10 6 UNDERCLOCK, OVERCLOCK