头像

我要出去乱说

凯里学院 => 贵州大学




离线:1天前



早上十点在BOSS直聘联系了家公司,叫中国赛宝实验室(工业和信息化部电子第五研究所),base北京,然后12点半就安排面试了,电话面了20分钟,自我介绍后就问了七个问题:

1. set和map底层实现?

2. C++的多态是什么?

3. 构造函数可不可以为虚函数?

4. 说一下快排?

5. Linux下你常用的命令有哪些?

6. MySQL中底层索引的实现?

7. B树和B+树的区别?

答完了面试官说我基础不错😂,一点半就直接发入职邀请了。从开始联系到确认入职只用了三个半小时,太快了我现在都还有点不敢相信。之前大厂面试被虐得怀疑人生,这次终于找回了点自信🤣。入职了要好好学习,继续提升!




要注意这里的同步并不是指同时进行的意思,而是按照先后顺序依次进行。
首先了解一下同步与互斥的概念:

  • 同步:多个进程因为合作产生的直接制约关系,使得进程有一定的先后执行关系;
  • 互斥:多个进程在同一时刻只有一个进程能进入临界区。

一、进程同步方式

进程同步就是控制多个进程按一定顺序执行,而进程间通信(IPC)是在进程间传输信息。它们之间的关系是:进程通信是一种手段,而进程同步是一种目的,为了能够达到进程同步的目的,需要让进程进行通信,传输一些进程同步所需要的信息。借用知乎某佬的一句话:

不要当那种考试考傻了的书呆子,把“同步”和“通信”的概念分得那么清楚,能通信就一定是一种同步机制,这是显而易见的。

所以面试官问你进程同步的方式时,他的意思其实是让你回答进程间的通信方式。
常用的进程间通信方式:管道,共享内存,消息队列,信号量,套接字。

1)管道

管道分为命名管道和匿名管道,命名管道可以用于两个或任意多个进程间通信,匿名管道则只能用于有血缘关系(父子进程、兄弟进程、爷孙进程等)的进程间通信。Linux中的“|”命令就是匿名管道,表示把一个进程的输出作为另一个进程的输入。管道就是内核里的一段缓存,从管道一端写入的数据实际上是缓存在内核中,从另一端读取也就是从内核中读取这段数据。管道是半双工的,数据只能向一个方向流动,双方需要互相通信时,需要建立起两个管道。

2)共享内存

共享内存就是映射一段能被其他进程所访问的内存,这段共享内存由一个进程创建,但多个进程都可以访问。共享内存是最快的一种IPC方式,因为没有内存拷贝的操作,但需要依靠互斥锁或信号量来实现同步。

3)信号

信号是Linux系统中的进程间通信方式,信号可以在任何时候发给某一进程,用于通知该进程某个事件已经发生。比如kill -9命令就可以向指定的进程发送一个终止信号从而杀死进程。

4)信号量

信号量本质就是一个计数器,记录资源能被多少个进程同时访问,用来实现进程之间的互斥与同步,信号量的引入的是为了解决共享内存通信方式造成的进场安全问题。

5)消息队列

多个不相干的进程可以通过一个消息队列来传递数据,且传递的是一个有意义的数据结构,而管道只能传递没有意义的字节流,还需要在接收端做解析。消息队列和管道一样是有一个buffer size限制的,当buffer size 为空或为满的时候,send和receive会sleep。

6)套接字

可用于不同主机之间的进程间通信。


二、线程同步方式

对于多线程访问共享资源出现数据混乱的问题,需要进行线程同步。所谓的共享资源就是多个线程共同访问的变量,这些变量通常为全局数据区变量或者堆区变量,这些变量对应的共享资源也被称之为临界资源。
常用的线程同步方式有四种:互斥锁、读写锁、条件变量、信号量。

1)互斥锁

互斥锁是线程同步最常用的一种方式,通过互斥锁可以锁定一个代码块,对于被锁定的这个代码块,所有的线程只能串行处理,不能并行处理。

2)读写锁

读写锁是互斥锁的升级版,所有线程的读操作都是并行的,只有写操作是串行的。程序中的读操作越多,读写锁性能就越高,相反,若程序中全是写操作,那么读写锁会退化成互斥锁。

3)条件变量

条件变量的主要作用不是处理线程同步,而是进行线程的阻塞。常常和互斥锁一起用在生产者和消费者模型中。举个例子:当任务队列为空时,消费者无法消费,使用条件变量把消费者线程阻塞住,等待生产者生产出任务后,再唤醒一个或多个被条件变量阻塞的消费者线程;反过来也可以控制生产者生产的上限,当任务队列达到一个上限值时用条件变量阻塞住生产者线程,直到消费者把任务消费后再唤醒被条件变量阻塞的生产者线程。

