C语言（C++）作业_c++作业

一、指针和内存泄露

1. malloc函数

malloc的全称是memory allocation，中文叫动态内存分配，用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址，当无法知道内存具体位置的时候，想要绑定真正的内存空间，就需要用到动态的分配内存。 void* 类型表示未确定类型的指针。C,C++规定，void* 类型可以通过类型转换强制转换为任何其它类型的指针。malloc 一般需和free函数配对使用。

注意：

（1）若申请内存空间较大时，就会申请失败，返回空指针。所以申请后一定要判定指针是否为空。
（2）使用malloc（）申请的内存，必须进行释放，否则会出现“内存泄露”的问题。

2. 内存泄漏

指程序中己动态分配的堆内存由于某种原因程序未释放或无法释放，造成系统内存的浪费，导致程序运行速度减慢甚至系统崩溃等严重后果。当在程序中反复使用molloc函数申请内存空间，但并没有使用free函数来进行空间释放，系统内存越来越少，最终导致内存不足。

内存泄漏的几种情况：

（1）指针重新赋值

看下面一段示例代码：

char * p = (char *)malloc(10);
char * np = (char *)malloc(10);

其中，指针变量 p 和 np 分别被分配了 10 个字节的内存，它们各自的内存如图 1 所示。

如果程序需要执行如下赋值语句：

p=np;

这时候，指针变量 p 被 np 指针重新赋值，其结果是 p 以前所指向的内存位置变成了孤立的内存，如图 2 所示。它无法释放，因为没有指向该位置的引用，从而导致 10 字节的内存泄漏。
 因此，在对指针赋值前，一定确保内存位置不会变为孤立的。

（2）错误的内存释放

假设有一个指针变量 p，它指向一个 10 字节的内存位置。该内存位置的第三个字节又指向某个动态分配的 10 字节的内存位置，如图 3 所示。

如果程序需要执行如下赋值语句时： 

free(p);

很显然，如果通过调用 free 来释放指针 p，则 np 指针也会因此而变得无效。np 以前所指向的内存位置也无法释放，因为已经没有指向该位置的指针。换句话说，np 所指向的内存位置变为孤立的，从而导致内存泄漏。
因此，每当释放结构化的元素，而该元素又包含指向动态分配的内存位置的指针时，应首先遍历子内存位置（如本示例中的 np），并从那里开始释放，然后再遍历回父节点，如下面的代码所示： 

free(p->np);
free(p);

（3）返回值的不正确处理

有时候，某些函数会返回对动态分配的内存的引用，如下面的示例代码所示：

char *f()
{
    return (char *)malloc(10);
}
void f1()
{
    f();
}

很明显，函数 f1 中对 f 函数的调用并未处理该内存位置的返回地址，其结果将导致 f 函数所分配的 10 个字节的块丢失，并导致内存泄漏。

（4）程序执行不到free（）就跳出

void Fun()
{
	int *p = (int*)malloc(sizeof(int)* 10);
	if (p == NULL)
	{
		return;
	}
	if (cond1)
	{
		return;
	}
	if (cond2)
	{
		return;
	}
	do_something;
	free(p);
}

在上述程序中，一旦程序中满足了cond1、cond2等条件，就会return跳出，并不能执行到free（）。导致申请的空间内存不能被释放，从而可能出现内存泄露问题。

（5）在内存分配后忘记使用 free 进行释放 

要避免这些内存相关的问题导致的内存越界与内存遗漏等错误，可以参考如下几点进行：

• 确保没有在访问空指针。
• 每个内存分配函数都应该有一个 free 函数与之对应，alloca 函数除外。
• 每次分配内存之后都应该及时进行初始化，可以结合 memset 函数进行初始化，calloc 函数除外。
• 每当向指针写入值时，都要确保对可用字节数和所写入的字节数进行交叉核对。
• 在对指针赋值前，一定要确保没有内存位置会变为孤立的。
• 每当释放结构化的元素（而该元素又包含指向动态分配的内存位置的指针）时，都应先遍历子内存位置并从那里开始释放，然后再遍历回父节点。
• 始终正确处理返回动态分配的内存引用的函数返回值。

3. 作业解析

（a）第三行，使用malloc函数动态分配内存空间，并使指针A指向该内存空间。在第五行和第六行的操作是将指针A赋值给指针B，即此时指针A和指针B同时指向同一块内存空间。后续通过free函数释放内存空间后，还应该将指针A和指针B都置为null。

