0%

0x00 Problem

Problem link

Description

Given \(n\) non-negative integers \(a_1, a_2, ..., a_n\) , where each represents a point at coordinate \((i, a_i)\). \(n\) vertical lines are drawn such that the two endpoints of the line \(i\) is at \((i, a_i)\) and \((i, 0)\). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant(倾斜) the container.

1
2
3
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

0x01 Answer

本题标准解法为双指针法,时间复杂度为\(O(n)\)

Solution

设置两个指针ij,分别指向输入数组的头部和尾部。即i=0,j=len(arr)-1

进行循环,每次循环过程将i往右移动或者将j往左移动,一轮循环只移动一个指针。当指针i与指针j相遇时,终止循环。

每次循环时计算当前指针指向位置所能容纳的最大水量,并保存该最大水量值。

移动i或者移动j由arr[i]arr[j]的大小决定。若arr[i] < arr[j],则将i向右移动,反之,则将j向左移动。i只会由左向右移动,j只会由右向左移动。表现上即ij都在互相靠近,直到相遇。每次循环移动的指针为指向的值较小的指针。

Correctness

该解法的正确性的定性论证如下。假设指针i对应的数组值为\(f(i)\)

设对\(i,j\)\(S(i,j)\)表示此时存储的水量。根据短板效应,此时的水量为\(S(i,j)=min(f(i),f(j)) * (j - i)\)

假设 \(f(i) < f(j)\)

  1. 若移动\(i\),则新的蓄水量\(S_1 = S(i+1,j) = min (f(i+1),f(j)) * (j-i-1)\)

    • \(f(i+1) > f(j)\),宽度减少,高度增加到\(f(j)\),则有 \(S_1 > S(i,j)\)\(S_1 <= S(i,j)\)
    • \(f(i+1) <= f(j)\),宽度减少,高度依然有可能增加(\(f(i+1)>f(i)\)的情况),有 \(S_1 < S(i,j)\)\(S_1 <= S(i,j)\)

    • 即移动\(i\)后,新的蓄水量可能变大或者变小。
  2. 若移动\(j\),则新的蓄水量\(S_2 = S(i,j - 1) = min (f(i),f(j - 1)) * (j-i-1)\)
    • \(f(i) > f(j - 1)\),宽度减少,高度也减少。则有\(S_2 <= S(i,j)\)
    • \(f(i) <= f(j - 1)\),宽度减少,高度不变(根据短板效应,高度为\(f(i)\)) 则有 \(S_2 < S(i,j)\)
    • 无论如何,移动\(j\)后,新的蓄水量一定变小。

故我们只移动ij中指向的值较小的那个。

设置和指令

设置 go module 的启用与不启用。

1
go env -w GO111MODULE=on

Shebang

SheBang - Wikipedia

在计算领域中,Shebang(也称为Hashbang)是一个由井号和叹号构成的字符序列#!,其出现在文本文件的第一行的前两个字符。 在文件中存在Shebang的情况下,类Unix操作系统的程序加载器会分析Shebang后的内容,将这些内容作为解释器指令,并调用该指令,并将载有Shebang的文件路径作为该解释器的参数。

/bin/sh 和 /usr/bin/env sh

/bin/bash到指定目录中去找sh

/usr/bin/env shenv | grep PATH 中寻找sh。因此它的可移植性更好。

查看shell

  • 当前shell
    • echo $SHELL
  • 所有shell
    • cat /etc/shells

zip版本的Visual Studio Code需要手动进行升级。

升级步骤

  1. 根据升级提示,下载压缩包。例如VSCode-win32-x64-1.58.2.zip

  2. 解压安装包,找到原快捷方式指向位置,进行替换。

  3. 修改快捷方式指向位置为新解压的软件包的code.exe的位置。

Macro

Recording a macro

Each register of macro is identified by a letter from z to a.

To enter a macro, type:

1
q<letter><commands>q

To execute the macro <number> times (once by default), type:

1
<number>@<letter>

Vim 锁定屏幕和解锁

使用ctrl-S锁定vim,使用ctrl-Q解锁。

使用ssh key 连接到GitHub仓库

  1. 创建密钥

    1
    ssh-keygen -t rsa # 可以将ssh密钥对文件取名为GitHub

  2. ~/.ssh/config中配置

    1
    vim ~/.ssh/config

    配置如下:

    1
    2
    3
    4
    5
    6
    host github.com
    HostName github.com
    IdentityFile /root/.ssh/github
    User git
    IdentitiesOnly yes
    port 22

启用IdentitiesOnly yes 设置项,ssh不会尝试所有的key。只会尝试指定 IdentifyFile所指定的key

  1. 在Github账户中添加账号

    新增 SSH 密钥到 GitHub 帐户

  2. 测试链接

    测试 SSH 连接

    如果测试有问题,可以添加-v选项来对ssh进行debug

注意:将仓库地址指定为[email protected]开头的地址,ssh在连接仓库时才会使用密钥进行连接。

Git Author相关

切换 Git Author

Git共有三个级别的config文件,分别是systemgloballocal。其中,local对应某个具体的仓库。默认执行使用顺序为 local > global > system

设置repo级别(local)的Author

1
2
git config --local user.name yidaoxiangan
git config --local user.email [email protected]

设置global级别的Author

1
2
git config --global user.name yidaoxiangan
git config --global user.email [email protected]

查看当前仓库的Author

1
2
git config user.name
git config user.email

在zsh的git插件中,使用 gcf 代替 (git config --list) 来查看当前配置。

Git 分支操作

从某一分支新建分支并切换到该新分支上

1
git checkout -b iss53

相当于

1
2
git branch iss53
git checkout iss53

source here

现在我成功的将手机上的APP数量降到了27个,其中包含了原生APP。这些APP有3个在dock栏中,另外24个则刚好占满iPhone 8 plus 的一页。

我想谈谈我在这个过程中遇到的一些困难和思路,也许能够给和我有着相同目标的极简主义者一些启发。

