操作系统

保护模式大坑——特权级详解

Posted on

终于看懂系列…………

本菜鸡这次主要讲的内容是对三个特权级DPL,CPL,RPL在x86下的理解,如果大佬想看的不是这个就请关上这个标签页。

一些自我理解与背景

负责任地说,操作系统是一个死循环,其间有很多确定和与不确定的中断与调用,最后再被不确定地break掉。在中断与调用中,我们作为用户自然是不可能随意触碰,因为用户不都是满怀好意并且是极其细心的。因此操作系统需要对资源进行保护,而特权级就是保护模式最大的体现。

特权级简介

特权级使用两位4个级别,特权级0通常赋予内核,特权级1,2则是一些系统级服务,常见的就是外设,而我们的应用程序全都在特权级3。
值得注意的是,任何对段寄存器的修改都会触发CPU进行特权级检测,以防任务越权访问。

特权级字段有以下4个:
DPL: 段描述符特权级,最好理解的特权级,位于段描述符的高32位,表示的是这个段描述符所表示的段的特权级。
RPL: 请求特权级。位于选择子的最后两位。字面意思,表示请求时的特权级。这里强调,选择子可以保存在任意段寄存器中。
CPL: 当前特权级。当前任务/cpu/系统所处的特权级,永远位于当前CS寄存器所存的段选择子的RPL位。正如其存储位置表明,大部分情况下,CPL==RPL。在下面会说反例。
IOPL: I/O特权级,位于EFLAGS寄存器中,表示当前任务的I/O特权级别,通常是对端口访问的许可权。

CPL != RPL的情况

RPL真正强调的是请求者的特权级,因为在大多数情况下,请求者就是自己,所以CPL==RPL。而当请求者并非是自己的时候,两者自然不再相等,举个栗子:
我有一段程序需要从外设(比如键盘)中获取数据,而应用程序显然没有这个权限,但是可以通过调用门调用内核例程去获取外设的数据。
这个过程中,系统例程的请求者为应用程序,在使用调用门时必然会对任一段寄存器修改,其选择子的RPL为3,因为是系统调用,CS的段选择子的RPL为0。

引入RPL的必要性

段寄存器并非唯一,并且在大多数情况下CPL与RPL相同,看似RPL十分多余而费力,其实是为了更好地保护。
如果不存在RPL,当我们通过调用门访问系统数据段的时候,当前CPL为0,我们的特权上升到最高,就可以任意修改系统数据段,这是十分危险的。

控制转移的特权级检查规则

  • 在任何时候,都不允许将控制从较高的特权级代码段转移到控制较低的特权级代码段。这非常好理解,因为操作系统不会引用可靠性比自己低的代码。
  • 通过设置段描述符的TYPE字段的C位,更改其依从性,所谓依从性,即允许低特权级代码段转移到高特权级代码段,且在数值上满足 min(CPL , RPL) \geq 目标DPL。否则,只能同特权级转移。
  • 高特权级的代码段可以任意访问低特权级的数据段,反之则需要特权级检查:在数值上必须满足 max(CPL , RPL) \leq 目标DPL

这里需要强调控制转移和任务不要混淆…………

大概就这些了……

红黑树

红黑树入门

Posted on

刚看完网易公开课上算法导论中的平衡搜索树,传送门,讲的真的炒鸡好,这里就稍微总结一下。
另一方面,视频是英文板书,在一些地方讲述有点慢,这时候就凸显了文章的优势了。

红黑树性质

红黑树的性质判定红黑树的充要条件,性质见下:

  1. 每个节点不是红色就是黑色。
  2. 根节点和叶子节点必须为黑色。
  3. 每个红色节点的父亲节点必须为黑色节点。
  4. 对于每个节点,在它到每一个子树的叶子节点的所有路径中,所经过的黑色节点数量相同。并定义这个数量为黑高(black height)。

补充一条推论,由性质3易得,一颗红黑树的红色节点不会超过总节点数的一半。
而对于第2条性质,我们一般会使最后指向的空节点染色成黑色即可。

红黑树的树高

先说结论,红黑树的树高 height 不会超过 2log_2{(n+1)},即 height \leq 2 log_2{(n+1)}

证明如下:
将所有红色节点合并到其父亲节点,同时使该节点的孩子节点也合并成为其父亲节点的孩子节点。
这时候我们会得到一棵特别的树,它也是一棵平衡搜索树,称为2-3-4树。(建议在纸上画画)

