复习总结(4)操作系统(2)进程与线程ProcessAndThread

第二章:进程与线程(Process and Thread)

线程Process

2.1.1进程模型

一个进程就是一个正在执行程序的实例,包括程序计数器(program counter)、寄存器和变量的当前值。

2.1.2创建进程

有4种主要事件导致进程的创建:
1)系统初始化
2)执行了正在运行的进程所调用的进程创建系统调用
3)用户请求创建一个新进程
4)一个批处理作业的初始化

停留在后台处理的进程称为守护进程(daemon),在UNIX中使用ps命令可以列出正在运行的进程。

使用fork系统调用可以创建新进程。(可能需要了解的:fork和vfork区别)

2.1.3进程的终止

进程的终止通常由下列条件引起:
1)正常退出(自愿的)
2)出错退出(自愿的)
3)严重错误(非自愿)
4)被其他进程杀死(非自愿)

2.1.4进程的层次结构

进程和它的所有子女以及后裔共同组成一个进程组。
在整个系统中,所有的进程都属于以init为根的一棵树。
windows没有进程层次的概念,所有的进程都是地位相同的。创建进程时,父进程得到一个句柄,可以用来控制子进程。

2.1.5进程的三个状态

 

2.1.6进程的实现

操作系统维护一张表格(结构数组),即进程表(process table)。
每个进程占用一个进程表项(Processing Control Block)
包括一下内容。

 

2.1.7多道程序(multiprogramming)设计模型

 

 

 

 

 

线程(Thread)

2.2.1线程的使用

这里简单介绍了一下线程的使用场景。

2.2.2经典的线程模型

 

这里要注意的是线程之间共享的东西。

2.2.3POSIX线程

介绍了一下Pthread的函数调用。

2.2.4在用户空间中实现线程
2.2.5在内核中实现进程

 

2.3进程间通讯(Inter Process Communication)#重点

2.3.1竞争条件(race condition)
2.3.2临界区(critical region)

需要互斥(mutual exclusion),即确保当一个进程在使用一个共享变量或文件时,其它进程不能做同样的操作。

2.3.3忙等待的互斥

讨论几种实现互斥的方案,包括:
屏蔽中断
锁变量
严格轮转法
peterson解法
TSL指令:测试并加锁(Tset and Set Lock)是硬件支持的一种方案。

2.3.4睡眠与唤醒

生产者-消费者问题(producer-consumer)称为有界缓冲区(bounded-buffer)问题。# 这个是重点

2.3.5信号量(semaphore)#这个也是重点

用一个整型变量累计唤醒次数。Proberen使信号量减一,Verhogen使信号量加一。

如何用信号量解决生产者-消费者问题。

另一种用途是同步(synchronization)。用信号量来保证某种时间的顺序发生或不发生。

2.3.6互斥量(mutex)

信号量的一个简化版本。

2.3.7管程(Monitor)

任一时刻管程中只能有一个活跃进程。
互斥由编译器负责,但通常的做法是用一个互斥量或二元信号量。

2.3.8消息传递massage passing
2.3.9屏障barrier

用于进程组而不是用于生产者-消费者类情形的。

 

2.4调度

调度的三种不同环境:
批处理
交互式
实时

批处理系统中的调度:
先来先服务(first-come first-severd)
最短作业优先(shortest job first)
最短剩余时间优先(shortest remaining time next)有关的运行时间必须提前掌握。

交互式系统的调度
1轮转调度(round robin),每个进程分配一个时间片(quantum)。进程切换(Process switch)又称为上下文切换(context switch)
2、优先级调度
3、多级队列
4、最短进程优先。根据过去的行为进程推车某命令运行时间。T=aT0+(1-a)T1
5、保证调度:每个进程获得1/n的CPU时间。
6、彩票调度(lottery scheduling)
7、公平分享调度Fair-Share Scheduling:n个用户每个用户有1/nCPU时间,无关进程

 

2.5经典的IPC问题

2.5.1哲学家就餐问题

2.5.2读者-写者问题

 

 

复习总结(3)操作系统OperatingSystem(1)BasicConcepts

第一章:引论

1.1:作为扩展机器的操作系统

作为资源管理者的操作系统

 

1.2:操作系统的历史:

真空管和穿孔卡片

