Operating System

Linux cmd

cat
- Concatenate 2 files and print them to the console

1	$ cat ex1.txt ex2.txt

cd
- change directory

$ cd .. #return to the upper directory
$ cd ~ #home
$ cd / #root
$ cd /Users/lee/desktop/year3/note/try # absolute path

pwd
- print work directory

$ pwd

mkdir
- make directory
- -p : create the intermediate directories
- -m : set file mode

1
2
3

$ mkdir hello
$ mkdir -p note/items/hello
$ mkdir -m 700 hello

rm
- Remove a file
- -p : remove a directory and its files included

1 2	$ rm hello.txt $ rm hello

rmdir
- romve directory(if empty)
- -p : remove an empty directory and its upper directories(if empty)

1 2	$ rmdir hello $ rmdir -p hello/note

link
- hard link
- -s : symbolic link

1 2	$ link hello.txt linkA $ link -s hello.txt linkB

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
2
3

$ cp hello.txt hello/note
$ cp -r hello/ mydir/hello
$ cp -i hello.txt hello

mv
- move file
- rename

1
2
3

$ mv hello.txt ex.txt
$ mv hello.txt hello
$ mv hello/ work/note

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 2	$ head hello.txt $ head -n 20 heallo.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 2	$ ls $ ls -l

drwxr-xr-x  3 lee  staff  96 10 14 16:56 hello

//total: the blocks used
//directory with 755 mode
//3 hard link(".", "..", "a subdirectory")
//lee is the user name
//staff is the group name
//96 is the size, which is 96 bytes
//10 14 16:56 is the last modification time
//hello is the name of this file

pipes

1 2	$ ls -l\|wc # wc: word count, \| : pass the output of command1 to command2 $ ls -l\|sort -k5n # sort long list of directory by size

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

  PID TTY           TIME CMD
26467 ttys000    0:00.02 -zsh

//ps output(unix from mac)
//pid is the id of the process
//TTY(teletypes) is the terminal that user is logged into
//time is the amount of time that the process has been running
//cmd is the command that executed to launch the process

  PID TTY          TIME CMD
26223 pts/0    00:00:00 bash
28160 pts/0    00:00:00 ps

//ps output(linux from remote server)


  PID TTY           TIME CMD
    1 ??        22:22.88 /sbin/launchd
26590 ttys000    0:00.00 ps -e

//ps -e output(unix from mac)
//? means that the process does not belong to any terminal and is a system process

  PID TTY          TIME CMD
    1 ?        00:00:02 systemd
29168 pts/0    00:00:00 ps

//ps -e (linux from remote)


  UID   PID  PPID   C STIME   TTY           TIME CMD
  501 26467 26466   0  9:15上午 ttys000    0:00.04 -zsh
  
//ps -f output(unix from mac)
//uid is the id of users
//ppid id is the id of the parent process
//C is the CPU utilization
//stime is the start time

  UID        PID  PPID  C STIME TTY          TIME CMD
  ubuntu   26223 26222  0 Oct16 pts/0    00:00:00 -bash
  ubuntu   32648 26223  0 00:13 pts/0    00:00:00 ps -f
  
//ps -f (linux from remote)


USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
root         1  0.0  0.4 159828  9096 ?        Ss   Oct16   0:02 /sbin/init noibrs

//ps aux (linux)
//%CPU: the percentage of cpu used
//%MEM: memory usage
//VSZ: virtual memory size in KB
//RSS: resident set size, RAM currently used
//STAT: R(running), S(sleeping), T(stopped), Z(zombie), D(uninterrupted sleeping, IO)


F S   UID   PID  PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
0 S   500  5282  5281  0  80   0 -  5999 wait   pts/1    00:00:00 bash
0 R   500  7107  5282  0  80   0 -  7496 -      pts/1    00:00:00 ps

//ps -l (linux)
//F: process flag, status of a process, octal number
//S: state
//PRI: priority, for scheduling tasks
//NI: niceness, adjustment to priority(-20~+19, lower niceness means higher priority)
//ADDR: address of a process in memory that starts from
//SZ: size in memory, in pages(4096 bytes)
//WCHAN: channel in which a process is waiting


  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND
    1 root      20   0  159828   9100   6696 S   0.0  0.4   0:02.86 systemd

//SHR: shared memory size
//TIME+: cumulative CPU time


sshd───bash───pstree

systemd───(sd-pam)