无疑的,我曾经是一个重度的移动互联网用户。如果按照十年前的标准,我想,现在绝大多数人都可以被称作是重度的移动互联网用户。我的手机也曾被各式各样的APP占满。在最开始接触到极简主义的思想时,我曾统计过我的APP总数,那时我手机中有150个APP。而如今,在接触极简主义的一年多后,我成功将这个数字降低到了27。除去Apple的原生app外,在手机上,我总共使用了其他互联网服务商的总计8个APP。

在最初接触极简主义之后,我首先将这个数量降低到了60多。这一步非常的容易,因为我很轻松的就找到了那些我三个月以上未曾打开的APP,并且将他们全部删掉。但在这之后的APP,才是极简路上的真正的大难题。

在逐渐极简掉剩下的APP的过程中,我的许多思维发生了很大的改变。

审视互联网服务商的开放性

自人类进入移动互联网时代以来,总体来说,互联网走向更加狭隘,封闭的地步。作为用户的我们似乎总是认为所有服务都应该有它自己的APP,而我们却忘记了互联网本质上是基于PC和Web服务这两个事实。但是实际上,所有你可以用手机做的事情,你都可以用PC更快更好的完成。基于互联网开放和自由的原则,我仔细审视了那些故意封闭自己服务圈的互联网服务,在这里我给出几个例子。

我不会使用知乎APP,知乎作为一个问答社区的所有功能和内容本可以在移动端的Web页面完成,但是它为了所谓的日活,KPI以及广告投放数据,在移动端的Web页面强制引导你下载它的APP。在APP中,如果你不登陆你就没法浏览它的内容。我是一个不在知乎上做内容产出和社交互动的用户,但即使如此我也必须登录才能使用。除此之外,你不得不忍受骚扰推送,不得不忍受夹杂在答案中的广告,不得不忍受那些把圈钱写在脸上的二级页面甚至是一级页面。但是我无法完全放弃知乎,因为它现在依然是中文互联网最优质的内容社区。因此,我转向于Web端的知乎。在浏览器上,我可以管控属于我自己的Web页面。我可以用基于JS的插件直接屏蔽掉它的广告,我可以随意的使用URL分享内容,我可以找到/explore这个未被服务商意识到的免登录使用的页面,或是直接使用插件屏蔽登录检测。在浏览器上,用户要自由得许多,而这些我在APP上被服务商故意限制和禁止的行为,本就是互联网赋予我们的基本的权利。

不使用APP的另一个好处是,它限制了我无时无刻沉迷在知乎的社区内容中。我不再会向从前一样从早到晚的被信息流干扰,只有在坐在PC前学习或工作时,我才会搜索我所需要的信息。如果不得已需要用手机使用知乎时,可以暂时的请求PC端的/explore的页面来查找信息。

我也不会使用支付宝APP和淘宝APP。作为一个互联网自由和开放的忠实拥趸,我旗帜鲜明的反对移动支付。因为无法接受我的交易情况可以被除了商家和我之外的另一个人知晓,也无法接受我的余额可以被其他人监管和冻结(你的现金无法被冻结,而银行卡被冻结的难度要比支付宝高上许多)。现金交易的匿名性无法被取代,在现实中可以使用现金的场景我绝不会使用移动支付。我曾经也使用支付宝购买基金,或是使用花呗分期付款,但现在我一律不用它额外的金融服务。我只用它来转账和在淘宝购物。

因此,我的一个原则就是:能够通过浏览器使用的服务,就不要通过APP来使用。基于这个原则,我卸载了很多的APP:知乎,淘宝,支付宝,豆瓣,百度网盘,百度等等

重新思考智能手机这件工具的用途

智能手机变得越来越强大,在很多事情上,智能手机表现得和PC端一样出色。比如说收发邮件,使用IM软件即时通讯,购物,刷微博等等。但是,智能手机破坏了不同事务之间的边界。工作,学习,娱乐之间不再泾渭分明。在十五年前,我们只能在电脑上使用QQ,如果要和人交流,我们必须打开电脑登录QQ。但是现在,我们每时每刻都登陆着QQ和微信,每天的上线时间是24个小时。智能手机消除了这种中断感----人们可以永远都在线,而不是像从前一样在特定的时间上线,在特定的时间下线。

这是我拒绝使用智能手机做太多事情的另一个原因,因为它实在是太强大了,随时随地都可以完成任务,比起PC来也毫不逊色。但是我的时间不再是整块的了。上一分钟可以在收发邮件,下一分钟就刷起了朋友圈。这种对于边界的消融让我感到害怕,因此我极简掉了许多的工具型的APP。我强迫自己使用专门的工具来做这些事情,给自己留出专注做事的时间。

比如说我卸载了GuitarTuna,转而使用实体的节拍器和调音器来练习乐器;我卸载了OneDrive,这样我只能在PC上进行学习(我的学习材料都在这里面);我也卸载掉了Documents和PDF experts,以及Microsoft的御三家,因为我不想在手机上查看,编辑,管理文件。卸载掉许多的APP,让我在时间上重新找回了边界感。简而言之,我不希望用智能手机做太多的事,哪怕它能做,而且也做得很好。如果能用一件工具完成某件事情,那我就不会保留多件相同用途的不同工具。

关于音乐

音乐是我生活中很重要的一部分,对大多数年轻的中国人来说,手机里必然会有一款音乐软件,甚至更多。我从15年开始使用网易云音乐,辅助使用QQ音乐,虾米音乐等其他软件。直到19年放弃它。最初我无比喜欢网易云的音乐+评论社区的设计,那会儿它也没有什么广告,我在上面建立了我整套的个人听歌体系。但后来,我发现它的曲库越来越少,越来越多的歌慢慢的灰了下去。有的时候甚至不给你提示,某首歌直接消失在你的歌单之中,直到你意识到你很久没有听到某一首歌了。软件里的广告和视频流多了起来,音乐页面被弱化成次要页面。更为过分的是,对于网易云没有的音乐,它会扫描识别出你手机中的对应的音乐,并且将它删掉,哪怕你是从其他的地方下载了这些音乐的文件。随后,网易云在某些歌上加入了经过aes加密的ncm格式,在从网易云下载音乐源文件时增加了一道不低的门槛。而我最终放弃网易云的导火索事件发生在19年的暑假,那会儿我在美国,惊诧的发现,由于地区版权保护,网易云中几乎所有的歌都变成了灰色。

