原文

原文出处

Introduction

Hi, I’m Glenn Fiedler and welcome to Networking for Game Programmers.

In this article we start with the most basic aspect of network programming: sending and receiving data over the network. This is perhaps the simplest and most basic part of what network programmers do, but still it is quite intricate and non-obvious as to what the best course of action is.

You have most likely heard of sockets, and are probably aware that there are two main types: TCP and UDP. When writing a network game, we first need to choose what type of socket to use. Do we use TCP sockets, UDP sockets or a mixture of both? Take care because if you get this wrong it will have terrible effects on your multiplayer game!

The choice you make depends entirely on what sort of game you want to network. So from this point on and for the rest of this article series, I assume you want to network an action game. You know, games like Halo, Battlefield 1942, Quake, Unreal, CounterStrike and Team Fortress.

In light of the fact that we want to network an action game, we’ll take a very close look at the properties of each protocol, and dig a bit into how the internet actually works. Once we have all this information, the correct choice is clear.

TCP/IP

TCP stands for “transmission control protocol”. IP stands for “internet protocol”. Together they form the backbone for almost everything you do online, from web browsing to IRC to email, it’s all built on top of TCP/IP.

If you have ever used a TCP socket, then you know it’s a reliable connection based protocol. This means you create a connection between two machines, then you exchange data much like you’re writing to a file on one side, and reading from a file on the other.

TCP connections are reliable and ordered. All data you send is guaranteed to arrive at the other side and in the order you wrote it. It’s also a stream protocol, so TCP automatically splits your data into packets and sends them over the network for you.

IP

The simplicity of TCP is in stark contrast to what actually goes on underneath TCP at the IP or “internet protocol” level.

Here there is no concept of connection, packets are simply passed from one computer to the next. You can visualize this process being somewhat like a hand-written note passed from one person to the next across a crowded room, eventually, reaching the person it’s addressed to, but only after passing through many hands.

There is also no guarantee that this note will actually reach the person it is intended for. The sender just passes the note along and hopes for the best, never knowing whether or not the note was received, unless the other person decides to write back!

Of course IP is in reality a little more complicated than this, since no one computer knows the exact sequence of computers to pass the packet along to so that it reaches its destination quickly. Sometimes IP passes along multiple copies of the same packet and these packets make their way to the destination via different paths, causing packets to arrive out of order and in duplicate.

This is because the internet is designed to be self-organizing and self-repairing, able to route around connectivity problems rather than relying on direct connections between computers. It’s actually quite cool if you think about what’s really going on at the low level. You can read all about this in the classic book TCP/IP Illustrated.

UDP

Instead of treating communications between computers like writing to files, what if we want to send and receive packets directly?

We can do this using UDP.

UDP stands for “user datagram protocol” and it’s another protocol built on top of IP, but unlike TCP, instead of adding lots of features and complexity, UDP is a very thin layer over IP.

With UDP we can send a packet to a destination IP address (eg. 112.140.20.10) and port (say 52423), and it gets passed from computer to computer until it arrives at the destination or is lost along the way.

On the receiver side, we just sit there listening on a specific port (eg. 52423) and when a packet arrives from any computer (remember there are no connections!), we get notified of the address and port of the computer that sent the packet, the size of the packet, and can read the packet data.

Like IP, UDP is an unreliable protocol. In practice however, most packets that are sent will get through, but you’ll usually have around 1-5% packet loss, and occasionally you’ll get periods where no packets get through at all (remember there are lots of computers between you and your destination where things can go wrong…)

There is also no guarantee of ordering of packets with UDP. You could send 5 packets in order 1,2,3,4,5 and they could arrive completely out of order like 3,1,2,5,4. In practice, packets tend to arrive in order most of the time, but you cannot rely on this!

UDP also provides a 16 bit checksum, which in theory is meant to protect you from receiving invalid or truncated data, but you can’t even trust this, since 16 bits is just not enough protection when you are sending UDP packets rapidly over a long period of time. Statistically, you can’t even rely on this checksum and must add your own.

So in short, when you use UDP you’re pretty much on your own!

TCP vs. UDP

We have a decision to make here, do we use TCP sockets or UDP sockets?

Lets look at the properties of each:

TCP:

