###### tags: `OS`

# 1062 - Operating System

## Ch01 - Introduction
- Computer system can be divided into four components:
- **Hardware** (ex: CPU, memory, I/O devices)
- **Operating system**
- Controls and coordinates use of hardware among various applications and users
- **Application programs**
- **Users** (ex: people, machines, other computers)
- 

## Ch02 - Operating-System Structures
- A View of Operating System Services
- 
- Layered Operating System
- 
- MS-DOS Layer Structure
- 
- Traditional UNIX System Structure
- 
- Compare with Microkernel System Structure
- 

## Ch03 - Processes
- A **process** includes
- program counter
- stack
- data section
- Process in Memory
- 
- Diagram of Process State
- 
- Process Control Block (**PCB**)
- Process state
- Program counter
- CPU registers
- CPU scheduling information
- Memory-management information
- Accounting information
- I/O status information
- CPU Switch From Process to Process
- 
- **Context-switch** - to save and load PCB
- Process Scheduling Queues
- **Job queue** - set of all processes in the system
- **Ready queue** - set of all processes residing in main memory, ready and waiting to execute
- **Device queues** - set of processes waiting for an I/O device
- Processes migrate among the various queues
- Process Representation in Linux

task_struct {
    pid_t pid;                  // process identifier
    long state;                 // state of the process
    unsigned int time_slice     // scheduling information
    struct task_struct *parent; // this process’s parent
    struct list_head children;  // this process’s children
    struct files_struct *files; // list of open files
    struct mm_struct *mm;       // space of this process
}

- Representation of Process Scheduling
- 
- Schedulers
- **Long-term scheduler** (or job scheduler)
- selects which processes should be brought **into the ready queue**
- is invoked very infrequently (seconds, minutes) -> (may be **slow**)
- controls the **degree of multiprogramming**
- **Short-term scheduler** (or CPU scheduler)
- selects which process should be **executed next and allocates CPU**
- Sometimes the **only** scheduler in a system
- is invoked very frequently (milliseconds) -> (must be **fast**)
- Medium Term Scheduling
- 
- 臨時將進程從內存中去除，放入第二儲存設備（如硬碟）中，或亦而反之。這通常被稱為「換出(swap out)」和「換入(swap in)」。
- **目的**：可以會將那些一直不活躍的進程，優先級低的進程，頻繁產生頁錯誤的進程，或者占用大量內存的進程放入交換區，為其它程序釋放內存。當系統內存充足時，或者程序不再處於阻塞狀態時，調度器又會將剛剛被放入交換區中的進程重新放入內存中。
- Advantages of **process cooperation**
- Information sharing
- Computation speed-up
- Modularity
- Convenience
- Two models of interprocess communication (**IPC**)
- Shared memory
- Message passing
- 
- **Direct** Communication
- Processes must name each other explicitly:
- `send(P, message)` - send a message to process `P`
- `receive(Q, message)` - receive a message from process `Q`
- Properties of communication link
- Links are established automatically
- A link is associated with exactly one pair of communicating processes
- Between each pair there exists exactly one link
- The link may be unidirectional, but is usually bi-directional
- **Indirect** Communication
- Messages are directed and received from mailboxes (also referred to as ports)
- Each mailbox has a unique id
- Processes can communicate only if they share a mailbox
- Properties of communication link
- Link established only if processes share a common mailbox
- A link may be associated with many processes
- Each pair of processes may share several communication links
- Link may be unidirectional or bi-directional
- Operations
- create a new mailbox
- send and receive messages through mailbox
- destroy a mailbox
- Primitives are defined as:
- `send(A, message)` - send a message to mailbox `A`
- `receive(A, message)` - receive a message from mailbox `A`
- Execution of RPC
- 