在那之后,我仔细思考了音乐流媒体服务对于用户的意义。从前的我是一个自诩保护版权的人,我同时拥有三个音乐软件的年度会员(网易云,QQ,虾米)。但随后我发现,作为支持正版的付费用户的我得到的听歌体验甚至不如十几年前的盗版用户,没有会员,不再给资本家交钱的我甚至失去了听歌权。

我一直相信,互联网应该是自由的。互联网给了我不付钱自由听歌的权利。但是资本用所谓的版权意识教化人们放弃这种基本的权利。了解到版权之恶后,我才知道现行畸形的版权制度成了资本家敛财的工具,而没能真正的保护创作人,也没能给用户带来良好的体验。在这之后,我停用了所有的音乐服务,转向Apple Music 和 iTunes。Apple Music的曲库覆盖了我原有的音乐库。对于那些没法覆盖的歌曲,我会在国内软件中下载源文件(flac,ncm),然后将它转码成m4a导入iCloud资料库。至此,我才发现,每个月只用花5块钱就能带给我比同时使用三家音乐软件的会员更好的听歌体验。我的音乐完全属于我自己,我可以自己随意上传,修饰,描述它,不用担心它突然变灰或是被消失。而只保留一个音乐软件也符合极简主义的理念。同时,Apple Music中不存在censorship,我在iCloud中的某些歌不会像在网易云音乐云盘中被禁止收听。如果你想在多设备上同步音乐收听,同时也需要听一些利维坦不希望你听的歌(南京市民的歌,或是来自南方某座城市的一些歌,抑或《 Les Misérables 》中传唱度极高的主题曲),那么Apple Music和iCloud资料库应该是在中国最好的解决方案了。

关于IM软件,微信,QQ

如果你的手机中不存在微信,你在中国寸步难行。

在中国,你没办法逃避企鹅公司,一个中国人从出生到死亡的每一天都会收到企鹅公司的影响(尽管它的已知寿命还没有那么长),正如韩国人永远避不开三星公司一般。

在微信上,我取消关注了所有的公众号。其一出于我对其封闭内容生态的抗拒,其二出于我对这种“将信息送到我面前来”的信息推送方式的抗拒,其三出于我对内容本身的抗拒。第一点我在前面已经谈过许多了。企鹅至今没有完全开放过微信文章这个巨大的内容池的搜索接口,只为它的合作伙伴搜狗提供了一个搜索入口(和知乎如出一辙)。除此之外,你只能使用app内部的搜索入口,而这个搜索功能的体验如何自不比我多说。还可以谈谈微信的评论功能,作为一个内容发布平台,微信公众号在设计上就不存在让读者讨论的功能。文章底部的讨论最多只能做到个人留言以及作者本人的回复。我实在是无法理解这种功能残缺又封闭的平台如何就成为了中国最大的互联网内容池之一。

关于其二,我厌恶这种将信息摆在我眼前强迫我过目的方式。当我需一些内容时,我希望由我自己去搜索和比较,而不是在我不需要内容的时候有人将它放在我眼前。

我想这也是极简主义的一种体现:关注自己需要什么,而不是别人觉得我需要什么。

而第三点,微信文章这一形式本身并不适合作为工具类信息的载体,它与我信奉的实用主义并不相符。当一篇文章作为微信文章发布时,它必然背负了涨粉,流量转化,增加用户粘度,或是直接盈利的功能。在这种功利性的内容载体的影响下,文章本身的内容必然会受到影响。有多少次我们可以看到关注公众号领取,关注公众号获取密码,阅读原文查看原内容。这种模式强制性的将本可以开放的工具性信息转为封闭,强迫和诱导你在它的平台上进行内容消费和获取。文章本身也被强力的限制在微信这一载体中传播。这些形式会潜在而强力的影响文章内容本身。

我完全关闭了朋友圈功能,隐藏了所有的朋友圈,同时不再查看他人的朋友圈。当我意识到中国人群体性的社交模式的改变是一种社会学意义上的巨大变革时,已经是我开始使用朋友圈功能的五年后了。人们的社交思维和理念被一些代码改变,作为深刻影响人类的发明,朋友圈是成功的。你必须思考朋友圈礼仪,思考每个点赞带来的后果,思考评论的时机和意义,思考他的朋友圈所隐含的信息,思考每条朋友圈带来的潜在人际关系影响,思考朋友圈内容对个人形象的塑造作用。中国人头脑中的社交思维已经发生了剧烈的改变。

想清楚这些事实之后,我便发现我完全没法接受它们。我不能忍受一个互联网公司在一个app中推出的一个二级页面,就成为了在中国社会除学识,修养,谈吐,智商这些禀赋之外的另一种评判人的维度。我不能忍受一个互联网公司把持我人际交往中的重要部分,它应该只是社交内容传达的载体和工具,而不应该反过来影响我的社交内容本身。我不能容忍所有人都在朋友圈中评判与被评判,就像《黑镜》中的某集,所有人一辈子都在评分和被评分。弄明白这些事情之后,我能够坚决果断的跳出这个圈子。

我拒绝使用微信小程序以及微信支付。后者我也已经说明过,前者是站在作为开发者的我的角度思考而得出的结论。作为开发者,我非常讨厌微信的立志于做操作系统的态度。在对工具的使用上,我奉行Unix系统“小即是美”的哲学。一件工具应该专注于做好它本被赋予的任务,而不应该越俎代庖做操作系统或是其他软件该做的事情(这是国内的互联网公司的通病)。音乐软件只应该用来听歌,而不应该用来进行短视频流内容消费或是进行实体购物。同样的,IM软件应该只用来传递和交流信息,而不是应该去做支付软件或是小程序平台。

