# Introduction of Computer Science<br>Ch7 & Ch8
NTNU 計算機概論

##### [Back to Note Overview](https://reurl.cc/XXeYaE)
##### [Back to Introduction of Computer Science](https://hackmd.io/@NTNUCSIE112/SyU5Uuyhr)

###### tags: `NTNU` `CSIE` `必修` `Introduction of Computer Sciencce`

# Ch7 Operating System
## 7-1 Introduction
+ An operation system:
- an **interface** between the hardware of a computer and the user(programs or humans)
- a program(or a set of programs) that facilitates the execute of other programs
- acts as a **general manager** supervising the **activity** of each component in the computer system
+ Two major design goals of an operation system are:
- Efficient use of hardware.
- Ease of use of resources.

作業系統如何被載入的呢?大多採用兩階段處理。

1. bootstrap program runs
- The ROM BIOS bootstrap process (啟動程式)
2. Operating system is loaded
3. Operation system runs

## 7-2 Evolution
1. Manual Manipulation 手動操作階段
- 1940-1950
- e.g. ENIAC
- To execute the program, the operator is responsible for the computer process.
- User must be familiar with hardware operation, it is **troublesome and error-prone**.
2. Evolution──Batch Systems 批次系統
- Beginning 1950
- Each program to be executed was called a **job**
- Collect jobs into **batched**
- Conversion between Each job is **handled automatically** by the program
- e.g.電腦閱卷的處理模式
- **_OS only ensured that all the resources were transferred from one job to the next._**
3. Evolution──Time-sharing Systems 分時系統
- （I）Multiprogramming 多重程式處理
+ to hold several jobs in memory.
+ only assign a resource to a job that needs it on the *condition that resource is available*.
- （II）Time sharing 分時
+ each job can be allocated a portion of time to use the resource.
+ resource can be **shared** between different jobs
+ because a computer is much faster than a human, time sharing is hidden from the user
+ each user regards the whole system as it serves them exclusively
- （III） Scheduling 排程
+ OS allocates the resources to different programs and decides which program should use which resource and when to run.
- （IV） Process 程序
+ A job is a program to be **run**.
+ A process is a program that in memory and waiting for resources.
4. Evolution──Personal Systems 個人系統
- The first microprocessor：Intel 4004 calculator chip, available 1971.
- 1981：IBM PC(Personal computer)
- Single-user operating system
- e.g. MS-DOS(Disk Operating System)
- 單人單工
5. Evolution──Parallel System　平行系統
- **Multiple CPUs** on the same machine.
- Each CPU can serve one program or a part of a program.
- Many tasks can be accomplished in parallel.
6. Evolution──Distributed Systems 分散式系統
- A job can be shared between **computers**.
+ Networking or inter-networking.
- Resource can be distributed.
+ Data in thousand miles away
- New issue: controlling security.
7. Evolution──Real-time Systems 即時系統
- do a task **within a specific time constraint**
- used with **real-time applications**, which monitor, respond to or control external processes or environments
## 7-3 Components of an Operating System

- An operating system has at least four duties：**memory manager, process manager, device manager, and file manager**.
### User Interface
- **Each OS has a user interface.**
- A program that **accepts requests and interprets** them.
- 2 kinds of user interfaces：
- Command-driven 命令驅動
- UNIX→Shell
- Menu-driven 選單驅動
- Window→Menu-driven and GUI
### Memory Manager

digraph hierarhcy 
{
	nodesep=1
	node[color = pink, fontname=Courier,shape=box]
	edge [color=pink,style=line]
	
	MemoryManager->{Monoprogramming Multiprogramming}
	
	Multiprogramming->{NonSwapping Swapping}
	NonSwapping->{Partitioning Paging}
	Swapping->{"Demand Paging" "Demand Segmentation"}
	{"Demand Paging" "Demand Segmentation"}->"Demand Paging and Segmentation"
}

- Monoprogramming 單一程式
1. loads the whole program into memory
2. run it
3. replaces it with the next program.
- Several problems:
+ If the size of memory is less than the size of the program → cannot be run.
+ When one program is being run, no other program can be executed.
+ When performs I/O **－＞** CPU is idle.
- Multiprogramming
- Began at 1960.
- We don't want CPU idle.
- More than one program is in memory at the same time.
- Execute concurrently,illusion the user that the computer is only executing his program。
- CPU switches between the programs.
- Several improvements.
- Categories of Multiprogramming
- Multiprogramming
- Non-swapping：
- the program remains in memory for the duration of execution.
- Partitioning
+ Memory is divided into variable length sections.
+ Each section or partition holds one program.The CPU switches between programs.
+ CPU executes instructions until either the program encounters an I/O operation or the time allocated for the program(about 15ms in x64) has expired.
+ CPU saves the address of the memory location where the last instruction was executed and moves to the next program.
+ **Problems:**
+ the size of the partitions has to be determined beforehand by the memory manager.
+ There may be some holes after programs are replaced by new ones.