2-3-4树有如下两条性质:
1. 对于每个非叶子节点,它的孩子节点数量范围为[2,4]
2. 对于每个叶子节点,它的深度都相同。

我们设由红黑树所得的2-3-4树的树高为 h',其叶子节点的数量为 leaf_num。可得不等式

    \[2^{h'} \leq leaf\_num \leq 4^{h'}\]

进而推导出 h' \leq log_2{leaf\_num}

就剩下我们的leaf_num了,其实leaf_num和红黑树的叶子节点的数量是一样的,而一棵树的叶子节点的数量是这棵树的非叶子节点数量 + 1,这是显而易见的。而在我们的红黑树中,非叶子节点数量就是我们插入的元素数量 n
将其代入得h' \leq log_2{(n+1)}
最后再联系到我们最开始的目标,红黑树的树高height,因为我们只合并了红色节点,根据红黑树性质3的推论可得

    \[2height \geq h'\]

因此,height \leq 2log_2{(n+1)} 得证。

红黑树的查询

因为树高是在 log 级别,所以只要按照二叉搜索树的查找方法来即可。
复杂度上限为一个树高,即一个 log 。

红黑树的插入

省去引入与例子,直接讲解法。

首先插入时按照二叉搜索树的方法插入,将其染色为红色,这样不会影响树高,易修复,但可能会破坏性质3。

现在假设插入节点 x与其父亲节点p[x]都为红色,即破坏了性质3。

其修复步骤主要分2种情况,这里将之称为两个主要情况:
1. 父亲节点是祖父节点的左孩子
2. 父亲节点是祖父节点的右孩子

这两种主要情况下又分为三种次要情况,这里以上述主要情况1的条件下分类讨论:
1. 祖父节点的右孩子p[p[x]].right,即叔叔(uncle)节点也为红色。此时让父亲节点和叔叔节点都染色成黑色,祖父节点染色成红色,将当前节点变更到祖父节点,进入下一个循环。
2. 叔叔(uncle)节点为黑色,当前节点x为父亲节点p[x]的右孩子。此时将父亲节点左旋,使得进入情况3。
3. 叔叔(uncle)节点为黑色,当前节点x为父亲节点p[x]的左孩子。可由情况2旋转得来。此时将祖父节点右旋并重新染色。染色方案为,新的祖父节点为黑色,新的父亲节点和新的叔叔节点为红色。退出循环。

而对于主要情况2,只要对主要情况1的3种次要情况做类似操作即可,唯一不同的就是方向反一下。
即 “左”--> “右”,“右”--> “左”。

红黑树的删除

视频没讲,有点晚了,明天看,并且补上C++代码实现。

翻译

Photon 也许能成为你最喜爱的容器操作系统

Posted on

Photon OS

Phonton OS 专注于容器,是一个非常出色的平台。 —— Jack Wallen

容器在当下的火热,并不是没有原因的。正如之前讨论的,容器可以使您轻松快捷地将新的服务与应用部署到您的网络上,而且并不耗费太多的系统资源。比起专用硬件和虚拟机,容器都是更加划算的,除此之外,他们更容易更新与重用。

更重要的是,容器喜欢 Linux(反之亦然)。不需要太多时间和麻烦,你就可以启动一台 Linux 服务器,运行Docker,然后部署容器。但是,哪种 Linux 发行版最适合部署容器呢?我们的选择很多。你可以使用标准的 Ubuntu 服务器平台(更容易安装 Docker 并部署容器)或者是更轻量级的发行版 —— 专门用于部署容器。

Photon 就是这样的一个发行版。这个特殊的版本是由 VMware 于 2005 年创建的,它包含了 Docker 的守护进程,并可与容器框架(如 Mesos 和 Kubernetes )一起使用。Photon 经过优化可与 VMware vSphere 协同工作,而且可用于裸机、Microsoft Azure、 Google Compute Engine、 Amazon Elastic Compute Cloud 或者 VirtualBox 等。

Photon 通过只安装 Docker 守护进程所必需的东西来保持它的轻量。而这样做的结果是,这个发行版的大小大约只有 300MB。但这足以让 Linux 的运行一切正常。除此之外,Photon 的主要特点还有:

  • 内核为性能而调整。
  • 内核根据内核自防护项目(KSPP)进行了加固。
  • 所有安装的软件包都根据加固的安全标识来构建。
  • 操作系统在信任验证后启动。
  • Photon 的管理进程可以管理防火墙、网络、软件包,和远程登录在 Photon 机器上的用户。
  • 支持持久卷。
  • Project Lightwave 整合。
  • 及时的安全补丁与更新。

Photon 可以通过 ISO 镜像OVAAmazon Machine ImageGoogle Compute Engine 镜像Azure VHD 安装使用。现在我将向您展示如何使用 ISO 镜像在 VirtualBox 上安装 Photon。整个安装过程大概需要五分钟,在最后您将有一台随时可以部署容器的虚拟机。

创建虚拟机

在部署第一台容器之前,您必须先创建一台虚拟机并安装 Photon。为此,打开 VirtualBox 并点击“新建”按钮。跟着创建虚拟机向导进行配置(根据您的容器将需要的用途,为 Photon 提供必要的资源)。在创建好虚拟机后,您所需要做的第一件事就是更改配置。选择新建的虚拟机(在 VirtualBox 主窗口的左侧面板中),然后单击“设置”。在弹出的窗口中,点击“网络”(在左侧的导航中)。

在“网络”窗口(图1)中,你需要在“连接”的下拉窗口中选择桥接。这可以确保您的 Photon 服务与您的网络相连。完成更改后,单击确定。

change settings

图 1: 更改 Photon 在 VirtualBox 中的网络设置。经许可使用

从左侧的导航选择您的 Photon 虚拟机,点击启动。系统会提示您去加载 ISO 镜像。当您完成之后,Photon 安装程序将会启动并提示您按回车后开始安装。安装过程基于 ncurses(没有 GUI),但它非常简单。

接下来(图2),系统会询问您是要最小化安装,完整安装还是安装 OSTree 服务器。我选择了完整安装。选择您所需要的任意选项,然后按回车继续。

installation type

图 2: 选择您的安装类型。经许可使用

在下一个窗口,选择您要安装 Photon 的磁盘。由于我们将其安装在虚拟机,因此只有一块磁盘会被列出(图3)。选择“自动”按下回车。然后安装程序会让您输入(并验证)管理员密码。在这之后镜像开始安装在您的磁盘上并在不到 5 分钟的时间内结束。

Photon

图 3: 选择安装 Photon 的硬盘。经许可使用

安装完成后,重启虚拟机并使用安装时创建的用户 root 和它的密码登录。一切就绪,你准备好开始工作了。

在开始使用 Docker 之前,您需要更新一下 Photon。Photon 使用 yum 软件包管理器,因此在以 root 用户登录后输入命令 yum update。如果有任何可用更新,则会询问您是否确认(图4)。

Updating

图 4: 更新 Photon。经许可使用

用法

正如我所说的,Photon 提供了部署容器甚至创建 Kubernetes 集群所需要的所有包。但是,在使用之前还要做一些事情。首先要启动 Docker 守护进程。为此,执行以下命令:

systemctl start docker
systemctl enable docker

现在我们需要创建一个标准用户,以便我们可以不用 root 去运行 docker 命令。为此,执行以下命令:

useradd -m USERNAME
passwd USERNAME

其中 “USERNAME” 是我们新增的用户的名称。

接下来,我们需要将这个新用户添加到 “docker” 组,执行命令:

usermod -a -G docker USERNAME

其中 “USERNAME” 是刚刚创建的用户的名称。

注销 root 用户并切换为新增的用户。现在,您已经可以不必使用 sudo 命令或者切换到 root 用户来使用 docker 命令了。从 Docker Hub 中取出一个镜像开始部署容器吧。

一个优秀的容器平台

在专注于容器方面,Photon 毫无疑问是一个出色的平台。请注意,Photon 是一个开源项目,因此没有任何付费支持。如果您对 Photon 有任何的问题,请移步 Photon 项目的 GitHub 下的 Issues,那里可以供您阅读相关问题,或者提交您的问题。如果您对 Photon 感兴趣,您也可以在该项目的官方 GitHub中找到源码。

尝试一下 Photon 吧,看看它是否能够使得 Docker 容器和 Kubernetes 集群的部署更加容易。

欲了解 Linux 的更多信息,可以通过学习 Linux 基金会和 edX 的免费课程,“Linux 入门”


via: https://www.linux.com/learn/intro-to-linux/2017/11/photon-could-be-your-new-favorite-container-os

作者:JACK WALLEN
译者:KeyLD (其实就是我啦~~)
校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出

LinuxCN原文传送门