• Connection based


• Guaranteed reliable and ordered


• Automatically breaks up your data into packets for you


• Makes sure it doesn’t send data too fast for the internet connection to handle (flow control)


• Easy to use, you just read and write data like its a file

UDP:

• No concept of connection, you have to code this yourself


• No guarantee of reliability or ordering of packets, they may arrive out of order, be duplicated, or not arrive at all!


• You have to manually break your data up into packets and send them


• You have to make sure you don’t send data too fast for your internet connection to handle


• If a packet is lost, you need to devise some way to detect this, and resend that data if necessary


• You can’t even rely on the UDP checksum so you must add your own

The decision seems pretty clear then, TCP does everything we want and its super easy to use, while UDP is a huge pain in the ass and we have to code everything ourselves from scratch.

So obviously we just use TCP right?

Wrong!

Using TCP is the worst possible mistake you can make when developing a multiplayer game! To understand why, you need to see what TCP is actually doing above IP to make everything look so simple.

How TCP really works

TCP and UDP are both built on top of IP, but they are radically different. UDP behaves very much like the IP protocol underneath it, while TCP abstracts everything so it looks like you are reading and writing to a file, hiding all complexities of packets and unreliability from you.

So how does it do this?

Firstly, TCP is a stream protocol, so you just write bytes to a stream, and TCP makes sure that they get across to the other side. Since IP is built on packets, and TCP is built on top of IP, TCP must therefore break your stream of data up into packets. So, some internal TCP code queues up the data you send, then when enough data is pending the queue, it sends a packet to the other machine.

This can be a problem for multiplayer games if you are sending very small packets. What can happen here is that TCP may decide it’s not going to send data until you have buffered up enough data to make a reasonably sized packet to send over the network.

This is a problem because you want your client player input to get to the server as quickly as possible, if it is delayed or “clumped up” like TCP can do with small packets, the client’s user experience of the multiplayer game will be very poor. Game network updates will arrive late and infrequently, instead of on-time and frequently like we want.

TCP has an option to fix this behavior called TCP_NODELAY. This option instructs TCP not to wait around until enough data is queued up, but to flush any data you write to it immediately. This is referred to as disabling Nagle’s algorithm.

Unfortunately, even if you set this option TCP still has serious problems for multiplayer games and it all stems from how TCP handles lost and out of order packets to present you with the “illusion” of a reliable, ordered stream of data.

How TCP implements reliability

Fundamentally TCP breaks down a stream of data into packets, sends these packets over unreliable IP, then takes the packets received on the other side and reconstructs the stream.

But what happens when a packet is lost?

What happens when packets arrive out of order or are duplicated?

Without going too much into the details of how TCP works because its super-complicated (please refer to TCP/IP Illustrated) in essence TCP sends out a packet, waits a while until it detects that packet was lost because it didn’t receive an ack (or acknowledgement), then resends the lost packet to the other machine. Duplicate packets are discarded on the receiver side, and out of order packets are resequenced so everything is reliable and in order.

The problem is that if we were to send our time critical game data over TCP, whenever a packet is dropped it has to stop and wait for that data to be resent. Yes, even if more recent data arrives, that new data gets put in a queue, and you cannot access it until that lost packet has been retransmitted. How long does it take to resend the packet?

Well, it’s going to take at least round trip latency for TCP to work out that data needs to be resent, but commonly it takes 2*RTT, and another one way trip from the sender to the receiver for the resent packet to get there. So if you have a 125ms ping, you’ll be waiting roughly 1/5th of a second for the packet data to be resent at best, and in worst case conditions you could be waiting up to half a second or more (consider what happens if the attempt to resend the packet fails to get through?). What happens if TCP decides the packet loss indicates network congestion and it backs off? Yes it actually does this. Fun times!

Never use TCP for time critical data

The problem with using TCP for realtime games like FPS is that unlike web browsers, or email or most other applications, these multiplayer games have a real time requirement on packet delivery.

What this means is that for many parts of a game, for example player input and character positions, it really doesn’t matter what happened a second ago, the game only cares about the most recent data.

TCP was simply not designed with this in mind.