## Ch04 - Threads
- Single and Multithreaded Processes
- 
- Multithreading Model (user-level thread to kernel thread)
- Many-to-One
- Solaris Green Threads
- GNU Portable Threads
- One-to-One
- Windows NT/XP/2000
- Linux
- Solaris 9 and later
- Many-to-Many
- Solaris prior to version 9
- Windows NT/2000 with the **ThreadFiber** package
- Two-level Model (base on **M:M**, but allow **1:1**)
- IRIX
- HP-UX
- Tru64 UNIX
- Solaris 8 and earlier
- Threading Issues
- Semantics of **fork()** and **exec()** system calls
- `fork()` - 用來建立 child process。
- `exec()` - 以一個「外部程式」來取代自己的執行空間。
- `spawn()` - 建立一個「外部程式」的 child process `= fork() + exec()`
- Thread cancellation of target thread
- **Asynchronous** - terminates the target thread immediately.
- **Deferred** - allows the target thread to periodically check if it should be cancelled.
- Signal handling
- Synchronous and asynchronous
- Thread pools
- Create a number of threads in a pool where they await work
- Thread-specific data
- Allows each thread to have its own copy of data
- Scheduler activations
- Both **M:M** and **Two-level models** require communication to maintain the appropriate number of kernel threads allocated to the application
- Scheduler activations provide **upcalls** - a communication mechanism from the kernel to the thread library
- This communication allows an application to maintain the correct number kernel threads
- Windows XP Threads
- Implements the 1:1 mapping, kernel-level
- Each thread contains
- A thread id
- context include
1. Register set
2. Separate user and kernel stacks
3. Private data storage area
- 
- Linux Threads
- refers to them as **tasks** rather than *threads*
- Thread creation is done through `clone()` system call
- `clone()` allows a child task to share the address space of the parent task
- `struct task_struct` points to **process data structures** (shared or unique)

