C语言及C++专项练习部分:


  1. C语言和C++中,赋值语句的返回值都是所赋的值。

  2. 结构化程序设计的思想包括:自顶向下、逐步求精、模块化、限制使用goto语句。

  3. fork()函数会把它所在语句以后的语句复制到一个子进程里,单独执行。如果printf函数最后没有"\n",则输出缓冲区不会被立即清空,而fork函数会把输出缓冲区里的内容也都复制到子进程里。

  4. c语言提供一种特殊的运算符,逗号运算符,优先级别最低,它将两个及其以上的式子联接起来,从左往右逐个计算表达式,整个表达式的百值为最后一个表达式的值。如:(3+5,6+8)称为逗号表达式,其求解过程先表达式1,后度表达式2,整个表达式值是表达式2的值,如:(3+5,6+8)的值是14

  5. static_cast 的用法
    static_cast < type-id > ( expression )
    该运算符把expression转换为type-id类型,但没有运行时类型检查来保证转换的安全性。它主要有如下几种用法:
    ①用于类层次结构中基类(父类)和派生类(子类)之间指针或引用的转换。
    进行上行转换(把派生类的指针或引用转换成基类表示)是安全的;
    进行下行转换(把基类指针或引用转换成派生类表示)时,由于没有动态类型检查,所以是不安全的。
    ②用于基本数据类型之间的转换,如把int转换成char,把int转换成enum。这种转换的安全性也要开发人员来保证。
    ③把空指针转换成目标类型的空指针。
    ④把任何类型的表达式转换成void类型。
    注意:static_cast不能转换掉expression的const、volatile、或者__unaligned属性。

  6. EOF
    在 C 语言中,或更精确地说成 C 标准函数库中表示文件结束符( end of file )。在 while 循环中以 EOF 作为文件结束标志,这种以 EOF 作为文件结束标志的文件,必须是文本文件。在文本文件中,数据都是以字符的 ASCII 代码值的形式存放。我们知道, ASCII 代码值的范围是 0~255 ,不可能出现 -1 ,因此可以用 EOF 作为文件结束标志。

  7. C++ static类成员,static类成员函数
    C++ static类成员,static类成员函数

  8. int (*p)[3]:定义了一个名为p的指针变量,该指针指向一个三元素数组,p是一个指针变量,可以重新赋值;
    int *p[3]:定义了一个名为p的数组,该数组有三个元素,每个元素都是一个指针,指针指向整形变量;

  9. 待续

操作系统专项练习部分

  1. 缓冲机制是用空间换取时间。

  2. 各进程采取互斥的方式,实现共享的资源称作临界资源。

  3. 重定位是把程序的逻辑地址空间变换成内存中的实际物理地址空间的过程,也就是说在装入时对目标程序中指令和数据的修改过程。
    重定位有两种,分别是动态重定位与静态重定位。
    静态重定位:即在程序装入内存的过程中完成,是指在程序开始运行前,程序中的各个地址有关的项均已完成重定位,地址变换通常是在装入时一次完成的,以后不再改变,故成为静态重定位。
    动态重定位:它不是在程序装入内存时完成的,而是CPU每次访问内存时由动态地址变换机构(硬件)自动进行把相对地址转换为绝对地址。动态重定位需要软件和硬件相互配合完成。

  4. 同一进程内的线程共享 1代码段 2数据段 3打开文件列表 线程私有 1线程id 2寄存器 3工作栈

  5. 抖动
    定义:从主存中刚刚换出的页面,根据请求立刻换入,反复换入换出的现象。
    抖动不会造成系统崩溃,只会导致CPU忙碌

    抖动产生的原因:
    置换算法选择不合适;(主要原因)
    物理内存数量不足;
    运行的进程太多。

  6. 分段对应的是内存具体存储管理的一种方式,是对具体内存进行管理,段号+基地址,分段尺寸最大为具体内存。在动态链接时先将主程序所对应的目标程序装入内存并启动运行,运行过程中需要调用某段时才将该段内存合并进行链接。
    而作业的大小不受内存大小限制,由虚拟存储器解决空间不够问题,允许作业装入的时候只装入一部分,另一部分放在磁盘上,当需要的时候再装入到主存,这样以来,在一个小的主存空间就可以运行一个比它大的作业。同时,用户编程的时候也摆脱了一定要编写小于主存容量的作业的限制。

  7. 互斥是两个进程或线程之间不可以同时运行,它们会互相排斥,必须等待其中的一个运行完,另一个才可以运行。而同步也是不可以同时运行,并且还需要按照某种顺序来运行。也可以说互斥是指某一资源同时只允许一个访问者使用,其他线程需要等待执行完毕再用,具有唯一性和排它性。但互斥无法控制对资源的访问顺序,而同步是在互斥的基础上实现对资源的有序访问。

  8. 磁盘允许一段时间内,多个进程交叉访问,对于每一时刻而言,只允许一个进程访问。

  9. 阵列的基础信息存放在所有磁盘的扇区尾部

  10. 内存是处理器可以直接访问的唯一大容量存储区域(数兆到数千兆字节)

  11. 易失存储:寄存器、高速缓存、主存、电子磁盘。非易失存储:电子磁盘、磁盘、光盘、磁带。

