Notes for 周志遠作業系統 Most of the content are just text version of the slides at the slide link. The images are from the text book and the slides. The order of the chapters follows the teacher’s teaching sequence, not the numerical order. Ch0: Historical Prospective Ch1: Introduction Ch2: OS Structure Ch3: Processes Concept Ch8: Memory Management Ch9: Virtual Memory Ch4: Multithreaded Programming Ch5: Process Scheduling
Process Scheduling Overview Basic Concepts Scheduling Algorithms Special Scheduling Issues Scheduling Case Study Basic Concepts The idea of multiprogramming: Keep several processes in memory. Every time one process has to wait, another process takes over the use of the CPU CPU-I/O burst cycle: Process execution consists of a cycle of CPU execution and I/O wait (i.e., CPU burst and I/O burst). Generally, there is a large number of short CPU bursts, and a small number of long CPU bursts A I/O-bound program would typically has many very short CPU bursts A CPU-bound program might have a few long CPU bursts ...
Multithreaded Programming Overview Thread Introduction Multithreading Models Threaded Case Study Threading Issues Thread Introduction Thread thread a.k.a lightweight process: basic unit of CPU utilization all threads belonging to the same process share: code section, data section, and OS resources (e.g. open files and signals) But each thread has its own (thread control block): thread ID, program counter, register set, and a stack Motivation Example: a web browser One thread displays contents while the other thread receives data from network Example: a web server One request / process: poor performance One request / thread: better performance as code and resource sharing Example: RPC server One RPC request / thread Benefits of Multithreading Responsiveness: allow a program to continue running even if part of it is blocked or is performing a lengthy operation Resource sharing: several different threads of activity all within the same address space Utilization of MP (multi processor) architectur e: Several threads may be running in parallel on different processors Economy: Allocating memory and resources for process creation is costly. In Solaris, creating a process is about 30 times slower than is creating a thread, and context switching is about five times slower. A register set switch is still required, but no memory-management related work is needed Why Thread? ...
Memory Management Overview Background Demand Paging Process Creation Page Replacement Allocation of Frames Thrashing Operating System Examples Background Why we don’t want to run a program that is entirely in memory Many code for handling unusual errors or conditions Certain program routines or features are rarely used The same library code used by many programs Arrays, lists and tables allocated but not used Virtual memory: separation of user logical memory from physical memory ...
Memory Management Overview Background Swapping Contiguous Allocation Paging Segmentation Segmentation with Paging Background Main memory and registers are the only storage CPU can access directly Collection of processes are waiting on disk to be brought into memory and be executed Multiple programs are brought into memory to improve resource utilization and response time to users A process may be moved between disk and memory during its execution How to refer memory in a program? address binding How to load a program into memory? static/dynamic loading and linking How to move a program between mem. & disk? swap How to allocate memory? paging, segment ...
Processes Concept Process Concept Process Scheduling Operations on Processes Interprocess Communication Process Concept Program: passive entity stored on disk (executable file) Process: active entity, program in execution in memory A process includes: Code segment (text section) Data section: global variables Stack: temporary local variables and functions Heap: dynamically allocated memory current activity: program counter, register contents A set of associated resources Threads lightweight process, basic unit of CPU utilization All threads belonging to the same process share the same code, data section, OS resources But each threads has its own thread ID, program counter, register set, stack Process State New: process is being created Ready: the process is in the memory waiting to be assigned to a processor Running: instructions are being executed by CPU, might be interrupt and switch to Ready state Waiting: process is waiting for some event to occur (I/O completion, etc) Terminated: process has finished execution Process Control Block (PCB) Info about each process ...
OS Structure OS Services User interface Program Execution I/O operations File-system manipulation Communication (not just between computer, but also between cores, processes, etc) Error detection Resource allocation Accounting Protection and security User Interface CLI (Command Line Interface) Shell: Command-line interpreter (ZSH, BASH), adjusted according to user behavior and preferences (this is also the reason why we need shell even if we have GUI) GUI (Graphical User Interface) Icon represent files, programs, actions, etc ...
Introduction What is an Operating System? computer system has four components: Hardware Operating System Application programs Users OS controls and coordinates the use of hardware/resources. Provides Application Programming Interface (API) to users. User program Executable binary user | ^ v | Compiler -----> Linker compiler ^ user mode | ------------ System library OS interface kernel ^ | v Operating System OS Device drivers ^ | v Architecture Hardware Definition of an OS: Resource allocator: manages and allocates resources to insure efficiency and fairness Control program: controls the execution of user programs and operation of I/O devices Kernel: the one program running at all times (all else begin either system or user programs) Kernel is the most used term for OS. Kernal == OS. ...
This chapter is a historical prospective of OS. Most of them are just conceptual, but they are important to understand the evolution of OS. I find its hard to organize the content, so the table of content is not very structured. Historical Prospective Mainframe: Batch Systems One job at a time No interaction between users and jobs CPU is often idle (I/O speed « CPU speed) OS doesn’t need to make any decision Mainframe: Multi-programming System Overlaps the I/O and computation of jobs Spooling (Simultaneous Peripheral Operation On-Line) I/O is done with no CPU intervention CPU just needs to be notified when I/O is done Memory management, CPU scheduing, I/O system comes in Mainframe: Time-sharing System (Multi-tasking System) interactive system CPU swiches among jobs so frequently that users may interact with programs Switch job when finish waiting I/On a short period of time Users will feel like the task run at the same time New features appear to address new problems ...
How to find all primes under n? Sieve of Eratosthenes This algorithm is a very intuitive way to find all primes under n. We first create a list of numbers from 2 to n and then iterate over the list. For each number i, we mark all its multiples as non-prime. At the end, all numbers that are not marked are prime. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 vector<int> find_primes(int n) { vector<int> primes; vector<bool> is_prime(n + 1, true); for (int i = 2; i * i <= n; i++) { if (is_prime[i]) { for (int j = i * i; j <= n; j += i) { is_prime[j] = false; } } } for (int i = 2; i <= n; i++) { if (is_prime[i]) { primes.push_back(i); } } return primes; } Let’s analyze the time complexity. For each prime number p, we will iterate from p * p to n. Which means that the time complexity is $\sum_{p \text{ is prime}}^{p \leq n} \frac{n}{p} = n\sum_{p \text{ is prime}}^{p \leq n} \frac{1}{p} = n\log\log n$ (prime harmonic series). ...