Consider a very simple example of a multiplayer game, some sort of action game like a shooter. You want to network this in a very simple way. Every frame you send the input from the client to the server (eg. keypresses, mouse input controller input), and each frame the server processes the input from each player, updates the simulation, then sends the current position of game objects back to the client for rendering.

So in our simple multiplayer game, whenever a packet is lost, everything has to stop and wait for that packet to be resent. On the client game objects stop receiving updates so they appear to be standing still, and on the server input stops getting through from the client, so the players cannot move or shoot. When the resent packet finally arrives, you receive this stale, out of date information that you don’t even care about! Plus, there are packets backed up in queue waiting for the resend which arrive at same time, so you have to process all of these packets in one frame. Everything is clumped up!

Unfortunately, there is nothing you can do to fix this behavior, it’s just the fundamental nature of TCP. This is just what it takes to make the unreliable, packet-based internet look like a reliable-ordered stream.

Thing is we don’t want a reliable ordered stream.

We want our data to get as quickly as possible from client to server without having to wait for lost data to be resent.

This is why you should never use TCP when networking time-critical data!

Wait? Why can’t I use both UDP and TCP?

For realtime game data like player input and state, only the most recent data is relevant, but for other types of data, say perhaps a sequence of commands sent from one machine to another, reliability and ordering can be very important.

The temptation then is to use UDP for player input and state, and TCP for the reliable ordered data. If you’re sharp you’ve probably even worked out that you may have multiple “streams” of reliable ordered commands, maybe one about level loading, and another about AI. Perhaps you think to yourself, “Well, I’d really not want AI commands to stall out if a packet is lost containing a level loading command - they are completely unrelated!”. You are right, so you may be tempted to create one TCP socket for each stream of commands.

On the surface, this seems like a great idea. The problem is that since TCP and UDP are both built on top of IP, the underlying packets sent by each protocol will affect each other. Exactly how they affect each other is quite complicated and relates to how TCP performs reliability and flow control, but fundamentally you should remember that TCP tends to induce packet loss in UDP packets. For more information, read this paper on the subject.

Also, it’s pretty complicated to mix UDP and TCP. If you mix UDP and TCP you lose a certain amount of control. Maybe you can implement reliability in a more efficient way that TCP does, better suited to your needs? Even if you need reliable-ordered data, it’s possible, provided that data is small relative to the available bandwidth to get that data across faster and more reliably that it would if you sent it over TCP. Plus, if you have to do NAT to enable home internet connections to talk to each other, having to do this NAT once for UDP and once for TCP (not even sure if this is possible…) is kind of painful.

Conclusion

My recommendation is not only that you use UDP, but that you only use UDP for your game protocol. Don’t mix TCP and UDP! Instead, learn how to implement the specific features of TCP that you need inside your own custom UDP based protocol.

Of course, it is no problem to use HTTP to talk to some RESTful services while your game is running. I’m not saying you can’t do that. A few TCP connections running while your game is running isn’t going to bring everything down. The point is, don’t split your game protocol across UDP and TCP. Keep your game protocol running over UDP so you are fully in control of the data you send and receive and how reliability, ordering and congestion avoidance are implemented.

The rest of this article series show you how to do this, from creating your own virtual connection on top of UDP, to creating your own reliability, flow control and congestion avoidance.

译文

译文出处

项目越来越大，每次需要重新编译整个项目都是一件很浪费时间的事情。Research了一下，找到以下可以帮助提高速度的方法，总结一下。

tmpfs

有人说在Windows下用了RAMDisk把一个项目编译时间从4.

5小时减少到了5分钟，也许这个数字是有点夸张了，不过粗想想，把文件放到内存上做编译应该是比在磁盘

上快多了吧，尤其如果编译器需要生成很多临时文件的话。

这个做法的实现成本最低，在Linux中，直接mount一个tmpfs就可以了。而且对所编译的工程没有任何要求，也不用改动编译环境。

mount -t tmpfs tmpfs ~/build -o size=1G

用2.6.32.2的Linux Kernel来测试一下编译速度：

• 用物理磁盘：40分16秒

• 用tmpfs：39分56秒

呃……没什么变化。看来编译慢很大程度上瓶颈并不在IO上面。但对于一个实际项目来说，

编译过程中可能还会有打包等IO密集的操作，所以只要可能，用tmpfs是有

