内存管理

Memory management is the act of managing computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when no longer needed. This is critical to any advanced computer system where more than a single process) might be underway at any time.

内存管理术语

内存管理需求：重定位、保护、共享、逻辑组织、物理组织

内存管理最基本的操作是由处理器把程序装入内存中执行。

内存分区

内存管理最基本的操作是由处理器把程序装入内存中执行。

类型

算数类型

内置类型的机器实现

计算机以比特序列存储数据，每个比特非0即1。大多数计算机以2的整数次幂个比特为块来处理内存，可寻址的最小内存块称为“字节（byte）”。存储的基本单元称为“字（word）”，它通常由几个字节组成。

除去布尔和扩展的字符外，其他整型可以划分为带符号的（signed）和无符号的（unsigned）两种。带符号的类型可以表示整数、负数或0，无符号类型则仅能表示大于等于0的值。

Intro

Coroutines are computer program components that generalize subroutines for nonpreemptive multitasking, by allowing multiple entry points for suspending and resuming execution at certain locations. Coroutines are well-suited for implementing more familiar program components such as cooperative tasks, exceptions, event loop, iterators, infinite lists and pipes.

Coroutines are a natural way of expressing many algorithms, such as simulations, games, asynchronous I/O, and other forms of event-driven programming or co-operative multitasking. Python’s generator functions are almost coroutines — but not quite — in that they allow pausing execution to produce a value, but do not provide for values or exceptions to be passed in when execution resumes. They also do not allow execution to be paused within the “try” portion of try/finally blocks, and therefore make it difficult for an aborted coroutine to clean up after itself.

Such applications could then write co-routines to do non-blocking socket I/O by yielding control to an I/O scheduler until data has been sent or becomes available.

Because generator-iterators begin execution at the top of the generator’s function body, there is no yield expression to receive a value when the generator has just been created. Therefore, calling send() with a non-None argument is prohibited when the generator iterator has just started, and a TypeError is raised if this occurs. Thus, before you can communicate with a coroutine you must first call next() or send(None) to advance its execution to the first yield expression.

这应该是一篇迟到好几年的文章了，之前面试就被问过关于nginx的东西。回忆一下回答的并不好，大多数时候其实都只是简单的应用而已。很少去关心为什么用？所以想想也对，一直逃避的问题其实是逃不掉，所以最终还是要坦然面对。

简介

nginx（pronounced “engine x”），开源web服务器。nginx has focused on high performance, high concurrency and low memory usage.

Architechture

nginx在启动后，会有一个master进程和多个worker进程。master进程主要用来管理worker进程，包含：接收来自外界的信号，向各worker进程发送信号，监控worker进程的运行状态，当worker进程退出后，会自动重新启动新的worker进程。而基本的网络事件，则是放在worker进程中来处理了。worker进程的个数是可以设置的，一般我们会设置与机器cpu核数一致。

树的遍历

• 前序（preorder），我们访问该几点，然后访问该节点的左子树和右子树；
• 中序（inoder），我们访问该节点的左子树，然后访问该节点，再访问该节点的右子树；
• 后序（postorder），我们访问该节点的左子树和右子树，再访问该节点。

递归遍历

1
2
3
4
5
6
7

void traverse(link h, void(*visit)(link))
{
    if(h == NULL) return;
    (*visit) (h);
    traverse(h->l, visit);
    traverse(h->r, visit);
}

非递归遍历

所有的递归都可以用迭代来实现么？

1
2
3
4
5
6
7
8
9
10
11

void traverse(link h, void(*visit)(link))
{
    STACKinit(max);
    STACKpush(h);
    while(!STACKempty())
    {
        (*visit)(h = STACKpop());
        if (h->r != NULL) STACKpush(h->r);
        if (h->l != NULL) STACKpush(h->l);
    }
}

简介

泛型程序设计是程序设计语言的一种风格或范式。允许程序员在强类型程序设计语言中编写代码时使用一些以后才指定的类型，在实例化时作为参数指明这些类型。

Java generics 是JDK 5中引入的一个新特性，允许在定义类和接口的时候使用类型参数（type parameter）。声明的类型参数在使用时用具体的类型来替换。

从好的方面来说，泛型的引入可以解决之前的集合类框架在使用过程中通常会出现的运行时候类型错误，因为编译器可以在编译时刻就发现很多明显的错误。

泛型的本质是参数化类型（ Parameterized Type）的应用，也就是说所操作的数据类型被指定为一个参数。这种参数类型可以用在类、接口和方法的创建中，分别称为泛型类、泛型接口和泛型方法。

Java语言中的泛型只在程序源码中存在，在编译后的字节码文件中，就已经被替换为原来的原生类型（Raw Type）了，并且在响应的地方插入了强制转型代码，Java语言中的泛型实现方法称为类型擦除，基于这种方法实现的泛型被称为伪泛型。