4)信号量

信号量可以实现线程同步也可以实现进程同步,它允许多个线程在同一时刻访问同一资源,但是需要限制在同一时刻访问此资源的最大线程数目。信号量主要阻塞线程,不能完全保证线程安全,如果要保证线程安全,需要和互斥锁一起使用。信号量也可以用来实现生产者消费者模型,在用条件变量实现生产者消费者模型时需要自己做条件判断,而使用信号量就不需要。举个例子:初始化生产者的信号量为5,消费者的信号量为0,因为消费者信号量为0所以会被阻塞,生产者进行一次生产后会将自己的信号量减1,将消费者信号量加1,这时消费者解除阻塞,进行消费后再将自己的信号量减1生产者信号量加1。

补充一个死锁的概念:当多个线程访问共享资源时,需要加锁,如果锁使用不当,就会造成死锁,导致所有的线程都被阻塞,并且线程的阻塞无法解开。
造成死锁的场景有:
①、加锁后忘记解锁;
②、重复加锁造成死锁;
③、程序中存在多个共享资源,有多把锁,随意加锁导致相互被阻塞。
解决方式:
①、多检查,避免重复加锁;
②、资源访问完毕后一定要解锁,或者在访问时使用trylock(),因为trylock()在加锁失败时不会一直阻塞,而是返回错误号。

参考文献

Alan_操作系统知识点总结
苏丙榅的博客
《现代操作系统》




三套算法分别是:内存分配算法,页面置换算法,和进程调度算法。之所以说三套,是因为每一类算法有多种实现。


一:内存分配算法(用于空闲内存管理)

1. 首次适配算法(first fit)
每次接到内存申请,按空闲区地址由低到高查找,找到第一个不小于分配请求的空闲块,将其分割并分配。该算法实现简单,但会在低地址部分产生许多无法利用的小空闲块(外部碎片),好处是可以在高地址部分保留大的空闲块。

2. 最佳适配算法(best fit)
需要先将空闲块按尺寸由小到大排列,每次找到最适合分配请求的空闲块。该算法用最小空间满足了要求,保留了大的空闲区,但会造成许多外部碎片。

3. 最差适配算法(worst fit)
需要先将空闲块按尺寸由大到小排列,每次找到能满足分配请求且最大的空闲块。该算法适用于请求分配的内存大小范围较窄的系统,保留了小的空闲块,减少了外部碎片的产生。

4. 下次适配算法(next fit)
首次适配算法的改进版,每次找到合适的空闲区后记录当时的位置,以便在下次寻找空闲区时从上次结束的地方开始搜索,而不是像首次适配算法那样每次都从头开始。实际性能略低于首次适配算法。

5. 快速适配算法(quick fit)
为那些常用大小的空闲区维护单独的链表,在寻找一个指定大小的空闲区时十分快速,但寻找相邻块合并的过程非常费时。


二:页面置换算法(用在虚拟内存中缺页中断时)

1. 最优页面置换算法
每次淘汰掉最长时间后才会用到的页面,因为无法预知哪些页面最长时间后才会用到,所以该算法只是理论上的,无法实现。但可以用来与其他可实现算法做性能对比。

2. 先进先出页面置换算法(FIFO)
每次淘汰掉最早进入内存的页面。该算法实现简单,但性能不高,因为最早进入的页面不代表最不常使用。

3. 第二次机会页面置换算法
改进版的FIFO算法,使用了访问位,每次淘汰掉最早进入且访问位为0的页面。

4. 最近未使用页面置换算法(NRU)
每次淘汰掉最近一个时钟滴答中没有被访问的页面,且定期清0所有页面的访问位,以区别最近没有被访问的页面和被访问的页面。

5. 最近最少使用页面置换算法(LRU)
每次淘汰掉最长时间没有访问过的页面,该算法理论上可以实现,但代价太高,因为每次访问内存都必须要更新整个链表。所以一般用微调后的NFU算法(老化算法)来模拟LRU算法。

6. 时钟置换算法
将所有页面保存在环形链表中,发生缺页中断时,首先检查指针指向的页面,若该页面访问位为0则淘汰,否则将访问位置0后指针前移一个位置,重复这个过程直到找到一个访问位为0的页面为止。

7. 工作集页面置换算法
原理类似滑动窗口,先指定一个工作集窗口,还需要额外维护一个在工作集窗口内的所有页面的集合,每当发生缺页中断时,淘汰一个不在工作集中的页面。