益无害的。

当然对于大项目来说，你需要有足够的内存才能负担得起这个tmpfs的开销。

make -j

既然IO不是瓶颈，那CPU就应该是一个影响编译速度的重要因素了。

用make -j带一个参数，可以把项目在进行并行编译，比如在一台双核的机器上，完全可以用make -
j4，让make最多允许4个编译命令同时执行，这样可以更有效的利用CPU资源。

还是用Kernel来测试：

• 用make： 40分16秒

• 用make -j4：23分16秒

• 用make -j8：22分59秒

由此看来，在多核CPU上，适当的进行并行编译还是可以明显提高编译速度的。但并行的任务不宜太多，一般是以CPU的核心数目的两倍为宜。

不过这个方案不是完全没有cost的，如果项目的Makefile不规范，没有正确的设置好依赖关系，并行编译的结果就是编译不能正常进行。如果依赖关系设置过于保守
，则可能本身编译的可并行度就下降了，也不能取得最佳的效果。

ccache

ccache用于把编译的中间结果进行缓存，以便在再次编译的时候可以节省时间。这对于玩Kernel来说实在是再好不过了，因为经常需要修改一些Kernel的代码，然后
再重新编译，而这两次编译大部分东西可能都没有发生变化。对于平时开发项目来说，也是一样。为什么不是直接用make所支持的增量编译呢？还是因为现实中，因
为Makefile的不规范，很可能这种“聪明”的方案根本不能正常工作，只有每次make clean再make才行。

安装完ccache后，可以在/usr/local/bin下建立gcc，g++，c++，cc的symbolic
link，链到/usr/bin/ccache上。总之确认系统在调用gcc等命令时会调用到ccache就可以了（通常情况下/usr/local/bin会在PATH中排在/usr/bin前面）。

继续测试：

• 用ccache的第一次编译(make -j4)：23分38秒

• 用ccache的第二次编译(make -j4)：8分48秒

• 用ccache的第三次编译(修改若干配置，make -j4)：23分48秒

看来修改配置（我改了CPU类型…）对ccache的影响是很大的，因为基本头文件发生变化后，就导致所有缓存数据都无效了，必须重头来做。但如果只是修改一些.
c文件的代码，ccache的效果还是相当明显的。而且使用ccache对项目没有特别的依赖，布署成本很低，这在日常工作中很实用。

可以用ccache -s来查看cache的使用和命中情况：

cache directory /home/lifanxi/.ccache

cache hit 7165

cache miss 14283

called for link 71

not a C/C++ file 120

no input file 3045

files in cache 28566

cache size 81.7 Mbytes

max cache size 976.6 Mbytes

可以看到，显然只有第二编次译时cache命中了，cache miss是第一次和第三次编译带来的。两次cache占用了81.7M的磁盘，还是完全可以接受的。

distcc

一台机器的能力有限，可以联合多台电脑一起来编译。这在公司的日常开发中也是可行的，因为可能每个开发人员都有自己的开发编译环境，它们的编译器版本一般
是一致的，公司的网络也通常具有较好的性能。这时就是distcc大显身手的时候了。

使用distcc，并不像想象中那样要求每台电脑都具有完全一致的环境，它只要求源代码可以用make -j并行编译，并且参与分布式编译的电脑系统中具有相同的编译
器。因为它的原理只是把预处理好的源文件分发到多台计算机上，预处理、编译后的目标文件的链接和其它除编译以外的工作仍然是在发起编译的主控电脑上完成，
所以只要求发起编译的那台机器具备一套完整的编译环境就可以了。

distcc安装后，可以启动一下它的服务：

/usr/bin/distccd –daemon –allow 10.64.0.0/16

默认的3632端口允许来自同一个网络的distcc连接。

然后设置一下DISTCC_HOSTS环境变量，设置可以参与编译的机器列表。

通常localhost也参与编译，但如果可以参与编译的机器很多，则可以把localhost从这个列表

中去掉，这样本机就完全只是进行预处理、分发和链接了，编译都在别的机器上完成。

因为机器很多时，localhost的处理负担很重，所以它就不再“兼职”编译了。

export DISTCC_HOSTS="localhost 10.64.25.1 10.64.25.2 10.64.25.3"

