超市排队随想录

昨天阳光城一新超市开张，去超市晃了一圈，人山人海啊！突然感觉这抚州的消费能力不是一般的强。今天讨论一个问题：队列，资源竞争和锁。
“称重处”一定是最繁忙的，因为“资源独占”，如果写代码的时候这个地方是要加锁的，不然一定会出现多线程下的并发问题。所以我一直观察这“壮烈”的场景。很多人是没有排队的，直接拥堵在周围，这里我称之为“抢占式资源竞争”。计算机内部对于任务的调度并非采用这种方式，原因很简单，会导致用户响应不及时这样不太好的用户体验。简单的说一下为什么，以“称重处”这个场景为例，可能某个人抢了很久，但是他仍然没有抢到“秤”这样一个资源，所以他一直要等待，假设有另外一个人要等他称重完，那么对于等他的这个人而言体验是很不好的。即使从资源公平来讲也是不合理的。这里基本上谁更蛮横谁力气大则更有机会抢到“秤”。所以一定会出现“排队”的必要性。
排队的好处不言而喻，计算机里面所说的“FIFO（先进先出）”。这样尽量的保证了资源竞争的公平性。程序员也很多的会出现排队的场景。很多情况下会有“Queue(队列)”的应用。这里再说一下CPU的时间片分配。如果知道操作系统的都知道对于CPU而言是并非严格的按照排队的顺序进行处理。这里也是为了解决一个问题。比如说一个任务执行时间是半个小时，如果严格按照排队的方式则我运行下一个程序则需要在半个小时后（PS：另外还有一个原因，因为本身一个程序的运行并非都是CPU独占的，有可能等待IO，请求网络等其他资源）。对于多任务场景下肯定是不适合的。所以计算机会引入“时间片”的概念。这里其实最关键的是进行“任务切分”。这里再回到超市排队的这样一个场景。小A拿着10袋东西去称重，假设小A把所以东西称完作为一个任务（这里称之为任务A）。同样小B拿着5袋东西去称重（这里称之为任务B）。小A和小B组成一个多任务运行场景。由于称重处只有一处，也就是相当于一个“CPU”。这样的场景处理策略是什么。
第一种策略是小A和小B进行“抢占”。这样小A和小B完成的时间是不可控的。比如说称一袋商品的时间是20ms。在最优的情况下，小A完成的时间200ms。小B是100ms。当然最差的情况下小A是300ms。小B也是300ms。从算法的角度来讲可以说这个时间复杂度是不稳定的。下面的图是一个简化版，只要小A或者小B只要抢到秤就可以把所有的东西称完。

下面是任务A最优的情况

下面是任务B最优的情况




第二种策略就是简单的排队，比如说小A排前面，那么小A称完10袋商品花了200ms。那么再称小B的商品。这样称完小B是100ms，但是小B总的时间是多少？300ms(等待时间200ms)。其实就是上图中任务A最优的情况。
下面就把这个场景进行复杂化。这里增加一个打包处(打包处是可以并行的，小A和小B打包互不干扰)，每打包一份商品消耗20ms，这里假设小A在打包的同时是无法把商品放到称重处进行称重的（现实场景中人有两只手，本身会有一个并行的工作，所以即使任务内部也可以进行并行，这里为了把问题简化，就不做这种处理）。那么按照刚才排队的策略很显然，小A工作完是需要400ms。小B工作完是600ms。“称重处”总的算起来是工作了580ms。

这张图简单的描述了小A在称重和打包的同时间时间消耗，这里可以很清楚的看到称重处是有大量时间空闲的，B的工作队列就不在此画出来了。

上面那种策略有什么问题？就是在小A或者小B打包的同时称重处是空闲的，总的算起来其实空闲了280ms。这里小A打包的同时，称重处可以为小B进行称重，这样下来小A和小B工作完是400ms和220ms。但是最后称重处并非工作了580ms。而是380ms，节约了200ms的时间。当然这里跟CPU的时间片有关系吗？已经有些接近了。CPU为了简化一些处理，比如说CPU把时间切分成一个一个小片然后分配给任务。假设在这里一个时间片为20ms是最优的。当然CPU的工作远没有这么简单，由于任务切换也同样是需要时间的，这里所描述的场景并没有体现这样点。

下面这张图中很清楚的看到称重处消耗的时间是380ms。时间利用率有比较大的提升，小A任务完成总共是400ms。小B任务完成只需要220ms。

这里要讲的其实是生活各处都会有各种策略运用于计算机的设计中。有些人说艺术来源于生活，计算机也是如此。上次在某篇文章中谈到“图像记忆”。比如说我到过某个地方，其实在脑海里会有一个快照（snapshot），这样就记下来了。当然计算机怎么做这个事情，呵呵，就复杂了，目前来讲其实是记住“特征值”，简单点讲比如说这里有个星巴克，有多少楼，什么颜色，朝向等一些重要特征然后进行比对。当然人其实也是这样的。真正把所有的信息记下来是不可能的。