三:进程调度算法(用在多个进程同时竞争CPU时)

1. 先来先服务(FCFS)
非抢占式,按照进程请求CPU的顺序使用CPU,该算法实现简单,但平均等待时间波动较大,不公平。

2. 最短作业优先
非抢占式,优先执行最短的作业,需要预估作业运行所需时间,且有可能导致长作业饥饿。

3. 最短剩余时间优先
最短作业优先的抢占式版本,调度程序总是选择剩余运行时间最短的那个进程运行。

4. 轮转调度(Round Robin)
每个进程被分配一个时间片,时间片用完就剥夺该进程的CPU并分配给另一个进程,该算法的关键在于选择一个适合的时间片长度。如果太长,可能会退化成FCFS,太短又会导致上下文切换开销过大。根据经验,上下文切换开销最好处于1%以内。

5. 多级反馈队列
每一个队列都是一个轮转调度,且越往下时间片越大,一个进程可以在不同的队列中移动。当一个进程用完分配的时间片后,它将被移到下一个队列中。

6. 优先级调度
为每个进程分配一个优先级,按优先级顺序进行调度,同时为了防止低优先级的进程永远得不到调度,可以随着时间的推移增加等待进程的优先级。


以上提到的只是常用的算法,还有一些偏冷门的算法没有列出。感觉每套 能记住三四个算法就足够应付面试了,此处针对每种算法只进行了简单描述,做备忘之用,若要知晓其细节,还请参考经典的操作系统书籍,如《现代操作系统》,《深入理解计算机系统》等。




初始化最小辅助栈时放入一个INT_MAX。

class MinStack {
private:
  stack<int> stk;
  stack<int> monoStk;
public:
  MinStack() {
      monoStk.push(INT_MAX);    //单调栈中放一个最大数垫底
  }

  void push(int x) {
    stk.push(x);
    int t = monoStk.top() > x ? x : monoStk.top();
    monoStk.push(t);     
  }

  void pop() {
    monoStk.pop();
    stk.pop();
  }

  int top() {
    return stk.top();
  }

  int min() {
    return monoStk.top();
  }
};


活动打卡代码 LeetCode 155. 最小栈

初始化最小辅助栈时放入一个INT_MAX。

class MinStack {
private:
  stack<int> stk;
  stack<int> monoStk;
public:
  MinStack() {
      monoStk.push(INT_MAX);    //单调栈中放一个最大数垫底
  }

  void push(int x) {
    stk.push(x);
    int t = monoStk.top() > x ? x : monoStk.top();
    monoStk.push(t);     
  }

  void pop() {
    monoStk.pop();
    stk.pop();
  }

  int top() {
    return stk.top();
  }

  int min() {
    return monoStk.top();
  }
};


活动打卡代码 LeetCode 155. 最小栈

class MinStack {
private:
  stack<int> stk;
  stack<int> monoStk;
public:
  MinStack() {
      monoStk.push(INT_MAX);    //单调栈中放一个最大数垫底
  }

  void push(int x) {
    stk.push(x);
    int t = monoStk.top() > x ? x : monoStk.top();
    monoStk.push(t);     
  }

  void pop() {
    monoStk.pop();
    stk.pop();
  }

  int top() {
    return stk.top();
  }

  int min() {
    return monoStk.top();
  }
};


活动打卡代码 AcWing 53. 最小的k个数

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        sort(input.begin(), input.end());

        for (int i = 0; i < k; i ++ ) res.push_back(input[i]);  //直接sort然后拷过来

        return res;
    }
};



class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int two_xor = 0;

        for (int x : nums)                      //所有数异或一遍,重复数字双双抵消
            two_xor ^= x;                       //剩下的是两个不同数字的异或值

        int mask = two_xor & (-two_xor);        //lowbit算法得到该数二进制最低的非零位

        int a = 0, b = 0;
        for (int x : nums)
        {
            //注意这里要么写(x & mask)要么写((x & mask) == mask),不能写((x & mask) == 1)
            if (x & mask) a ^= x;               //用这个非零位将整组数分为a,b两组分别异或
            else b ^= x;
        }

        return {a, b};
    }
};


活动打卡代码 AcWing 78. 左旋转字符串

class Solution {
public:
    string leftRotateString(string str, int n) {

        return str.substr(n) + str.substr(0, n);    
    }
};


活动打卡代码 LeetCode 7. 整数反转

class Solution {
public:
    int reverse(int x) {
        long res = 0;

        while (x)
        {
            res = res * 10 + (x % 10);
            x /= 10;
        }

        if (res > INT_MAX || res < INT_MIN) return 0;
        return res; 
    }
};