然后与ccache类似把g++，gcc等常用的命令链接到/usr/bin/distcc上就可以了。

在make的时候，也必须用-j参数，一般是参数可以用所有参用编译的计算机CPU内核总数的两倍做为并行的任务数。

同样测试一下：

• 一台双核计算机，make -j4：23分16秒

• 两台双核计算机，make -j4：16分40秒

• 两台双核计算机，make -j8：15分49秒

跟最开始用一台双核时的23分钟相比，还是快了不少的。如果有更多的计算机加入，也可以得到更好的效果。

在编译过程中可以用distccmon-text来查看编译任务的分配情况。distcc也可以与ccache同时使用，通过设置一个环境变量就可以做到，非常方便。

总结

• tmpfs： 解决IO瓶颈，充分利用本机内存资源

• make -j： 充分利用本机计算资源

• distcc： 利用多台计算机资源

• ccache： 减少重复编译相同代码的时间

这些工具的好处都在于布署的成本相对较低，综合利用这些工具，就可以轻轻松松的节省相当可观的时间。

上面介绍的都是这些工具最基本的用法，更多的用法可以参考它们各自的man page。

A fish flock AI Plugin for Unreal Engine 4
一个基于虚幻4的鱼群 AI 插件

this Plugin version can Run 2000+ fishes at the same time
这个插件版本可以同时运行 2000+ 条鱼儿

源码已放到fish

Video Preview 视频演示

Download

MyFish.exe (Win64)

. . .

在数据的加解密领域，算法分为对称密钥与非对称密钥两种。

对称密钥与非对称密钥由于各自的特点，所应用的领域是不尽相同的。

对称密钥加密算法由于其速度快，一般用于整体数据的加密，而非对称密钥加密算法的安全性能佳，在数字签名领域得到广泛的应用。

微型加密算法（TEA）及其相关变种（XTEA，Block TEA，XXTEA） 都是分组加密算法，它们很容易被描述，实现也很简单（典型的几行代码）。

TEA是Tiny Encryption Algorithm的缩写，以加密解密速度快，实现简单著称。

TEA 算法最初是由剑桥计算机实验室的 David Wheeler 和 Roger Needham 在 1994 年设计的。

该算法使用 128 位的密钥为 64 位的信息块进行加密，它需要进行 64 轮迭代，尽管作者认为 32 轮已经足够了。

该算法使用了一个神秘常数δ作为倍数，它来源于黄金比率，以保证每一轮加密都不相同。

但δ的精确值似乎并不重要，这里 TEA 把它定义为 δ=「(√5 - 1)231」（也就是程序中的 0×9E3779B9）。

之后 TEA 算法被发现存在缺陷，作为回应，设计者提出了一个 TEA 的升级版本——XTEA（有时也被称为“tean”）。

XTEA 跟 TEA 使用了相同的简单运算，但它采用了截然不同的顺序，为了阻止密钥表攻击，四个子密钥（在加密过程中，原 128 位的密钥被拆分为 4 个 32 位的子密钥）采用了一种不太正规的方式进行混合，但速度更慢了。

在跟描述 XTEA 算法的同一份报告中，还介绍了另外一种被称为 Block TEA 算法的变种，它可以对 32 位大小任意倍数的变量块进行操作。

该算法将 XTEA 轮循函数依次应用于块中的每个字，并且将它附加于它的邻字。

该操作重复多少轮依赖于块的大小，但至少需要 6 轮。

该方法的优势在于它无需操作模式（CBC，OFB，CFB 等），密钥可直接用于信息。

对于长的信息它可能比 XTEA 更有效率。

在 1998 年，Markku-Juhani Saarinen 给出了一个可有效攻击 Block TEA 算法的代码，但之后很快 David J. Wheeler 和 Roger M. Needham 就给出了 Block TEA 算法的修订版，这个算法被称为 XXTEA。

XXTEA 使用跟 Block TEA 相似的结构，但在处理块中每个字时利用了相邻字。

它利用一个更复杂的 MX 函数代替了 XTEA 轮循函数，MX 使用 2 个输入量。

XXTEA 算法很安全，而且非常快速，非常适合应用于 Web 开发中。

