純虛函數
純虛函數為了解決基類派生出對象不合理的情況,而被使用。
例如,動物作為一個基類可以派生出老虎、孔雀等子類,但動物本身生成對象明顯不合常理。
#include <iostream>
#include <memory>
class Animals {
public:
virtual void roar() = 0;
};
class Tigers : public Animals {
public:
virtual void roar();
};
void Tigers::roar() { std::cout << "Tiger's roar" << std::endl; }
class Lions : public Animals {
public:
virtual void roar();
};
void Lions::roar() { std::cout << "Lions's roar" << std::endl; }
int main() {
std::shared_ptr<Tigers> tiger = std::make_shared<Tigers>();
std::shared_ptr<Lions> lion = std::make_shared<Lions>();
tiger->roar();
lion->roar();
return 0;
}
抽象類不能執行個體化
菱形繼承問題:
利用虛函數解決該問題
#include <iostream>
#include <memory>
class Animals {
public:
virtual void roar() = 0;
};
class Tigers : public Animals {
public:
virtual void roar();
};
void Tigers::roar() { std::cout << "Tiger's roar" << std::endl; }
class Lions : public Animals {
public:
virtual void roar();
};
void Lions::roar() { std::cout << "Lions's roar" << std::endl; }
class Liger : public Lions, Tigers {
public:
virtual void roar();
};
void Liger::roar() { std::cout << "Liger's roar" << std::endl; }
int main() {
std::shared_ptr<Tigers> tiger = std::make_shared<Tigers>();
std::shared_ptr<Lions> lion = std::make_shared<Lions>();
std::shared_ptr<Liger> liger = std::make_shared<Liger>();
tiger->roar();
lion->roar();
liger->roar();
return 0;
}
Lambda表達式
匿名函數:沒有名字的函數
寫法->函數傳回類型{函數實作方法}
樣例:
#include <algorithm>
#include <iostream>
int main() {
int a[10] = {1, 2, 3, 4, 5};
std::sort(a, a + 5, [=](int x, int y) -> bool { return x > y; });
for (auto x : a) {
std::cout << x << std::endl;
}
return 0;
}
/*樣例輸出
5
4
3
2
1
0
0
0
0
0*/
智能指針産生記憶體洩漏:
兩個類中的智能指針互相指向,造成引用循環,造成記憶體洩漏。
為了解決循環引用而造成的記憶體洩漏:
引入弱指針weak_ptr的構造函數不會修改引用計數,進而不會對對象的記憶體進行管理,但是會檢測所管理對象記憶體是否釋放掉,進而避免非法通路。
說說什麼是大端小端,如何判斷大端小端?
小端模式:低的有效位元組存儲在低的存儲器位址。小端一般為主機位元組;常用x86結構是小端很多arm,dsp都為小端模式
大端模式:高的有效位元組存儲在低的存儲器位址。大端為網絡位元組;KEIL C51則為大端模式。
如何判斷:
我們可以用聯合體來判斷什麼是大端什麼是小端,因為聯合體變量總是從低位址存儲
int fun1(){
union test{
char c;
int i;
};
test t; t.i = 1;
//如果是大端,則t.c為0x00,則t.c != 1,反之是小端
return (t.c == 1);
}
說說程序排程算法有哪些?
1.先來先服務排程算法
2.程序優先排程算法
3.高優先級優先排程算法
4.時間片輪轉
5.多級回報隊列排程算法
1.先來先服務排程算法
把先進入隊列的一個或幾個程序調入記憶體,為其配置設定資源,建立程序,然後放進就緒隊列。
2.程序現有排程算法
從後備隊列裡選若幹個運作時間短的程序,把他們調入記憶體運作。
3.高優先級優先排程算法
從後備隊列裡選優先級高的程序先調入記憶體運作。
4.時間片輪轉
後備隊列裡的每個程序都有一個相同的時間片,當時間片用完,該程序被送入就緒隊列的末尾,再把處理機制配置設定給就緒隊列的新對手程序
5.多級回報隊列排程算法
分為搶占式和非搶占式,綜合前面多種排程算法
作業系統如何管理記憶體?
1.實體記憶體:實體記憶體有四個層次,寄存器,高速緩存,主存,磁盤
寄存器:速度最快,量少,貴
高速緩存次之
主存次之
磁盤速度最慢,量多,價格便宜
2.虛拟記憶體:作業系統為每一個程序配置設定一個獨立的位址空間,但是虛拟記憶體,虛拟記憶體與實體記憶體存在映射關系,通過頁表尋址完成虛拟位址和實體位址的轉換。
Linux的使用者态與系統态
1.核心态擁有最高權限,而使用者态隻能通路一部分指令
2.再進行中斷,系統調用和異常的時候,會進入系統态
3.為什麼要區分使用者态和系統态?
再CPU所有的指令中一些指令是非常危險的?比如清記憶體,設定時鐘等。是以區分使用者态和系統态是處于安全考慮。
一個線程占多大記憶體?
一個linux線程大約占8M記憶體
linux的棧是同個缺頁來配置設定記憶體的,不是所有的棧位址空間都配置設定記憶體。是以8M是最大消耗,實際記憶體的消耗隻會實際需要的的記憶體(記憶體消耗每個再4k以内)
什麼是頁表?
頁表是虛拟記憶體的概念。作業系統虛拟記憶體到實體記憶體的映射的表就是頁表。
原因:不可能每一個虛拟記憶體的byte都對應到實體記憶體的位址。這張表将大的真正的實體記憶體位址也放不下,于是作業系統引入了頁的概念。這樣可以減少虛拟記憶體頁對應實體記憶體頁的映射表大小。
如果将每一個虛拟記憶體的Byte都對應到虛拟記憶體上,每個條目最少需要8位元組(32位虛拟位址->32位實體位址)在4G記憶體的情況下,就需要32G的空間來存放對照表,那麼這張表就大的真正的實體位址也存不下。
為什麼要用虛拟記憶體:因為早期的記憶體配置設定方法存在問題:
程序的位址空間不隔離,會導緻資料被随意修改。
記憶體使用效率低。
程式運作位址不确定。作業系統随機為程序配置設定記憶體空間,是以程式運作的位址不确定。
使用虛拟記憶體的好處:
實作記憶體的連續使用,雖然實體記憶體上不連續,但映射到虛拟記憶體上是連續的。
友善實作程序通信和記憶體共享。
擴大位址空間,每一個程序獨占一個4G的記憶體,雖然實際記憶體沒有那麼大。
記憶體保護:防止不同程序對實體記憶體的争奪和踐踏,可以對特定的記憶體位址提供寫保護,防止惡意篡改。
虛拟記憶體的缺點:
虛拟記憶體需要額外建構一個資料結構,占用記憶體。
虛拟位址映射到實體位址浪費時間
頁面換入換出耗時。
虛拟位址到實體位址是如何映射的關系資料結構?
作業系統為每一個程序維護了一個從虛拟位址到實體位址的映射關系的資料結構,叫頁表。頁表中的每一項都記錄了這個頁的基位址。
基位址+偏移位址=線性位址
32位系統能通路4G以上的記憶體?
正常情況下是無法通路的。原因是計算機使用二進制,每位隻有0或1,32位正好是2^32,正好是4G,因其他原因還需要占用一部分空間,是以記憶體隻夠識别3G多。要使用4G以上就隻能換64位的作業系統。
但是PAE技術就可以實作32為通路4GB以上的記憶體。
原因:PAE技術将位址擴充到了36位,這樣,系統就能夠容納2^36=64GB的記憶體。
并行和并發
1.并發:對于單個cpu在一個時刻隻有一個程序在運作,但是線程的切換時間則減少到納秒的數量級,多個任務不停來回切換。
2.并行:對于多個cpu,多個程序同時運作。
3.差別:通俗來講,他們雖然都說是多個程序同時運作,但是他們的同時不是一個概念。并行的同時是多個程序同一時刻進行。并發的同時是經過線程的快速切換,使得看上去任務同時都在運作的現象。
說說程序,線程,協程是什麼?
程序:程式是指令,資料以及其組織形式的描述,而程序則是程式的執行個體。
線程:微程序,一個程序裡更小粒度的執行單元。一個程序裡包含多個程序并發執行任務。
協程:協程是微線程,在子程式内部執行,可在子程式内部中斷,轉而執行别的子程式,在适當的時候傳回來接着執行。
差別:
線程與程序的差別:
一個線程屬于一個程序,一個程序可以包含多個線程。
一個線程挂掉,會令對應的程序挂掉,一個程序挂掉,不會對其他程序造成影響。
程序是系統資源排程的最小機關:線程是cpu排程的最小機關。
程序系統開銷大于線程,線程需要的資源更少。
程序執行時擁有獨立的記憶體,多個線程共享程序的記憶體,如代碼段,資料段,擴充段,每個線程擁有自己的棧段和核心棧。
程序切換時需重新整理TLB并獲得新的位址空間,然後切換硬體上下文和核心棧,線程切換時隻需要切換硬體上下文和核心棧。
每個程序都有一個映射表,程序切換是指令的切換和映射表的切換,線程的切換是指令的切換。
通信方式不一樣.
線程和協程的差別?
協程執行效率極高。協程直接操作核心棧,基本上沒有核心切換的開銷,是以上下文切換非常快。
協程不需要多線程的鎖機制,因為協程屬于一個線程
一個線程可以有多個協程
什麼是孤兒程序,僵屍程序,如何解決僵屍程序?
孤兒程序是指父程序停止運作後,而他的一個或多個子程序還在運作,那麼這些程序将成為孤兒程序,孤兒程序将被init程序(程序号1)所收養,并由init程序對他們的完整狀态收集工作。
僵屍程序:是指一個程序fork()函數建立子程序,如果子程序退出,而父程序并沒調用wait()或者waitpid()系統調用取得子程序的終止狀态,那麼子程序的程序描述符仍然儲存在系統中,占用系統資源,這中程序成為僵屍程序。wait()清理掉子程序PID。
如何解決僵屍程序:
(1)一般,為了防止産生僵屍程序,在fork子程序之後我們都要及時用wait系統調用;同時當子程序退出的時候,核心都會給父程序發送一個SIGCHLD信号,是以我們可以建立一個捕獲SIGCHLD信号的信号處理函數,在函數體中調用waitpid,就可以清理退出的子程序以訪達到防止僵屍程序的目的。
(2)使用kill指令
打開終端并輸入下面指令
ps aux| grep Z
會列出程序表中所有的僵屍程序的詳細内容。
然後輸入指令:
kill -s SIGCHLD pid(父程序PID)
程序間通信的方式:
管道
套接字socket:用于不同主機之間的通信
消息隊列
信号量
信号
共享記憶體
程序間同步的方式:
1.信号量semaphone:是一個計數器,可以用來控制多個程序對共享資源的通路。信号量用于實作程序間同步和互斥。P操作(遞減操作)可以用于阻塞一個程序,V操作(增加操作)可以用于解除阻塞程序。
2.管道:一個程序通過調用管程的一個過程進入管程。在任何時候,隻能有一個程序在管程中執行,調用管程的任何其他程序都被堵塞,以待管程可用。
3.消息隊列:消息的連結表,放在核心中,消息獨立于發送與接受程序,程序終止時,消息隊列及其内容并不會被删除;消息隊列可以實作消息的随機查詢,可以按照消息類型讀取。
多線程:
第一個多線程程式
#include <iostream>
#include <thread>
void hello() { std::cout << "hello current world!" << std::endl; }
int main() {
std::thread t(hello);
std::cout << "Test order" << std::endl;
t.join();
return 0;
}
join()可以保證線程在函數完成前結束
deatch()線程分離,可以自己進行回收
線程同步:
線程資料共享,避免多線程對資料進行搶奪
互斥量:pthread_mutex
#include <pthread.h>
#include <unistd.h>
#include <iostream>
static int ticks = 100;
pthread_mutex_t mutex;
void *sellticks(void *sg) {
static int _indexTick = 1;
while (true) {
pthread_mutex_lock(&mutex);
if (ticks > 0) {
std::cout << pthread_self() << " Selling" << ' ' << _indexTick << " tick"
<< std::endl;
ticks--;
} else {
pthread_mutex_unlock(&mutex);
break;
}
_indexTick++;
pthread_mutex_unlock(&mutex);
}
return NULL;
}
int main() {
pthread_mutex_init(&mutex, NULL);
pthread_t seller1;
pthread_t seller2;
pthread_t seller3;
int sfg = pthread_create(&seller1, NULL, sellticks, NULL);
int stg = pthread_create(&seller2, NULL, sellticks, NULL);
int ssg = pthread_create(&seller3, NULL, sellticks, NULL);
pthread_detach(seller1);
pthread_detach(seller2);
pthread_detach(seller3);
pthread_exit(NULL);
return 0;
}
線程産生死鎖:
1.忘記解鎖
2.線程多次加鎖,由于已經加鎖,已經拿到鎖後,再次加鎖,拿不到鎖陷入死鎖
3.一個線程占用了A資源,想要占用B資源,而B資源被另一個線程占用,線程B想要占用A資源,隻用當這兩個線程占用占用其想占用的資源後,才會對資源進行釋放,造成死鎖。
#include <pthread.h>
#include <iostream>
pthread_mutex_t mutex1, mutex2;
void *workA(void *sg) {
pthread_mutex_lock(&mutex1);
pthread_mutex_lock(&mutex2);
while (true) {
std::cout << "cpu use mutex1 and mutex2 source" << std::endl;
}
pthread_mutex_unlock(&mutex1);
pthread_mutex_unlock(&mutex2);
}
void *workB(void *sg) {
pthread_mutex_lock(&mutex2);
pthread_mutex_lock(&mutex1);
while (true) {
std::cout << "cpu use mutex2 and mutex1 source" << std::endl;
}
pthread_mutex_unlock(&mutex2);
pthread_mutex_unlock(&mutex1);
}
int main() {
pthread_mutex_init(&mutex1, NULL);
pthread_mutex_init(&mutex2, NULL);
pthread_t worker1, worker2;
int sgw1 = pthread_create(&worker1, NULL, workA, NULL);
int sgw2 = pthread_create(&worker2, NULL, workB, NULL);
pthread_detach(worker1);
pthread_detach(worker2);
pthread_exit(NULL);
return 0;
}
生産者消費者模型
使用:條件變量和互斥量
前提:生産倉庫大小無限大
問題:再delete時需要把目前置為空
#include <pthread.h>
#include <unistd.h>
#include <iostream>
class Node {
public:
Node(int val, Node *next = NULL) : data(val), Next(next) {}
~Node(){}
int data;
Node *Next;
};
/*共享資料*/
int serialNumber = 0;
pthread_mutex_t mutex;
pthread_cond_t cond;
Node *head = NULL;
void *Factory(void *arg) {
while (true) {
pthread_mutex_lock(&mutex);
Node *nextNode = new Node(++serialNumber);
std::cout << "Factory produce goods of serial number = " << next->data
<< std::endl;
nextNode->Next = head;
head = nextNode;
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
usleep(100);
}
return NULL;
}
void *Consumer(void *arg) {
while (true) {
Node *tmp = head;
pthread_mutex_lock(&mutex);
if (head != NULL) {
std::cout << "Consumer consume goods of serial number = " << head->data
<< std::endl;
head = head->Next;
tmp = NULL;
delete tmp;
pthread_mutex_unlock(&mutex);
} else {
pthread_cond_wait(&cond, &mutex);
pthread_mutex_unlock(&mutex);
}
usleep(100);
}
return NULL;
}
int main() {
pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&cond, NULL);
pthread_t producer[3], consumer[3];
for (int i = 0; i < 3; i++) {
pthread_create(&producer[i], NULL, Factory, NULL);
pthread_create(&consumer[i], NULL, Consumer, NULL);
}
for (int i = 0; i < 3; i++) {
pthread_detach(producer[i]);
pthread_detach(consumer[i]);
}
pthread_exit(NULL);
return 0;
}
信号量
生産者消費者模型
倉庫固定大小
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <iostream>
class Node {
public:
Node(int val, Node *next = NULL) : data(val), Next(next) {}
~Node() {}
int data;
Node *Next;
};
/*共享資料*/
int serialNumber = 0;
pthread_mutex_t mutex;
Node *head = NULL;
sem_t psem; //生産者倉庫信号量
sem_t csem; //消費者信号量
void *Factory(void *arg) {
while (true) {
/*若psem倉庫為0,産生阻塞,等待倉庫有空間可以使用*/
sem_wait(&psem);
pthread_mutex_lock(&mutex);
Node *nextNode = new Node(++serialNumber);
std::cout << "Factory produce goods of serial number = " << nextNode->data
<< std::endl;
nextNode->Next = head;
head = nextNode;
pthread_mutex_unlock(&mutex);
sem_post(&csem);
}
return NULL;
}
void *Consumer(void *arg) {
while (true) {
Node *tmp = head;
sem_wait(&csem);
pthread_mutex_lock(&mutex);
std::cout << "Consumer consume goods of serial number = " << head->data
<< std::endl;
head = head->Next;
tmp = NULL;
delete tmp;
pthread_mutex_unlock(&mutex);
sem_post(&psem);
}
return NULL;
}
int main() {
pthread_mutex_init(&mutex, NULL);
/*初始化信号量 生産者倉庫為8*/
sem_init(&psem, 0, 8);
sem_init(&csem, 0, 0);
pthread_t producer[3], consumer[3];
for (int i = 0; i < 3; i++) {
pthread_create(&producer[i], NULL, Factory, NULL);
pthread_create(&consumer[i], NULL, Consumer, NULL);
}
for (int i = 0; i < 3; i++) {
pthread_detach(producer[i]);
pthread_detach(consumer[i]);
}
pthread_mutex_destroy(&mutex);
pthread_exit(NULL);
return 0;
}
讀寫鎖
由于共享資料有種情況,很多線程一起通路都不會有問題,比如讀取某個檔案的資料,這時候互斥量就不适合出現這裡了,是以讀寫鎖應運而生,我們可以一起讀資料,但是不可以一起寫資料,當一個線程在寫資料時,不允許其他線程讀取資料,和寫入資料。
寫時獨占的,寫的優先級高
pthread_rwlock_wrlock()寫鎖
pthread_rwlock_rdlock()讀鎖
pthread_rwlock_unlock()解鎖
判斷大小端位元組序:
#include <iostream>
int main() {
union {
short value;
char bytes[sizeof(short)];
} test;
test.value = 0x0102;
if (test.bytes[0] == 1 && test.bytes[1] == 2) {
std::cout << "Big" << std::endl;
}
if (test.bytes[0] == 2 && test.bytes[1] == 1) {
std::cout << "Small" << std::endl;
}
return 0;
}
網絡程式設計socket實作簡單的通信:
client
/*頭檔案*/
#include <arpa/inet.h>
#include <stdlib.h>
#include <sys/socket.h>
#include <unistd.h>
#include <cstring>
#include <iostream>
#include <memory>
#define maxBuf (1 << 20)
#ifndef _CLIENT_H_
#define _CLIENT_H_
static char messages[maxBuf]="I am client";
class ClientSock {
public:
ClientSock(char *ip, char *port);
~ClientSock() { close(clientFd); };
void error(char *error);
void clientConnect();
virtual void clientWrite();
virtual void clientRead();
private:
char *_port;
char *_ip;
int clientFd;
struct sockaddr_in serverAddr;
};
#endif
/*實作代碼*/
#include "client.h"
static char reciveBuf[maxBuf] = {0};
void ClientSock::error(char *error) {
std::cout << error << std::endl;
exit(1);
}
ClientSock::ClientSock(char *ip, char *port) {
this->_ip = ip;
this->_port = port;
/*建立套接字*/
this->clientFd = socket(PF_INET, SOCK_STREAM, 0);
/*為目前套接字配置設定位址資訊*/
memset(&serverAddr, 0, sizeof(serverAddr));
serverAddr.sin_family = AF_INET;
serverAddr.sin_addr.s_addr = inet_addr(ip);
serverAddr.sin_port = htons(atoi(port));
}
void ClientSock::clientConnect() {
/*connect()向伺服器發送連接配接請求*/
if (connect(clientFd, (struct sockaddr *)&serverAddr, sizeof(serverAddr)) ==
-1) {
this->error(const_cast<char *>("connect() error!"));
}
}
void ClientSock::clientWrite() {
// std::cout << "Listen...." << std::endl;
char buf[] = "I am client";
int nowLen = 0;
int allLen = sizeof(buf);
int getLen = 0;
while (getLen < allLen) {
nowLen = write(clientFd, buf + getLen, allLen - getLen);
getLen += nowLen;
}
}
void ClientSock::clientRead() {
char buf[1024];
int strLen = 0;
int allLen = sizeof(buf);
strLen = read(clientFd, buf, allLen);
if (strLen == -1) {
this->error(const_cast<char *>("read() error!"));
}
std::cout << "I accept from server information: " << buf << std::endl;
}
/*主體函數*/
#include "client.h"
int main(int argc, char *argv[]) {
ClientSock *client = new ClientSock(argv[1], argv[2]);
client->clientConnect();
while(true){
client->clientWrite();
sleep(2);
client->clientRead();
}
delete client;
return 0;
}
server
/*頭檔案*/
#include <arpa/inet.h>
#include <stdlib.h>
#include <sys/socket.h>
#include <unistd.h>
#include <cstring>
#include <iostream>
#include <memory>
#define maxBuf (1 << 20)
#ifndef _SERVER_H_
#define _SERVER_H_
static char messages[maxBuf];
class ServerSock {
public:
ServerSock(char *ip, char *port);
~ServerSock();
void serverBind();
void error(char *error);
void serverListen();
void serverAccept();
void setMessages(char *others);
virtual void serverWrite();
virtual void serverRead();
private:
char *_port;
char *_ip;
int serverFd;
int clientFd;
struct sockaddr_in serverAddr;
struct sockaddr_in clientAddr;
socklen_t clientAddrLen;
};
#endif
/*實作代碼*/
#include "server.h"
void ServerSock::error(char *error) {
std::cout << error << std::endl;
exit(1);
}
ServerSock::ServerSock(char *ip, char *port) {
this->_ip = ip;
this->_port = port;
this->clientAddrLen = sizeof(clientAddr);
/*建立套接字*/
this->serverFd = socket(PF_INET, SOCK_STREAM, 0);
/*為目前套接字配置設定位址資訊*/
memset(&serverAddr, 0, sizeof(serverAddr));
serverAddr.sin_family = AF_INET;
serverAddr.sin_addr.s_addr = inet_addr(ip);
serverAddr.sin_port = htons(atoi(port));
}
void ServerSock::serverBind() {
if (bind(serverFd, (struct sockaddr *)&serverAddr, sizeof(serverAddr)) ==
-1) {
this->error(const_cast<char *>("bind() error!"));
}
}
void ServerSock::serverListen() {
if (listen(serverFd, 5) == -1) {
this->error(const_cast<char *>("listen() error!"));
}
}
void ServerSock::serverAccept() {
clientFd = accept(serverFd, (struct sockaddr *)&clientAddr, &clientAddrLen);
if (clientFd == -1) {
this->error(const_cast<char *>("accept() error!"));
}
}
void ServerSock::serverWrite() {
//std::cout << "Listen...." << std::endl;
char others[] = "I am server";
int nowLen = 0;
int allLen = sizeof(others);
int getLen = 0;
while (getLen < allLen) {
nowLen = write(clientFd, others + getLen, allLen - getLen);
getLen += nowLen;
}
}
void ServerSock::serverRead() {
char buf[maxBuf];
int strLen = 0;
int allLen = sizeof(buf);
strLen = read(clientFd, buf, allLen);
if (strLen == -1) {
this->error(const_cast<char *>("read() error!"));
}
std::cout << "I accept from client information: " << buf << std::endl;
}
void ServerSock::setMessages(char *others) { strcpy(messages, others); }
ServerSock::~ServerSock() {
close(clientFd);
close(serverFd);
}
/*Main入口*/
#include "server.h"
int main(int argc, char *argv[]) {
//char others[] = "I am server";
ServerSock *server = new ServerSock(argv[1], argv[2]);
server->serverBind();
server->serverListen();
server->serverAccept();
//server->setMessages(others);
while (true) {
server->serverRead();
sleep(2);
server->serverWrite();
}
delete server;
return 0;
}
Tcp滑動視窗:
由于發送端和接收端處理資料的能力不一樣,可能發送端發送資料很快,而接收端處理資料很慢,是以利用一個固定大小的緩存區進行滑動,來控制發送資料的大小。
端口複用:setsockopt()可能端口被占用,我們可以複用該端口
通信并發
利用子程序和父程序進行通信,可以允許多個用戶端進行通路,問題:每次調用select()過程耗費資源
IO多路複用
select:server
/*select多路複用*/
#include "socket.h"
int main(int argc, char *argv[]) {
ServerSock *server = new ServerSock(argv[1], argv[2]);
server->serverBind();
server->serverListen();
fd_set rdset, tmp;
FD_ZERO(&rdset);
FD_SET(server->serverFd, &rdset);
int maxfd = server->serverFd;
while (1) {
tmp = rdset;
/*将fdset集合從使用者态拷貝到核心态,擷取新的fdset集合*/
int ret = select(maxfd + 1, &tmp, NULL, NULL, NULL);
if (ret == -1) {
server->error("select error");
} else if (ret == 0) {
continue;
} else if (ret > 0) {
if (FD_ISSET(server->serverFd, &tmp)) {
server->serverAccept();
FD_SET(server->clientFd, &rdset);
maxfd = maxfd > server->clientFd ? maxfd : server->clientFd;
}
}
for (int i = server->serverFd + 1; i <= maxfd; i++) {
if (FD_ISSET(i, &tmp)) {
char buf[1024] = {0};
int len = read(i, buf, sizeof(buf));
if (len == -1) {
server->error("read() error!");
} else if (len == 0) {
close(i);
FD_CLR(i, &rdset);
} else if (len > 0) {
std::cout << "read buf = " << buf << std::endl;
write(i, buf, strlen(buf) + 1);
}
}
}
}
return 0;
}
缺點:
1.每次調用select都需要把fd集合從使用者态拷貝到核心态,這個開銷在fd很多時,開銷很大。
2.每次調用select都需要在核心周遊傳進來的fd,這個開銷在fd很多的時候也很大.
3.select支援的檔案描述符數量很小,隻能有1024個。
4.fds集合不能重用,每次需要重置。
epoll
#include "socket.h"
int main(int argc, char *argv[]) {
ServerSock *server = new ServerSock(argv[1], argv[2]);
server->serverBind();
server->serverListen();
/*調用epoll_create()建立一個epoll執行個體*/
int epfd = epoll_create(100);
/*将監聽的檔案描述符相關的資訊添加入epoll執行個體中*/
struct epoll_event epev;
epev.events = EPOLLIN;
epev.data.fd = server->serverFd;
epoll_ctl(epfd, EPOLL_CTL_ADD, server->serverFd, &epev);
struct epoll_event epevs[1024];
while (true) {
int ret = epoll_wait(epfd, epevs, 1024, -1);
if (ret == -1) {
server->error(const_cast<char *>("epoll_wait() error"));
}
for (int i = 0; i < ret; i++) {
int curfd = epevs[i].data.fd;
if (curfd == server->serverFd) {
server->serverAccept();
epev.events = EPOLLIN;
epev.data.fd = server->clientFd;
epoll_ctl(epfd, EPOLL_CTL_ADD, server->clientFd, &epev);
} else {
if (epevs[i].events & EPOLLOUT) {
continue;
}
char buf[1024];
memset(buf, 0, sizeof(buf));
int Len = read(curfd, buf, sizeof(buf));
if (Len == -1) {
server->error(const_cast<char *>("read() error!"));
} else if (Len == 0) {
std::cout << "close client" << std::endl;
epoll_ctl(epfd, EPOLL_CTL_DEL, curfd, NULL);
} else if (Len > 0) {
std::cout << buf << std::endl;
write(curfd, buf, strlen(buf) + 1);
}
}
}
}
return 0;
}
epoll對檔案描述符有兩種操作模式LT(水準模式)和ET(邊緣模式)。簡單來說,LT是epoll的預設模式。
當epoll_wait函數檢測到有事件發生并通知應用程式,而應用程式不一定立即處理,這樣epoll_wait再次檢測到事件時
還會通知應用程式,直到事件被處理。
ET模式,隻要epoll_wait函數檢測到事件發生,通知應用程式立即進行處理,後續的epoll_wait函數将不在檢測此事件。
是以ET模式在很大程度上降低了同一個事件被epoll觸發的次數,是以效率比LT模式高。
解釋為什麼epoll預設時LT模式
LT是省卻的工作模式,并且同時支援阻塞與非阻塞 socket,這種做法中核心告訴你一個檔案描述符就緒了,然後你可以對這個
就緒的檔案描述符進行IO。如果你不做任何操作,核心還是會繼續通知你,是以這種模式出問題的機率會小一點。傳統的select
和poll都是這種模型。
設計模式
目前單例模式,構造函數不能被調用,隻有一個執行個體,該執行個體被所有程式子產品共享。
那麼我們必須保證:
(1)該類不能被複制。
(2)該類不能被公開創造。
那麼對于c++來說,它的構造函數,拷貝構造函數和指派函數都不能被公開。
#include <iostream>
class SignleTon {
private:
static SignleTon* p;
SignleTon() { std::cout << "create Singleton" << std::endl; }
~SignleTon() { std::cout << "destory Singleton" << std::endl; }
public:
static SignleTon* getSignleTon() {
if (p == nullptr) {
p = new SignleTon();
}
return p;
}
};
SignleTon* SignleTon::p = nullptr;
int main() {
SignleTon* p = SignleTon::getSignleTon();
SignleTon* pp = SignleTon::getSignleTon();
return 0;
}
該單例模式在單線程是安全的,但是在多線程時,并不安全,當有A,B兩個線程可以對SignleTon進行通路時,當A通路SignleTon
進入if()中,由于第一個進入,是以p==nullptr,但是發生系統中斷,B線程也進入,然後執行完上述流程,切換至A,又重新執行了一遍,
這樣就産生了兩個執行個體,造成資料安全問題,并且發生了記憶體洩漏問題。
保證線程安全和記憶體安全單例模式
#include <iostream>
#include <memory>
#include <mutex>
class SignleTon {
private:
static std::shared_ptr<SignleTon> p;
static std::mutex m_mutex;
SignleTon() { std::cout << "create Singleton" << std::endl; }
public:
~SignleTon() { std::cout << "destory Singleton" << std::endl; }
static std::shared_ptr<SignleTon> getSignleTon() {
if (p == nullptr) {
std::lock_guard<std::mutex> lock(m_mutex);
p = std::shared_ptr<SignleTon>(new SignleTon);
}
return p;
}
};
std::shared_ptr<SignleTon> SignleTon::p = nullptr;
std::mutex SignleTon::m_mutex;
int main() {
std::shared_ptr<SignleTon> p = SignleTon::getSignleTon();
std::shared_ptr<SignleTon> pp = SignleTon::getSignleTon();
return 0;
}
lock_guard和unique_lock的差別
lock_guard是一個互斥量作用包裝程式,他提供RALL機制,在作用域塊的持續時間内擁有一個互斥量。
當控制流離開lock_guard作用域時,lock_guard析構并釋放互斥量。它的特點,無需手動加鎖解鎖,不能中途
解鎖,需要等到作用域結束才解鎖。不能複制。
unique_lock,建立可以不鎖定,可以随時加鎖解鎖,作用域規則同lock_guard相同,條件變量需要該類型的鎖作為參數。
此時必須使用(unique_lock)。
線程池:
#include <assert.h>
#include <condition_variable>
#include <functional>
#include <iostream>
#include <memory>
#include <mutex>
#include <queue>
#include <thread>
class ThreadPool {
public:
/*處理task*/
explicit ThreadPool(int threadcount = 8) : _pool(std::make_shared<Pool>()) {
assert(threadcount > 0);
for (int i = 0; i < threadcount; i++) {
std::thread([pool = _pool] {
std::unique_lock<std::mutex> locker(pool->m_mutex);
while (true) {
if (!pool->m_queues.empty()) {
auto task = std::move(pool->m_queues.front());
pool->m_queues.pop();
locker.unlock();
task();
locker.lock();
} else if (pool->isClose) {
break;
} else {
pool->cond.wait(locker);
}
}
}).detach();
}
}
ThreadPool() = default;
ThreadPool(ThreadPool&&) = default;
/*當線程池析構時,喚醒阻塞的線程并關閉*/
~ThreadPool() {
if (static_cast<bool>(_pool)) {
std::lock_guard<std::mutex> locker(_pool->m_mutex);
_pool->isClose = true;
}
_pool->cond.notify_all();
}
template <class F>
void AddTask(F&& task) {
{
std::lock_guard<std::mutex> locker(_pool->m_mutex);
_pool->m_queues.emplace(std::forward<F>(task));
}
_pool->cond.notify_one();
}
private:
struct Pool {
std::mutex m_mutex;
std::condition_variable cond;
bool isClose = false;
std::queue<std::function<void()>> m_queues;
};
std::shared_ptr<Pool> _pool;
};
void task1() { std::cout << "I am first thread!" << std::endl; }
void task2() { std::cout << "I am second thread!" << std::endl; }
int main() {
std::shared_ptr<ThreadPool> pool = std::make_shared<ThreadPool>(8);
pool->AddTask(task1);
pool->AddTask(task2);
pool->AddTask(task2);
return 0;
}
為什麼要使用線程池技術?
好處:
重用存在的線程,減少對象的消亡,和建立,提高性能。
控制最大并發線程數,提高系統資源的使用率,同時避免過多的競争,避免堵塞。
程序有多少種狀态?
5種:建立态,運作态,就緒态,阻塞态,中止态。
過程:一個程序被建立後,放入就緒隊列,等待作業系統排程執行,執行過程中,可能切換到阻塞狀态(并發),任務完成後,程序銷毀中止。
管道的實作原理:
作業系統在核心開辟一段緩存區(成為管道)用于通信。管道是一種兩個程序間進行單項通信的機制。
簡述mmap的使用場景
mmap是一種記憶體映射檔案的方法,即将一個檔案或其他對象映射到程序的位址空間,實作檔案磁盤位址和程序虛拟位址空間中一段虛拟位址
的一一對映關系。
死鎖的條件:
程序之間互斥
請求且保持
不可剝奪條件
循環且等待
常見的關系性資料庫和非關系型資料庫之間的差別
關系型資料庫有:mysql,oracle,sql server ,sqlite
關系型資料庫最典型的資料庫是表,由二維表及其之間的聯系所組成的一個資料組織。
優點:
1.易于維護:都使用表結構,格式一緻。
2.使用友善,Sql語言通用,可用于複雜查詢。
3.複雜操作:支援sql,可用于一個表及多個表之間的非常複雜的查詢。
缺點:
1.讀寫能力較差,尤其是一個海量資料的高效讀寫。
2.固定的表結構,靈活欠缺。
3.高并發讀寫需求傳統關系型資料庫來說,硬碟IO是一個很大瓶頸。
非關系型資料庫:redis,mongoDB
非關系型資料庫,嚴格意義上不是一種資料庫,應該是一種資料結構化存儲方式的集合,可以是文檔或鍵值對等。
從資料結構的角度看,有哪些索引:
B+樹索引
為什麼使用B+樹而不是用紅黑樹?
原因:當資料量很大時,資料無法存儲在主存上,資料需要存儲在磁盤上,而在磁盤上存取的效率本身就很低,有加上機械運動,效率更低。
是以需要減少樹的高度,又因為磁盤順序通路的速度很快,可以預讀取,效果十分不錯,而紅黑樹是一個二叉樹,樹高遠大于b+樹,是以執行IO操作的次數多于B+樹。
GET和POST的差別:
GET産生一個TCP資料包,POST産生兩個TCP資料包
對于GET請求,浏覽器會把http header和data一并發送出去,伺服器相應200ok,速度快,但是不安全。
對于POST請求,浏覽器先發送header,伺服器相應100continue,浏覽器再發送data,伺服器傳回200ok,速度慢,安全。
GET請求隻能進行url編碼,POST支援多種類型的編碼。
GET比POST更不安全,參數直接漏在URL上,不能傳輸敏感資訊。
面試題:NC102 在二叉樹中找到兩個節點的最近公共祖先
題解:
1.資料量小用暴力方法先求出每個節點的父親,和深度,然後不斷往上爬,然後判斷兩個點是不是一個點。
2.資料量大,用樹剖的寫法,用重兒子把樹化成輕重鍊,通過節點往上跳方法實作
這裡隻給出資料量大的代碼:
class Solution {
public:
/**
*
* @param root TreeNode類
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
std::unordered_map<TreeNode*, TreeNode*> wightSon;
std::unordered_map<int, int> linkHead;
std::unordered_map<int, int> sonSize;
std::unordered_map<int, int> father;
std::unordered_map<int, int> dep;
void dfs1(TreeNode* pa, TreeNode* pb) {
int u = pa->val;
int fa = pb->val;
dep[u] = dep[fa] + 1;
father[u] = fa;
sonSize[u] = 1;
int Maxson = 0;
std::vector<TreeNode*> edge;
edge.clear();
if (pa->left != nullptr) {
edge.push_back(pa->left);
}
if (pa->right != nullptr) {
edge.push_back(pa->right);
}
for (int i = 0; i < edge.size(); i++) {
TreeNode* pv = edge[i];
int v = pv->val;
dfs1(pv, pa);
sonSize[u] += sonSize[v];
if (sonSize[v] > Maxson) {
wightSon[pa] = pv;
Maxson = sonSize[v];
}
}
}
void dfs2(TreeNode* pa, int phead) {
int u = pa->val;
linkHead[u] = phead;
if (wightSon[pa] == nullptr) {
return;
}
dfs2(wightSon[pa], phead);
std::vector<TreeNode*> edge;
edge.clear();
if (pa->left != nullptr) {
edge.push_back(pa->left);
}
if (pa->right != nullptr) {
edge.push_back(pa->right);
}
for (int i = 0; i < edge.size(); i++) {
TreeNode* pv = edge[i];
int v = pv->val;
if (pv != wightSon[pa]) {
dfs2(pv, v);
}
}
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
dfs1(root, root);
dfs2(root, root->val);
while (linkHead[o1] != linkHead[o2]) {
if (dep[linkHead[o1]] < dep[linkHead[o2]]) {
swap(o1, o2);
}
o1 = father[linkHead[o1]];
}
return dep[o1] < dep[o2] ? o1 : o2;
return 0;
}
};
mmap技術:
mmap的工作原理,當你調用這個的時後,他隻是在你的虛拟空間中配置設定一段記憶體,連真實的實體位址都不會配置設定,當通路這段空間時,cpu陷入os核心執行異常處理,然後異常處理會在這個時間配置設定一段實體記憶體,然後用檔案内容填充這塊記憶體,然後傳回你程序的上下文,這時的程式才會感覺到這塊記憶體有資料。
mmap優點總結
1.對檔案的讀取操作跨過頁緩存,減少了資料的拷貝次數,用記憶體讀寫代替I/O讀寫,提高檔案的讀取效率。
2.實作了使用者和核心的高效互動方式。兩空格的各自修改操作可以直接反應在映射的區域内。進而被對方空間及時捕捉。
3.提供程序的共享記憶體及互相通信的方式。不管是父程序還是無親緣關系的程序,都可以将自身使用者空間映射到同一個檔案或匿名映射到同一片區域。進而通過各自對映射區域的改動,達到程序間互相通信和資料共享的目的。
4.可用于實作大規模的資料傳輸。記憶體空間不足,是制約大資料操作的一個方面,解決方案往往是借助磁盤空間協助操作,補充記憶體的不足。但是進一步會造成大規模的IO操作,極大的影響效率。這個問題可以通過mmap映射技術很好的解決。
mmap是共享檔案
Linux下mmap讀取檔案内容/修改檔案内容
#include <errno.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#include <iostream>
int main(int argc, char *argv[]) {
int fd = 0;
char *ptr = NULL;
struct stat buf = {0};
/*擷取檔案描述符*/
fd = open(argv[1], O_RDWR);
/*将檔案複制到buf中*/
fstat(fd, &buf);
/*mmap将檔案内容拷貝到記憶體中,傳回指針ptr*/
ptr = (char *)mmap(NULL, buf.st_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd,
0);
/*關閉檔案描述符fd*/
close(fd);
/*列印檔案中的内容*/
std::cout << "MMAP: " << ' ' << ptr << std::endl;
/*修改檔案中的内容*/
ptr[0]='M';
/*列印修改後的内容*/
std::cout << "MMAP: " << ' ' << ptr << std::endl;
return 0;
}
合并有序連結清單
因為是有序的,是以用兩個指針,一個一個慢,遇到符合條件的,就把目前元素插傳入連結表,然後後移一位直到結束。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode *T, *Ts, *ans;
if (pHead1 == nullptr && pHead2 != nullptr) {
return pHead2;
} else if (pHead1 != nullptr && pHead2 == nullptr) {
return pHead1;
} else if (pHead1 != nullptr && pHead2 != nullptr) {
T = pHead1->val < pHead2->val ? pHead1 : pHead2;
Ts = T != pHead1 ? pHead1 : pHead2;
ans = T;
} else {
return pHead1;
}
while (T != nullptr || Ts != nullptr) {
if ((T->next == nullptr && Ts != nullptr) || (Ts == nullptr)) {
if (Ts != nullptr) {
T->next = Ts;
}
break;
}
int u = T->val;
int v = T->next->val;
int w = Ts->val;
if (w >= u && w <= v) {
auto p = Ts;
Ts = Ts->next;
auto Tnxt = T->next;
T->next = p;
p->next = Tnxt;
}
T = T->next;
}
return ans;
}
};
Mysql面試題:
1.說下mysql的索引有哪些,聚簇和非聚簇索引是什麼?
索引按照資料結構來說主要包含B+數和Hash索引。
聚簇索引是指索引和資料是綁定的,找到了索引就找到了資料。
2.非聚簇索引是指索引和資料是分離的,需要根據索引上的值回表查詢,非聚簇索引也叫輔助索引。2.什麼是覆寫索引和回表?
如果在查詢過程中,如果一個索引覆寫或者覆寫所需要查詢的字段值,我們就稱為覆寫索引。
回表,是select獲得的列中,包含大量非索引列,索引就需要到表中找相應列的資訊。
3.鎖的類型有哪些?
mysql鎖又分為(共享鎖)讀鎖和(排他鎖)寫鎖
讀鎖是共享的,寫鎖是不共享的,他會阻塞其他讀鎖和寫鎖
行鎖又可以分為樂觀鎖和悲觀鎖,悲觀鎖可以用update實作,樂觀鎖則通過版本号實作。
4.事務的基本特性和隔離級别?
事務基本特性ACID分别是:
原子性 指的是一個事務中的操作要麼全部成功,要麼全部失敗。
一緻性 指的是資料庫總是從一個一緻性的狀态轉換到另一個一緻性狀态。
隔離性 一個事務的修改在最終送出前都不可見。
持久性 一個事務一旦送出,就永久儲存到資料庫中。
計算機網絡:
七層模型:
應用層:例如為作業系統或網絡應用程式提供通路網絡服務的接口常見:Telent,Ftp,http,snmp,dns
表示層:(提供資料轉換格式服務)例如解密與加密,圖檔解碼和編碼,資料的壓縮和解壓縮,常見:URL加密,密碼加密,圖檔編碼碼
會話層:建立端連接配接,并提供通路驗證和會話管理。
傳輸層:提供程序之間的通信邏輯,常見的TCP,UDP,socket
網絡層:為資料在節點之間傳輸建立邏輯鍊路,并分組轉發資料,常見路由器
鍊路層:在通信的實體間建立資料鍊路
實體層:為資料裝置提供原始比特流的傳輸通路
簡述靜态路由和動态路由
1.靜态路由是由系統管理者設計與建構的路由表規定的路由。适用于網關數量有限的場合
2.動态路由是由路由選擇協定而動态建構的,路由協定之間通過交換各自所擁有的路由資訊實時更新路由表的内容。
動态路由可以自動學習網絡的拓撲結構,并更新路由表。其缺點是路由廣播更新資訊将占用大量的網絡寬帶。
說說有哪些路由協定:
RIP路由協定:距離向量協定。收集所有可到達目的地的站點資訊,并儲存到達目的地的站點數量,但RIP隻用于小型的同構網絡,因為它運作的最大站點數不超過15個,任何超過15個站點目的地均被标記不可到達。
OSPF路由協定:收集所有路由的鍊路狀态資訊,然後再利用一定的算法計算出到每個節點的最短路徑。OSPF将一定區域劃分為區,相應的對應兩種選擇方式。當源和目的地在同一區域,選擇區内路由協定,當源和目的地不在一個區時,選擇區間路由協定。
IGRP和EIGRP協定
3.簡述域名的解析過程,本機如何幹預域名解析
(1)在浏覽器中輸入www.baidu.com,作業系統會先檢查自己本地的host檔案是否有這個網址映射關系,如果有,就先調用這個IP位址映射。
(2)如果hosts裡沒有這個域名的映射,則查找本地DNS解析緩存器,是否有這個網址映射關系,如果有直接傳回,完成域名解析。
(3)如果hosts與本地DNS解析器緩存都沒有相應的網址映射關系,首先回找TCP/IP參數中設定的伺服器,通過伺服器進行查詢域名。
4.MAC位址和ip位址的差別?
(1)ip位址是IP協定統一的提供的位址格式,它為網際網路上的每一個網絡和每一台主機配置設定一個邏輯位址,以此來屏蔽實體位址的差異。而MAC位址,指的是實體位址,用來定義網絡裝置的位置。
(2)IP位址的配置設定是根據網絡的拓撲結構,而不是根據誰制造了網絡配置。
(3)ARP協定負責将IP位址映射到MAC位址上來完成。
TCP三向交握?
(1)第一次握手:建立連接配接時,用戶端向伺服器發送SYN包(seq=x),請求建立連接配接,等待确認
(2)第二次握手:伺服器收到一個SYN包傳回一個ACK(ACK=x+1)包,同時發送一個SYN包(seq=y)給用戶端。
(3)第三次握手:用戶端收到一個SYN+ACK,在傳回一個ACK(ACK=y+1),告訴伺服器端已經收到了。
(4)三次握手完成,開始傳輸資料。
說說TCP兩次握手行不行?
不行。為了資料的可靠傳輸,TCP協定的通信雙方,都必須維護一個序列号,以辨別發送出去的資料包,哪些是已經被對方所接收的。三次握手的通信雙方,即是通信雙方互相告知序列号的起始值,并确定對方已經收到了序列号起始值的必經步驟。兩次握手無法做到。
TCP和UDP的差別?
TCP協定是有連接配接的 ,UDP是無連接配接的
TCP面向位元組流,UDP面向封包。
TCP確定逾時重傳,保證資料完整,UDP不保證,隻努力傳遞。
TCP有流量控制和堵塞控制,UDP沒有,網絡擁堵不會影響發送端的發送速率。
TCP是一對一連接配接,UDP可以一對一也可以一對多。
簡述TCP逾時重傳
TCP可靠性中最重要的一個機制是處理資料逾時和重傳。TCP協定要求在發送端每發送一個封包段,就啟動一個定時器并等待确認資訊;接收端成功接收新資料後傳回确認資訊。若在定時器逾時前資料未能被确認,TCP就認為封包段中的資料已丢失或損壞,需要對封包段中的資料重新組織和重傳。
TCP協定在發送端每發送一個封包段,就啟動一個定時器并等待确認資訊。
解決擁塞:擁塞控制
通過慢啟動解決
發送開始時,定義擁塞視窗為1,每次收到一個ACK應答,擁塞視窗增加1;每次發送視窗取擁塞視窗和接收視窗的最小值。
慢啟動:在啟動初期以指數增長;設定一個慢啟動門檻值,當指數增長達到門檻值就停止指數增長,開始線性增長,按照線性增長的方式增長到擁塞視窗;線性增長達到網絡擁塞時立即把擁塞視窗置回1,進行新一輪慢啟動,同時新一輪的門檻值變為原來的一半。
HTTP:
cookie和session的關系和差別是什麼
1.cookie與session都是會話方式的一種。他們的典型使用場景就是“購物車”,當你點選下單按鈕時,服務端并不清除具體的使用者的具體操作。為了辨別并跟蹤該使用者,了解購物車中有幾樣物品,伺服器通過使用者建立cookie/session來擷取這些資訊。
2.cookie資料放在用戶端浏覽器上,session資料放在伺服器上。
vector的擴容
/*頭檔案*/
#include <iostream>
#ifndef _VECTOR_H_
#define _VECTOR_H_
class Vector;
class Vector {
public:
Vector() : _factor(2), _capcity(0), _size(0), isguard(0) {}
~Vector() {
if (_arry != nullptr) {
delete[] _arry;
}
}
int _size;
int _capcity;
int _factor;
int isguard;
int *_arry = nullptr;
void rebuildcapcity();
void push_back(int val);
void prVal();
};
#endif
/*.cpp檔案*/
#include "Vector.h"
void Vector::rebuildcapcity() {
int n = (_capcity == 0) ? 1 : _capcity;
this->isguard++;
int *_tmp = new int[n << 1];
for (int i = 0; i < n; i++) {
_tmp[i] = _arry[i];
}
_capcity = n << 1;
delete[] _arry;
_arry = _tmp;
}
void Vector::push_back(int val) {
if (_size == _capcity) {
rebuildcapcity();
}
++_size;
_arry[_size - 1] = val;
}
void Vector::prVal() {
for (int i = 0; i < _size; i++) {
std::cout << _arry[i] << std::endl;
}
}
設定非阻塞:
int flag=fcntl(fd,F_GETFD,0);
flag|=O_NONBLOCK;
fcntl(fd,F_SETFL,flag);
assert(條件)函數如果條件為真,繼續向下執行,反則終止程式
Reactor模式:
利用IO多路複用和線程池技術,其中read()操作是阻塞操作
用戶端1,用戶端2,用戶端3->epoll:Accept處理監聽的事件,利用線程池的子線程去處理read(),write(),等任務。
需要主線程(I/O處理單元)隻負責監聽檔案描述符上是否有事件發生,有的話,就立即将該事件通知工作線程,将socket可讀可寫事件,放入請求隊列,交給工作線程處理,除此之外主線程不做任何其他實質性的工作,讀寫資料,接收新的連接配接,以及處理客戶請求均在工作線程中完成。
使用同步I/O(以epoll_wait為例)實作reactor模式的工作流程:
1.主線程往epoll核心事件表中注冊socket上的讀就緒事件。
2.主線程調用epoll_wait等待socket上有資料可讀。
3.當socket上有資料可讀時,epoll_wait通知主線程,主線程則将socket可讀事件放入請求隊列。
4.睡眠在請求隊列上的某個線程被喚醒,他從socket讀取資料,并處理客戶請求,然後往epoll核心事件表中注冊該socket上的寫就緒事件。
5.當主線程調用epoll_wait等待socket可寫。
6.當socket可寫時,epoll_wait通知主線程,主線程将socket可寫事件放入請求隊列。
7.睡眠在請求隊列上的某個工作隊列被喚醒,它往socket上寫入伺服器處理客戶請求的結果。
c++11 chrono
chrono是c++11中的時間庫,提供計時,時鐘等功能。
學習chrono,關鍵是了解裡面時間段(Durations),時間點(Time points)的概念。
1.精度
時鐘節拍(時間精度):
template<intmax_t N,intmax_t D=1>class ratio;
其中N表示分子,D表示分母,預設用秒表示時間機關。N對應其成員num,D對應于其成員den
常用的機關:
ratio<60,1> mintue
ratio<1,1> second
ratio<1,1000> microsecond
std::atomic對int,char,bool等資料結構實作原子封裝,在多線程環境中,對std::atomic的通路
不會造成競争-冒險,利用std::atomic可實作資料結構的無鎖設計。
bzero函數
函數原型:void bzero(void *s,int Len);設定字元串前Len位為0
struct iovec
{
ptr iov_base;/*Starting address*/
size_t iov_len;/*Length in bytes*/
}
struct iovec定義了一個向量元素。通常這個結構用作一個多元素數組。對于某一個傳輸的元素,指針的成員iov_base指向一個緩沖區,這個緩沖區是存放readv所接收的資料。成員iov_len在各種情況下分别确定了所接收的最大長度以及實際寫入的長度。
分頁和分段有什麼差別?
- 段時資訊的邏輯機關,他是根據使用者的需求劃分的,是以段對使用者是可見的,頁是資訊的實體機關,是為了管理主存的友善而劃分的,對使用者是透明的。
- 段的大小不固定,由他所完成的功能決定,頁的大小固定,由系統決定。
- 段向使用者提供二維位址空間;頁向使用者提供一維位址空間。
- 段是資訊的邏輯機關,便于存儲保護和資訊的共享,頁的保護和共享受限。
說說程序同步有哪幾種機制。
原子操作,信号量機制,自選鎖管程,會合,分布式系統。
預防死鎖:
資源一次性配置設定,破壞請求且保持。
可剝奪資源。
資源有序配置設定法,配置設定資源按序配置設定,釋放則相反。
求最大連續不相同字元串(‘a’-‘z’)
class Solution {
int clac(int nowst) {
int ans = 0;
while (nowst) {
if (nowst & 1) {
ans++;
}
nowst >>= 1;
}
return ans;
}
public:
int lengthOfLongestSubstring(string nowstr) {
int n, maxLength = 0;
vector<int> st(26, 0);
string getLongest = "";
n = nowstr.size() + 1;
vector<int> suffxor(n, 0);
for (int i = 0; i < n - 1; i++) {
suffxor[i + 1] = suffxor[i] ^ (1<<(nowstr[i] - 'a'));
}
int nowst = 0;
for (int i = 0; i < n - 1; i++) {
if ((nowst >> (nowstr[i] - 'a')) & 1) {
int nowLen = clac(nowst);
if (nowLen > maxLength) {
maxLength = nowLen;
}
nowst = suffxor[i + 1] ^ st[nowstr[i] - 'a'];
st[nowstr[i] - 'a'] = suffxor[i + 1];
} else {
nowst |= 1 << (nowstr[i] - 'a');
st[nowstr[i] - 'a'] = suffxor[i + 1];
int nowLen = clac(nowst);
if (nowLen > maxLength) {
maxLength = nowLen;
}
}
}
return maxLength;
}
};
- 聯合索引在B+樹上的存儲結構
- 聯合索引的查找方式
- 為什麼會有最左字首比對原則
聚簇索引和非聚簇索引
聚簇索引也叫聚集索引,它實際上并不是一個中單獨的索引類型,而是一種資料存儲方式,聚簇索引的葉子節點儲存了一行記錄的所有列資訊。也就是說,聚簇索引的葉子節點中,包含了記錄行。
非聚簇索引也叫輔助索引,普通索引,它的葉子節點隻對應一個主鍵值,通過非聚簇索引查找記錄要先找到主鍵,然後通過主鍵再到聚簇索引中找到對應記錄行,這個過程被稱為回表。
覆寫索引
如果輔助索引已經得到我們想要的資料了,那麼我們就不需要,進行回表查詢了,這個給就是覆寫索引。
聯合索引
同時對多列建立索引,建立聯合索引,葉節點會同時包含每個索引列的值。并且同時根據多列排序,這個排序和我們平時了解的字典序類似。
唯一索引
唯一索引是一種不允許有相同索引值的索引,系統在建立索引時,會檢查是否有重複出現的鍵值,每次更新或增加都會檢查這一點,主鍵索引就是唯一索引。
隻要建立了索引就一定會走索引嗎?
不對,在使用聯合索引時,索引的使用要符合一原則:最左字首比對原則,不然索引會失效。
不應該對索引使用運算,例如id+1等,會使索引失效。
索引列不能包含NULL。
為什麼會産生粘包問題?
Nagle算法主要做兩件事,隻有上一個分組得到确認,才會發送下一個分組,在一個确認到來時一起發送。多個分組拼裝為一個資料段發送出去,如果沒有處理好邊界問題,在解包時會出現粘包。
流量控制,擁塞控制也可能導緻粘包。
接收方不及時接收緩沖區的包,造成多個包被接受。
如何解決TCP粘包問題:
1.在适當場景禁用nagle算法。
2.其他幾種情況的處理方法主要分為兩種:
- 尾部标記序列。通過特殊辨別符表示資料包的邊界
- 頭部标記分步接收。在TCP封包的頭部上表示資料長度。
- 應用層發送資料定時發送。
Time-Wait的作用?
- 為了保證用戶端發送的最後一個ack封包段能搞到達伺服器。因為這最後一個ack可能會丢失。Time-Wait的持續時間為2MSL,MSL是Maximum Segment Lifetime,譯為最大生存時間。如果沒有2MSL,用戶端發送完ACK後就直接關閉了,如果出現ACK丢包現象,伺服器端就收不到逾時重傳的fin資訊封包,就産生異常,消耗資源。
- g++ -E test.cpp >test.ii 預處理
- g++ -S test.ii 編譯
- g++ -c test.ii 彙編
- g++ test.o -o test 連結
- ./test 運作