晶体管和批处理系统

集成电路芯片和多道程序设计

个人计算机

 

1.3:计算机硬件介绍:

CPU

存储器

磁盘

磁带

I/O设备

总线

启动计算机

 

1.4:各种操作系统介绍:

大型机操作系统

服务器操作系统

多处理器操作系统

个人计算机操作系统

掌上计算机操作系统

嵌入式操作系统

传感器节点操作系统

实时操作系统

智能卡操作系统

 

1.5:操作系统概念(Basic concepts)

进程

地址空间

文件

输入输出

保护

Shell

程序计数器:program counter,保存下一条指令的内存地址

堆栈指针:stack pointer,内存栈顶

程序状态字:PSW,program status word保存条件码位,CPU优先级,模式(用户/内核),其他控制位

多路复用:multiplexing

堆栈指针:stack pointer,内存栈顶

程序状态字:PSW,program status word保存条件码位,CPU优先级,模式(用户/内核),其他控制位

多路复用:multiplexing

用户态:user mode

内核态:kernel mode

系统调用:System Call,从操作系统获得服务,陷入内核并调用操作系统

Trap:Trap指令把用户态切为内核态

 

进程:Process

地址空间:address space :从某个最小值的存储位置到最大值存储位置的列表

进程表:Process table,操作系统的一个表,数组或者链表结构,记录进程的所有信息

命令解释器:command interpreter用于从终端上读命令

进程间通讯:interprocess communication

UID: User Identification 用户标识

 

 

复习总结(2)数据结构data structure(2)树

