Skip to content

Latest commit

 

History

History
162 lines (125 loc) · 6.78 KB

08-1-spoc-discussion.md

File metadata and controls

162 lines (125 loc) · 6.78 KB

死锁与IPC(lec 20) spoc 思考题

  • 有"spoc"标记的题是要求拿清华学分的同学要在实体课上完成，并按时提交到学生对应的ucore_code和os_exercises的git repo上。

个人思考题

死锁概念

  • 尝试举一个生活中死锁实例。
  • 可重用资源和消耗资源有什么区别？

可重用和不可撤销；

  • 资源分配图中的顶点和有向边代表什么含义？
  • 出现死锁的4个必要条件是什么？

死锁处理方法

  • 死锁处理的方法有哪几种？它们的区别在什么地方？
  • 安全序列的定义是什么？

进程的最大资源需要量小于可用资源与前面进程占用资源的总合；

  • 安全、不安全和死锁有什么区别和联系？

银行家算法

  • 什么是银行家算法？
  • 安全状态判断和安全序列是一回事吗？

死锁检测

  • 死锁检测与安全状态判断有什么区别和联系？

死锁检测、安全状态判断和安全序列判断的本质就是资源分配图中的循环等待判断。

进程通信概念

  • 直接通信和间接通信的区别是什么？ 本质上来说，间接通信可以理解为两个直接通信，间接通信中假定有一个永远有效的直接通信方。
  • 同步和异步通信有什么区别？

信号和管道

  • 尝试视频中的信号通信例子。
  • 写一个检查本机网络服务工作状态并自动重启相关服务的程序。
  • 什么是管道？

消息队列和共享内存

  • 写测试用例，测试管道、消息队列和共享内存三种通信机制进行不同通信间隔和通信量情况下的通信带宽、通信延时、带宽抖动和延时抖动方面的性能差异。

小组思考题

  • （spoc） 每人用python实现银行家算法。大致输出可参考参考输出。除了YOUR CODE部分需要填写代码外，在算法的具体实现上，效率也不高，可进一步改进执行效率。

代码见本目录下Banker/bankers.py

程序运行输出如下：

start here
_____________________________________________
MAX		Allocated	Need
[18, 16, 0, 0]	[17, 8, 0, 0]	[1, 8, 0, 0]
[4, 5, 0, 0]	[0, 0, 0, 0]	[4, 5, 0, 0]
[2, 2, 0, 1]	[0, 0, 0, 0]	[2, 2, 0, 1]
_____________________________________________
Resources:
Total: [28, 28, 1, 2]	Available: [11, 20, 1, 2]

Executing...
Request: 
[1, 8, 0, 0]
Dispatching Done...
_____________________________________________
MAX		Allocated	Need
[18, 16, 0, 0]	[1, 8, 0, 0]	[0, 0, 0, 0]
[4, 5, 0, 0]	[0, 0, 0, 0]	[4, 5, 0, 0]
[2, 2, 0, 1]	[0, 0, 0, 0]	[2, 2, 0, 1]
_____________________________________________
Resources:
Total: [28, 28, 1, 2]	Available: [10, 12, 1, 2]

-----Releasing Process------
_____________________________________________
MAX		Allocated	Need
[18, 16, 0, 0]	[0, 0, 0, 0]	[0, 0, 0, 0]
[4, 5, 0, 0]	[0, 0, 0, 0]	[4, 5, 0, 0]
[2, 2, 0, 1]	[0, 0, 0, 0]	[2, 2, 0, 1]
_____________________________________________
Resources:
Total: [28, 28, 1, 2]	Available: [28, 28, 1, 2]

Executing...
Request: 
[4, 5, 0, 0]
Dispatching Done...
_____________________________________________
MAX		Allocated	Need
[18, 16, 0, 0]	[0, 0, 0, 0]	[0, 0, 0, 0]
[4, 5, 0, 0]	[4, 5, 0, 0]	[0, 0, 0, 0]
[2, 2, 0, 1]	[0, 0, 0, 0]	[2, 2, 0, 1]
_____________________________________________
Resources:
Total: [28, 28, 1, 2]	Available: [24, 23, 1, 2]

-----Releasing Process------
_____________________________________________
MAX		Allocated	Need
[18, 16, 0, 0]	[0, 0, 0, 0]	[0, 0, 0, 0]
[4, 5, 0, 0]	[0, 0, 0, 0]	[0, 0, 0, 0]
[2, 2, 0, 1]	[0, 0, 0, 0]	[2, 2, 0, 1]
_____________________________________________
Resources:
Total: [28, 28, 1, 2]	Available: [28, 28, 1, 2]

Executing...
Request: 
[2, 2, 0, 1]
Dispatching Done...
_____________________________________________
MAX		Allocated	Need
[18, 16, 0, 0]	[0, 0, 0, 0]	[0, 0, 0, 0]
[4, 5, 0, 0]	[0, 0, 0, 0]	[0, 0, 0, 0]
[2, 2, 0, 1]	[2, 2, 0, 1]	[0, 0, 0, 0]
_____________________________________________
Resources:
Total: [28, 28, 1, 2]	Available: [26, 26, 1, 1]

-----Releasing Process------
_____________________________________________
MAX		Allocated	Need
[18, 16, 0, 0]	[0, 0, 0, 0]	[0, 0, 0, 0]
[4, 5, 0, 0]	[0, 0, 0, 0]	[0, 0, 0, 0]
[2, 2, 0, 1]	[0, 0, 0, 0]	[0, 0, 0, 0]
_____________________________________________
Resources:
Total: [28, 28, 1, 2]	Available: [28, 28, 1, 2]

SUCCESS proc lists  [0, 1, 2]
  • (spoc) 以小组为单位，请思考在lab1~lab5的基础上，是否能够实现IPC机制，请写出如何实现信号，管道或共享内存（三选一）的设计方案。

共享内存

在pmm.c中增加支持共享内存的几个函数

uint32_t getShid();
获取共享块的id，由此函数分配id，以确保对同一共享块，不同进程拿到的相同，以确保共享块id的全局唯一

bool cancleShid(uint32_t shm_id);
当某一共享段没有被任何进程的地址空间映射(没有被使用)时，应调用此函数，回收id.具体判断是否还有进程在使用共享段在此函数中调用。

uint32_t shmget(size_t size, bool flags);
创建一个共享块，调用alloc_page申请size大小的page，然后调用getShid获得该共享空间的唯一表示并返回。此处应创建一个全局结构，用于维护共享空间id shm_id到对应物理页的映射。

void shmat(uint32_t shmid, bool flags)；
把共享段映射到该进程的地址空间，完成页表项的建立，设置共享标志为等工作

void shmdt(uint32_t shm_id);
取消共享段到进程笛子空间的映射。完页表项的修改，将相应标志位置为0.最后需要调用cancleShid完成id回收。

void shmctl(uint32_t shm_id);
控制函数，用于共享段的空间回收等工作。

协调共享内存的访问冲突可以用信号量来解决。

  • (spoc) 扩展：用C语言实现某daemon程序，可检测某网络服务失效或崩溃，并用信号量机制通知重启网络服务。信号机制的例子

  • (spoc) 扩展：用C语言写测试用例，测试管道、消息队列和共享内存三种通信机制进行不同通信间隔和通信量情况下的通信带宽、通信延时、带宽抖动和延时抖动方面的性能差异。管道的例子