我删除了所有的微信表情包。在已经切断了微信的这么多功能之后,做到这一点条轻而易举。表情包在改变人类的交流模式上也是成功的发明。但表情包将本可以严肃的内容交流娱乐化,降低了人们交流的严肃性,也在一定程度上阉割了人类的语言表达能力。我会轻微的抵触表情包。

关于QQ,我的做法大致与微信相同,不再赘述。

最终,我让我的微信和QQ成为了一个部分契合我理想的IM软件。在一定程度上我做到了极简,它们本就只应该用来交流和传递信息,而不是用来做其他不是它们分内的事情。我只用它们做本应该做的事情,仅此而已。

做同样的事情,我们需要多少工具

智能手机是一件强大的工具,我们可以用它做很多事情。很多原本需要由不同工具来完成的任务现在都可以用手机来完成。你不再需要随身音乐播放器,车载导航系统,或是如我前文所述的调音器和节拍器。但是定下心来想想,手机太强大了,但是我们需要这么强大的它吗?我们真的需要手机厂商宣传的无缝工作功能,让我们可以在电脑和手机之间同步工作内容吗?我们真的需要每一台设备上都有Kindle的APP,PC上有Kindle的桌面软件,以及还拥有一部实体的Kindle吗?玩《集合啦!动物森友会》时我们一定要用手机APP来查看小动物们的状态或是和朋友聊天吗?电脑上登录了QQ,手机上也要一直登陆着吗?电脑上可以看bilibili,手机上也需要保留bilibili的APP吗?能用一件工具解决的问题,就不用两件工具解决,我想这也是极简主义的原则。极简主义会要求我只保留一个我最喜爱的杯子用来喝水,而不是同时有三四个好看而且都不忍割舍的杯子。现在这件事情只是转移到了小小的屏幕上,主体对象也不再是杯子,变成了互联网服务。

这样,我们可以轻而易举的把对待实体物品的态度转移到对待虚拟物品上来。既然我只保留一个水杯或是一个台灯或一支笔,那我就没有必要保留多个Kindle的APP或是Word,Powerpoint和Excel。我可以用iPad和PC来查看学习笔记或者读论文,我就不会用手机去学习。Web端的淘宝也可以购物,我就没必要留下淘宝APP。公交卡可以乘车,为何我一定要下载APP呢?我们需要弱化手机的功能。那些用其他工具完成得更好的事情,就不要用手机来做。我只用手机做那些只有手机能做,或是手机做得比其他工具要好的事情。

Lecture 8: Address Translation

Want Processes to Co-exist

image.png
image.png
  • Consider multiprogramming on physical memory
    • What happens when pintos needs to expand?
    • If emacs needs more memory than is on the machine?
    • If pintos has an error and writes to address 0x7100?
    • When does gcc have to know it will run at 0x4000?
    • What if emacs is not using its memory?

Virtualizing Resources

  • Physical Reality: different processes/threads share the same hardware
    • Need to multiplex CPU (done)
    • Need to multiplex use of Memory (today)
    • Need to multiplex disk and devices (later in term)
  • Why worry about memory sharing?
    • The complete working state of a process is defined by its data in memory (and registers)
    • Consequently, two different processes cannot use the same memory
      • Two different data cannot occupy same locations in memory
    • May not want different threads to have access to each other’s memory

Next Objective

  • Dive deeper into the concepts and mechanisms of memory sharing and address translation
  • Enabler of many key aspects of operating systems
    • Protection
    • Multi-programming
    • Isolation
    • Memory resource management
    • I/O efficiency
    • Sharing
    • Inter-process communication
    • Demand paging
  • Today: Linking, Segmentation

Recall: Single and Multithreaded Processes

image.png
image.png
  • Threads encapsulate concurrency
    • “Active” component of a process
  • Address spaces encapsulate protection
    • Keeps buggy program from trashing the system
    • “Passive” component of a process

Important Aspects of Memory Multiplexing

  • Protection: prevent access to private memory of other processes
    • Kernel data protected from User programs
    • Programs protected from themselves
    • May want to give special behavior to different memory regions (Read Only, Invisible to user programs, etc)
  • Controlled overlap: sometimes we want to share memory across processes.
    • E.g., communication across processes, share code
    • Need to control such overlap
  • Translation:
    • Ability to translate accesses from one address space (virtual) to a different one (physical)
    • When translation exists, processor uses virtual addresses, physical memory uses physical addresses
    • Side effects:
      • Can be used to give uniform view of memory to programs
      • Can be used to provide protection (e.g., avoid overlap)
      • Can be used to control overlap

Recall: OS Bottom Line: Run Programs

image.png
image.png

Recall: Address Space

image.png
image.png

Recall: Context Switch

image.png
image.png

Binding of Instructions and Data to Memory

image.png
image.png

2nd copy of program from previous example

image.png
image.png

Multi-step Processing of a Program for Execution

  • Preparation of a program for execution involves components at:
    • Compile time (i.e., “gcc”)
    • Link time (UNIX “ld” does link)
    • Load time
    • Execution time (e.g., dynamic libs)
  • Addresses can be bound to final values anywhere in this path
    • Depends on hardware support
    • Also depends on operating system
  • Dynamic Libraries
    • Linking postponed until execution
    • Small piece of code, stub, used to locate appropriate memory-resident library routine
    • Stub replaces itself with the address of the routine, and executes routine
image.png
image.png

Multiplexing Memory Approaches

  • Uniprogramming
  • Multiprogramming
    • Without protection
    • With protection (base+bound)
  • Virtual memory
    • Base & Bound
    • Segmentation
    • Paging
    • Paging + Segmentation

Uniprogramming

Uniprogramming (no Translation or Protection)

  • Application always runs at same place in physical memory since only one application at a time
  • Application can access any physical address

Multiprogramming (primitive stage)

Multiprogramming without Translation or Protection

  • Must somehow prevent address overlap between threads