- Paging
- Paging improves the efficiency of the partitioning.
- **Memory** is divided into equally sized sections called **frames**.
- The **program** is divided into equally sized sections called **pages**.
- **Problems:** The whole programs still needs to be in memory before being executed.

**Page的大小**
| 硬體機型 | Page的大小 |
|------------------| -----------|
| IBM AS/400 | 512 bytes |
| DEC Alpha | 8K bytes |
| UltraSPARC | 8K~4M bytes |
| PowerPC | 4K bytes |
| Intel Pentium | 4K~4M bytes |
| Intel Core i7-3700 | 4M bytes |
- Swapping: the program can be swapped between memory and disk one or more times.
- Swapping
- Demand Paging
- Demand Segmentation
- A program is usually made of a main program and sub program
- Demand Paging and Segmentation
- A segment may be too large to fit any available free space in memory.
- Memory is divided into frames.
- Segment is divided into pages.
- The page of module can be loaded into memory one and one executed.

#### Virtual Memory(虛擬記憶體)
- Only some parts of the programs is in main memory and some parts its in the disk.
- Used in almost all OSs today
- Windows -> C:\pagefile.sys

虛擬記憶體的需求
- 需有MMU(Memory Management Unit)硬體來支援分頁和分段機制。
- 需有軟體來管理page或flame，在Disk和Memory之間移入和移出的動作

### Process manager
- Program 程式
+ A program is a **non-active** set of instructions written by a programmer and stored on disk.
- Job 工作
+ A program becomes a job from the moment it is selected for **execution** until it has finished running and becomes a program again.

- Process 程序
+ A process is a program in execution. It has started but has not finished.

State diagram with the boundaries between a program, a job, and a process.
+ Job Scheduler
+ Job scheduler moves a job from the hold state to the running state to the terminated state.
- 一個Process中可以同時包括多個執行緒(multithreading)，CPU會分配時間片段來處以這些Thread，這使得一個Process可以像是同時間處理多個任務
- Process Scheduler
- Process scheduler moves a process form one state to another.
- Queues for Process Management
- The process manager users queues to handle multiple process and jobs that competing with each other for computer resources.
- The Queuing policies
- Process Synchronization
- Deadlock
- Four Necessary Condition for Deadlock
- Mutual Exclusion
- Resource Holding
- No Preemption
- Circular
- Solutions of deadlock
- Not to allow a process to start running until the resources are free
- To limit the time a process can hold a resource
- Starvation
- Starvation can happen when the operating system puts too many resource restrictions on a process.
1. Process A needs both File 1 and File 2
2. Process A still needs both File 1 and File 2
3. Process A still needs File 1 and File 2 (starvaing)
### Device Manager
- The device manger is responsible for the efficient use on I/O devices.
## 7-4 A Survey of Operating System
- For personal computers
- 單人單工
- MS-DOS
- 單人多工
- Wondows 95/98/Me
- OS/2
- 多人多工
- Windows XP
- For servers
- Windows NT/2000
- Unix
- Bell Laboratories(AT&T貝爾實驗室)
- FreeBSD
- Linux
- For PDA and Smart phone
- Palm OS
- Window CE
- iOS
- Other famous OSs
- DEC VMS
- Mac OS

# Ch8 Algorithm
## 8-1 Concept
- step-by-step method of solving a problem
- accept an input list of data and creates an output list of data

digraph hierarhcy {
	nodesep=1.0
	node[color = pink, fontname=Courier,shape=box]
	edge [color=pink,style=line]
	rankdir=LR
	"Input list" -> Algorithm -> "Output list"
	
}

## 8-2 Three Constructs
- A program is a combination of sequence constructs, decision constructs, and repetition constructs(loop construct).
- Commonly used Constructs
- Sequence
- Decision
- Repetition
## 8-3 Algorithm Rresentation

$O()$：Time complexity [(learn more)](https://jason-chen-1992.weebly.com/home/time-space-complexity)

### Pseudocode
## 8-4 More Formal Definition
- An ordered set of unambiguous......
### Executable steps of Algorithm
- Every step-by-step be executable
- A wrong example:find the max positive integer.
1. Make a list of all positive integer
2.
## 8-5 Basic Algorithm
### sort
- $O(n^2)$
- Insertion sort
- sort with unsort in order and move sorted list every strp
- Selection sort
- Find minimum in unsort put in The
- Bubble sort
- if front is bigger than now than swap until the minimum move to the first in unsort list
- $O(n \log n)$
- Quick sort
- Merge sort
### Search
- Unsort list
- Sequential search
- $O(n)$
- Sorted list
- Binary search
- $O(\log n)$
{%hackmd @sophie8909/pink_theme %}
## 8-6 Subalgorithm
Other name: subpogram, subroutine, procedure, function, method, module
## 8-7 Recursion
Iterative solution:
This solution usually involves a loop
### Recursive solution
The recursive solution does not need a loop, as the recursion concept itself involves repetition. An recursive algorithm calls the algorithm itself.

### 問題難易度
+ 容易的問題
+ 困難的問題(NP-complete, NP-hard)
+ 不可解的問題(undecidable)

{%hackmd @sophie8909/csabb %}