Skip to content

Latest commit

 

History

History
215 lines (154 loc) · 10 KB

03-1-spoc-discussion.md

File metadata and controls

215 lines (154 loc) · 10 KB

lec5 SPOC思考题

提前准备

  • 完成lec５的视频学习和提交对应的在线练习
  • git pull ucore_os_lab, v9_cpu, os_course_spoc_exercises 　in github repos。这样可以在本机上完成课堂练习。
  • 理解连续内存动态分配算法的实现（主要自学和网上查找）

NOTICE

  • 有"w3l1"标记的题是助教要提交到学堂在线上的。
  • 有"w3l1"和"spoc"标记的题是要求拿清华学分的同学要在实体课上完成，并按时提交到学生对应的git repo上。
  • 有"hard"标记的题有一定难度，鼓励实现。
  • 有"easy"标记的题很容易实现，鼓励实现。
  • 有"midd"标记的题是一般水平，鼓励实现。

个人思考题

请简要分析最优匹配，最差匹配，最先匹配，buddy systemm分配算法的优势和劣势，并尝试提出一种更有效的连续内存分配算法 (w3l1)

  + 采分点：说明四种算法的优点和缺点
  - 答案没有涉及如下3点；（0分）
  - 正确描述了二种分配算法的优势和劣势（1分）
  - 正确描述了四种分配算法的优势和劣势（2分）
  - 除上述两点外，进一步描述了一种更有效的分配算法（3分）

{%s%}

  • 最优匹配算法总是把能满足要求的最小空闲分区分配出去。这种分配算法可以让碎片达到最小，但是为了能够快速找到最适合的内存块，需要将所有的空闲内存块管理起来，带来了一定的开销。同时，在内存空间分配一段时间后，会产生很多的小块的难以利用的内存碎片。
  • 最差匹配算法，和最优匹配相反，每次都找到最大的空闲块进行分配。好处是寻找内存块的速度非常快，同时内存碎片往往较大。
  • 最先匹配，该算法按照地址空间找到第一个能够满足要求的内存块。其优势时管理简单，同时倾向于保留高地址空间的内存给后期的大作业。缺点在于低地址部分不断被划分，变成很多小的空闲块，加大了查找的开销。
  • 伙伴算法将内存每次对半分，直到恰好大于需要分配的大小。伙伴算法极大的解决了内存的外碎片问题，但是一个很小的块可能就会阻止一个大块的回收。同时，算法有一定的浪费。对内存块的分配和释放开销也比较大。
  • 为了能够解决伙伴算法中的分配和回收开销问题，引入二级索引，一级索引由2的次幂构成，二级索引是对应的该次幂的线性增长。每个索引用位图中表明是否存在该大小区间的内存块。具体参见TLSF算法。 {%ends%}

小组思考题

请参考xv6（umalloc.c），ucore lab2代码，选择四种（0:最优匹配，1:最差匹配，2:最先匹配，3:buddy systemm）分配算法中的一种或多种，在Linux应用程序/库层面，用C、C++或python来实现malloc/free，给出你的设计思路，并给出可以在Linux上运行的malloc/free实现和测试用例。 (spoc)

如何表示空闲块？ 如何表示空闲块列表？
[(start0, size0),(start1,size1)...]
在一次malloc后，如果根据某种顺序查找符合malloc要求的空闲块？如何把一个空闲块改变成另外一个空闲块，或消除这个空闲块？如何更新空闲块列表？
在一次free后，如何把已使用块转变成空闲块，并按照某种顺序（起始地址，块大小）插入到空闲块列表中？考虑需要合并相邻空闲块，形成更大的空闲块？
如果考虑地址对齐（比如按照4字节对齐），应该如何设计？
如果考虑空闲/使用块列表组织中有部分元数据，比如表示链接信息，如何给malloc返回有效可用的空闲块地址而不破坏
元数据信息？
伙伴分配器的一个极简实现
http://coolshell.cn/tag/buddy

扩展思考题

阅读slab分配算法，尝试在应用程序中实现slab分配算法，给出设计方案和测试用例。

“连续内存分配”与视频相关的课堂练习

5.1 计算机体系结构和内存层次

1.操作系统中存储管理的目标是什么？

  • {%s%}抽象{%ends%}
  • {%s%}保护{%ends%}
  • {%s%}共享{%ends%}
  • {%s%}虚拟化{%ends%}

2.MMU的工作机理？

{%s%}

  • MMU 通过页表寄存器查找到页表，然后对应页表中存储的虚拟地址空间到物理地址空间的映射关系，将虚拟地址空间映射到物理地址空间。 {%ends%}

http://en.wikipedia.org/wiki/Memory_management_unit

3.L1、L2和L3高速缓存有什么区别？

{%s%}

  • L1 高速缓存的速度更快，容量更小。
  • 通常可以把L1、L2和L3的区别理解为，L1在CPU核内，只有同一个核的重复访问时提供共享；L2在CPU内但不在核内，在同一个CPU上的不同核间提供共享；L3在CPU外的主板上，在不同CPU间提供共享。它们的容量大致相差一个数量级，如L1 32KB，L2 256KB，L3 8MB。 {%ends%}