## Ch05 - CPU Scheduling
- Basic Concepts
- Maximum CPU utilization obtained with **multiprogramming**
- **CPU-I/O Burst Cycle** - Process execution consists of a cycle of CPU execution and I/O wait
- 
- **CPU burst** distribution
- 
- CPU Scheduler
- CPU scheduling decisions may take place when a process
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
- Scheduling under 1 and 4 is **nonpreemptive**
- All other scheduling is **preemptive**
- Consider access to shared data
- Consider preemption while in kernel mode
- Consider interrupts occurring during crucial OS activities
- Dispatcher
- gives control of the CPU to the process selected by the **short-term scheduler**, this involves:
- switching context
- switching to user mode
- jumping to the proper location in the user program to restart that program
- **Dispatch latency** - time it takes for the dispatcher to stop one process and start another running
- 
- Scheduling Criteria
- Max **CPU utilization** - keep the CPU as busy as possible
- Max **Throughput** - # of processes that complete their execution per time unit
- Min **Turnaround time** - amount of time to execute a particular process
- Min **Waiting time** - amount of time a process has been waiting in the ready queue
- Min **Response time** - amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)
- First-Come, First-Served (**FCFS**) Scheduling
- 
- Shortest-Job-First (**SJF**) Scheduling
- 
- Associate with each process the length of its next CPU burst
- Use these lengths to schedule the process with the shortest time
- **SJF** is optimal - gives minimum average waiting time for a given set of processes
- The difficulty is **knowing the length of the next CPU request**
- Could ask the user
- Determining Length of Next CPU Burst
- $\tau_{n+1} = \alpha t_n + (1 - \alpha) \tau_n$
- $t_n =$ actual length of $n^{th}$ CPU burst
- $\tau_{n+1} =$ predicted value for the next CPU burst
- $\alpha =$ coefficient that $0 \leq \alpha \leq 1$ . commonly, $\alpha$ set as $\dfrac{1}{2}$
- Preemptive version called **Shortest-Remaining-Time-First**
- Shortest-remaining-time-first
- 
- Priority Scheduling
- A **priority number** (int) is associated with each process
- Commonly **smallest int** -> **highest priority**
- The CPU is allocated to the process with the highest priority
- Preemptive
- Nonpreemptive
- **SJF** is a kind of priority scheduling where priority is **the inverse of predicted next CPU burst time**
- Problem : **Starvation** - low priority processes may never execute
- Solution : **Aging** - as time progresses increase the priority of the process
- Round Robin (**RR**)
- Each process gets a small unit of CPU time (time quantum `q`), usually 10-100 ms. After this time has elapsed, the process is preempted and added to the end of the ready queue.
- If there are `n` processes in the ready queue, then each process gets `1/n` of the CPU time in chunks of at most `q` time units at once. No process waits more than `(n-1)q` time units.
- Timer interrupts every quantum to schedule next process
- Performance
- `q` large -> FIFO
- `q` small -> `q` should be large compared to context switch time(< 10 μs), otherwise overhead is too high
- Typically, higher average turnaround than SJF, but better response
- 80% of CPU bursts should be shorter than `q`
- Multilevel Feedback Queue
- A process can move between the various queues; aging can be implemented this way
- Multilevel-feedback-queue scheduler defined by the following parameters:
- number of queues
- scheduling algorithms for each queue
- method used to determine when to upgrade a process
- method used to determine when to demote a process
- method used to determine which queue a process will enter when that process needs service
- 
- Thread Scheduling
- Distinction between **user-level** and **kernel-level** threads
- When threads supported, threads scheduled, not processes
- For **M:1** and **M:M**, thread library schedules user-level threads to run on **LWP**
- Known as **process-contention scope** (**PCS**) since scheduling competition is within the process
- Typically done via priority set by programmer
- Kernel thread scheduled onto available CPU is **system-contention scope** (**SCS**) – competition among all threads in system
- Multiple-Processor Scheduling
- **Homogeneous processors** within a multiprocessor
- **Asymmetric multiprocessing** - only one processor accesses the system data structures, alleviating the need for data sharing
- **Symmetric multiprocessing** (**SMP**) - each processor is self-scheduling, all processes in common ready queue, or each has its own private queue of ready processes
- Currently, most common
- **Processor affinity** – process has affinity for processor on which it is currently running
- soft affinity
- hard affinity
- Variations including **processor sets**
- Multithreaded Multicore System
- 
- Little’s Formula
- $n =$ average queue length
- $W =$ average waiting time in queue
- $\lambda =$ average arrival rate into queue
- Little’s Law - in steady state, processes leaving queue must equal processes arriving, thus $n = \lambda W$
- Valid for any scheduling algorithm and arrival distribution

## 必考

### 名詞解釋
- **System call**
- The OS interface to a running program
- An explicit request to the kernel made via a software interrupt
- General available as assembly language instructions.
- **Bootstrap program**
- Bootstrap program is loaded at power up or reboot.
- Initializes all aspects of system.
- Loads operating system kernel and starts execution.
- **Time sharing**
- Time sharing (multitasking) is logical extension in which CPU switches jobs so frequently that users can interact with each job while it is running, creating interactive computing.
- **Virtual machine**
- A VM is an emulation of a particular computer system. VM operate based on the computer architecture and functions of a real or hypothetical computer, and their implementations may involve specialized hardware, software, or a combination of both.

- **Diagram of Process State**
- 

- **Process Control Block** (**PCB**)
- Process state
- Program counter
- CPU registers
- CPU scheduling information
- Memory-management information
- Accounting information
- I/O status information

### 比較
- **Process** v.s. **Thread**
- 
- **Scheduler**
- **Long-Term Scheduler** - selects which processes should be brought into the ready queue, invoked infrequently, and controls the degree of multiprogramming.
- **Short-Term Scheduler** - selects which processes should be executed next and allocates CPU, invoked frequently.
- **Medium-Term Scheduler** - used especially with time-sharing systems as an intermediate scheduling level. A swapping scheme is implemented to remove partially run programs from memory and reinstate them later to continue where they left off.
- **Interrupt** v.s. **Trap**
- Interrupt
- Hardware generated
- I/O-completed
- Device-ready
- I/O-error
- Trap
- Software generated
- call OS routines
- Catch up arithmetic errors