https://www.youtube.com/playlist?list=PLu77E6J7s6Ko3Ft4XcOX1yKW6iX3eEFqS
文件权限分为owner(所有者)、group(组)和other(其他人)三部分,对应读(r)、写(w)和执行(x)三种权限。
每个文件创建时,系统会根据用户的umask值来设定默认权限。umask用于控制程序创建文件时允许设定的默认权限。
umask用八进制表示,每个数字代表一个权限 bits。默认值为077,表示group和other无法写入。将umask改为000后,程序可以自由设定所有权限。
每个文件除了拥有一个owner外,还有一个group属性。group代表若干用户可以共享该文件。
通过groups命令可以查看用户所在的group。文件第二栏group显示该文件的组,不同用户可能属于同一个group,共享此文件。
当程序试图设置某组权限时,系统会进行与umask的值的位运算,采取umask的反值,这样就可以实现umask的限制作用。
例如设置为RW-RW-RW-,遇到umask为0的情况下可以正确设置,但遇到umask为077的情况下,会屏蔽 group 和 other 的写入权限。
程序可以修改umask结果设定自己想要的默认权限,但一般来说,umask给用户控制程序设置权限的能力。
第一个作业是通过连接不同演员之间的合作关系,计算出两名演员之间的“六度分割”距离。
使用 IMDB 数据库,运行 search 文件计算两名演员(例如Meryl Streep 和 Jack Nicholson)之间最短的合作关系链。
这个作业旨在回顾 C/C++ 的基础知识,为之后课程做准备。
后续扇区分为两部分:
Version 6文件系统利用元数据和数据分配在磁盘不同区域,实现文件快速定位和高效读取。
课程最后给出三个例子,对文件系统操作具体流程进行解析,有助于理解Version 6文件系统和编程任务二的实现。
Linux系统会为每个进程维护一个进程控制块(process control block),存储进程相关信息。进程控制块中包含一个描述符表(descriptor table),记录进程打开的文件描述符。
文件描述符用于进程与文件系统交互,如读写文件。最常用的文件描述符0、1、2分别对应标准输入、标准输出和标准错误。
Linux系统还会维护一个打开文件表(open file table),为各个进程共享。打开文件表中每个条目对应一个打开文件,存储 mode(只读、只写等)、当前文件的读取位置(cursor)以及引用计数(ref count,记录对应文件描述符的数量)等信息。
文件描述符指向 openings 文件表中的特定条目。当文件被多个进程打开时,它们会指向打开文件表中的同一个条目,从而实现文件共享。
每一个打开文件表条目还会链接到一个V节点(V node),它缓存文件相关的元数据,如文件长度、时间戳等,以提高效率。
系统调用是用户空间程序请求操作系统内核服务的接口。常见的系统调用包括读写文件、创建删除文件、进程相关的fork、exec等。
系统调用的特点是:
多处理是利用多核CPU实现任务并行的一种编程模型。与同步编程不同,多处理中每个进程独立运行,不需要等待其它进程。
支持多处理的编程语言包括C、Go等。可以通过函数fork实现并行执行多个任务,或者使用消息传递在多个进程间进行通信协同工作。
execvp是一种新的进程创建机制。它允许进程运行其他程序,从而实现程序之间的合作。
Fork从本质上创建了一个新的进程,这个新进程与父进程几乎一模一样,但它们各自有独立的内存空间。
Fork的一个限制是,它只适合用于简单的进程模型。在多线程环境中,Fork无法很好地工作。
execvp会替换当前进程空间,加载并执行指定的程序。这意味着:
这样可以很好地支持脚本语言和 pipes机制。父进程可以启动子进程运行其他程序,然后等待结果。
Fork后,父子进程会共享打开的文件描述符。但是使用execvp后,文件描述符不再共享。
这使得可以在脚本中打开文件,然后使用execvp运行其他程序时,文件还保持打开状态。实现了 Files输入/输出的重定向。
execvp有几个使用限制:
所以在使用execvp前需要提前准备程序路径等信息。
理解进程、文件描述符、内存模型等概念。掌握C语言编程基础,能独立阅读源代码和API文档。
程序模拟一个父进程带5个子进程去迪士尼游玩:
此程序演示了如何使用SIGCHLD信号跟踪子进程状态,并使用waitpid获取详细信息。
sleep函数在收到信号时会提前返回,这和父进程根据子进程状态循环判断的逻辑不符。
应使用自定义的snooze函数,令其忽略SIGCHLD信号,这样父进程睡眠不会被信号提前唤醒。
进程间使用信号时很容易出现竞争条件,如果信号处理函数和主进程代码没有正确同步,可能会导致程序逻辑错误。
例如使用sleep让子进程暂停,主进程添加任务到任务队列,但信号处理函数 printer 先打印”任务移除”的消息,这不合逻辑。
可以使用sigprocmask系统调用 blockade 特定信号,避免在添加任务前信号处理函数被调用。执行后再使用sigprocmask解除封锁。
函数execve会覆盖原进程,信号处理器回调会消失。但进程ID不变,子进程结束后信号还是会被调用。
死锁可能发生在多个进程试图持有对方已持有的资源时。必须谨慎设计并发算法,避免这种情况。
例如实现银行家算法:每个进程申请资源前,检查整个系统是否存在安全序列能满足所有进程需求。若不存在,拒绝申请。
另外通过消息传递来改善同步问题。每个进程只调整自己的状态或资源,不直接影响他进程。
避免一个进程长时间占用共享资源而阻塞其他进程。尽量减少关键区代码,防止引入不必要的同步。
使用信号量和条件变量进行同步,避免直接使用互斥锁。因为死锁更容易发生在对多个锁的持有上。
Pipeline需要两个参数:
Pipeline首先fork第一个子进程,然后fork第二个子进程。第一个子进程的标准输出通过管道输入到第二个子进程的标准输入。
具体如何实现:
cat test.txt | sort
子进程需要一个struct,包含:
子进程通过文件描述符与父进程进行通信:
跟踪函数使用Ptrace系统调用跟踪其他进程的系统调用事件:
输出包含:
和简单跟踪类似,不同之处在于输出更详细的系统调用信息:
人:很好,你总结得很完整。但有些细节可以明确一点,比如:
Pipeline的两个子进程分别是cat和sort
子进程结构里,是否获取子进程输出对应文件描述符读子进程输出,是否提供子进程输入对应文件描述符写子进程输入
跟踪函数使用Ptrace让父进程可以跟踪子进程,而不是直接跟踪其他进程
系统调用号映射表和错误码映射表用于将编号映射为名称和描述
其他enerate不需要修改,请根据我的意见修改一下你的笔记。
多线程程序可以同时运行多个任务,使得CPU资源得到更充分利用。
C++标准线程库(std::thread)可以创建线程。
#include <thread>
void function() {
// 该函数将在新线程中执行
}
int main() {
std::thread t(function); // 创建新线程
t.join(); // 等待新线程结束
return 0;
}
信号量sem可以用于线程同步。信号量初值为0,调用sem.post()增加1,sem.wait()减少1。
#include <semaphore>
std::semaphore sem(0);
void thread1() {
// ...
sem.post();
}
void thread2() {
sem.wait();
// ...
}
互斥量mutex可以防止多个线程同时访问共享资源,避免竞争条件。
#include <mutex>
std::mutex mutex;
void thread_func() {
std::lock_guard<std::mutex> lock(mutex);
// 访问共享资源
}
条件变量cond_var可以让一个线程等待,直到某个条件满足。
std::mutex mutex;
std::condition_variable cond;
void thread1() {
std::unique_lock<std::mutex> lock(mutex);
// 条件不满足,等待
cond.wait(lock);
// 条件满足,继续
}
void thread2() {
// 改变条件
cond.notify_one();
}
而lock_guard和unique_lock用来自动上锁和解锁mutex。
时间:周四6点至8点,在Hewlett 200教室举行(和本课不同教室)
使用BlueBook在线考试软件进行答题
考试采取编程问题、输出判断问题和简答问题混合形式
考生需要提前在电脑上安装并测试BlueBook软件
考试期间提供功能参考表,但不允许使用其他资源
考试采用密封式,考前给出密码后软件即开始计时
考完后答题直接提交到后台自动评分
考生电脑电池持续时间不足需要提前联系老师寻找备用电脑
实现Shell基本功能:启动、后台运行、前台切换等
处理信号量:Ctrl+C、Ctrl+Z不终止Shell本身
设置管道连接多个 processo
跟踪和管理所有进程状态
测试通过程序或驱动程序
使用sigchild处理程序结束信号
区分Shell和子进程信号处理
重建管道连接不同进程标准输入输出
依次完成各个阶段进行测试
注重测试,积累问题解决经验
设计 robust 信号处理器
实现正确的管道连接
追踪和管理大量进程状态
将各部分模块组合起来
找到问题并进行调试
这就是著名的“Dining Philosophers”问题,常用于多线程和同步机制的学习。它直观展示了在共享资源访问方面的潜在冲突,以及避免死锁的重要性。
互斥锁可以解决多线程访问共享资源时的竞争条件问题。
一个线程想获取互斥锁时,如果锁已经被其他线程获取,那么它会被阻塞等待。等到持有锁的线程释放锁后,等待线程才能继续运行并获取锁。
互斥锁本身无法实现线程间的通信和同步。如果一个线程需要等待另一个线程完成某个操作,那么就需要条件变量。
条件变量可以让等待线程阻塞,直到其他线程通知它恢复运行。
信号量用来控制对共享资源的访问 permits 数量。每个信号量都有一个值为非负整数的 permits。
线程需要获取信号量时,会减少 permits 值。释放信号量时,会增加 permits 值。如果 permits 为 0,获取信号量的线程会阻塞,直到有其他线程释放信号量,增加 permits 值。
pthread_mutex_t mutex;
void *thread_func() {
pthread_mutex_lock(&mutex);
// 访问共享资源
pthread_mutex_unlock(&mutex);
}
pthread_mutex_t mutex;
pthread_cond_t cond;
void *producer() {
pthread_mutex_lock(&mutex);
// 产生数据
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
}
void *consumer() {
pthread_mutex_lock(&mutex);
pthread_cond_wait(&cond, &mutex);
// 消费数据
pthread_mutex_unlock(&mutex);
}
sem_t sem;
sem_init(&sem, 0, 1);
sem_wait(&sem);
// 访问资源
sem_post(&sem);
这堂课将通过实践模拟一个冰淇淋店的工作流程。
顾客:会询问需要多少个冰淇淋甜筒,并指派服务生制作。支付后取号,到收银台结账。
服务生:每个被指派都需要为顾客制作一个冰淇淋甜筒。制作完将甜筒呈现给经理,等待批准。如果不合格需要重新制作。
经理:审核服务生所做的冰淇淋甜筒是否合格。合格即批准,不合格需要重做。
收银员:在服务生都处理完订单后,收银员负责顾客的付款流程。
顾客指派指定数量的服务生为他制作冰淇淋甜筒。
服务生为顾客制作一个冰淇淋甜筒,呈现给经理。
经理审核冰淇淋甜筒质量,合格即批准,不合格则重做。
所有冰淇淋甜筒制作完毕后,顾客前往排队付款。
收银员完成指定数量顾客的付款后开店结束。
本次模拟使用线程技术来实现顾客、服务生、经理等不同角色同时处理工作的场景。
其中包括:
这些线程技术可以很好地模拟冰淇淋店的实时并发工作流程。
网络是指连接两个或多个计算机的技术。它可以是在同一台计算机内两个进程之间,也可以是不同计算机之间。
网络通信需要一个计算机作为服务器,等待其他计算机的请求。其他计算机作为客户端,向服务器发出连接请求。
世界宽根网即通过此模式工作,用户通过浏览器连接各种网站服务器。
网络通信通过套接字实现。套接字是一个16位整数,范围在0-65535。它代表一个虚拟进程ID。
服务器告诉操作系统监听某个套接字(通常也叫端口),当客户端连接请求来时,操作系统会触发服务器程序处理这个连接。
常见的网络通信协议有:
用netstat命令可以查看本机打开的网络连接及监听的端口:
netstat -antl
也可以通过浏览器查看本机打印机服务 127.0.0.1:631
IP地址采用32位数字表示,为了方便记忆采用”点分十进制”格式记录。全球超过42亿个网络设备正在使用更多的IP地址。
TCP/IP协议套件是internet工作的基础。它通过路由器将单一IP地址映射到内部多个局域网IP,解决了32位IP容量不足的问题。
网络分为客户端和服务器端。客户端发起请求,服务器端响应。
大多数网站的URL开始为HTTP://或HTTPS://。HTTPS表示安全连接,数据传输经过加密。
URL包含主机名和路径。例如web.stanford.edu/class/cs110。主机名为web.stanford.edu,路径为/class/cs110。
默认路径为/,表示无路径。
用于解析URL的函数会返回主机名和路径作为pair返回。
默认网络端口号为80。网页服务器通常监听80端口。
使用wget url可以从网站下载页面到本地文件。内部实现了GET请求。
创建Socket对象,连接到服务器指定端口。
创建流对象,用于读写数据。
构建HTTP请求,格式为:
GET /path HTTP/1.0
Host: hostname
请求结束标识为\r\n。
跳过HTTP头,只取网站主体内容。
将内容保存到本地文件。
\r代表回车,将写到行首。\n代表换行。两者结合表示结束一行。
HTTP请求第一行包含METHOD(GET)、路径和HTTP版本。
第二行为Host标题,包含目标主机名。
请求结束标识为\r\n\r\n。
服务器响应也包含状态行和多个Header行。
可以请求压缩等格式,需要自行解压缩。
Socket和流对象设置需要目标主机和端口作为参数。
struct hostent {
struct in_addr addr; // IPv4地址,unsigned int类型
char *name; // 官方主机名
char **aliases; // 别名列表
int addrtype; // IPv4或IPv6等
int length; // 地址长度
char **addrlist; // 地址列表
}
网络代理是一个位于客户端(例如浏览器)和目标 web 服务器之间的中间服务器。它可以起到几个作用:
网络代理可以根据策略来阻止或允许访问某些网站。比如公司可以限制员工上非工作相关网站,学校可以限制学生上色情网站等。
通过多次加密传输请求,Tor网络可以完全匿名化用户的网络活动原点。这对于那些担心政府监视的用户很有用。但是,利用外部信息还是能暴露用户真实活动,例如根据同一时期网络使用情况来推断潜在用户。
网络代理可以根据文件类型来限制下载。比如飞机上的网络通常会限制视频流流量。
一些网络代理会修改 passing through 的网络内容。例如有人设置无线hotspot 时,设计代理翻转或者模糊所有图片,往往可以阻止他人非法连接wifi。
网络代理可以拦截流量,然后将其转发到不同的目标服务器。这就是无线接入点在机场工作的原理。
MapReduce 程序通常会用多个 intermediate 服务器对大量数据进行分布式处理。它需要结合多线程、同步机制将复杂任务分解成独立的步骤,再进行Results 归并。
网络代理可以用来过滤网站、匿名化网络访问、限制文件类型、修改内容、调度请求顺序等。不同场景下有不同应用,需要结合技术细节一起设计。
MapReduce是一种分布式计算框架,它通过map和reduce两个步骤来处理大数据问题。
map过程将数据拆分成小块,分配给不同的服务器进行处理。
具体来说,它会将大量数据拆分成许多小块数据片段,分配到各个节点进行并行处理。每个节点仅负责处理自己分配到的数据块,执行指定的map函数对数据进行转换输出作为结果。
reduce过程将map输出结果进行汇总。
它会将map输出的不同结果分组,然后对同一组内的数据进行归约,产生最终的计算结果。这一过程需要将分布在各个节点的数据通过网络传输拉取回来,最后在一台机器上汇总输出。
map阶段:将输入数据集拆分成一小块一小块的数据表示。对每一小块数据都执行用户指定的map函数,产生一系列的(中间键,中间值)对。
排序阶段:系统自动将所有(中间键,中间值)对按中间键进行排序。
reduce阶段:系统自动对中间结果进行分组,把相同键值的记录归系到一起,作为输入传递给reduce函数,针对每个中间键调用一次reduce函数,产生最终输出结果。
整个任务运行在一组机器组成的集群上,数据在各个机器间进行传输,MapReduce框架会自动处理并行化,容错等事宜。
支持大规模并行计算。可以利用大量廉价机器实现海量数据的分布式高效计算。
易于编程。开发者仅需实现map和reduce两个函数,框架会自动进行数据分布、任务调度、处理故障等。
异常容错能力强。如果一个节点故障,其它节点可以接管任务计算,整体计算不受影响。
扩展性强。程序运行在多台机器上,可以无限扩展计算能力实现对更大数据规模的支持。
抽象是指将程序所做的事情从实现细节中独立出来。
一个例子是排序程序,排序程序的接口是传入一组数据并返回排序后的结果,但排序的实现方式取决于具体算法。
其他抽象例子包括:
文件系统与低级读写的区别。抽象后让读写更容易使用。
进程操作接口如fork与实际如何实现分叉的差别。
线程如何运行的实现细节被抽象隐藏。
HTTP定义了网络数据传输格式和消息,但不需要了解底层传输细节。
模拟化是将一个大型系统分解成许多个小模块。
比如复印机可以分为以下模块:
每个模块负责的功能不同,但共同完成复印任务。
命名主要解决计算机使用数字而人类使用名称的差异问题。比如文件系统中路径名到inode编号的映射。
操作系统虚拟化和硬件虚拟化。操作系统虚拟化通过隔离给每个进程提供独立环境。硬件虚拟化虚拟出多个计算机。
并发是此课程重点,包括进程、线程、互斥锁等概念。
不仅网络本身,任何两个程序通信都会有请求响应模式,比如客户端服务端通信。
IO操作可以分为阻塞IO和非阻塞IO。
阻塞IO:读写操作会阻塞进程,直到有数据返回。例如read()和write()系统调用。
非阻塞IO:读写可能立即返回,即使没有数据,此时返回的字节数为0。
IObound:程序执行被IO操作限制,CPU处于等待状态。例如网络通信。
CPUbound:程序执行被CPU计算限制,CPU忙于计算无法进行其他任务。例如数字运算。
要实现非阻塞IO,需要操作系统的支持,比如支持非阻塞读写系统调用。
系统调用包括:
快速系统调用:立即返回,如获取时间。
阻塞读写系统调用:read(),write()会阻塞等待数据传输完成。
通过多线程/进程实现:
将阻塞IO操作放在独立线程中执行。
主线程可以处理其他任务,同时其他线程处理IO操作。
CPU利用率提高,在等待IO时可以进行其他计算。
避免了线程blocked,更高效地利用CPU。
Linux系统提供了非阻塞读写系统调用如read(),write(),可以实现非阻塞IO。