不要将两个指针变量指向同一块动态内存。这个容易引起很严重的问题。如果将两个指针变量指向同一块动态内存，而其中一个生命期结束释放了该动态内存，这个时候就会出现问题，另一个指针所指向的地址虽然被释放了但该指针并不等于NULL，这就是所谓的悬垂指针错误，这种错误很难被察觉，而且非常严重，因为这时该指针的值是随机的，可能指向一个系统内存而导致程序崩溃。但也就是因为值是随机的，所以运行程序时有时正常有时崩溃，这一点要特别注意。
 

#include<stdio.h>
#include<malloc.h>
 
int main()
{
	printf("hello main\n");
 
	int N = 1000;
	int* p1 = (int*)malloc(N * sizeof(int));
	int* p2 = p1;
 
	//同一个内存地址只能free一次（ free(p1);和free(p2); 二者选一执行，不能同时执行，否则报错 ）
	//free(p1);
	free(p2); 
 
	//释放后的内存为可再分配给其他指针的内存，
	//（1）若此时没有再分配给其他指针，原指针处的内容不变
	//（2）若分配给了其他指针，原指针处的内容会改变
	//因此，释放内存后的指针变为野指针， 不能再使用，需要指向NULL
 
	p1 = NULL;
	p2 = NULL;
 
	printf("goodbye main\n");
	return 0;
}

（b）第三行声明临时数组，应该采用（a）问题中第三行动态申请的方式。

数组与动态内存分配相比有以下缺点：

• 数组的长度必须事先指定，而且只能是常量，不能是变量。
• 因为数组长度只能是常量，所以它的长度不能在函数运行的过程当中动态地扩充和缩小。
• 对于数组所占内存空间程序员无法手动编程释放，只能在函数运行结束后由系统自动释放，所以在一个函数中定义的数组只能在该函数运行期间被其他函数使用。

而“传统数组”的问题，实际上就是静态内存的问题。但是动态内存就不存在这个问题，因为动态内存是由程序员手动编程释的，所以想什么时候释放就什么时候释放。只要程序员不手动编程释放，就算函数运行结束，动态分配的内存空间也不会被释放，其他函数仍可继续使用它。除非是整个程序运行结束，这时系统为该程序分配的所有内存空间都会被释放。

（c）第二种遍历方式效率更高。即：按行遍历的效率更高！

我们眼中的二维数组：

 内存中的二维数组：

 分析：

•  CPU高速缓存（英语：CPU Cache，在本文中简称缓存）是用于减少处理器访问内存所需平均时间的部件。在金字塔式存储体系中它位于自顶向下的第二层，仅次于CPU寄存 器。其容量远小于内存，但速度却可以接近处理器的频率。当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载入缓存，再将其返回处理器。缓存之所以有效，主要是因为程序运行时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利用这种局部性，缓存可以达到极高的命中率。
•  缓存从内存中抓取一般都是整个数据块，所以它的物理内存是连续的，几乎都是同行不同列的，而如果内循环以列的方式进行遍历的话，将会使整个缓存块无法被利用，而不得不从内存中读取数据，而从内存读取速度是远远小于从缓存中读取数据的。
• 分页调度：物理内存是以页的方式进行划分的，当一个二维数组很大是如 int[128][1024],假设一页的内存为4096个字节，而每一行正好占据内存的一页，如果以列的形式进行遍历，就会发生128*1024次的页面调度，而如果以行遍历则只有128次页面调度，而页面调度是有时间消耗的，因而调度次数越多，遍历的时间就越长。

二、并发编程（多线程）

1. PV操作

• p操作（wait）：申请一个单位资源，进程进入
• v操作（signal）：释放一个单位资源，进程出来

若有一售票厅只能容纳300人，当少于300人时，可以进入；否则，需在外等候。若将每一个购票者作为一个进程，请用P（wait）、V（signal）操作编程，并写出信号量的初值。（强调：只有一个购票窗口，每次只能为一位购票者服务）

分析：题中有两类资源，售票厅和售票窗口，售票厅可以容纳300人，窗口只能服务1个人。用户到达后要想买到票，首先要进入售票厅，然后申请到窗口才行。因此用户需要获得两类资源才能成功购票。好了，我们定义两个信号量一个是S1，代表售票厅还能容纳的人数，一个是S2，代表窗口，它们的初始值一个是300，一个是1。程序如下：

