Operating System
Linux cmd
- cat
- Concatenate 2 files and print them to the console
1 | cat ex1.txt ex2.txt |
- cd
- change directory
1 | cd .. #return to the upper directory |
- pwd
- print work directory
1 | pwd |
- mkdir
- make directory
- -p : create the intermediate directories
- -m : set file mode
1 | mkdir hello |
- rm
- Remove a file
- -p : remove a directory and its files included
1 | rm hello.txt |
- rmdir
- romve directory(if empty)
- -p : remove an empty directory and its upper directories(if empty)
1 | rmdir hello |
- link
- hard link
- -s : symbolic link
1 | link hello.txt linkA |
- cp
- copy file
- -r : copy a directory
- -i : when there is a same file in the destination, you need to press y to confirm
1 | cp hello.txt hello/note |
- mv
- move file
- rename
1 | mv hello.txt ex.txt |
- more
- make a long file into pages
- Space : next page
- b : previous page
1 | more hello.txt |
- head
- Print the head of a file
- -n : print n lines of the head of a file
1 | head hello.txt |
- tail
- opposite to the “head” command
- chmod
- change file mode
1 | chmod 777 hello.txt |
- ls
- list information of files
- -l : long list that includes more information
1 | ls |
1 | drwxr-xr-x 3 lee staff 96 10 14 16:56 hello |
- pipes
1 | ls -l|wc # wc: word count, | : pass the output of command1 to command2 |
- ps
- process status(only the running process from the terminal that the “ps” command ran from)
- -e : list all processes including other users and system processes
- -d : exclude session leaders
- -u : specified user
1 | PID TTY TIME CMD |
- grep
- Global regular expression(match operation)
processes
A process is an instance of a running program, with current state and system resources.
elements
- program code
- set of data
- process context – PCB(process control block, uniquely identify)
- key to implement multiprocessing. when a process is interrupted, key data are saved.
- elements
- identifier(unique)
- state
- priority
- PC(program counter)
- memory pointers
- context data
- I/O status information
- accounting information
creation
when
- new batch job
- interactive log-on
- created by OS to provide a service
- spawned by existing process
how
- assign a unique process identifier
- allocate space
- initialize PCB
- set linkages(ready linked-list queue)
- create or expand other data structures
termination
- normal completion
- time limit exceeded
- memory unavailable
- bounds violation
- arithmetic error
- time overrun
- I/O failure
- Invalid instruction
- Privileged instruction
- Data misuse
- Operator or OS intervention
- Parent termination
- Parent request
5-state model
- new – PCB is created, has not committed to the execution yet
- ready – prepared to execute
- running – being executed
- blocked – cannot be executed for now (such as when there is a I/O process)
- exit – process that is released
important transitions
- running ready
- timeout(most)
- OS has a preempted process
- running blocked
- request a service(resource)
- initiate an action(I/O)
- other communication between processes
queues
- ready queue
- blocked queue – based on different events
suspending
improve processor efficiency
-
load more processes
-
swapping(important) – move blocked processes out of the main memory to the disk.(disk I/O is faster than printer I/O)
2 new states
- blocked/suspend
- ready/suspend
more transitions
- blocked blocked/suspend
- no ready processes. swap out blocked processes to make room for others
- need more main memory
- blocked/suspend ready/suspend
- event occurs
- ready/suspend ready
- no ready processes in main memory
- higher-priority process
- ready ready/suspend
- need more main memory
- lower-priority process
- blocked/suspend blocked
- has free main memory, higher priority
OS control structures
- memory tables
- allocation of main memory, secondary memory
- other information of memory management
- I/O tables
- I/O management
- file tables
- state of files
- location of files
- process tables
- process management
process control structures
process image
- user data
- user program
- stack
- PCB
process control
modes of execution
- user mode
- kernel mode
process switching
- ordinary interrupt
- clock interrupt – program executing for more than allowable time(time slice)
- I/O interrupt
- memory fault
- trap
- error/exception occurs
- fatal exit
- not fatal recovery procedure, notify users
- error/exception occurs
- supervisor call
mode switching
change of process state
- save the context of the processor, eg. PC, SP
- update PCB, eg. update state
- move the PCB to the appropriate queue
- select another process
- update the PCB of the new process
- update memory management data structures
- restore the context of the processor
scheduling
-
Pre-konwledge
- the OS runs a lot of processes. But, at any time, one processor runs only one process
- Good analogy(模拟): dealing with multiple processes
- scheduling can be applied to different areas in the OS
-
aim
-
Response: be reaponsive(反应热烈的), which means programs respond in a short time
-
Throughput(吞吐量): For a given time, the processor should complete as more processes as possible.
-
Efficiency: Efficiently use resources
- for processor: reduce idle time
-
Prevent process starvation
- Starvation: not being executed or being denied resources for a long time
-
share time fairly
-
Fairly: “batch” jobs & interactive – most throughput & least response time
types of processes (a process does not have a fixed type)
- Batch(批量) process(CPU Intensive(密集型)) – longer burst duration, lower frequency
- Interactive process(I/O intensive) – shorter burst duration, higher frequency
-
-
CPU burst: the process is being executed in the CPU
FCFS/FIFO(First-Come-First-Served)
- process in the order they request CPU
- a ready queue(simple linked list queue) is needed
- Favors CPU intensive process
- the process will not be interrupted because of the long time running
- Disadvantage: short processes have to wait for a long time to complete
- calculation terms:
- waiting time
- average waiting time
- average completion time
- Gantt chart is needed
SJF(Shortest Job First)
Shortest processes will be served first.
Non-preemptive & preemptive scheduling(抢占式调度)
- Non-preemptive scheduling
- a process in running state will not be interrupted unless I/O or giving up CPU resources
- FCFS is non-preemptive
- Preemptive scheduling
- Preemption(抢先占有)(–a run time interruption) occurs when
- a new process(with higher priority) arrives
- Timer
- on an interrupt
- Preemption(抢先占有)(–a run time interruption) occurs when
RR(Round Robin)
- features
- preemptive scheduling
- Clock interrupt (an interrupted process will be pushed back of the queue)
- more fair
- time quntum(q) size
- too long high computation favors, poor responsiveness
- too short high overhead(开销) of process switching(0.1 ms ~1 ms)
scheduling with priority
- features
- Scheduler always choose a process with higher priority
- Can be dynamic(update priorities) or static
- priority queuing
- to solve starvation problem
- the priority of processes will change based on their age and history
- to solve starvation problem
- multi-level feedback queues
- to solve starvation
- when a process is blocked or preempted, it will be pushed back of the lower level queue
- Processes in can be served time units
- to solve starvation
File system
DEF: A File System is a layer of OS that transforms block interface of disks (or other block devices) into Files, Directories, etc.
Function:
- Disk management: disk block files
- Naming: make reference by file name possible
- protection: data security
- Reliability/durability: make data durable against attacks or failures
different views:
- User: durable files
- system call interface: collection of bytes
- system inside OS: disk blocks
Components:
file path directory structure file index structure(inode) data blocks (4KB)
File
- features
- Non-volatile storage
- named permanent storage
- logic unit of information
- contains
- data
- Metadata(元数据): data used to describe data
- Owner
- size
- access rights
- R, W, X(read, write, execute)
- Owner, group, other
- requirements
- Variable size
- multiple user with protection
- find files(directory structure, search)
- free disk blocks
directory
- features
- is a file
- can contain files or directories
- details
- a list of file name
- pointers to inodes
path name
- Absolute path name
- unique
- starts from the root directory
- Relative path name
- Based on the current working directory
Opening & closing files
- information of open files – the OS keeps information about open files
- a system-wide open file table
- Contain information of currently opened file
- eg. Inode information
- a pre-process open file table
- a pointer to the syetem open file table
- other information, eg. current file position pointer
- a system-wide open file table
- open a file
- Open system call reads the inode information, stores it in the system-wide open file table
- the reference of system-wide table is stored in the pre-process table, and open return a pointer towards pre-process table
- close a file
- Pre-process table entry is freed
- Data stored in memory cache is written out to the disk
- Locks: management of simultaneous access
Groups & permissions
- Groups:
- owner
- group
- world
- permissions
- read – 4
- Write – 2
- Execute – 1
Eg. 744 user: rwx, group: r–, world: r–
Inode
- features
- keep metadata
- Keep disk blocks information
- details
- Size in bytes
- Device ID
- User ID
- Group ID
- File mode
- timestamps
- link counter
- storage
- Early – outermost cylinder disk poor performance, poor reliability
- now – Spread across the disk closer to the data
File link
- hard link
- Two files share the same inode
- Cannot link a directory
1 | ln original link |
- Soft(symbolic) link
- Contains the full path of another file
- like a reference(pointer)
1 | ln -s original link |
File allocation
-
Contiguous(连续的) file allocation
- entry in file allocation table: start address, length
- easy+good performance
- no full dynamic growth, external fragment(make the rest of the memory little and separated)
-
Linked allocation: FAT( file allocation table)
- a linked list
-
free space management
- method
-
bit table (bitmap)
- 0 – a free block
- 1 – a block in use
- Adv: can be used in any file allocation, small size
-
linked list
-
- method
-
examples
-
FAT32(file allocation table)
- Root record the start point of a file
- FAT like a linked list. It record the next block(4B) a file uses until the end
-
EXT2(indexed file allocation)
- root record a file has which inode(128B)
- inode have id and the clocks it uses
- Free space: bitma
-
EXT2 is faster than FAT32
-
Disk & I/O
Principle of I/O H/W
- memory device speed
- register > cache > main memory > disk
- PCI & IO buses >>
- Deal with connection issues
- connect computer devices together
![](https://pic.imgdb.cn/item/6537731dc458853aef4ead58.png)
- Device controller >>
- Deal with IO devices connection issues
- The OS has drivers to “speak” to it
- Cache >>
- Data buffer
- store neighbouring sectors
- store recently accessed blocks
- The OS keeps a log to prevent exceptions such as power switching off with data still in buffer
- register >>
- status
- command
- data
- tasks
- RW
- Validation/error detection
- communication with CPU
- OS operates I/O devices
- detect whether the status register is BUSY
- OS writes into data register and controller sets the status register BUSY
- controller reads the command and data register and then launches the executions of them
- The OS detects when the command has been executed based on the status register
- controller either resets the status register or set it ERROR
- Memory-Mapped I/O
- target
- solve how CPU communicates with controller registers and data buffers
- def: a system that maps all controller registers into the main memory
- features
- some locations in the main memory are reserved only for I/O device
- alternatives
- assign each register an I/O port number
- target
- DMA(Direct memory access) >>
![](https://pic.imgdb.cn/item/6533b6e9c458853aef3bbebc.png)
![](https://pic.imgdb.cn/item/65377316c458853aef4e9a87.png)
Principle of I/O S/W
Programmed I/O
- actions by the OS
1 | copy_from_user(buffer, p, count); /* p is the kernel buffer */ |
- characterics
- polling
- disadv
- tying up the cpu full time
- Adv:
- low overhead
Interrupt-driven I/O
- Action by the OS(initialize the I/O)
1 | copy_from_user(buffer, p, count); |
- interrupt handling
1 | if (count == 0) { |
- Adv:
- save CPU time
- Deal with unpredictable events
- Disadvantage:
I/O with DMA
I/O with DMA instead of CPU
- action by the OS
1 | copy_from_user(buffer, p, count); |
- Interrupt handling
1 | acknowledge_interrupt( ); |
I/O S/W layers
Device-independent s/w
- functions
- Uniform interfacing for device drivers
- Buffering
- Error reporting
- Allocating and releasing dedicated devices
- Providing a device-independent block size
Interrupt Handlers
- Def: is a special block of code associated with a specific interrupt condition in computer system.>>
Device driver
- Def: device-specific code for controlling the device attached to a computer>>
![](https://pic.imgdb.cn/item/65376c73c458853aef3bb08b.png)
Disks
-
hard disk
- track
- cylinder
- sector
- head
-
addressing method
-
CHS(cylinder head sector)
-
LBA(logical block addressing)
- linear
-
Method: conversion
HPC: heads per cylinder
SPT: sectors per track
Suppose: start with
-
-
Performance: delay
- Seek time: time to position head over the required track/cylinder
- rotational delay: time to make the proper sector to appear under the head
- transfer delay: time to transfer a block of bits(sectore) under r/w head
Disk scheduling
- FIFO
- First in first out, first come first served
- the most fair
- SSTF
- Shortest seek time first
- move from the current position to the closest position
- Adv: reduce seek time
- Disadv: stravation
- SCAN
- elevator algorithm
- take the closest request in the current direction
- Adv: no stravation
- Disadv: not fair
- C-SCAN
- circular SCAN algorithm
- SCAN but when reach the end of the travel, move to the opposite end of the disk
- Fairer than C-SCAN
- anticipatory I/O scheduler
- in linux
- because
- Process requests access more likely to data close by --locality of reference>>
- Too fast scan will make close requests left behind
- how
- introducing a small delay to wait for issuing a request to nearby blocks
- Adv
- get faster overall I/O
SSD
solid state drive
-
NAND flash memory – trap electrons with transistors
-
SLC&MLC
- SLC – single level cell
- 1bit per cell
- Fast, high endurance, expensive
- MLC – multi-level cell
- mutiple bits per cell
- Slow, low endurance, cheap
- SLC – single level cell
-
flash chip structure
-
Chips organised into banks
-
banks are divided into blocks(256KB)
-
blocks are divided into pages(4KB)
-
-
R/W/E(erasing)
-
No seek and rotational delay
-
reading
- Unit: pages
- Performance: 10
- orders of mangnitude faster than HDD
-
writing
- Need erasing a block before writing a page
- set bits to 0
- Performance: 200
-
erasing
- Set bits to 1
- Copies back data that should not be lost
- Performance: 1~2
Note: performance –
-
-
🆚 HDD
- random access I/O
- Less delay
- Sequential access I/O
- Differences are smaller
- more reliable because of not having mechanical parts
- long lifespan
- light
- low power
- silent
- very shock insensitive
- random access I/O