12.多处理器系统三个主要优点:增加吞吐量、规模经济、增加可靠性。

  1. 进程与程序的区别:
    (1)进程是动态的,程序是静态的:程序是有序代码的集合;进程是程序的执行。
    (2)进程是暂时的,程序是永久的:进程是一个状态变化的过程,程序可长久保存。
    (3)进程与程序的组成不同:进程的组成包括程序、数据、和进程控制块(即进程状态信息)
    (4)进程与程序的对应关系:通过多次执行,一个程序可对应多个进程;通过调用关系,一个进程可包括多个程序。

14.进程间通信机制:(1)共享内存(2)消息传递
消息传递对于交换少量数据很好用,易于实现(通常用系统调用实现)。
共享内存以最快的速度进行方便的通信。

常用通信机制:信号(signal)、共享存储区(shared memory)、管道(pipe)、消息(message)、套接字(socket)

当使用消息传递这一通信方式时,进程之间需要有通信线路,通信线路的逻辑实现有三种方法:
直接通信或间接通信、同步或异步通信、自动或显式缓存。

一、直接通信或间接通信
通过直接通信搭建起的通信线路有着以下属性:
(1)自动建立通信线路
(2)一个线路只能在两个进程之间搭建
(3)每对进程之间只能有一个线路
(4)链接可以是单向的,但是通常是双向的

通过间接通信搭建起的通信线路有着以下属性:
(1)只有进程间共享一个mailbox时,线路才可以搭建
(2)一条线路可以在多个进程之间搭建
(3)两个进程之间可能有多个不同的线路
(4)链接可以是单向或者双向的

二、同步或异步通信
同步-阻塞、异步-非阻塞

当send和receive都阻塞,则在发送者和接受者之间有一个集合点。

三、缓存
不管通信直接或者间接,通信进程交换的消息都在临时队列中-缓存
队列实现三种方法:
零容量、有限容量、无限容量

  1. 管道(pipes)
    两种管道-ordinary pipes、named pipes
    普通管道不能从创建其的进程外部访问,通常由父进程创建,与其子进程通信(windows调用这些管道)单向
    命名管道不需要父子关系就可以访问(UNIX与Windowsx系统都提供)双向

16.资源拥有单位称为进程(或任务),调度的单位称为线程、又叫轻型进程(light weight process、LWP)
线程只拥有一点在运行中必不可少的资源(程序计数器、一组寄存器和栈),但他可与同属一个进程的其他线程共享进程拥有的全部资源

线程定义为进程内一个执行单元或一个可调度实体。

线程的特点:
不拥有系统资源(只拥有少量的资源,资源是分配给进程的)
一个进程中的多个线程可以并发执行(进程可创建线程执行同一程序的不同部分)
系统开销小、切换快。(进程的多个线程都在进程的地址空间活动)
线程共享的内容:代码段,数据段,操作系统资源

线程的优点:
创建一个新线程花费时间少
两个线程的切换花费时间少
由于同一进程内的线程共享内存和文件,因此他们之间的相互通信无需调用内核
适合多处理器系统

17.线程的实现机制
用户级线程、内核级线程、两者结合方法

用户级线程:不依赖OS核心,应用程序利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程
特点:用户线程的维护由应用进程完成;内核不了解用户线程的存在;用户线程的切换不需要内核特权;用户线程调度算法可以针对应用优化;一个线程发起系统调用而阻塞,则整个进程在等待(多对一模型中)
三个基本的线程库:POSIX Pthreads、Win32 threads、Java threads