解：semophore S1=330，S2=1；
 
    用户进程Pi {
 
                    Wait（S1）
 
                    进入大厅
 
                    Wait（S2）
 
                    窗口购票
 
                   退出购票窗口
 
                    Signal（S2）
 
                     退出大厅
 
                    Signal（S1）
 
}

案例：

package day20211028;
 
import java.util.concurrent.Semaphore;
 
public class SemaphoreDemo {
	private static Semaphore semaphore1 = new Semaphore(1);
    private static Semaphore semaphore2 = new Semaphore(1);
    public static void main(String[] args) {
        final Thread thread1 = new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("产品经理规划新需求");
                semaphore1.release();
            }
        });
 
        final Thread thread2 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    semaphore1.acquire();
                    System.out.println("开发人员开发新需求功能");
                    semaphore1.release();
                    semaphore2.release();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        });
 
        Thread thread3 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    semaphore2.acquire();
                    System.out.println("测试人员测试新功能");
                    semaphore2.release();
                    
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        });
 
 
        thread3.start();
        thread1.start();
        thread2.start();
    }
 
 
}

2. 作业

（a）使用信号量机制

Solution:
Semaphore sA = new Semaphore(0), sB = new Semaphore(0);
 
void P2(void) {
Statement B;
sB.release();
}
 
Void P1(void){
sB.require();
Statement A;
sB.release();
sA.release();
}
 
Void P3(void){
sA.require();
Statement C;
sA.release();
}

(b) 让线程按照顺序执行（加锁并控制顺序）

(c) 数字正常，线程不固定（加锁）

参考售票案例

三、CPU调度

作业

（a）

fork函数是用来创建进程的，在fork函数执行后，如果成功创建新进程就会出现两个进程，一个子进程，一个父进程，fork函数有两个返回值。

int main(){
    printf(输出当前进程);
    sleep(1);
    fork();
    sleep(1)
    printf(输出当前进程);
    sleep(1);
}

fork有两个返回值：

• 在父进程中，fork返回新创建子进程的进程id
• 在子进程中，fork返回0
• 未能创建，fork返回负值

我们可以通过fork返回值判断当前进程是什么进程。父进程和子进程同时执行

输出结果

#include <sys/types.h>
#include <sys/wait.h>
#include <stdio.h>
#include <unistd.h>
 
int main(){
    int x = 1;
    pid_t pid = fork();
    if(pid == 0){
        x = x*2;
    }else if(pid>0){
        wait(NULL);
        x = 3;
    }
    printf("%d\n",x);
}
 
//本来同时执行，有了wait（null），则子进程优先
//2
//3

（b）轮循调度算法（每个时间片为10）

（c）

为了实现进程，从逻辑地址到物理地址的转换功能，在系统中设置了段表寄存器，用于存放段表始址和段表长度TL。最进行地址转换时，系统将逻辑地址等段号和段表长度TL进行比较。

• 如果S>TL，表示段号太大，访问越界。于是产生越界中断信号。
• 若未越界，则根据段表的始址和该断的段号，计算出该段对应段表的位置，从中读取该段在内存中的起始地址。然后，再检查段内地址d是否超过该段的段长SL。若超过，同样发出越界中断信号。
• 若未越界，则将该段的基址d与段内地址相加，即可得到要访问的内存物理地址。

（d）缺页中断与页面置换算法

每当所要访问的页面不在内存时，会产生一次缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

（e）考虑一个请求分页的计算机系统，它最近被测量以确定 CPU 的利用率和分页磁盘来决定多程序的程度。 结果如下图所示。 解释每个场景中发生的事情以及操作系统可以采取的行动。

场景一：

场景二：说明当前系统频繁缺页，频繁进行页面置换，导致真正执行任务的时间变短，效率变低，系统发生抖动。因此要缓解这种情况就需要降低系统缺页率，才能使系统有更多时间来处理任务而不是置换页面。减少进程运行数目，这样每个进程分配到的内存空间会相对增大，可以有效降低缺页率。

调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动。

• 页面淘汰算法不合理，分配给进程的物理页面数太少
• 同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面调进/调出的进程数目增加。造成每个进程的大部分时间都用于页面的换进/换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降并趋于0的情况。

场景三：