图片未标明出处的均为使用ProcessOn(https://www.processon.com/)作图。

二叉树(Binary Tree)

每个节点(node)最多有两个子树(children)。

—Wikipedia

二叉树的遍历:

深度优先遍历(depth-first order)、广度优先遍历(Breadth-first order)

前序遍历(pre-order)、中序遍历(in-order)、后序遍历(post-order)

 

二叉搜索树(Binary Search Tree)

是一颗二叉树同时有以下性质:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。—wikipedia

当插入的数据有序时,查找效率跟顺序查找的效率相当,所以有了平衡树,使得左右子树高度严格平衡(相差0或1)。

 

平衡二叉搜索树(Balanced Binary Tree)

平衡二叉搜索树跟二叉搜索树差别在于,当插入、删除数据导致树的高度相差大于1时,会对树进行旋转(rotate)。

平衡二叉树可以保证查找时间,但是删除节点需要检查从删除节点开始到根的路径上所有的平衡因子,因此删除代价较大。

图自百度百科

红黑树(Red-black tree) # 划重点

牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树。—wikipedia

删除节点时只需要进行最多3次的旋转。

 

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

—-wikipedia

 

B树(B-Tree)

一般化的二叉查找树,可以拥有多于2个子节点。

 

B+树(B+Tree) # 划重点

 

插入搜索删除都是重点

 

 

 

 

复习总结(1)数据结构data structure(1)

对学过的数据结构做一个简单的归纳总结,且作为以后的复习提纲。

图片未标明出处的均为使用ProcessOn(https://www.processon.com/)作图。

数组(Array)

线性结构。

 

链表(Linked List)

包括单向链表(Singly linked list)、双向链表(Doubly linked list)、循环链表(Circular linked list)等。

单向链表 —-Wikipedia

双向链表 —-Wikipedia

循环链表—-Wikipedia

 

 

队列(queue)

先进先出(First-In-First_Out)的线性表(Linear List),常用数组(Array)或者链表(Linked list)实现。

栈(Stack)

先进后出(First-In-Last-Out),从同一端进(push)和出(pop)

 

哈希表(Hash Table)

散列函数为F(),通过index = F(key)获得元素在哈希表内的位置。

—Wikipedia

重点:

哈希函数(Hash function)

冲突处理(Collision resolution)

 

堆(heap)

使用线性结构存储的二叉树(通常情况下),满足

(ki <= k2i, ki <= k2i+1)或者(ki >= k2i, ki >= k2i+1), (i = 1, 2, 3, 4… n/2) —wikipedia

常用于堆排序

 

2018春季头条实习面试总结

3月1号投了今日头条深圳的后台开发岗位,第二天HR就打电话商量面试时间,定在了3月6号下午。

到达之后,在前台签到,签到本可以看见在我之前有几个人也是去面试的,但是人数不多。签到之后,HR安排了一小间会议室,让我在里面等面试官,不久就进来一位面试官,一对一面试。

首先是给了一张试卷,上面有仨算法题,给10分钟的时间,选一题得出思路,然后10分钟之后给他讲思路。题目难度都不算大,大约在中等題的难度。因为可能他们还会使用同样题目面试,所以这里就不总结算法题了。10分钟之后,面试官进来,我讲了思路,他的反应我感觉还行。然后给我30分钟,用纸和笔写下代码。(这里我写的是python,因为他们岗位要求python或者golang,但是他看见我写python的时候愣了一下然后说了一句“python也可以,不规定语言”,似乎python不是回答的首选语言)

然后就开始问问题,都是比较基础的题,我把回忆到的题归纳了一下。顺序不一定是当时面试顺序。

有哪些排序算法

这个是算法里面基础知识,当时回答了冒泡、插入、选择排序,快排、归并排序,堆排序。回来查一下,排序还有希尔排序、计数排序、桶排序、基数排序等等排序算法。这次没有问到其中哪种的具体实现。

linux的常用命令

问了查看内存占用的命令和创建文件夹的命令。就是考察linux的常用命令,看看有没有相关经验。可惜当时一个紧张死活想不起来查看内存命令是哪个了,而文件管理相关我都是用winscp于是也想不起来了,于是面试官补问了删除的命令,这个我终于答上了。(毕竟rm是个梗)所以linux的常规命令还是需要熟悉下记住的。

僵尸进程、孤儿进程

在类UNIX系统中,僵尸进程是指完成执行(通过 exit 系统调用,或运行时发生致命错误或收到终止信号所致)但在操作系统的进程表中仍然有一个表项(进程控制块PCB),处于”终止状态”的进程。—-wikipedia

在操作系统领域中,孤儿进程指的是在其父进程执行完成或被终止后仍继续运行的一类进程。—-wikipedia

孤儿进程会被init进程收养善后,没有危害。如果僵尸进程过多,则会大量占用系统的进程号,导致不能创建新进程。可以通过kill父进程,让僵尸进程被init进程收养善后。

附相关的知识“守护进程”:

在一个多任务的电脑操作系统中,守护进程英语:daemon/ˈdmən//ˈdmən/)是一种在后台执行的电脑程序。此类程序会被以进程的形式初始化。守护进程程序的名称通常以字母“d”结尾:例如,syslogd就是指管理系统日志的守护进程。

通常,守护进程没有任何存在的父进程(即PPID=1),且在UNIX系统进程层级中直接位于init之下。守护进程程序通常通过如下方法使自己成为守护进程:对一个子进程运行fork,然后使其父进程立即终止,使得这个子进程能在init下运行。这种方法通常被称为“脱壳”。

系统通常在启动时一同起动守护进程。守护进程为对网络请求,硬件活动等进行响应,或其他通过某些任务对其他应用程序的请求进行回应提供支持。守护进程也能够对硬件进行配置(如在某些Linux系统上的devfsd),运行计划任务(例如cron),以及运行其他任务。—-wikipedia

进程间通讯方式
  1. 管道(pipe),流管道(s_pipe)和有名管道(FIFO)
  2. 信号(signal)
  3. 消息队列
  4. 共享内存
  5. 信号量
  6. 套接字(socket)

进程间通讯主要是这6种通讯方式,要注意的是,pipe(无名管道)只能在父子进程之间通讯,要在任意两个进程直接通讯的话需要有名管道(FIFO)

TCP为什么需要三次握手和4次分手

这个据说是面试中的经典题,网上也有很多答案,此处就不贴了。

cookie和session的区别

cookie 和session 的区别:

1、cookie数据存放在客户的浏览器上,session数据放在服务器上。

2、cookie不是很安全,别人可以分析存放在本地的COOKIE并进行COOKIE欺骗
考虑到安全应当使用session。

3、session会在一定时间内保存在服务器上。当访问增多,会比较占用你服务器的性能
考虑到减轻服务器性能方面,应当使用COOKIE。

4、单个cookie保存的数据不能超过4K,很多浏览器都限制一个站点最多保存20个cookie。

5、所以个人建议:
将登陆信息等重要信息存放为SESSION
其他信息如果需要保留,可以放在COOKIE中

(以上摘自http://www.cnblogs.com/shiyangxt/articles/1305506.html)

也有其它相关的比较详细的解答可以参考https://www.zhihu.com/question/19786827

HTTP请求报文的结构

一个HTTP请求报文由请求行(request line)、请求头部(header)、空行和请求数据4个部分组成,下图给出了请求报文的一般格式。

典型的请求头有:

User-Agent:产生请求的浏览器类型。

Accept:客户端可识别的内容类型列表。

Host:请求的主机名,允许多个域名同处一个IP地址,即虚拟主机。

附相关内容:

  • 200 OK:客户端请求成功。
  • 301 redirect: 301 代表永久性转移(Permanently Moved)。
  • 302 redirect: 302 代表暂时性转移(Temporarily Moved )。
  • 400 Bad Request:客户端请求有语法错误,不能被服务器所理解。
  • 401 Unauthorized:请求未经授权,这个状态代码必须和WWW-Authenticate报头域一起使用。
  • 403 Forbidden:服务器收到请求,但是拒绝提供服务。
  • 404 Not Found:请求资源不存在,举个例子:输入了错误的URL。
  • 500 Internal Server Error:服务器发生不可预期的错误。
  • 503 Server Unavailable:服务器当前不能处理客户端的请求,一段时间后可能恢复正常,举个例子:HTTP/1.1 200 OK(CRLF)。
数据库是怎么样做索引的

应该是考察B树和B+树和相关内容,此处可以参阅

http://blog.csdn.net/suifeng3051/article/details/52669644

有哪些数据库引擎

面试官让我说出我记得的数据库引擎的名字,应该是考察有没有了解不同数据库引擎特征和区别。现在总结了一下主要这几种:

  • ISAM:执行读取操作的速度很快,而且不占用大量的内存和存储资源。不支持事务处理,也不能够容错
  • MYISAM:MYISAM是MYSQL的ISAM扩展格式和缺省的数据库引擎。强调了快速读取操作。

  • HEAP:允许只驻留在内存里的临时表格。驻留在内存里让HEAP要比ISAM和MYISAM都快,但是它所管理的数据是不稳定的,而且如果在关机之前没有进行保存,那么所有的数据都会丢失。
  • INNODB和BERKLEYDB:比ISAM和MYISAM引擎慢很多,但是INNODB和BDB包括了对事务处理外来键的支持

更详细可以参考:http://www.cnblogs.com/0201zcr/p/5296843.html

数据库单个表数据量量多大时需要做分表

先是问了我们项目的数据库数据量一般有多大,然后就问到了这个问题。在数据量多大的时候,查询速度会明显下降,我们需要进行分表操作。这个问题我至今仍不能确定答案。有说法是百万条到千万条的时候需要做分表。

计算字符串种类

面试最后的一题,算法题。有一个很大的TB级的文件,里面是一个一个字符串,用空格隔开。问里面有多少种字符串。例如aab和aab是一种,aab和aac是两种。使用一个分布式的系统解决。当时我提出使用map-reduce,一开始说按照字符串首几位分发,被提醒后改为按SHA1后的首几位分发,然后reduce的过程当时说得不太清楚,就说把种类加起来就可以了(已经被问到一愣一愣了)。现在觉得应该在每个系统维护一个哈希表,然后就可以在O(1)的时间内对单条记录计算种类累加了,最后表有多少项就是有多少种,把所有的加起来就是总的种类数了。此题可能有更好的解法。

面试小结:

面试问的基本都是计算机基础题,算法、操作系统、计网、数据库系统。然后还会问到项目的内容和项目相关的问题。可见基础在面试里面的比重非常的大,项目经历也要有,会根据项目经历问一些题目。没有问到python相关的问题,面试前几天把蛇书《python高性能编程》过了一遍,白看了。本来预计他4月才面试,才刚刚开始复习课本,没想到面试来得猝不及防,基础题回答得一塌糊涂。问完后他说找下一个面试官,然后出去没一会就回来了,说下一面面试官不在。当时就知道凉了。拒信在面试完第二天中午就发过来,HR一直都很有效率。。。