7.5 死锁避免
Banker’s Algorithm 银行家算法
Data structures:
- Let n = number of processes, and m = number of resources types.
Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj available.Rj类资源有个可用
Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj .行表示某一个进程对所有资源的请求，M[i,j]表示Pi进程对Rj资源最大的需求是k个
Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj. Rj资源对Pi已分配了k个
Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task. Need [i,j] = Max[i,j] – Allocation [i,j] Pi还需k个Rj资源
Safety Algorithm 安全算法
1. Let Work and Finish be vectors of length m and n, respectively.
Initialize: Work = Available Finish [i] = false for i = 1,2,3, …, n.
2. Find an index i such that both:
(a). Finish[i] = false
(b). Need[i] <= Work
If no such i exists, go to step 4.
3. Work = Work + Allocation
Finish[i] = true
go to step 2.
4. If Finish[i] == true for all i, then the system is in a safe state.所有进程完成
Resource-Request Algorithm
Requesti = request vector for process Pi . If Requesti [j] = k then process Pi wants k instances of resource type Rj.
1. If Requesti <= Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.
2. If Requesti <= Available, go to step 3. Otherwise Pi must wait, since resources are not available.可用满足，继续
3. Pretend to allocate requested resources to Pi by modifying the state as follows:
Available = Available - Requesti ;
Allocationi = Allocationi + Requesti ;
Needi = Needi – Requesti ;
• Call Safety Algorithm
• If safe -> the resources are allocated to Pi .
• If unsafe -> Pi must wait, and the old resource-allocation state is restored
7.7 死锁恢复 recovery
检测到死锁后采取措施：
- 通知系统管理员
- 系统自己恢复
打破死锁两种方法：
- 进程终止
- 抢占资源
Abort all deadlocked processes.
Abort one process at a time until the deadlock cycle is eliminated.
Many factors may determine which process is chosen, include:
- Priority of the process.优先级
- How long process has computed, and how much longer to completion.已运行时间
- Resources the process has used.已占用资源
- Resources process needs to complete.需要完成资源
- How many processes will need to be terminated.
- Whether the process is interactive or batch.
Chapter 8 Main Memory
8.1 Background
必须将程序（从磁盘）带入内存并放置在进程中才能运行
– 主存储器和寄存器仅是存储CPU可以直接访问的
– 在一个CPU时钟（或更少）中进行寄存器访问
– 主内存可能需要很多周期
– 缓存位于主存储器和CPU寄存器之间
– 需要保护内存以确保正确操作
The concept of a logical address space that is bound to a separate physical address
space is central to proper memory management
– Logical address（逻辑地址，相对地址，虚地址）– generated by the CPU; also referred
to as virtual address（从0开始的）
- 用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。
- 其首地址为0，其余指令中的地址都相对于首地址来编址。
- 不能用逻辑地址在内存中读取信息。
– Physical address （物理地址，绝对地址，实地址） – address seen by the memory unit
– 内存中存储单元的地址。物理地址可直接寻址
MMU（Memory-Management Unit）
In MMU scheme, the value in the relocation register（重定位寄存器） is added to every address generated by a user process at the time it is sent to memory
Dynamic Linking（动态链接）
Using dynamic linking, external libraries can be preloaded into (shared) memory
When a process calls a library function, the corresponding physical address is determined
Small piece of code, stub, used to locate the appropriate memory-resident library routine
Stub replaces itself with the address of the routine, and executes the routine
Operating system needed to check if routine is in processes’ memory addres
Dynamic linking is particularly useful for libraries
System also known as shared libraries
- Dynamically Linked Library 动态链接库
8.2 Swapping （交换技术）
- 交换技术
可以将进程暂时从内存中交换到后备存储，然后进行处理返回内存以继续执行。
后备存储–快速磁盘，其大小足以容纳所有存储映像的副本用户； 必须提供对这些内存映像的直接访问。
Linux，UNIX—交换区
Windows-交换文件（pagefile.sys）
推出，推出（调出，调进）–用于基于优先级的调度的交换变体算法; 交换较低优先级的进程，以便可以加载较高优先级的进程并执行。
交换时间的主要部分是传输时间； 总传输时间与交换的内存量在许多系统（例如UNIX，Linux和Windows）上都可以找到修改后的交换版本。
系统维护着一个准备就绪的准备运行队列，这些队列上有内存映像磁碟。
on Moblie Systems:
- 移动系统不支持交换，Flash memory based:
- 小空间
- 闪存写次数限制
- 在移动平台上闪存和CPU之间的吞吐量很低
- iOS要求应用程序自愿放弃分配的内存
- 只读数据从系统中直接删除，已修改数据不会被删除
- OS可以终止任何未能释放足够空间的应用
- Android如果空闲内存不足，会终止应用程序，但首先会将应用程序状态写入闪存，以便快速重启
8.3 连续分配
主内存通常分为两个分区：
- Resident operating system（驻留操作系统），通常保存在带有中断向量的低内存中
- User processes 将用户进程保存在高内存中
重定位寄存器，用于保护用户进程彼此之间以及更改操作系统代码和数据时相互保护：
- 基址寄存器包含最小物理地址的值
- 限制寄存器包含逻辑地址范围–每个逻辑地址必须小于限制寄存器
- MMU动态映射逻辑地址
0 条评论