Why use generics?

In a nutshell, generics enable types (classes and interfaces) to be parameters when defining classes, interfaces and methods. Much like the more familiar formal parameters used in method declarations, type parameters provide a way for you to re-use the same code with different inputs. The difference is that the inputs to formal parameters are values, while the inputs to type parameters are types.

Generic Types

The most commonly used type parameter names are:

• E - Element (used extensively by the Java Collections Framework)
• K - Key
• N - Number
• T - Type
• V - Value
• S,U,V etc. - 2nd, 3rd, 4th types

A process generally also includes the process stack, which contains temporary data(such as function parameters, return addresses, and local variables), and a data section, which contains global variables. A process may also include a heap, which is memory that is dynamically allocated during process run time.

A program becomes a process when an executable file is loaded into memory.

进程描述和控制

操作系统必须满足的大多数需求表示都涉及进程：

• 操作系统必须交替执行多个进程，在合理的响应时间范围内使处理器的利用率最大
• 操作系统必须按照特定的策略给进程分配资源，同时避免死锁。
• 操作系统可以支持进程间的通信和用户创建进程，它们对构造应用程序很有帮助

从本质上看，如果两个进程为了继续进行而需要相同的两个资源，而它们每人都拥有其中的一个资源，这时就会发生死锁。每个进程都将无限地等待自己没有的那个资源。

操作系统的目标和功能

它有三个目标：

• 方便：操作系统使计算机更易于使用。
• 有效：操作系统允许以更有效的方式使用计算机系统资源。
• 扩展能力：在构造操作系统时，应该允许在不妨碍服务的前提下有效地开发、测试和引进新的系统功能。

作为用户/计算机接口的操作系统

简单的说，操作系统通常提供了以下几个方面的服务：

• 程序开发：操作系统提供各种各样的工具和服务，如编辑器和调试器，用于帮助程序员开发程序。
• 程序运行：运行一个程序需要很多步骤，包括必须把指令和数据载入到内存、初始化I/O设备和文件、准备其他一些资源。操作系统为用户处理这些调度问题。
• I/O设备访问：每个I/O设备的操作都需要特有的指令集和控制信号，操作系统隐藏这些细节并提供了统一的接口，因此程序猿可以使用简单的读和写操作访问这些设备。
• 文件访问控制：对操作系统而言，关于文件的控制不仅必须详细了解I/O设备的特性，而且必须详细了解存储介质中文件数据的结构。
• 系统访问：对于共享或公共系统，操作系统控制对整个系统的访问以及对某个特殊系统资源的访问。
• 错误检测和响应：计算机系统运行时可能发生各种各样的错误，包括内部和外部硬件错误，如存储器错误、设备失效或故障，以及各种软件错误，如算术溢出、试图访问被禁止的存储器但愿、操作系统无法满足应用程序的请求等。
• 记账：一个好的操作系统可以收集对各种资源使用的统计信息，监控诸如响应时间之类的性能参数。

基本构成

计算机有4个主要的结构化部件：

• 处理器（processor）: 控制计算机的操作，执行数据处理能力。当只有一个处理器时，它通常指中央处理单元（CPU）。
• 内存（main memory）: 存储数据和程序。此类存储器通常是易失的，即当计算机关机时，存储器的内容会丢失。相反，当计算机关机时，磁盘存储器的内容不会丢失。内存通常也称为 实存储器（real memory） 或者主存储器（primary memory）。
• 输出/输出模块（I/O module）: 在计算机和外部环境之间移动数据。外部环境由各种外部设备组成，包括辅助存储器设备（如硬盘）、通信设备和终端。
• 系统总线（system bus）： 为处理器、内存和输入/输出模块间提供通讯的设施。

处理器寄存器

• 用户可见寄存器： 优先使用这些寄存器，可以减少使用机器语言或汇编语言的程序员对内存的访问次数。
• 控制和状态寄存器： 用以控制处理器的操作，且主要被具有特权的操作系统例程使用，以控制程序的执行。

用户可见寄存器

数据寄存器（data register）可以被程序员分配给各种函数。

地址寄存器（address register） 存放数据和指令的内存地址，或者存放用于计算完整地址或有效地址的部分地址。

• 变址寄存器（index register）： 变址地址是一种最常见的寻址方式，它通常给一个基值加一个索引来获得有效地址。
• 段指针（segment pointer）： 对于分段寻址方式，存储器被划分成段，这些段由长度不同的字块组成，段由若干长度的字组成。
• 栈指针（stack pointer）： 如果对用户可见的栈进行寻址，则应该有一个专门的寄存器指向栈顶。这样就可以使用不包含地址域的指令，如入栈（push）和出栈（pop）。