Use Loader/Linker: Adjust addresses while program loaded into memory (loads, stores, jumps)

  • Everything adjusted to memory location of program
  • Translation done by a linker-loader (relocation)
  • Common in early days (… till Windows 3.x, 95?)j

With this solution, no protection: bugs in any program can cause other programs to crash or even the OS

Multiprogramming (Version with Protection)

  • Can we protect programs from each other without translation?
image.png
image.png
  • Yes: use two special registers BaseAddr and LimitAddr to prevent user from straying outside designated area
    • If user tries to access an illegal address, cause an error
  • During switch, kernel loads new base/limit from PCB (Process Control Block)
    • User not allowed to change base/limit registers

Virtual memory support in modern CPUs

  • The MMU – memory management unit
    • Usually on-chip (but some architecture may off-chip or no hardware MMU)
image.png
image.png

Virtual memory – how does it work?

  • Step 1. When CPU wants to fetch an instruction
    • the virtual address is sent to MMU and
    • is translated into a physical address.
image.png
image.png
  • Step 2. The memory returns the instruction
image.png
image.png
  • Step 3. The CPU decodes the instruction.
    • An instruction uses virtual addresses
      • but not physical addresses.
image.png
image.png
  • Step 4. With the help of the MMU, the target memory is retrieved.
image.png
image.png

General Address translation

  • Recall: Address Space:
    • All the addresses and state a process can touch
    • Each process has different address space
  • Consequently, two views of memory:
    • View from the CPU (what program sees, virtual memory)
    • View from memory (physical memory)
    • Translation box (MMU) converts between the two views
  • Translation makes it much easier to implement protection
    • If task A cannot even gain access to task B’s data, no way for A to adversely affect B
  • With translation, every program can be linked/loaded into same region of user address space

Simple Example: Base and Bounds

image.png
image.png
  • Could use base/bounds for dynamic address translation – translation happens at execution:
    • Alter address of every load/store by adding “base”
    • Generate error if address bigger than limit
  • This gives program the illusion that it is running on its own dedicated machine, with memory starting at 0
    • Program gets continuous region of memory
    • Addresses within program do not have to be relocated when program placed in different region of DRAM

Issues with Simple B&B Method

image.png
image.png
  • Fragmentation problem over time
    • Not every process is same size  memory becomes fragmented
  • Missing support for sparse address space
    • Would like to have multiple chunks/program (Code, Data, Stack)
  • Hard to do inter-process sharing
    • Want to share code segments when possible
    • Want to share memory between processes
    • Helped by providing multiple segments per process

More Flexible Segmentation

  • Logical View: multiple separate segments
    • Typical: Code, Data, Stack
    • Others: memory sharing, etc
  • Each segment is given region of contiguous memory
    • Has a base and limit
    • Can reside anywhere in physical memory

Implementation of Multi-Segment Model

image.png
image.png

Observations about Segmentation

  • Virtual address space has holes
    • Segmentation efficient for sparse address spaces
    • A correct program should never address gaps
      • If it does, trap to kernel and dump core
  • When is it OK to address outside valid range?
    • This is how the stack and heap are allowed to grow
    • For instance, stack takes fault, system automatically increases size of stack
  • Need protection mode in segment table
    • For example, code segment would be read-only
    • Data and stack would be read-write (stores allowed)
    • Shared segment could be read-only or read-write
  • What must be saved/restored on context switch?
    • Segment table stored in CPU, not in memory (small)
    • Might store all of processes memory onto disk when switched (called “swapping”)

Problems with Segmentation

  • Must fit variable-sized chunks into physical memory
  • May move processes multiple times to fit everything
  • Fragmentation: wasted space
    • External: free gaps between allocated chunks
    • Internal: do not need all memory within allocated chunks

General Address Translation

image.png
image.png

Paging: Physical Memory in Fixed Size Chunks

  • Solution to fragmentation from segments?
    • Allocate physical memory in fixed size chunks (“pages”)
    • Every chunk of physical memory is equivalent
      • Can use simple vector of bits to handle allocation:
        • 00110001110001101 … 110010
      • Each bit represents page of physical memory
        • 1 -> allocated, 0 -> free
  • Should pages be as big as our previous segments?
    • No: Can lead to lots of internal fragmentation
      • Typically have small pages (1K-16K)
    • Consequently: need multiple pages per segment

How to Implement Paging?

image.png
image.png

Simple Page Table Example

image.png
image.png

What about Sharing?

image.png
image.png

Summary: paging

image.png
image.png
image.png
image.png

Page Table Discussion

  • What needs to be switched on a context switch?
    • Page table pointer and limit
  • Analysis
    • Pros
      • Simple memory allocation
      • Easy to share
    • Con: What if address space is sparse?
      • E.g., on UNIX, code starts at 0, stack starts at (231-1)
      • With 1K pages, need 2 million page table entries!
    • Con: What if table really big?
      • Not all pages used all the time -> would be nice to have working set of page table in memory
  • How about multi-level paging or combining paging and segmentation?

Fix for sparse address space: The two-level page table

image.png
image.png

Summary: Two-Level Paging

image.png
image.png
image.png
image.png

Multi-level Translation: Segments + Pages

image.png
image.png

What about Sharing (Complete Segment)?

image.png
image.png

Lecture 7: Deadlock

starvation vs Deadlock

  • Starvation vs. Deadlock
    • Starvation: thread waits indefinitely(无限期的)
      • Low-priority thread waiting for resources constantly in use by high-priority thread
    • Deadlock: circular waiting for resources
      • Thread A owns Res 1 and is waiting for Res 2
      • Thread B owns Res 2 and is waiting for Res 1

Conditions for Deadlock

  • Deadlock not always deterministic
  • Deadlocks occur with multiple resources
    • Means you cannot decompose the problem
    • Cannot solve deadlock for each resource independently
    • System with 2 disk drives and two threads
      • Each thread needs 2 disk drives to function
      • Each gets one disk and waits for another one

