Segmentation
1. Segmentation: Generalized Base/Bounds
我们可以看一下（Figure 16.1），尽管每个CPU都有一对硬件寄存器（base register和bounds register），但是还是不可避免的会产生内存浪费（阴影部分表示未被使用）。为了解决这个问题，就引入了segmentation：既然每一个MMU（内存管理单元）有一对base register和bounds register，为什么不设置成每个地址空间逻辑分段都有一对base register和bounds register呢？
看一下下图（Figure 16.2）:
64KB的内存地址中有3个segments（Stack、Code、Heap and 16KB reserved fir the OS）。Figure 16.3展示了Figure 16.2每个分段：
2. Which Segment Are We Referring To?
引入了segmentation后，硬件使用分段寄存器将虚拟地址转换成实际物理地址。但是硬件怎么知道一个分段的偏移量？或者哪个分段是地址需要的？
一个直接的方法就是把虚拟地址的高几位地址作为分段基准。如下所示：
上图是对应于上述3个分段，所以选取了14位虚拟地址的首2位作为分段基准。例如，如果该两位是00，那么就表示Code分段，01表示Heap分段。
举个例子：虚拟地址为4200
我们可以看到高2位01表示选取heap分段，后12位为000 0110 1000（0x068或104），所以该虚拟地址的实际地址 = 104 + base register。
3. What About The Stack?
我们上面谈到了Code分段和Heap分段，那么Stack分段呢？我们再来看一下Figure 16.1。
Stack从高地址向低地址增长，和Code、Heap分段正好相反。为了解决这一问题，我们从高2位地址入手，学过数的二进制表示都知道，最高位0代表正，1代表负。那么我们可以引入这个原理。故有了下图所示：
4. Support for Sharing
引入了segmentation后，系统设计者们意识到可以进一步实现效率提高，就是在地址空间之间共享内存分段。现今的操作系统，Code sharing是很普遍且仍然在使用。
共享内存分段就不可避免的产生一个问题，如何保证每个程序都是安全的，即一个程序不能访问其他程序内的内容，其他程序也不能访问它内部的内容。故而引入了protection bits。
5. Fine-grained vs Coarse-grained Segmentation
我们上述所有例子都只有一小部分分段，每个分段都有非常大的地址空间，所以我们称其为coarse-grained。但是，在早期的系统中，把地址空间分成了数量众多的小分段，这种叫fine-grained 。
分段一多，采用更多的位表示的话就很浪费，所以对于分段很多的，就引入了segment table。
6. OS Support
Not Compacted的分段随机分配内存地址导致当一个需要大内存空间的进程到来时没有足够连续的分段给其使用而使OS拒绝这个进程的请求；而Compacted的分段把内存中的进程地址重新排列，使其未使用的内存空间连续且更大，能更好的满足其他进程的到来。
7. Homework (Simulation)
This program allows you to see how address translations are performed in a system with segmentation. See the README for details.
7.1 Question & Answer
1. First let’s use a tiny address space to translate some addresses. Here’s a simple set of parameters with a few different random seeds; can you translate the addresses?
2. Now, let’s see if we understand this tiny address space we’ve constructed (using the parameters from the question above). What is the highest legal virtual address in segment 0? What about the lowest legal virtual address in segment 1? What are the lowest and highest illegal addresses in this entire address space? Finally, how would you run segmentation.py with the -A flag to test if you are right?
我们拿上面 -s 2 的例子。address space size = 128，故有虚拟地址总共7位。由于最高位是segment bit，为1则是segment 1；为0则是segment 0。则虚拟地址offset bit 有6位。
对于segment 0来说，segment bit = 0, 考虑到limit = 20，则offset bit最大可以为010011。如下图：
则the highest legal virtual address in segment 0 = 0x00000013 (decimal : 19)
进行验证：
同理可得，对于segment 1，segment bit = 1, limit = 20，offset bit最大可以为101100（20的二进制表示为010100，对其取反加1）。
the lowest legal virtual address in segment 1 = 0x0000006c(decimal : 108)
进行验证：
对于实际物理地址而言：
the lowest illegal addresses in this entire address space = 20
the highest illegal addresses in this entire address space = 491
3. Let’s say we have a tiny 16-byte address space in a 128-byte physical memory. What base and bounds would you set up so as to get the simulator to generate the following translation results for the specified address stream: valid, valid, violation, ..., violation, valid, valid? Assume the following parameters:
4. Assume we want to generate a problem where roughly 90% of the randomly-generated virtual addresses are valid (not segmentation violations). How should you configure the simulator to do so? Which parameters are important to getting this outcome?
128 / 259<= address space size / phys mem size < 0.5
能保证随机情况下全部是有效地址.....
不用说，肯定是address space size和phys mem size重要的参量。
5. Can you run the simulator such that no virtual addresses are valid? How?
只需要把address space size 设置成2。21 = 2，故虚拟地址中的只有1位而这1位刚好表示segment bit，不存在offset bit，故没有虚拟地址是有效的。