http://superuser.com/questions/196143/where-exactly-l1-l2-and-l3-caches-located-in-computer Where exactly L1, L2 and L3 Caches located in computer?

http://en.wikipedia.org/wiki/CPU_cache CPU cache

5.2 地址空间和地址生成

1.描述编译、汇编、链接和加载的过程是什么？

2.动态链接如何使用？

{%s%} 编译链接和加载 {%ends%}

5.3 连续内存分配

1.什么是内碎片、外碎片？

{%s%} 内碎片是指分配给任务的内存大小比任务所要求的大小所多出来的内存。外碎片只分配给任务的内存之间无法利用的内存。 {%ends%}

2.为什么最先匹配会越用越慢？

{%s%} 因为最先匹配总是先找低地址空间的内存，到后期低地址空间都是大量小的不连续的内存空间，每次都要扫描低地址空间后到达高地质空间才能得到可用的内存。 {%ends%}

3.为什么最差匹配会的外碎片少？

{%s%} 因为每次都找到最大的内存块进行分割，因此分割剩下的内存块也很大，往往还可以再装下一个程序。 {%ends%}

4.在几种算法中分区释放后的合并处理如何做？

{%s%} 查看边上是否也有空闲块，如果有，则合并空闲块，然后将空闲块管理数据插入链表中。 {%ends%}

5.4 碎片整理

1.对换和紧凑都是碎片整理技术，它们的主要区别是什么？为什么在早期的操作系统中采用对换技术？

  • {%s%}区别是，紧凑是在内存中搬动进程占用的内存位置，以合并出大块的空闲块；对换是把内存中的进程搬到外存中，以空出更多的内存空闲块{%ends%}
  • {%s%}采用对换的原因是，处理简单{%ends%}

2.一个处于等待状态的进程被对换到外存（对换等待状态）后，等待事件出现了。操作系统需要如何响应？

{%s%} 将进程从硬盘中读取到内存中，在这个过程中，操作系统将该进程标为等待状态并且调度其他进程。 {%ends%}

5.5 伙伴系统

1.伙伴系统的空闲块如何组织？

{%s%}

  • 按照内存的大小有一系列链表组织,类似于哈希表，将相同大小的内存区域首地址连接起来。 {%ends%}

2.伙伴系统的内存分配流程？

{%s%}

  • 当向内核请求分配(2^(i-1)，2^i]数目的页块时，按照2^i页块请求处理。如果对应的块链表中没有空闲页块，则在更大的页块链表中找。当分配的页块中有多余的页时，伙伴系统根据多余的页框大小插入到对应的空闲页块链表中。 {%ends%}

伙伴系统的内存回收流程？

{%s%} 　　当释放多页的块时，内核首先计算出该内存块的伙伴的地址。内核将满足以下条件的三个块称为伙伴：(1)两个块具有相同的大小，记作b。(2)它们的物理地址是连续的。(3)第一块的第一个页的物理地址是2*(2^b)的倍数。如果找到了该内存块的伙伴，确保该伙伴的所有页都是空闲的，以便进行合并。内存继续检查合并后页块的“伙伴”并检查是否可以合并，依次类推。 {%ends%}

struct list_entry是如何把数据元素组织成链表的？

{%s%}

  • 每个struct的list_entry 指向下一个的struct的list_entry {%ends%}

v9-cpu相关

[challenge]在v9-cpu上完成基于method-0/1/2/buddy system（选一个方法）with first/best/worst-fit(选一个fit)用户态动态内存分配函数malloc/free，要求在内核态实现sbrk系统调用以支持用户态动态内存分配方法。基于os4.c实现，可参考v9-cpu git repo的testing分支中的os.c和mem.h

  • [x]

[challenge]在v9-cpu上完成基GC算法，要求在内核态实现sbrk系统调用以支持用户态动态内存分配方法。基于os4.c实现，可参考v9-cpu git repo的testing分支中的os.c和mem.h

  • [x]

其它

  • 静态分配内存与动态分配内存的区别是啥？ {%s%}
    静态内存分配发生在程序编译和链接过程中，动态分配则发生在程序调入和执行时。 {%ends%}
  • 在隐式链表结构中，如何实现向前的合并操作？ {%s%}
    在内存块的末尾也放入一个size数据，以此找到前一个内存块的头部，并判断其是否空闲。 {%ends%}
  • 如何判断一个函数是库函数还是一个系统调用？ {%s%}
    用strace可以跟踪所有的系统调用。同时，有些库函数最后也会调用系统调用。 {%ends%}
  • 为何要在OS内部和用户态中实现两层动态内存分配？ {%s%}
    OS 才是系统资源的实际管理者，用户态的动态内存分配只是OS 提供给用户的一个资源管理接口，即用户态的的内存分配其实质也是调用OS内部的动态内存分配。 但是，有些时候为了能够达到性能等定制目的，也可能想内核申请一大块内存区域，并且在用户态实现一套内存分配机制。 {%ends%}
  • 为何在OS内部没有采用GC分配方式？ {%s%}
    GC需要对所有的内存分配和释放进行跟踪，同时在进行内存释放的时候非常消耗资源，可能会导致系统运行速度缓慢。 {%ends%}