Four requirements for Deadlock

  • Mutual exclusion
    • Only one thread at a time can use a resource
  • Hold and wait
    • Thread holding at least one resource is waiting to acquire additional resource held by other threads
  • No preemption
    • Resources are released only voluntarily by the thread holding the resource, after thread is finished with it
  • Circular wait
    • There exists a set {T_1, ..., T_n} of waiting threads
      • T1 is waiting for a resource that is held by T2
      • T2 is waiting for a resource that is held by T3
      • ...
      • Tn is waiting for a resource that is held by T1

Resource-Allocation Graph

  • System Model
    • A set of Threads T1, T2, ... Tn
    • Resource types R1,R2,...,Rm
      • CPU cycles, memory space, I/O devices
    • Each resource type R1 has W1 instances
    • Each thread utilizes a resources as follows:
      • Request(),Use(),Release()
  • Resource-Allocation Graph:
    • V is partitioned into two types:
      • T = {T1,T2,...,Tn}, the set threads in the system
      • R = {R1,R2,...,Rm}, the set of resource types in system
    • Request edge - directed edge - T1 -> Rj
    • assignment edge - directed edge Rj -> Ti
    image.png

Resource Allocation Graph Examples

  • Recall:
    • request edge - directed edge T1 -> Rj
    • assignment edge - directed edge Rj -> Ti
image.png
image.png

Methods for Handling Deadlocks

  • Allow system to enter deadlock and then recover
    • Requires deadlock detection algorithm
    • Some technique for forcibly preempting resources and/or terminating tasks
  • Ensure that system will never enter a deadlock
    • Need to monitor all resource acquisitions
    • Selectively deny those that might lead to deadlock
  • Ignore the problem and pretend that deadlocks never occur in the system
    • Used by most operating system, including UNIX

Deadlock Detection Algorithm

  • Only one of each type of resource -> look for cycles
  • More than one resource of each type
    • More deadlock detection algorithm

Several Instances of a Resource Type

  • Available: A vector of length m indicates the number of available resources of each type
  • Allocation: A n * m matrix defines the number of resources of each type currently allocated to each process.
  • Request: An n * m matrix indicates the current request of each process. If Request[i_j]=k, then process P_i is requesting k more instances of resource type. R_j.

Detection Algorithm

  1. Let Work and Finish be vectors of length m and n, respectly initialize:
    1. Work = Available
    2. For i = 1,2,...n, if Allocation_i not 0, then Finish[i] = false; otherwise, Finish[i] = true.
  2. Find an index i such that both:
    1. Finish[i] == false
    2. Request_i <= Work
    • If no such i exists, go to step 4
  3. As follow.
    • Work = Work + Allocation_i
    • Finish[i] = true
    • go to step 2
  4. If Finish[i] == false, for some i, 1 <= i <= n, then the system is in deadlock state. Moreover, if Finish[i] == false, then P_i is deadlocked

Example of Detection Algorithm

  • Five processes P_0 through P_4; three resource type A(7 instances), B(2 instances), and C(6 instances)
  • Snapshot at time T_0:

Allocation

A B C
P0 0 0 0
P1 2 0 0
P2 3 0 3
P3 2 1 1
P4 0 0 2

Request

A B C
P0 0 0 0
P1 2 0 2
P2 0 0 0
P3 1 0 0
P4 0 0 2

Available

A B C
0 0 0

Sequence <P_0,P_2,P_3,P_1,P_4> will result in Finish[i] = true for all i.

If P_2 request an additional instance of type C, that is

Request

A B C
P0 0 0 0
P1 2 0 2
P2 0 0 0
P3 1 0 0
P4 0 0 2

The state of system:

  • Can reclaim resources held by process P_0(not deadlocked), but insufficient resources to fulfill other process; request
  • Deadlock exist, consisting of processes P_1, P_2, P_3, and P_4

What to do when detect deadlock?

  • Terminate thread, force it to give up resources
    • In Bridge example, Godzilla picks up a car, hurls it into the river. Deadlock solved!
    • Shoot a dining philosopher
    • But, ont always possible
  • Preempt resources without killing off thread
    • Take away resources from thread temporarily
    • Does not always fit with semantics of computation
  • Roll back actions of deadlocked threads
    • For bridge example, make one car roll backwards(may require others behind him)
    • Common technique in databases(transactions)
    • Of courses, if you restart in exactly the same way, may reenter deadlock once again
  • Many operating systems use other options

Techniques for Preventing Deadlock

  • Infinite resources
    • Include enough resources so that no one ever runs out of resources. Examples:
      • Bay bridge with 12,000 lanes. Never wait!
      • Infinite disk space (not realistic yet?)
  • No sharing of resources(totally independent threads)
    • Not very realistic
  • Do not allow waiting
    • Technique used in Ethernet/some multiprocessor nets
      • Every speaks at once. On collision, back off and retry
    • Inefficient, since have to keep retrying
      • Consider: driving to SUSTech; when hit traffic jam, suddenly you are transported back home and told to retry!
  • Make all threads request everything they will need at the beginning
    • Problem: Predicting future is hard, tend to over-estimate resources. Example:
      • If need 2 chopsticks, request both at same time
      • Don not leave home until we know no one is using any intersection between home and SUSTech; only one car on the Bay Bridge at a time
  • Force all threads to request resources in a particular order preventing any cyclic use of resources
    • Thus, preventing deadlock
    • Example (x.P, y.P, z.P,…)
      • Make tasks request disk, then memory, then…
      • Keep from deadlock on freeways around SF by requiring everyone to go clockwise

Banker's Algorithm

  • Multiple instances of each resource type
  • Each process must a priori claim maximum use
  • When a process requests a resource it may have to wait
  • When a process gets all its resources it must return them in a finite amount of time

Data Structures for the Banker's Algorithm

Let n = number of processes, and m = number of resources type

  • Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj available
  • Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj
  • Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj
  • Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task

Need [i,j] = Max[i,j] – Allocation [i,j]

Safety Algorithm

1.Let Work and Finish be vectors of length m and n ,respectively. Initialize:

  • Work = Available
  • Finish [i] = false for i = 0, 1, …, n- 1