TEA算法是由剑桥大学计算机实验室的David Wheeler和Roger Needham于1994年发明，

TEA是Tiny Encryption Algorithm的缩写，以加密解密速度快，实现简单著称。

TEA算法每一次可以操作64bit(8byte)，采用128bit(16byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。

为解决TEA算法密钥表攻击的问题，TEA算法先后经历了几次改进，从XTEA到BLOCK TEA，直至最新的XXTEA。

XTEA也称做TEAN，它使用与TEA相同的简单运算，但四个子密钥采取不正规的方式进行混合以阻止密钥表攻击。

Block TEA算法可以对32位的任意整数倍长度的变量块进行加解密的操作，该算法将XTEA轮循函数依次应用于块中的每个字，并且将它附加于被应用字的邻字。

XXTEA使用跟Block TEA相似的结构，但在处理块中每个字时利用了相邻字，且用拥有两个输入量的MX函数代替了XTEA轮循函数。

import struct  
  
_DELTA = 0x9E3779B9  
  
def _long2str(v, w):  
    n = (len(v) - 1) << 2  
    if w:  
        m = v[-1]  
        if (m < n - 3) or (m > n): return ''  
        n = m  
    s = struct.pack('<%iL' % len(v), *v)  
    return s[0:n] if w else s  
  
def _str2long(s, w):  
    n = len(s)  
    m = (4 - (n & 3) & 3) + n  
    s = s.ljust(m, "\0")  
    v = list(struct.unpack('<%iL' % (m >> 2), s))  
    if w: v.append(n)  
    return v  
  
def encrypt(str, key):  
    if str == '': return str  
    v = _str2long(str, True)  
    k = _str2long(key.ljust(16, "\0"), False)  
    n = len(v) - 1  
    z = v[n]  
    y = v[0]  
    sum = 0  
    q = 6 + 52 // (n + 1)  
    while q > 0:  
        sum = (sum + _DELTA) & 0xffffffff  
        e = sum >> 2 & 3  
        for p in xrange(n):  
            y = v[p + 1]  
            v[p] = (v[p] + ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))) & 0xffffffff  
            z = v[p]  
        y = v[0]  
        v[n] = (v[n] + ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[n & 3 ^ e] ^ z))) & 0xffffffff  
        z = v[n]  
        q -= 1  
    return _long2str(v, False)  
  
def decrypt(str, key):  
    if str == '': return str  
    v = _str2long(str, False)  
    k = _str2long(key.ljust(16, "\0"), False)  
    n = len(v) - 1  
    z = v[n]  
    y = v[0]  
    q = 6 + 52 // (n + 1)  
    sum = (q * _DELTA) & 0xffffffff  
    while (sum != 0):  
        e = sum >> 2 & 3  
        for p in xrange(n, 0, -1):  
            z = v[p - 1]  
            v[p] = (v[p] - ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))) & 0xffffffff  
            y = v[p]  
        z = v[n]  
        v[0] = (v[0] - ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[0 & 3 ^ e] ^ z))) & 0xffffffff  
        y = v[0]  
        sum = (sum - _DELTA) & 0xffffffff  
    return _long2str(v, True)  
  
if __name__ == "__main__":  
    print decrypt(encrypt('Hello XXTEA!', '16bytelongstring'), '16bytelongstring')

问题:

在内存管理中，“内零头”和“外零头”个指的是什么？在固定式分区分配、可变式分区分配、页式虚拟存储系统、段式虚拟存储系统中，各会存在何种零头？为什么？

解答：

在存储管理中，

内零头是指分配给作业的存储空间中未被利用的部分，

外零头是指系统中无法利用的小存储块。

• 1. 在固定式分区分配中，为将一个用户作业装入内存，内存分配程序从系统分区表中找出一个能满足作业要求的空闲分区分配给作业，由于一个作业的大小并不一定与分区大小相等，因此，分区中有一部分存储空间浪费掉了。

由此可知，固定式分区分配中存在内零头。

• 1. 在可变式分区分配中，为把一个作业装入内存，应按照一定的分配算法从系统中找出一个能满足作业需求的空闲分区分配给作业，如果这个空闲分区的容量比作业申 请的空间容量要大，则将该分区一分为二，一部分分配给作业，剩下的部分仍然留作系统的空闲分区。