内核级线程:依赖OS核心,一个线程发起系统调用而阻塞,不会影响其他线程。时间片分配给线程,所以多线程的进程获得更多CPU时间
example:windows xp及以后、Solaris、Linux、Mac OS X

18.三种多线程模型:多对一、一对一、多对多
多对一中的缺点:一个线程阻塞,整个进程阻塞
一对一缺点:开销可能过大
多对多缺点:复杂的编程模型、信号处理复杂

19.线程库的两种实现方法
(1)没有内核支持的库:代码和数据结构都在用户空间,只导致用户空间中本地函数调用(而不是系统调用)
(2)由操作系统直接支持的内核级库,代码和数据结构都在内核空间,通常导致系统调用

20.多线程编程创建与管理复杂,一种流行解决方法:隐私线程
将线程的创建与管理交给编译器和运行时库来完成
几种设计方法:线程池、Fork and Join、OpenMP、Grand Central Dispatch(GCD、大中央调度)、Intel Thread Building Blocks(TBB)、Java

  1. fork()与exec()
    fork()有的Unix系统有两种形式的fork(),与应用程序有关
    (1)复制所有线程:如果调用fork()后不调用exec(),复制所有线程。
    (2)只复制调用fork()的线程:如果调用fork()后立即调用exec(),操作系统只需复制调用fork()的线程

exec():如果一个线程调用exec(),exec()参数指定的程序会替换整个进程(包括所有线程)

22.线程取消:在线程完成之前终止线程的任务,要取消的线程称为目标线程
线程取消的两种情况:
(1)异步取消:由一个线程立即终止目标线程。
ps:对于异步取消,如果在已经给目标线程分配资源或者目标线程正在更新与其他线程共享的数据情况下,操作系统回收系统资源时不能将所有资源全部回收。
(2)延迟取消:目标周期性地检查其是否应该终止,允许目标线程以有序方式终止自己。

23.Windows XP Threads
一对一模式
每个线程包括:线程id、寄存器集合、一个用户栈和一个内核堆栈、一个私有存储区域

同属一个进程的每个线程都能访问进程的地址空间。

1) ETHREAD:执行线程块,包括指向线程所属进程的指针、线程开始控制的子程序的地址、指向KTHREAD的指针。
2) KTHREAD:内核线程块,包括线程的调度和同步信息、指向内核栈的指针、指向TEB的指针
3) TEB:用户空间的数据结构,供线程在用户模式下运行时访问,包含许多其他域、用户模式栈、用于线程特定数据的数组。

24.Linux Threads
不区分进程和线程,通常称之为任务(task)
系统调用fork()提供进程复制功能,系统调用clone()提供进程创建功能
调用fork()时,所创建的新任务具有父进程所有数据的副本;调用clone()时,所创建新任务根据所传递标志集指向父任务的数据结构。

25.CPU调度的时机:
switch from running to waiting state
switch from running to ready state
switch from waiting to ready
terminates
以上1,4情况为非抢占式调度,2,3为抢占式调度

26.Dispatcher(调度程序)
调度程序的主要功能:
切换上下文、切换到用户模式、跳转到用户程序的合适位置,以重新启动程序
调度程序停止一个进程到启动一个进程所需要的时间叫做调度延迟

27.解决进程饥饿的策略:aging(老化)-随着进程的滞留时间提升进程的优先级

  1. I/O几种方式:轮询、中断、DMA
    DMA:直接内存访问
    用来避免处理大量数据移动时按字节来向控制器送入数据的问题
    需要DMA控制器
    绕过CPU直接在内存与I/O设备之间进行数据传输

29.大多数操作系统存在后门,允许应用程序将任何命令透明的传给设备控制器。对UNIX,这个系统调用是ioctl()。系统调用ioctl能使应用程序访问由设备驱动程序实现的一切功能。Ioctl有三个参数,第一个文件描述符,引用某一个硬件设备;第二个是整数,来确定哪个命令;第三个是内存中的指针,使得应用程序和控制器传输任何必要的命令信息或数据。

30.字符流设备按一个字节一个字节传输,块设备以块为单位进行传输。
顺序设备按固定顺序来传输数据,随机访问设备可以寻找任意数据存储位置。
同步设备按一定响应时间来进行数据传输,异步设备呈现的是无规则或不可预测的响应时间。
共享设备可以被多个进程或线程并发使用,而专用设备不能。
操作速度从每秒几个字节到每秒数G字节
有的设备能读能写,有的设备只能做单一操作。