2.Find an index i such that both:

  • Finish [i] = false
  • Need[i] <= Work (i.e., for all k, Need[i,k] <= Work[k])

3.Work = Work + Allocation[i]

  • Finish[i] = true
  • go to step 2

4.If Finish [i] == true for all i, then the system is in a safe state

Resource-Request Algorithm for Process Pi

Request = request vector for process P_i. If Request [i,j] = k then process P_i wants k instances of resource type R_j

1.If Request[i] <= Need[i] go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.

2.If Request[i] <= Available, go to step 3. Otherwise P_i must wait, since resources are not available

3.Pretend to allocate requested resources to P_i by modifying the state as follows:

  • Available = Available – Request;
  • Allocation[i] = Allocation[i] + Request[i];
  • Need[i] = Need[i] – Request[i];

If safe -> the resources are allocated to P_i

If unsafe -> P_i must wait, and the old resource-allocation state is restored

Example of Banker’s Algorithm

image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

Week6 Note

Lecture 7: Synchronization(同步化)

Synchronization of threads/processes

Shared memory between processes

Race Condition: Understanding the problem

Race Condition

Normal execution and Abnormal execution

Normal execution

Abnormal execution

  • The above scenario is called the race condition. May happen whenever shared object + multiple processes/threads + concurrently
  • A race condition means +the outcome of an execution depends on a particular order in which the shared resource is accessed.
  • Remember: race condition is always a bad thing and debugging race condition is a nightmare!
    • It may end up …
      • 99% of the executions are fine.
      • 1% of the executions are problematic.

Mutual Exclusion – the cure

Solution - Mutual exclusion

  • Shared object is still sharable, but
    • Do not access the “shared object” at the same time
    • Access the “shared object” one by one

Critical Section - the realization

  • Critical section is the code segment that is accessing the shared object

Critical Section (CS) – the realization

A typical mutual exclusion scenario

A typical mutual exclusion scenario

Summary

  • Race condition
    • Happens when programs accessing a shared object
    • The outcome of the computation totally depends on the execution sequences of the processes involved
  • Mutual exclusion is a requirement
    • If it could be achieved, then the problem of the race condition would be gone.
  • A critical section is the code segment that access shared objects.
    • Critical section should be as tight as possible>
      • Well, you can set the entire code of a program to be a big critical section
      • But, the program will have a very high chance to block other processes or to be blocked by other processes
  • Note that *one critical section can be designed for accessing more than one shared objects**.
  • Implementing section entry and exit is a challenge.
    • The entry and the exit are the core parts that guarantee mutual exclusion
    • Unless they are correctly implemented, race condition would appear.
  • Mutual exclusion hinders(阻碍) the performance of parallel computations.

Entry and exit implementation - requirements

  • Requirement #1. Mutual Exclusion
    • No two processes could be simultaneously go inside their own critical sections.
  • Requirement #2. Bounded Waiting
    • Once a process starts trying to enter her CS, there is a bound on the number of times other processes can enter theirs.
  • Requirement #3. Progress
    • Say no process currently in C.S.
    • One of the processes trying to enter will eventually get in.

#0 – disabling interrupt for the whole CS

  • Aim
    • To disable context switching when the process is inside the critical section.
  • Effect
    • When a process is in its critical section, no other processes could be able to run
  • Correctness?
    • Uni-core: Correct but not permissible
      • at userspace: what if one writes a CS that loops infinitely and the other process(e.g., the shell) never gets the context switch back to kill it.
    • Multi-core:Incorrect
      • If there is another core modifying the shared object in the memory(unless you disable interrupts on all cores)

Achieving Mutual Exclusion

  • Lock-based
    • Use yet another shared objects: locks
      • What about race condition on lock?
      • Atomic instructions: instructions that cannot be "interrupted"
    • Spin-based lock
      • Process synchronization
        • Basic spinning using 1 shared variable
        • Peterson's solution: Spin using 2 shared variables
      • Thread synchronization
        • pthread_spin_lock
    • Sleep-based lock
      • Process synchronization
        • POSIX semaphore(信号标,旗语)
      • Thread synchronization
        • pthread_mutex_lock

#1: Basic Spin lock(busy waiting)

  • Idea.
    • Loop on another shared object, turn, to detect the status of other process

  • Correct
    • but it wastes CPU resources
    • OK for short waiting
      • Especially these days we have multi-core
        • Will not block other irrelevant processes a lot
      • OK when spin-time < context-switch-overhead
  • Impose a strict alternation(交替) other
    • SOmetimes you give me my turn but I'm not ready to enter CS yet
      • Then you have to wait long

#1: Basic Spin lock violates progress

  • Consider the following sequence:
    • Process0 leaves cs(), set turn=1
    • Process enter cs(), leaves cs()
      • set turn=0, work on remainder_section_slow()
    • Process 0 loops back and enter cs() again, leaves cs(), set turn=1
    • Process 0 finishes its remainder_section(), go back to top of the loop
      • It can't enter its cs(), as turn=1
      • That is process0 gets blocked, but Process 1 is outside its cs(), it is at its remainder_section_slow()

#2: Spin Smarter(by Peterson's solution)

  • Highlight:
    • Use one more extra shared object: interested
      • If I am not interested
        • I let you go
      • If we are both interested
        • Takes turns

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int turn; /* who is last enter cs */
int interested[2] = {FALSE,FALSE}; /* express interest to enter cs*/

void lock( int process ) { /* process is 0 or 1 */
int other; /* number of the other process */
other = 1-process; /* other is 1 or 0 */
interested[process] = TRUE; /* express interest */
turn = other;
while ( turn == other && interested[other] == TRUE ) ; /* busy waiting */
}

void unlock( int process ) { /* process: who is leaving */
interested[process] = FALSE; /* I just left critical region */
}

Case 1

Case 2