由此可知，可变式分区分配中存在外零头。

• 1. 在页式虚拟存储系统中，用户作业的地址空间被划分成若干大小相等的页面，存储空间也分成也页大小相等的物理块，但一般情况下，作业的大小不可能都是物理块大小的整数倍，因此作业的最后一页中仍有部分空间被浪费掉了。

由此可知，页式虚拟存储系统中存在内零头。

• 1. 在段式虚拟存储系统中，作业的地址空间由若干个逻辑分段组成，每段分配一个连续的内存区，但各段之间不要求连续，其内存的分配方式类似于动态分区分配。

由此可知，段式虚拟存储系统中存在外零头。

详细解释

操作系统在分配内存时，有时候会产生一些空闲但是无法被正常使用的内存区域，这些就是内存碎片，或者称为内存零头，这些内存零头一共分为两类：内零头和外零头。

• 内零头是指进程在向操作系统请求内存分配时，系统满足了进程所需要的内存需求后，还额外还多分了一些内存给该进程，也就是说额外多出来的这部分内存归该进程所有，其他进程是无法访问的。

• 外零头是指内存中存在着一些空闲的内存区域，这些内存区域虽然不归任何进程所有，但是因为内存区域太小，无法满足其他进程所申请的内存大小而形成的内存零头。

页式存储管理的情况

页式存储管理是以页为单位（页面的大小由系统确定，且大小是固定的）向进程分配内存的，

例如：假设内存总共有100K,分为10页，每页大小为10K。
现在进程A提出申请56K内存，因为页式存储管理是以页为单位进程内存分配的，所以系统会向进程A提供6个页面，也就是60K的内存空间，那么在最后一页中进程只使用了6K，从而多出了4K的内存碎片，但是这4K的内存碎片系统已经分配给进程A了，其他进程是无法再访问这些内存区域的，

这种内存碎片就是内零头。

段式存储管理的情况

段式存储管理是段（段的大小是程序逻辑确定，且大小不是固定的）为单位向进程进行内存分配的，进程申请多少内存，系统就给进程分配多少内存，这样就不会产生内零头，但是段式分配会产生外零头。

例如：假设内存总的大小为100K，现在进程A向系统申请60K的内存，系统在满足了进程A的内存申请要求后，还剩下40K的空闲内存区域；这时如果进程B向系统申请50K的内存区域，而系统只剩下了40K的内存区域，虽然这40K的内存区域不归任何进程所有，但是因为大小无法满足进程B的要求，所以也无法分配给进程B，这样就产生了外零头。

请求段式存储管理是在段式存储管理的基础上增加了请求调段功能和段置换功能。
所以段式和请求段式存储管理会产生外零头

练习题

下面的内存管理模式中，会产生外零头的是(正确答案B, D)

A、页式
B、段式
C、请求页式
D、请求段式

PHP 将所有以 （两个下划线）开头的类方法保留为魔术方法。所以在定义类方法时，除了上述魔术方法，建议不要以 为前缀。

. . .

介绍

命令行接口是普遍,基础的人机交互接口，从命令行提取程序的运行时选项的方法有很多。

你可以自己编写相对应的完整的解析函数，或许你有丰富的C语言编程经验，熟知getopt()函数的用法，又或许使用Python的你已经在使用optparse库来简化这一工作。

大家在平时不断地谈及到“不要重复造轮子”，那就需要掌握一些顺手的库，这里介绍一种C++方式来解析命令行选项的方法，就是使用Boost.Program_options库。

program_options提供程序员一种方便的命令行和配置文件进行程序选项设置的方法。

使用program_options库而不是你自己动手写相关的解析代码，因为它更简单，声明程序选项的语法简洁，并且库自身也非常小。

将选项值转换为适合的类型值的工作也都能自动完成。

库有着完备的错误检查机制，如果自己手写解析代码时，就可能会错过对一些出错情况的检查了。

最后，选项值不仅能从命令行获取，也能从配置文件，甚至于环境变量中提取，而这些选择不会增加明显的工作量。

示例说明

以下面简单的hello程序进行说明，默认打印hello world,如果传入-p选项，就会打印出人的姓名，另外通过传入-h选项，可以打印出帮助选项。