31.操作系统内核与I/O有关服务:I/O调度(I/O scheduling)、缓冲(buffering)、高速缓存(caching)、假脱机(spooling)、设备预订(device reservation)、错误处理(error handling)

缓冲与高速缓存的差别是缓冲只是保留数据仅有的一个现存拷贝,而高速缓存只是提供了一个驻留在其他地方的数据的一个高速拷贝。
高速缓存和缓冲是两个不同的功能,但有时一块内存区域也可以同时用于两个目的。
当内核接收到I/O请求时,内核首先检查高速缓存以确定相应文件的内容是否在内存中。如果是,物理磁盘I/O就可以避免或延迟。

假脱机技术,是一种操作系统可以用来协调并发输出的方法

32.现代磁盘驱动器可以看做是一个一维的逻辑块的数组,逻辑块是最小的传输单位。逻辑块的大小通常为512B
一维逻辑块数组按顺序映射到磁盘的扇区,扇区0是最外面柱面的第一个磁道的第一个扇区。

33.磁盘管理:
低级格式化,或者物理格式化,是指将磁盘划分为扇区以便磁盘控制器能读和写。
为了使用磁盘存储文件,操作系统还需要将自己的数据结构记录在磁盘上,分为两步,第一步为分区(partition)和逻辑格式化(创建文件系统)

34.启动块(boot block)
用于启动电脑时,初始化系统的方方面面,从cpu寄存器到设备控制器和内存,接着启动操作系统。
自举加载程序(较小)一般存放在ROM中,负责进一步从磁盘上调入更加完整的自举程序。磁盘上的自举程序可以轻易的修改,拥有启动分区的磁盘称作启动磁盘或系统磁盘。

35.交换空间太大容易造成浪费
交换空间太小容易造成死机现象:中断进程或使整个系统死机

36.RAID
Raid 2:内存方式的差错纠正代码结构,内存系统中的每个字节都有一个相关奇偶位,以记录字节中置为1的个数是偶数还是奇数
Raid3和Raid4:奇偶校验码和其它磁盘的相应扇区或块一起用于恢复出错磁盘的扇区和块。
Raid5:将数据和奇偶校验分布在所有N+1块磁盘上
Raid6:保存了额外的冗余信息以防止多个磁盘出错,每4个位的数据使用了2个位的冗余数据,这样系统可以容忍两个磁盘出错。
Raid0+1:raid0和raid1的组合,raid0提供性能,raid1提供可靠性。一组磁盘分散成条,每一条再镜像到另一条。RAID0+1允许坏多个盘,但只能在坏在同一个RAID0中,不允许两个RAID0都有坏盘
Raid1+0:先镜像,再分散。如果单个磁盘不可用,其它镜像仍如其它磁盘一样可用。RAID1+0允许坏多个盘,只要不是一对磁盘坏就可以
RAID 1+0在整体容错能力和恢复代价上比RAID 0+1更有优势,所以更为常用。

37.网络文件系统(NFS)是一种常见的分布式文件共享方法。

38.three classes of users:owner access、group access、public access.

39.文件系统位于辅助存储(磁盘)上,文件控制块(FCB)包含文件的信息,如拥有者、权限、文件内容的位置。
分层设计的文件系统如下:
图片说明
Application Programs:The code that's making a file request

逻辑文件系统
管理元数据:文件系统的所有结构数据,而不包括实际数据(或文件内容)
根据给定符号文件名来管理目录结构
逻辑文件系统通过文件控制块(FCB)来维护文件结构

文件组织模块
文件组织模块可以将逻辑块地址转换成基本文件系统所用的物理块地址。每个文件的逻辑块按从0或1到N来编号,而包含数据的物理块并不与逻辑号匹配,因此需要通过翻译来定位块。
空闲空间管理器用来跟踪未分配的块并根据要求提供给文件组织模块。

基本文件系统
向合适的设备驱动程序发送一般命令就可对磁盘上的物理块进行读写

I/O控制
由设备驱动程序和中断处理程序组成,实现内存与磁盘之间的信息转移

