Operating System Concepts Exercises 8
操作系统作业 8
- 网上学习理解“代码可重入”
- 8.1，8.4，8.5，8.6，8.7
- 8.9， 8.12，8.13，8.14，8.15，8.18，8.19，8.20，8.21，8.23，8.28，8.29
每题最后一个引用块是老师提供的参考答案
网上学习理解“代码可重入”
若一个程序或子程序可以“在任意时刻被中断然后操作系统调度执行另外一段代码，这段代码又调用了该子程序不会出错”，则称其为可重入（reentrant 或 re-entrant）的。即当该子程序正在运行时，执行线程可以再次进入并执行它，仍然获得符合设计时预期的结果。与多线程并发执行的线程安全不同，可重入强调对单个线程执行时重新进入同一个子程序仍然是安全的。
可重入概念是在单线程操作系统的时代提出的。一个子程序的重入，可能由于自身原因，如执行了 jmp 或者 call，类似于子程序的递归调用；或者由于操作系统的中断响应。UNIX 系统的signal的处理，即子程序被中断处理程序或者 signal 处理程序调用。所以，可重入也可称作“异步信号安全”。这里的异步是指信号中断可发生在任意时刻。重入的子程序，按照后进先出线性序依次执行。
若一个函数是可重入的，则该函数应当满足下述条件：
- 不能含有静态（全局）非常量数据。
- 不能返回静态（全局）非常量数据的地址。
- 只能处理由调用者提供的数据。
- 不能依赖于单实例模式资源的锁。
- 调用 (call) 的函数也必需是可重入的。
上述条件就是要求可重入函数使用的所有变量都保存在呼叫堆叠的当前函数栈（frame）上，因此同一执行线程重入执行该函数时加载了新的函数帧，与前一次执行该函数时使用的函数帧不冲突、不互相覆盖，从而保证了可重入执行安全。
多“用户/对象/进程优先级”以及多进程（Multiple processes），一般会使得对可重入代码的控制变得复杂。同时，IO 代码通常不是可重入的，因为他们依赖于像磁盘这样共享的、单独的（类似编程中的静态、全域）资源。
可重入性是函数编程语言的关键特性之一。
[1]
Practice Exercises
8.1, 8.4, 8.5, 8.6, 8.7
8.1 Name two differences between logical and physical addresses.
说出逻辑地址和物理地址的两个区别。
答：
An address generated by the CPU is commonly referred to as a logical address, whereas an address seen by the memory unit—that is, the one loaded into the memory-address register of the memory—is commonly referred to as a physical address.
——教材 P355
物理地址是真实的地址，而逻辑地址不是。
逻辑地址范围为 0 ~ max，物理地址范围为 R + 0 ~ R + max。
Answer:
The basic difference between Logical and physical address is that Logical address is generated by CPU in perspective of a running program. On the other hand, the physical address is a location that exists in the memory unit, and can be accessed physically.
逻辑地址和物理地址的基本区别是，逻辑地址是由 CPU 从运行程序的角度产生的。另一方面，物理地址是存在于内存单元中的一个位置，可以被物理访问。
The set of all logical addresses generated by CPU for a program is called Logical Address Space. However, the set of all physical address mapped to corresponding logical addresses is referred as Physical Address Space.
由 CPU 为一个程序生成的所有逻辑地址的集合被称为逻辑地址空间。然而，所有物理地址映射到相应的逻辑地址的集合被称为物理地址空间。
Identical logical address and physical address are generated by Compile-time and Load time address binding methods.
相同的逻辑地址和物理地址是由编译时和加载时的地址绑定方法产生的。
The logical and physical address generated by run-time address binding method (Memory Management Unit) differs from each other.
由运行时地址绑定方法（内存管理单元）生成的逻辑地址和物理地址彼此不同。
8.4 Consider a logical address space of 64 pages of 1,024 words each, mapped onto a physical memory of 32 frames.
考虑一个由 64 个页面组成的逻辑地址空间，每个页面有 1,024 个字，映射到 32 个帧的物理存储器上。
a. How many bits are there in the logical address?
答： 64*1024words
b. How many bits are there in the physical address?
答： 32*1024words
Answer:
a. Logical address: 16 bits
b. Physical address: 15 bits
8.5 What is the effect of allowing two entries in a page table to point to the same page frame in memory? Explain how this effect could be used to decrease the amount of time needed to copy a large amount of memory from one place to another. What effect would updating some byte on the one page have on the other page?
允许页表中的两个条目指向内存中的同一个页框有什么效果？
答： 节省内存空间
解释一下如何利用这种效果来减少将大量内存从一个地方复制到另一个地方所需的时间。
答： 这样子就不需要花费时间复制内存了
更新一个页面上的某些字节对另一个页面有什么影响？
答： 会产生同样的变化
Answer:
By allowing two entries in a page table to point to the same page frame in memory, users can share code and data. If the code is reentrant, much memory space can be saved through the shared use of large programs such as text editors, compilers, and database systems. “Copying” large amounts of memory could be effected by having different page tables point to the same memory location.
However, sharing of non-reentrant code or data means that any user having access to the code can modify it and these modifications would be reflected in the other user’s “copy”. So “copy-on-write” should be used.
通过允许页表中的两个条目指向内存中的同一个页框，用户可以共享代码和数据。如果代码是可重入的，通过共享使用大型程序，如文本编辑器、编译器和数据库系统，可以节省很多内存空间。”复制 “大量的内存可以通过让不同的页表指向同一个内存位置来实现。
然而，共享非重复性的代码或数据意味着任何能够访问该代码的用户都可以修改它，这些修改将反映在其他用户的 “副本 “中。所以应该使用 “写时拷贝”。
8.6 Describe a mechanism by which one segment could belong to the address space of two different processes.
描述一种机制，通过这种机制，一个段可以属于两个不同进程的地址空间。
答： 共享页
Answer:
Since segment tables are a collection of base–limit registers, segments can be shared when entries in the segment table of two different processes point to the same physical location.
The two segment tables must have identical base pointers, and the shared segment number must be the same in the two processes.
由于段表是基限寄存器的集合，当两个不同进程的段表中的条目指向同一个物理位置时，段可以被共享。
这两个段表必须有相同的基数指针，而且两个进程中的共享段号必须相同。
8.7 Sharing segments among processes without requiring that they have the same segment number is possible in a dynamically linked segmentation system.
在动态链接的分段系统中，进程之间共享分段而不要求它们有相同的分段编号是可能的。
a. Define a system that allows static linking and sharing of segments without requiring that the segment numbers be the same.
定义一个系统，允许静态链接和共享段，而不要求段号相同。
答： 可以通过共享页来实现，不同的段指向相同的页
b. Describe a paging scheme that allows pages to be shared without requiring that the page numbers be the same.
描述一种允许共享页面而不要求页码相同的分页方案。
答： 不同页映射到相同的帧
Answer:
Both of these problems reduce to a program being able to reference both its own code and its data without knowing the segment or page number associated with the address. MULTICS solved this problem by associating four registers with each process. One register had the address of the current program segment, another had a base address for the stack, another had a base address for the global data, and so on. The idea isthat all references have to be indirect through a register that maps to the current segment or page number. By changing these registers, the same code can execute for different processes without the same page or segment numbers.
这两个问题都简化为程序能够同时引用自己的代码和数据而不知道与地址相关的段或页号。MULTICS 通过将四个寄存器与每个进程联系起来解决了这个问题。一个寄存器是当前程序段的地址，另一个是堆栈的基址，另一个是全局数据的基址，以此类推。这个想法是，所有的引用都必须通过映射到当前程序段或页号的寄存器间接进行。通过改变这些寄存器，相同的代码可以在没有相同页或段号的情况下为不同的进程执行。
Exercises
8.9， 8.12，8.13，8.14，8.15，8.18，8.19，8.20，8.21，8.23，8.28，8.29
8.9 Explain the difference between internal and external fragmentation.
解释内部和外部碎片的区别。
答：
内部碎片是填不满页表产生的碎片，目前没有很好地办法解决；外部碎片是内存分配中产生的碎片，目前可以用分页方案完美解决。
Answer:
Internal fragmentation occurs when fixed sized memory blocks are allocated to the processes. The memory assigned to the process is slightly larger than the memory requested by the process. It is the area occupied by a process but cannot be used by the process. This space is unusable by the system until the process release the space.
External fragmentation occurs when variable size memory space are allocated to the processes dynamically. It exists when total free memory (holes) is enough for the new process but it’s not contiguous and can’t satisfy the request. Storage is fragmented into small holes.
当固定大小的内存块被分配给进程时，就会发生内部碎片化。分配给进程的内存比进程要求的内存略大。它是被进程占用但不能被进程使用的区域。这个空间在进程释放空间之前，系统是无法使用的。
当可变大小的内存空间被动态地分配给进程时，就会出现外部碎片。它存在于总的自由内存（孔）足够新进程使用，但它不是连续的，不能满足要求。存储被分割成小孔。
8.12 Most systems allow a program to allocate more memory to its address space during execution. Allocation of data in the heap segments of programs is an example of such allocated memory. What is required to support dynamic memory allocation in the following schemes?
大多数系统允许程序在执行过程中为其地址空间分配更多的内存。在程序的堆段中分配数据是这种分配内存的一个例子。在下列方案中，需要什么来支持动态内存分配？
a. Contiguous memory allocation
毗连的内存分配
答： 程序全部重新分配
b. Pure segmentation
纯 segmentation
答： 分配拓展段
c. Pure paging
纯分页
答： 分配新分页
Answer:
a. Contiguous memory allocation:
might require relocation of the entire program since there is not enough space for the program to grow its allocated memory space.
b. Pure segmentation:
might also require relocation of the segment that needs to be extended since there is not enough space for the segment to grow its allocated memory space.
c. Pure paging:
Incremental allocation of new pages is possible in this scheme without requiring relocation of the program’s address space.
a. 毗连的内存分配。
可能需要重新定位整个程序，因为没有足够的空间让程序增长其分配的内存空间。
b. 纯粹的分段。
可能还需要重新定位需要扩展的程序段，因为没有足够的空间让该程序段增加其分配的内存空间。
c. 纯分页。
在这个方案中，新页的增量分配是可能的，不需要重新定位程序的地址空间。
8.13 Compare the memory organization schemes of contiguous memory allocation, pure segmentation, and pure paging with respect to the following issues:
在以下问题上，比较连续内存分配、纯分段和纯分页的内存组织方案。
a. External fragmentation
外部碎片
答： 连续内存分配：有；纯分段：有；纯分页：无
b. Internal fragmentation
内部碎片
答： 连续内存分配：无；纯分段：无；纯分页：有
c. Ability to share code across processes
跨进程共享代码的能力
答： 连续内存分配：不行；纯分段：可；纯分页：可
Answer:
a. Contiguous memory allocation scheme suffers from external fragmentation as address spaces are allocated contiguously and holes develop as old processes die and new processes are initiated. It also does not allow processes to share code, since a process’s virtual memory segment is not broken into non-contiguous fine-grained segments.
b. Pure segmentation also suffers from external fragmentation as a segment of a process is laid out contiguously in physical memory and fragmentation would occur as segments of dead processes are replaced by segments of new processes. Segmentation, however, enables processes to share code; for instance, two different processes could share a code segment but have distinct data segments.
c. Pure paging does not suffer from external fragmentation, but instead suffers from internal fragmentations. Processes are allocated in page granularity and if a page is not completely utilized, it results in internal fragmentation and a corresponding wastage of space. Paging also enables processes to share code at the granularity of pages.
a. 毗连内存分配方案受到外部碎片的影响，因为地址空间是毗连分配的，随着老进程的死亡和新进程的启动，会出现洞。它也不允许进程共享代码，因为一个进程的虚拟内存段没有被分解成非连续的细粒度段。
b. 纯粹的分段也会受到外部碎片的影响，因为一个进程的段在物理内存中是连续布置的，当死亡进程的段被新进程的段所取代时，就会发生碎片化。然而，分段使进程可以共享代码；例如，两个不同的进程可以共享一个代码段，但有不同的数据段。
c. 纯粹的分页不存在外部分片，而是存在内部分片的问题。进程是以页为单位分配的，如果一个页没有被完全利用，就会导致内部碎片化和相应的空间浪费。分页也使进程能够在页的粒度上共享代码。
8.14 On a system with paging, a process cannot access memory that it does not own. Why? How could the operating system allow access to other memory? Why should it or should it not?
在一个有分页的系统中，一个进程不能访问它不拥有的内存，为什么？
答： 保护
操作系统能允许访问其他内存吗？
答： 能
为什么它应该或不应该？
答： 因为操作系统得管理内存
Answer:
An address on a paging system is a logical page number and an offset. The physical page is found by searching a table based on the logical page number to produce a physical page number. Because the operating system controls the contents of this table, it can limit a process to accessing only those physical pages allocated to the process. There is no way for a process to refer to a page it does not own because the page will not be in the page table. To allow such access, an operating system simply needs to allow entries for non-process memory to be added to the processs page table. This is useful when two or more processes need to exchange data they just read and write to the same physical addresses (which may be at varying logical addresses). This makes for very efficient interprocess communication.
分页系统上的一个地址是一个逻辑页号和一个偏移量。物理页是通过搜索一个基于逻辑页号的表来产生一个物理页号的。因为操作系统控制着这个表的内容，它可以限制一个进程只访问分配给该进程的物理页。一个进程不可能引用它不拥有的页面，因为该页面不在页表中。为了允许这种访问，操作系统只需要允许非进程内存的条目被添加到进程的页表中。当两个或更多的进程需要交换数据时，这是非常有用的，它们只是对相同的物理地址（可能在不同的逻辑地址）进行读写。这使得进程间的通信非常有效。
8.15 Explain why mobile operating systems such as iOS and Android do not support swapping.
解释为什么 iOS 和 Android 等移动操作系统不支持 swap。
答： 闪存容量小，写入次数有限制，闪存与内存之间的吞吐量差。
8.2.2 Swapping on Mobile Systems
Although most operating systems for PCs and servers support some modified version of swapping, mobile systems typically do not support swapping in any form. Mobile devices generally use flash memory rather than more spacious hard disks as their persistent storage. The resulting space constraint is one reason why mobile operating-system designers avoid swapping. Other reasons include the limited number of writes that flash memory can tolerate before it becomes unreliable and the poor throughput between main memory and flash memory in these devices.
Instead of using swapping, when free memory falls below a certain threshold, Apple’s iOS asks applications to voluntarily relinquish allocated memory. Read-only data (such as code) are removed from the system and later reloaded from flash memory if necessary. Data that have been modified (such as the stack) are never removed. However, any applications that fail to free up sufficient memory may be terminated by the operating system.
Android does not support swapping and adopts a strategy similar to that used by iOS. It may terminate a process if insufficient free memory is available. However, before terminating a process, Android writes its application state to flash memory so that it can be quickly restarted.
Because of these restrictions, developers for mobile systems must carefully allocate and release memory to ensure that their applications do not use too much memory or suffer from memory leaks. Note that both iOS and Android support paging, so they do have memory-management abilities. We discuss paging later in this chapter.
——教材 P360
然而随着时代的发展，有些移动系统已经开始支持 swap
Answer:
Reasons:
First is that these mobile devices typically use flash memory with limited capacity and swapping is avoided because of this space constraint.
Second, flash memory can support a limited number of write operations before it becomes less reliable.
Primarily because Android does not wish for its boot disk to be used as swap space for the reasons outlined in the previous question. However, Android does support swapping, it is just that users must provide their own separate SD card for swap space.
原因是：
首先是这些移动设备通常使用容量有限的闪存，由于这种空间限制，交换被避免了。
第二，闪存在变得不那么可靠之前可以支持有限的写操作。
主要是因为安卓系统不希望其启动盘被用作交换空间，原因见前述问题。然而，安卓系统确实支持交换，只是用户必须提供自己的独立 SD 卡作为交换空间。
8.18 Explain why address space identifiers (ASIDs) are used.
答： 确保地址仍有效等作用
Some TLBs store address-space identifiers (ASIDs) in each TLB entry. An ASID uniquely identifies each process and is used to provide address-space protection for that process. When the TLB attempts to resolve virtual page numbers, it ensures that the ASID for the currently running process matches the ASID associated with the virtual page. If the ASIDs do not match, the attempt is treated as a TLB miss. In addition to providing address-space protection, an ASID allows the TLB to contain entries for several different processes simultaneously. If the TLB does not support separate ASIDs, then every time a new page table is selected (for instance, with each context switch), the TLB must be flushed (or erased) to ensure that the next executing process does not use the wrong translation information. Otherwise, the TLB could include old entries that contain valid virtual addresses but have incorrect or invalid physical addresses left over from the previous process.
——教材 P374
Answer:
ASIDs provide address space protection in the TLB as well as supporting TLB entries for several different processes at the same time.
If the TLB does not support separate ASIDs, then every time a new page table is selected (context switch), the TLB must be flushed to ensure that the next executing process does not use the wrong translation information.
ASIDs 在 TLB 中提供了地址空间保护，并支持 TLB 条目同时用于几个不同的进程。
如果 TLB 不支持独立的 ASID，那么每次选择新的页表（上下文切换）时，必须刷新 TLB 以确保下一个执行进程不会使用错误的翻译信息。
8.19 Program binaries in many systems are typically structured as follows. Code is stored starting with a small, fixed virtual address, such as 0. The code segment is followed by the data segment that is used for storing the program variables. When the program starts executing, the stack is allocated at the other end of the virtual address space and is allowed to grow toward lower virtual addresses. What is the significance of this structure for the following schemes?
许多系统中的程序二进制文件的结构通常如下。代码从一个小的、固定的虚拟地址开始存储，如 0。代码段之后是数据段，用于存储程序变量。当程序开始执行时，堆栈被分配在虚拟地址空间的另一端，并被允许向更低的虚拟地址增长。这种结构对以下方案的意义是什么？
a. Contiguous memory allocation
毗连的内存分配
答： 固定大小防止重新分配内存
b. Pure segmentation
纯分段
答： 方便拓展
c. Pure paging
纯分页
答： 方便新分配
Answer:
Contiguous-memory allocation requires the operating system to allocate the entire extent of the virtual address space to the program when it starts executing .This could be much higher than the actual memory requirements of the process.
Pure segmentation gives the operating system flexibility to assign a small extent to each segment at program startup time and extend the segment if required.
Pure paging does not require the operating system to allocate the maximum extent of the virtual address space to a process at startup time, but it still requires the operating system to allocate a large page table spanning all of the program’s virtual address space. When a program needs to extend the stack or the heap, it needs to allocate a new page but the corresponding page table entry is preallocated.
毗连内存分配要求操作系统在程序开始执行时分配整个虚拟地址空间的范围，这可能比进程的实际内存需求高得多。
纯粹的分段给了操作系统灵活性，在程序启动时给每个段分配一个小的范围，如果需要的话，可以扩展这个段。
3）纯分页不要求操作系统在启动时给进程分配最大范围的虚拟地址空间，但它仍然要求操作系统分配一个大的分页表，跨越程序的所有虚拟地址空间。当一个程序需要扩展堆栈或堆时，它需要分配一个新的页面，但相应的页表项是预先分配的。
8.20 Assuming a 1-KB page size, what are the page numbers and offsets for the following address references (provided as decimal numbers):
假设页面大小为 1KB，以下地址参考的页码和偏移量是多少（以十进制数字提供）。
a. 3085
答： 3；13
b. 42095
答： 41；111
c. 215201
答： 210；161
d. 650000
答： 634；784
e. 2000001
答： 1953；129
Answer:
Page size =2n=1024 B= 210 B
Logical address (decimal) Page # (decimal) Offset (decimal) 3085 3 13 42095 41 111 215201 210 161 650000 634 784 2000001 1953 129
8.21 The BTV operating system has a 21-bit virtual address, yet on certain embedded devices, it has only a 16-bit physical address. It also has a 2-KB page size. How many entries are there in each of the following?
BTV 操作系统有一个 21 位的虚拟地址，然而在某些嵌入式设备上，它只有一个 16 位的物理地址。它也有一个 2KB 的页面大小。以下每个条目有多少个？
a. A conventional, single-level page table
一个传统的、单层的页表
答： $\frac{2^{21}}{2\times 8\times 1024}=128 个$
$\frac{2^{21}}{2\times 1024}=1024 个$
b. An inverted page table
一个倒置的页表
答： $\frac{2^{16}}{2\times 8\times 1024}=4 个$
$\frac{2^{16}}{2\times 1024}=32 个$
Answer:
a. 2^10
b. 2^5
8.23 Consider a logical address space of 256 pages with a 4-KB page size, mapped onto a physical memory of 64 frames.
考虑一个具有 4KB 页大小的 256 页的逻辑地址空间，映射到 64 帧的物理内存上。
a. How many bits are required in the logical address?
答： $12+8=20 bits$
b. How many bits are required in the physical address?
答： $12+6=18bits$
Answer:
a. The logical address requires 8 bits for the page number because there are 256=2^8, of them. Then, the logical address requires 12 bits of the offset because there are 4KB=2^12B of them. So, the logical address requires a total is 20 bits.
b. The physical address requires 6 bits for the frame number because there are 64=2^6 of them. Then, the physical address also requires 12 bits of the offset because there are 4KB=2^12B them. So, the physical address requires a total is 18 bits.
8.28 Consider the following segment table:
1 | Segment Base Length |
What are the physical addresses for the following logical addresses?
a. 0,430
答： 219+430=649
b. 1,10
答： 2300+10=2310
c. 2,500
答： 非法
d. 3,400
答： 1327+400=1727
e. 4,112
答： 非法
Answer:
a. 219 +430 =649. Segment 0 has a length of 600, which is greater than 430.
b. 2300+10=2310. Segment 1 has a length of 14, which is greater than 10.
c. Illegal reference.
d. 1327+400=1727. Segment 3 has a length of 580, which is greater than 400.
e. Illegal reference. Segment 4 has a length of 96, which is less than 112.
8.29 What is the purpose of paging the page tables?
分页页表的目的是什么
答： 页表本身可能会很大
Answer:
Since most modern computer systems support a large logical address space (32/64 bits), the page table itself becomes excessively large (space cost). We know the fact that entire sections of virtual address space are frequently unused. Paging the page tables have no entries for these spaces, greatly decreasing the amount of memory needed to store virtual memory data structures.
由于大多数现代计算机系统支持大的逻辑地址空间（32/64 位），页表本身变得过分庞大（空间成本）。我们知道的事实是，虚拟地址空间的整个部分经常是未使用的。分页表没有这些空间的条目，大大减少了存储虚拟内存数据结构所需的内存量。
注：
参考资料：
[1] 可重入 - 维基百科，自由的百科全书 (wikipedia.org)
[2] Operating System Concepts – 9th Edition 及其答案