Spin Smarter (by Peterson’s solution)

  • Busy waiting
    • shared variable turn for mutual exclusion
    • shared variables interest to resolve strict alternation
  • Peterson’s solution satisfies all three criteria! (Why?) > “It satisfies the three essential criteria to solve the critical section problem, provided that changes to the variables turn, interest[0], and interest[1] propagate immediately and atomically.”---wikipedia
  • Suffer from priority inversion problem

Peterson’s solution satisfies three criteria

  • Mutual exclusion
    • interested[0] == interested[1] == true
    • turn == 0 or turn == 1, not both
  • Progress
    • If only P0 to enter critical section
      • interested[1] == false, thus P0 enters critical section
    • If both P0 and P1 to enter critical section
      • interested[0] == interested[1] == true and (turn == 0 or turn == 1)
    • One of P0 and P1 will be selected
  • Bounded-waiting
    • If both P0 and P1 to enter critical section, and P1 selected first
    • When P1 exit, interested[1] = false
      • If P0 runs fast: interested[1] == false, P0 enters critical section
      • If P1 runs fast: interested[1] = true, but turn = 0, P0 enters critical section

Peterson spinlock suffers from Priority Inversion

  • Priority/Preemptive Scheduling (Linux, Windows… all OS..)
    • A low priority process L is inside the critical region, but …
    • A high priority process H gets the CPU and wants to enter the critical region.
      • But H can not lock (because L has not unlock)
      • So, H gets the CPU to do nothing but spinning

#3: Sleep-based lock: Semaphore

  • Semaphore is just a struct, which includes
    • an integer that counts the # of resources available
      • Can do more than solving mutual exclusion
    • a wait-list
  • The trick is still the section entry/exit function implementation
    • Need to interact with scheduler (must involve kernel, e.g., syscall)
    • Implement uninterruptable section entry/exit
      • Section entry/exit function are short
        • Compared with Implementation #0 (uninterruptable throughout the whole CS)

Semaphore logical view

Using Semaphore(User-level)

image.png
image.png

Using Semaphore beyond mutual exclusion

Problem Properties
Producer-Consumer Problem Two classes of processes: producer and consumer;At least one producer and one consumer.[Single-Object Synchronization]
Dining Philosopher Problem They are all running the same program;At least two processes.[Multi-Object Synchronization]
Reader Writer Problem Multiple reads, 1 write

Producer-consumer problem – introduction

  • Also known as the bounded-buffer problem.
  • Single-object synchronization

Producer-consumer problem: semaphore

  • The problem can be divided into two sub-problems.
    • Mutual exclusion
      • The buffer is a shared object. MUtual exclusion is needed. Done by one binary semaphore
    • Synchronization.
      • Because the buffer’s size is bounded, coordination is needed. Done by two semaphores
        • Notify the producer to stop producing when the buffer is full
          • In other words, notify the producer to produce when the buffer is NOT full
        • Notify the consumer to stop eating when the buffer is empty
          • In other words, notify the consumer to consume when the buffer is NOT empty

Producer-consumer problem – question #1

Producer-consumer problem – question #2

  • This scenario is called a deadlock
    • Consumer waits for Producer’s mutex at line 6
      • i.e., it waits for Producer (line 9) to unlock the mutex
    • Producer waits for Consumer’s avail at line 7
      • i.e., it waits for Consumer (line 9) to release avail
  • Implication: careless implementation of the producer-consumer solution can be disastrous(灾难性的).

Deadlock

Summary on producer-consumer problem

  • How to avoid race condition on the shared buffer?
    • E.g., Use a binary semaphore
  • How to achieve synchronization?
    • E.g., Use two semaphores: fill and avail

Dining philosopher – introduction

  • 5 philosophers, 5 plates of spaghetti, and 5 chopsticks.
  • The jobs of each philosopher are to think and to eat +They need exactly two chopsticks in order to eat the spaghetti.
  • Question: how to construct a synchronization protocol such that they:
    • will not starve to death, and
    • will not result in any deadlock scenarios?
      • A waits for B’s chopstick
      • B waits for C’s chopstick
      • C waits for A’s chopstick …
  • It’s a multi-object synchronization problem

Dining philosopher - introduction

Dining philosopher – requirement #1

  • Mutual exclusion
    • While you are eating, people cannot steal your chopstick
    • Two persons cannot hold the same chopstick
  • Let’s propose the following solution
    • When you are hungry, you have to check if anyone is using the chopsticks that you need.
    • If yes, you wait
    • If no, seize both chopsticks
    • After eating, put down both your chopsticks.

Dining philosopher – meeting requirement #1?

Dining philosopher - deadlock

Dining philosopher – requirement #2

  • Synchronization
    • Should avoid deadlock.
  • How about the following suggestions:
    • First, a philosopher takes a chopstick.
    • If a philosopher finds that she cannot take the second chopstick, then she should put it down.
    • Then, the philosopher goes to sleep for a while.
    • When wake up, she retries
    • Loop until both chopsticks are seized.

Dining philosopher – meeting requirement #2?

Dining philosopher – before the final solution

  • Before we present the final solution, let us see what problems we have.

  • Problems
    • Model each chopstick as a semaphore is intuitive, but may cause deadlock
    • Using sleep() to avoid deadlock is effective, yet creating starvation.

Dining philosopher – the final solution

Dining philosopher – Hungry

Dining philosopher – Finish eating

Dining philosopher – the core

  • 5 philosophers -> ideally how many chopsticks?
  • how many chopsticks do we have now?
  • Very common in today’s cloud computing multi-tenancy model

Summary on IPC problems

  • The problems have the following properties in common:
    • Multiple number of processes;
    • Processes have to be synchronized in order to generate useful output;
    • Each resource may be shared as well as limited, and there may be more than one shared processes.
  • The synchronization algorithms have the following requirements in common:
    • Guarantee mutual exclusion;
    • Uphold(维护) the correct synchronization among processes; and
    • (must be) Deadlock-free.

Heisenbugs

  • Jim Gray, 1998 ACM Turing Award winner, coined that term
  • You find your program P has a concurrency bug
  • You insert ‘printf’ statements or GDB to debug P
  • Then because of those debugging things added, P behaves normally when you are in debug mode