略微看一眼代码文件和相应的屏幕输入输出，然后我们再一起来看看这些是如何发生的。

//hello.cpp 
#include <iostream>
#include <string>
#include <boost/program_options.hpp>

using namespace std;
int main(int argc, char* argv[])
{
    using namespace boost::program_options;
    //声明需要的选项
    options_description desc("Allowed options");
    desc.add_options()
        ("help,h", "produce help message")
        ("person,p", value<string>()->default_value("world"), "who")
        ;

    variables_map vm;        
    store(parse_command_line(argc, argv, desc), vm);
    notify(vm);    

    if (vm.count("help")) {
        cout << desc;
        return 0;
    }
    cout << "Hello " << vm["person"].as<string>() << endl;
    return 0;
}

下面是在Windows命令提示符窗口上的输入输出结果，其中”>”表示提示符。

>hello 
Hello world

>hello -h
Allowed options:
  -h [ --help ]                produce help message
  -p [ --person ] arg (=world) who

>hello --person len
Hello len

首先通过options_description类声明了需要的选项，add_options返回了定义了operator()的特殊的代理对象。

这个调用看起来有点奇怪，其参数依次为选项名，选项值，以及选项的描述。

注意到示例中的选项名为”help,h”，是因为声明了具有短选项名和长选项名的选项，这跟gnu程序的命令行具有一致性。

当然你可以省略短选项名，但是这样就不能用命令选项简写了。

第二个选项的声明，定义了选项值为string类型，其默认值为world.

接下来,声明了variables_map类的对象，它主要用来存储选项值，并且能储存任意类型的值。

然后，store,parse_command_line和notify函数使vm能存储在命令行中发现的选项。

最后我们就自由地使用这些选项了，variables_map类的使用就像使用std::map一样，除了它必须用as方法去获取值。

如果as方法调用的指定类型与实际存储的类型不同，就会有异常抛出。

具有编程的你可能有这样的经验，使用cl或gcc对源文件进行编译时，可直接将源文件名放置在命令行中，而无需什么选项字母，如gcc a.c之类的。

prgram_options也能处理这种情况，在库中被称为”positional options”(位置选项),但这需要程序员的一点儿帮助才能完成。

看下面的经过对应修改的代码，我们无需传入”-p”选项，就能可指定”person”选项值

positional_options_description p;
p.add("person", -1);
store(command_line_parser(argc, argv).options(desc).positional(p).run(), vm);

>hello len
Hello len

前面新增的两行是为了说明所有的位置选项都应被解释成”person”选项，这里还采用了command_line_parser类来解析命令行，而不是用parse_command_line函数。

后者只是对前者类的简单封装，但是现在我们需要传入一些额外的信息，所以要使用类本身。

选项复合来源
一般来说，在命令行上指定所有选项，对用户来说是非常烦人的。

如果有些选项要应用于每次运行，那该怎么办呢。

我们当然希望能创建出带有些常用设置的选项文件，跟命令行一起应用于程序中。

当然这一切需要将命令行与配置文件中的值结合起来。

比如，在命令行中指定的某些选项值应该能覆盖配置文件中的对应值，或者将这些值组合起来。

下面的代码段将选项通过文件读取，这文件是文本格式，可用”#”表示注释，格式如命令行中的参数一样，选项=值

ifstream ifs("config.cfg");
store(parse_config_file(ifs,config),vm);
notify(vm);

参考

Boost.prgram_options库文档

• 这本书不能一次性所有都想看完。

  要有目的性的看，因为这本书类似于百科全书所有都讲， 不分轻重， 如果都看，硬啃，只会迷失了自己，反而不知道看了什么

• 这本书不能单独看。

  这本书必须配合TCP/IP详解和UNIX环境高级编程（简称APUE）以及The Linux Programming Interface（不知道这本书的译名是什么， 简称TLPI）来看

• 个人看的是卷一第三版，因当前工作经验范围和阅历受限，对于IT码农，IPv6的和SCTP的章节暂且略过，所以目前大概划出的必看章节（其他可挑选）是

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 11
  • 13
  • 16
  • 22
  • 26
  • 30

. . .