1、系統調用與函數調用的區別;
2、Linux內存模型、布局
3、怎樣用O(1)的時間復雜度實現拒絕1秒超過百次訪問的IP
4、TCP模型
5、後台架構是怎樣的;
6、怎樣實現負載均衡;
7、怎樣進行服務發現;
8、O(n)時間復雜度實現刪除字符串的全部空格,不允許申請空間;
9、用非遞歸的方式實現二叉樹左右子樹的交換;
1、系統調用與函數調用的區別;Linux下對文件操作有兩種方式:系統調用(system call)和庫函數調用(Library functions)。系統調用實際上就是指最底層的一個調用,在linux程序設計裡面就是底層調用的意思。面向的是硬件。而庫函數調用則面向的是應用開發的,相當於應用程序的api,采用這樣的方式有很多種原因,第一:雙緩沖技術的實現。第二,可移植性。第三,底層調用本身的一些性能方面的缺陷。第四:讓api也可以有了級別和專門的工作面向。
1、系統調用
系統調用提供的函數如open, close, read, write, ioctl等,需包含頭文件unistd.h.以write為例:其函數原型為 size_t write(int fd, const void *buf, size_t nbytes),其操作對象為文件描述符或文件句柄fd(file descriptor),要想寫一個文件,必須先以可寫權限用open系統調用打開一個文件,獲得所打開文件的fd,例如 fd=open(\“/dev/video\”, O_RDWR)。fd是一個整型值,每新打開一個文件,所獲得的fd為當前最大fd加1.Linux系統默認分配了3個文件描述符值:0-standard
input,1-standard output,2-standard error.
系統調用通常用於底層文件訪問(low-level file access),例如在驅動程序中對設備文件的直接訪問。
系統調用是操作系統相關的,因此一般沒有跨操作系統的可移植性。
系統調用發生在內核空間,因此如果在用戶空間的一般應用程序中使用系統調用來進行文件操作,會有用戶空間到內核空間切換的開銷。事實上,即使在用戶空間使用庫函數來對文件進行操作,因為文件總是存在於存儲介質上,因此不管是讀寫操作,都是對硬件(存儲器)的操作,都必然會引起系統調用。也就是說,庫函數對文件的操作實際上是通過系統調用來實現的。例如C庫函數fwrite()就是通過write()系統調用來實現的。
這樣的話,使用庫函數也有系統調用的開銷,為什麼不直接使用系統調用呢?這是因為,讀寫文件通常是大量的數據(這種大量是相對於底層驅動的系統調用所實現的數據操作單位而言),這時,使用庫函數就可以大大減少系統調用的次數。這一結果又緣於緩沖區技術。在用戶空間和內核空間,對文件操作都使用了緩沖區,例如用fwrite寫文件,都是先將內容寫到用戶空間緩沖區,當用戶空間緩沖區滿或者寫操作結束時,才將用戶緩沖區的內容寫到內核緩沖區,同樣的道理,當內核緩沖區滿或寫結束時才將內核緩沖區內容寫到文件對應的硬件媒介。
2、庫函數調用
標准C庫函數提供的文件操作函數如fopen, fread, fwrite, fclose, fflush, fseek等,需包含頭文件stdio.h.以fwrite為例,其函數原型為size_t fwrite(const void *buffer, size_t size, size_t item_num, FILE *pf),其操作對象為文件指針FILE *pf,要想寫一個文件,必須先以可寫權限用fopen函數打開一個文件,獲得所打開文件的FILE結構指針pf,例如pf=fopen(\“~/proj/filename\”,
\“w\”)。實際上,由於庫函數對文件的操作最終是通過系統調用實現的,因此,每打開一個文件所獲得的FILE結構指針都有一個內核空間的文件描述符fd與之對應。同樣有相應的預定義的FILE指針:stdin-standard input,stdout-standard output,stderr-standard error.
庫函數調用通常用於應用程序中對一般文件的訪問。
庫函數調用是系統無關的,因此可移植性好。
由於庫函數調用是基於C庫的,因此也就不可能用於內核空間的驅動程序中對設備的操作。
※ 函數庫調用 VS 系統調用
原文出自【比特網】,轉載請保留原文鏈接:http://soft.chinabyte.com/os/258/12424258.shtml
2、Linux內存模型、布局
其實這個是個很牛的設計。linux充分利用了程序的局部性原理,結合線性地址的概念(虛擬地址)使得運行於操作系統上的每個進程都可以使用所有用戶空間主存。而且虛擬內存還解決了內存不連續和碎片的問題(因為在程序來說線性地址都是連續的);每個進程都有各自的頁表,虛擬地址空間都各自獨立,互補干擾;
那麼我們的程序裡申請的內存的時候,linux內核其實只分配一個虛擬內存( 線性地址),並沒有分配實際的物理內存。只有當程序真正使用這塊內存時,才會分配物理內存。這就叫做延遲分配和請頁機制。釋放內存時,先釋放線性區對應的物理內存,然後釋放線性區;
什麼時候內核為進程劃分物理內存的呢? 當進程執行時,申請的內存只是一塊虛擬內存區域,而不是實際的物理內存,只是獲得了一塊虛擬內存區域上線性地址區間的使用權。實際的物理內存只有當進程真的去訪問新獲得的虛擬地址時,才會由"請頁機制"產生"缺頁"異常,從而進入分配實際頁框的例程。此異常會告訴內核去真正為進程分配物理頁,並建立對應的頁表。這之後虛擬地址才實實在在的映射到了物理內存上了。"請頁機制"將物理內存的分配延後了,這樣是充分利用了程序的局部性原來,節約內存空間,提高系統吞吐;
那麼cpu執行指令訪存,使用的都是物理內存地址,而我們的編譯器生成的二進制碼實際上分配的都是邏輯內存(邏輯地址);那麼線性地址是如何轉換為物理內存地址的呢?我們知道內存模型裡有,段,頁機制來尋址內存的;(物理內存也是劃分為頁為單位劃分的) ;我們的程序主要分為數據段,代碼段;數據段存放代碼裡已初始化數據,代碼段存放可執行代碼指令;linux通過段機制將我們程序的邏輯地址轉換為線性地址,又通過頁機制將線性地址轉換為物理地址。
我們知道Linux內核啟動起來時,如果是4G內存,那麼會有大約1G被內核占用。其他3G會被用戶進行使用。我們稍後會講解內核內存如何和用戶內存通信。
一個進程對應的內存空間包含一下5個區:
代碼段 :存放可執行文件的操作指令;
數據段: 存放可執行文件申請已經初始化的全局變量;
BSS段: 存放未初始化的全局變量;
堆: 存放用戶程序運行中,動態申請的內存空間;
棧: 存放用戶程序運行中,臨時創建的局部變量;我們知道CPU有寄存器是直接可以訪問棧的,所以棧比堆快多了。
那麼既然每個進程都有各自的虛擬內存空間,各自互不相干,那麼進程間如何共享內存,內核又是如何向進程空間傳遞數據? 都是通過映射實現的,通過將內核的虛擬內存映射到當前進程用戶空間的虛擬內存,當然映射時,要新建一個頁表;
linux還通過cache+buffer機制: 將最近使用過的數據盡量cache,buffer起來,以便稍後會使用到;這就是說我們的可用內存=free + buffer + cache;
3、怎樣用O(1)的時間復雜度實現拒絕1秒超過百次訪問的IP
4、TCP模型
5、後台架構是怎樣的;
6、怎樣實現負載均衡;
7、怎樣進行服務發現;
8、O(n)時間復雜度實現刪除字符串的全部空格,不允許申請空間;
#include<conio.h>
#include<stdio.h>
#include<string.h>
char *fun(char *str)
{
int i = 0 ;
int j = 0 ;
for( ; i < strlen(str) ; i++ )
{
if( str[i] != ' ' )
{
str[j++] = str[i] ;
}
}
str[j] = '\0' ;
return str ;
}
void main()
{
char s[81],*ds;
printf("\nPlease enter a string:");
gets(s);
ds=fun(s);
printf("\nResult:%s\n",ds);
}
9、實現二叉樹左右子樹的交換;
遞歸:
BiNode* Exchange(BiNode* T)
{
BiNode* p;
if(NULL==T || (NULL==T->lchild && NULL==T->rchild))
return T;
p = T->lchild;
T->lchild = T->rchild;
T->rchild = p;
if(T->lchild)
{
T->lchild = Exchange(T->lchild);
}
if(T->rchild)
{
T->rchild = Exchange(T->rchild);
}
return T;
}
非遞歸:
void NonRecursive_Exchange(BiNode* T)
{
Stack s;
BiNode* p;
if(NULL==T)
return;
InitStack(&s);
Push(&s,T);
while(!isEmpty(&s))
{
T = Pop(&s);
p = T->lchild;
T->lchild = T->rchild;
T->rchild = p;
if(T->rchild)
Push(&s,T->rchild);
if(T->lchild)
Push(&s,T->lchild);
}
DestroyStack(&s);
}