40.操作系统类型:FAT(MS-DOS文件系统)、FAT32(win98文件系统)、NTFS(NT文件系统)、S51K/S52K(AT&T UNIX sysv)、EXT(Linux文件系统)、ext2、3、4(Linux文件系统)、HPFS(OS/2高性能文件系统)、UFS(UNIX文件系统)、iso9660(CD-ROM文件系统)、proc(Linux虚拟文件系统)、NFS(网络文件系统)、VFS(Linux虚拟文件系统)、ZFS(Open Solaris文件系统)、LTFS(Liner Tape File System 线性磁带文件系统)、APFS(Apple File System)
其中EXT为专门为Linux设计的文件系统,特点,速度最快,CPU占用率最小,目前支持分区的操作系统为Linux和Android

41.文件系统目录实现
线性列表(Linear List):简单但运行费时
哈希表(hash table):增加哈希表的线性列表,缺点,需要避免冲突,哈希表的最大困难是其通常固定的大小和哈希函数对大小的依赖性。

42.磁盘文件分配方法
Contiguous allocation(连续分配):存在外部碎片问题
Linked allocation(链接分配)
Indexed allocation(索引分配):随机访问,没有外部碎片问题,但是有索引块的开销
Unix、Linux直接间接混合分配方法

43.原子操作
指不需要中断即可完成的操作

44.进程两个最基本特性:并发性、独立性

  1. critical-section
    临界区,访问临界资源的进程代码段。临界资源为一次只允许一个进程使用(访问)的资源
    临界区问题解答必须满足三点要求:互斥(Mutual Exclusion)、空闲让进(progress)、让权等待(bounded waiting)

46.信号量(Semaphores)
整型信号量、记录型信号量、AND型信号量,信号量集、二值信号量
二值信号量也叫做互斥锁(mutex locks)

wait(S){
while(S<0){
;//no-op
S--;
}

signal(S){
S++;
}
上述信号量实现主要缺点在于忙等待,浪费了CPU时钟,克服忙等待的信号量叫做自旋锁。
自旋锁需要修改信号量S定义为:
typedef struct{
int value;
struct process *list;
}semaphore;
此时wait操作修改为:
wait(semaphore *s){
S->value--;
if(S->value<0){
add this process to S->list;
block;
}
}
signal操作修改为:
signal(semaphore *s){
S->value++;
if(S->value<=0){
remove a process P from S->list;
wakeup(P);
}
}
其中block()操作为把进程由running转换为waiting、wakeup()操作为把进程由waiting转换为ready。

47.信号量的物理含义:
S.value>0 表示有S.value个资源可用;
S.value=0 表示无资源可用或表示不允许进程再进入临界区;
S.value<0 则|S.value|表示在等待队列中进程的个数或表示等待进入临界区的进程个数。
wait(S)≡P(S)≡down(S):表示申请一个资源
signal(S)≡V(S)≡up(S):表示释放一个资源

wait、signal必须成对出现,一般情况下:当为互斥操作时,他们处于同一进程;当为同步操作时,则不在同一进程中出现。如果两个wait操作相邻,那么它们的顺序至关重要,而两个相邻的signal操作的顺序无关紧要。一个同步wait操作与一个互斥wait操作在一起时,同步wait操作在互斥wait操作前。

48.信号量同步的缺点:
同步操作分散:信号量机制中,同步操作分散在各个进程中,使用不当就可能导致各进程死锁(如wait、signal操作的次序错误、重复或遗漏)。
易读性差:要了解对于一组共享变量及信号量的操作是否正确,必须通读整个系统或者并发程序;
不利于修改和维护:各模块的独立性差,任一组变量或一段代码的修改都可能影响全局。
正确性难以保证:操作系统或并发程序通常很大,很难保证这样一个复杂的系统没有逻辑错误。

49.产生死锁的四个必要条件:
互斥、占有并等待、非抢占、循环等待

50.死锁预防(Prevention)、死锁避免(Avoidance)
确保死锁不会发生
死锁预防:资源静态预分配方式、限制资源申请、资源的有序申请

安全状态不是死锁状态,死锁状态一定是不安全状态。

死锁避免:确保系统不会进入不安全状态
资源分配图算法、银行家算法

51.死锁检测、死锁恢复
指在死锁发生后进行处理
打破死锁两种方法:进程终止,抢占资源

52.地址绑定发生时间:编译时,加载时,执行时

53.