OPERATING SYSTEM
Computer Operating System
导论
cs -> hardware(io cpu…) software(application) data
interface(接口)
hard - hard example： USB
soft - hard 操作系统通过instructions(指令集) example: printf() API接口
Virtual Machine
操作系统向用户提供一个容易理解和使用的计算机（虚拟的），用户对这个计算机操作将被操作系统转换成对计算机硬件的操作
计算机系统组成
CPU RAM DISK IOdevice …..
中断
当所有事情发生时，CPU收到一个中断信号
CPU停下来正在做的事，转而执行中断处理程序，执行完毕会回到之前被中断的地方继续执行
操作系统是一个以中断驱动的系统
存储系统
cpu负责将指令从内存读入，所以程序必须在内存中才能运行
内存以字节为存储单位，每个字节都有一个地址与之对应，通过load/store指令可以访问指定地址的内存数据
load：将内存数据装入寄存器(Register)
store:将寄存器数据写入内存
I/O结构
系统体系结构
单处理器系统
多处理系统
两个或多个CPU
非对称处理
对称处理
集群系统 ->cloud computing 云计算
若干节点，多台计算机通过网络连接在一起,节点之间是松耦合关系
高可用
高性能计算
操作系统结构
单用户单道模式
多道程序设计
让CPU总有一个执行任务
分时系统(多任务系统)
多个用户共享一天计算机
分时系统为每个用户轮流分配等量的CPU时间
发出指令到即时结果的时间为响应时间
提供服务
user interface 面向user
CLI GUI Batch
system calls 面向开发者
usermode:执行用户代码
kernelmode:执行os代码
目的：确保os正确运行
实现方式：0表示kernel模式 1表示user模式
process Concept
definition
process in memory
concurrency
进程是一个程序的一次执行过程
进程是资源分配，保护和调度的基本单位
PROCESS STATE
Running:此时进程的代码在cpu上运行
Ready:进程具备运行条件，等待分配cpu
Waiting:进程在等待某些时间的发生
process scheduling
进程切换
切换时机：
进入等待状态
进程被抢占CPU而进入就绪状态
切换过程：
保存被中断进程的上下文信息
修改被中断进程的控制信息
将被中断的进程加入相应的状态队列
调度一个新的进程并恢复他的上下文信息
中断技术
当发生某个异常事件，中止cpu上现行程序的运行
引出该事件的处理程序执行
执行完毕返回中断点继续执行
外中断
来自cpu外部
异步中断（随机）
内中断
硬件，程序异常，系统调用
中断处理过程
context:save the context of the excuting process
特权指令和非特权指令
privileged instructions: only in kernel mode process switch
non - privileged instructions: only in usermode
进程控制块
进程队列
进程调度
实验（创建子进程）
getpid:返回当前进程的id
wait(NULL)
Wait(NULL)：父进程做完，等待子进程，不加wait（NULL）子进程会变成孤儿进程，孤儿进程会继续运行，但是会把它托管给系统进程（pid=1）
THREAD
motivation
实现并行，把所有执行流封装到一个进程里
执行流（线程）
merit
响应性
资源共享
经济
可伸缩性
DEFINITION
Multithreading Model
用户线程
ULT在user mode下运行
内核线程
KLT在kernel mode下运行，由操作系统支持和管理
M：1模型
优：逻辑上提供了多个执行流
缺：实际上并不是并行，只占用了一个KLT
1：1模型
优：并发加并行
缺：空间和时间内核开销
M:M模型
优：开销减小
缺：实现复杂
多核编程
多线程实验
#include <sys/types.h> |
所有线程共享数据段
线程中局部变量是没用办法在另外一个线程中访问的,局部变量属于线程中自己的栈
线程是并发执行的
等待线程结束的原因（thread_join）：
实验中Linux命令：
编译多线程文件
gcc .c -o -pthread
time 命令获取程序在cpu，用户，实际运行时所需要的时间
void* Caculate(void* arg)
{
unsigned seed = time(NULL);
int circle_point = 0;
int square_point = 0;
int value = *((int*)arg);
for(int i = 0;i<value*value;i++)
{
double rand_x = (double)rand_r(&seed)/RAND_MAX;
double rand_y = (double)rand_r(&seed)/RAND_MAX;
if(rand_x*rand_x+rand_y*rand_y<=1)
{
circle_point++;
}
square_point++;
}
double PI = (4.0*circle_point)/square_point;
printf("PI=%lf in %d times \n",PI,value*value);
}
int main()
{
int args[10];
clock_t delta;
clock_t start = clock();
pthread_t calculate_pi_thread[10];
for(int i = 0;i<10;i++)
{
args[i] = 100+i;
pthread_create(calculate_pi_thread+i,NULL,Caculate,args+i);
}
for(int i = 0;i<10;i++)
{
pthread_join(calculate_pi_thread[i],NULL);
}
delta = clock()-start;
printf("total time is %lf\n",(double)delta/CLOCKS_PER_SEC);
return 0;
}
LECTURE 6 CPU SCHEDULING
CPU调度程序 基于单处理器
长进程：占用cpu时间长
短进程：占用cpu时间短
CPU bonding ： cpu占用密集
IO ….. :
非抢占调度：一个进程占用cpu直到进程中断或结束
抢占调度(Preemptive scheduling):
调度算法性能的衡量：
调度性能指标
ti = tf - ts;（进程提交给系统的时刻是ts，完成时刻是tf）
调度算法
FCFS(队列)
时间片轮转（TIME SHARING）
算法分析：
时间片选取：
取值太小： 进程切换开销太大
取值太大：响应速度下降
选区范围：10ms-100ms
对长作业切换开销太大
最短作业优先（SJF）
下一次调度选择所需要的CPU时间最短的那个进程
长进程可能长时间无法获取CPU
很难实现：该算法需要事先知道进程所需CPU时间
优先级调度
调度策略：下次调度总是选择优先级最高的进程
优先级定义
在Linux中，线程调度优先级由一个整数值表示，范围从0到最高优先级（通常是99）。较高的优先级值表示线程具有更高的优先级。
静态优先级：优先级保持不变，但会出现不公平现象
动态优先级：根据proess占用CPU时间：当进程占用CPU时间越长，慢慢降低优先级
根据进程等待：进程在就绪队列中等待时间越长，就慢慢提升优先级
调度
Linux 线程调度
pthread_attr_t attr //初始化线程属性为默认 |
1.Scope:
PTHREAD_SCOPE_SYSTEM 系统 scs Linux 一对一模型
PTHREAD_SCOPE_PROCESS 进程 pcs
2.调度策略，调度优先级
Scheduling policy :
NORMAL : SHED_OTHER ,SCHEO_IDLE , SCHED_BATCH,
REAL TIME: SCHED_FIFO , SCHED_RR
实时的线程总是比普通线程优先级更高
SCHED_OTHER: time -sharing NICE:友好值[-20,19] PR = 20+NICE[0,39] PR值越高，优先级越低
REAL TIME :PR = -1 - proirity_value
PR: rt —> PR = -100
‘chrt - p pid’->观察进程调度策略以及他的priority_value
‘sudo chrt -f -p || pid’ => 将皮带进程切换为rt并且设置其 priority_value和policy
调度策略的过程
LECTURE 7 进程同步
并发
在内存中存在若干进程或线程，由操作系统的调度程序采用适当策略将他们调度到CPU上运行，同时维护他们的状态队列
并发是交替执行
宏观上是同时运行
微观上是走走停停的
并发进程关系：
独立
交互：竞争和协作
异步
1.random
2.
3.
可能是图中情况，也可能是先执行完t1再执行t2
同步
维护数据的一致性 数据（协作或交互的进程）
Mutex lock （互斥锁）解决竞争问题
semaphore（信号量）解决协作问题
互斥锁
进程进出临界区协议
进入临界区前在entry section要请求许可
离开临界区后在exit section要归还许可
管理准则：
Mutual exclusion:互斥
Progress:前进
Bounded waiting：有限等待
1.section中有位置就必须进去一个
2.多个进程只能进去一个，其他进程等待
3.等待时间不能无限
4.在临界区里进程不能无限在临界区
测试：y->获得锁 n-> waiting
上锁和测试不能被打断
原子操作
test_and_set()
compare _and_swap()
busy waiting（自旋锁）
占用CPU执行空循环进行等待
浪费CPU时间
进程在等待时没有上下文切换//锁初始化
pthread_mutex_t lock = PTHREAD_MUTEX_INTIALIZER
//获取锁
pthread_mutex _lock(&lock)
//释放锁
pthread_mutex_unlock(&lock)
SIGNAL （信号量）
PV操作
P: wait()
V: signal()
信号量的实现
P(s) |
s<=0 P(s) :busy waiting V(s) :s++
s=1 P(s) :s=0 V(s): s = 2
信号量的使用
BINARY SEMAPHORE
二值信号量只能是0或1，通常将其初始化为1semaphore mutex = 1;
process p
{
P(mutex);
critical section
V(mutex)
}
COUNTING SEMAPHORE
一般信号量的取值可以是任意数值semaphore road = 2;
process Car
{
p(road);
pass the fork
in the road
V(road);
}
s=1->竞争
s>1->可用资源数量
Lab
sem_wait()——>P()
sem_post()———->V()
同步问题
找到并发进程交互点
P操作来调节进程执行速度
初始值为0的信号量可以让进程直接进行等待状态
Semaphore empty = 1; |
有界缓冲区
P(mutex);
B[i] = product
in = (in+1)%k;
V(mutex);P(mutex);
product = B[out];
out = (out+1)%k
对进程共享变量实施临界区管理（上锁）
1.不要随意扩大临界区
2.empty和full的p，v操作不在同一进程（同步信号量）
3.mutex和p，v操作在同一进程（互斥信号量)
同步问题案例
读者写者问题semaphore rw = 1,mutex=1;
int reader = 0;
Reader
{
p(mutex)
if(reader==0)
{
reader++;
p(rw);
}
v(mutex)
read;
p(mutex)
reader--;
if(reader==0)
{
v(rw);
}
v(mutex)
}
Writer
{
p(rw);
writ e;
v(rw);
}
barber问题
#define Max 3
semphore b = 1,c = 0,mutex = 1;
int waiting = 0;
Barber
{
p(c);
p(mutex);
waiting--;
v(mutex);
cut hair
v(b);
}
Customer
{
p(mutex);
if(waiting<Max)
{
waiting++;
v(mutex);
p(b);
v(c);
}
else
{
leaving
}
cut hair
}
DEAD LOCK
在多并发进程下，一些进程会去竞争有限的资源，当资源不可用，进程会进入等待状态，在有些时候，等待状态无法被改变（他等待的资源被另外一个进程占有并等待）。
饥饿：进程长时间等待
死锁：循环等待资源
产生死锁必要条件:
1.互斥使用
2.不可剥夺
3.占有和等待
4.循环等待
解决方案
1.死锁的防止(Prevention)
破坏四个必要条件
只能破坏循环等待
2.死锁避免（Avoidance）
在并发进程中做出妥善安排避免死锁发生
SAFE STATE
按照顺序分配资源给每个进程，避免死锁
Banker’s algorithm
已知系统中所有资源的种类和数量
已知进程所需要的各类资源最大需求量
该算法可以计算出当前系统状态是否安全
3.死锁的检测和恢复
进程内存空间
逻辑地址和物理地址
16进制下，
9+1=A, A+1=B, B+1=C,C+1＝D, D+1＝E, E+1=F, F+1=10,10+1=11…sample.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <sum>:
0: f3 0f 1e fa endbr64
4: 55 push %rbp
5: 48 89 e5 mov %rsp,%rbp
8: 89 7d fc mov %edi,-0x4(%rbp)
b: 89 75 f8 mov %esi,-0x8(%rbp)
e: 8b 55 fc mov -0x4(%rbp),%edx
11: 8b 45 f8 mov -0x8(%rbp),%eax
14: 01 d0 add %edx,%eax
16: 5d pop %rbp
17: c3 ret
//逻辑地址：0，4，5.....
0000000000000018 <main>:
18: f3 0f 1e fa endbr64
1c: 55 push %rbp
1d: 48 89 e5 mov %rsp,%rbp
20: be 05 00 00 00 mov $0x5,%esi//参数传入调用函数
25: bf 04 00 00 00 mov $0x4,%edi//参数传入调用函数
2a: e8 00 00 00 00 call 2f <main+0x17>//调用函数
2f: 89 c6 mov %eax,%esi
31: 48 8d 05 00 00 00 00 lea 0x0(%rip),%rax # 38 <main+0x20>
38: 48 89 c7 mov %rax,%rdi
3b: b8 00 00 00 00 mov $0x0,%eax
40: e8 00 00 00 00 call 45 <main+0x2d>
45: b8 00 00 00 00 mov $0x0,%eax
4a: 5d pop %rbp
4b: c3 ret
逻辑地址：给每一条指令提供编号
物理地址:内存单元看到的地址
物理地址=基址+逻辑地址
进程的内存映像
#include<stdlib.h>
#include<unistd.h>
#include<stdio.h>
int global_ar = 5;
int main()
{
static int static_var = 6;
int local_var=7;
int *p= (int*)malloc(100);
//use %lx to show a 64bits address
printf("the global_var address is %lx\n",&global_var);
printf("the static_var address is %lx\n",&static_var);
printf("the local_var address is %lx\n",&local_var);
printf("the address which the p points to is%lx\n",&p);
free(p);
sleep(1000);
return 0;
}$gcc sample2.c -o sample2
$./sample2
#输出结果
the global_var address is 561b0368e010
the static_var address is 561b0368e014
the local_var address is 7ffe6aa505ec
the address which the p points to is7ffe6aa505f0ps -el
把sample2的pid记录下来
356275 pts/3 00:00:00 sample2
$cat /proc/356275/maps |
内存管理
目标
高速缓存
保护os: 防止用户进程去读写os的内存空间
保护用户进程：用户进程之间不能随意存取对方内存空间
操作正确：地址转换。分配回收
逻辑地址和物理地址
地址转换时机
编译时：提前知道这个程序要加载的物理内存的起始地址
加载时：加载的时候知道基址R
这两个转换时机都是不可移动的
运行时：MMU（内存管理单元）将逻辑地址转换为物理地址
CONTIGUOUS MEMORY ALLOCATION
FIXED_SIZED PARTITION
将内存划分成不同一些固定容量的分区，每个分区都可能包含一个进程
VARIABLE_PARTITION 可变分区
动态存储分配方案:
首次适应
发呢配首个足够大的hole，效率最高
最佳适应
分配最小的足够大的hole，浪费最小
最坏适应，发配的孔，产生的剩余孔更可能再利用
地址转换与保护:
碎片问题:
compaction
static relocation
cost
分段和分页
动机
针对碎片的解决方案
内部：固定分区
外部：可变分区
分段
分段硬件
16为位段式地址转换实例:
pc寄存器存放的值是cpu下一条要执行的指令的地址
假设逻辑地址段号占2bits ， 段内位移占14bits pc寄存器的值为0x240
逻辑地址:0000 0010 0100 0000
段号是0x0
段内位移是0x240
分页
frame：页框
page：页面
页表：page table
页号和页内位移
分页硬件
分页计算物理地址
页表
页面大小
逻辑地址长度为mbits，页面大小 2的n次方 bytes
页内位移占 n bits
页号占m-n bits
快表
TLB（Translation Look-aside Buffer）
页的保护和共享