//pstree -u(linux)
//number is the number of threads

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 $\Rightarrow$ $\Rightarrow$ ready
- timeout(most)
- OS has a preempted process
running $\Rightarrow$ $\Rightarrow$ 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)

$\bigstar$ 2 new states

blocked/suspend
ready/suspend

$\bigstar$ more transitions

blocked $\Rightarrow$ $\Rightarrow$ blocked/suspend
- no ready processes. swap out blocked processes to make room for others
- need more main memory
blocked/suspend $\Rightarrow$ $\Rightarrow$ ready/suspend
- event occurs
ready/suspend $\Rightarrow$ $\Rightarrow$ ready
- no ready processes in main memory
- higher-priority process
ready $\Rightarrow$ $\Rightarrow$ ready/suspend
- need more main memory
- lower-priority process
blocked/suspend $\Rightarrow$ $\Rightarrow$ 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 $\Rightarrow$ exit
  - not fatal $\Rightarrow$ recovery procedure, notify users
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
    
    $\Rightarrow$ 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

$\bigstar$ 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

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 $\Rightarrow$ high computation favors, poor responsiveness
- too short $\Rightarrow$ 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
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 $RQ_i$ can be served $2^i$ time units

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 $\Rightarrow$ 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 $\Rightarrow$ directory structure $\Rightarrow$ file index structure(inode) $\Rightarrow$ 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

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
open a file
1. Open system call reads the inode information, stores it in the system-wide open file table
2. 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 $\Rightarrow$ 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 $\Rightarrow$ 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
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

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
1. detect whether the status register is BUSY
2. OS writes into data register and controller sets the status register BUSY
3. controller reads the command and data register and then launches the executions of them
4. The OS detects when the command has been executed based on the status register
5. 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
DMA(Direct memory access) >>

Principle of I/O S/W

Programmed I/O

actions by the OS

copy_from_user(buffer, p, count); 				/* p is the kernel buffer */
for (i = 0; i < count; i++) { 					/* loop on every character */
	while (*printer_status_register != READY); 	        /* loop until ready --polling*/
	*printer_data_register = p[i]; 				/* output one character */
}
return_to_user( );

characterics
- polling
disadv
- tying up the cpu full time
Adv:
- low overhead

Interrupt-driven I/O

Action by the OS(initialize the I/O)

copy_from_user(buffer, p, count);
enable_interrupts( ); 				/*allow or permit interrupts to be received*/
while (*printer_status_register != READY);	/*polling to send the first character*/
*printer_data_register = p[0];
scheduler( );					/*run other processes until receiving an interrupt*/

interrupt handling

if (count == 0) {
	unblock_user( );		/*after all characters are printed, unblock other processes*/
} else {
	*printer_data_register = p[i];
	count = count − 1;
	i = i + 1;
}
acknowledge_interrupt( );		/*successfully handle interrupts*/
return_from_interrupt( );		/*resume the previous processes*/

Adv:
- save CPU time
- Deal with unpredictable events
Disadvantage:
- High overhead >>
  - Context switching
  - ISR >>

I/O with DMA

I/O with DMA instead of CPU

action by the OS

1
2
3

copy_from_user(buffer, p, count);
set_up_DMA_controller( ); 
scheduler( );

Interrupt handling

1
2
3

acknowledge_interrupt( );
unblock_user( );
return_from_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>>

Disks

hard disk
- track
- cylinder
- sector
- head
addressing method
- CHS(cylinder head sector)
- LBA(logical block addressing)
  - linear
- Method: conversion
  
  $LBA=C*HPC*SPT+H*SPT+(S-1)\nonumber\\ inv.\\ \begin{align} S&=LBA\ \ mod\ \ SPT + 1\nonumber\\ H&=LBA\ \ div\ \ SPT\ \ mod\ \ HPC\nonumber\\ C&=LBA\ \ div\ \ SPT\ \ div\ \ HPC\nonumber \end{align}$
  
  HPC: heads per cylinder
  
  SPT: sectors per track
  
  Suppose: start with $C=0,\ H=0\ ,S=1$
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
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 $\mu s$
  - orders of mangnitude faster than HDD
- writing
  - Need erasing a block before writing a page
  - set bits to 0
  - Performance: 200 $\mu s$
- erasing
  - Set bits to 1
  - Copies back data that should not be lost
  - Performance: 1~2 $ms$
  Note: performance – $W=10\times R,\ E=10\times W$
🆚 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