• 正文
    • 那薪資待遇如何呢?
    • 具體的面試題如下:
    • 中國電信(一面)
    • 中國電信(二面)
  • 相關推薦
申請入駐 產(chǎn)業(yè)圖譜

中國電信一面二面直接秒了 附:面試題+解析

03/27 11:00
1458
加入交流群
掃碼加入
獲取工程師必備禮包
參與熱點資訊討論

圖解學習網(wǎng)站:https://xiaolincoding.com

大家好,我是小林。

有同學問我有沒有寫過電信的面經(jīng)?我翻了一下我的記錄,發(fā)現(xiàn)還沒寫過中國電信的面經(jīng),但是寫過中國移動的面經(jīng)。

中國電信、移動和聯(lián)通是國內三大運營商了,都屬于國企,每年也是一樣都有開發(fā)崗位的招聘需求,國企的優(yōu)勢就是加班不多,相比互聯(lián)網(wǎng)公司能早下班,而且也更加穩(wěn)定一些。

那薪資待遇如何呢?

中國電信給校招軟開崗的總包是?20 萬-25 萬(一線城市),二線城市的話是 15 萬左右,不過總包是算上各種福利總和(比如獎金、公積金啥的),每個月實際到手會比私企 20w 總包的低一些。

之前訓練營也有校招同學拿到一線城市中國電信 offer,開的是總包 21w。

二線城市的中國電信開的是 15w 總包

這次跟大家聊聊中國移動的軟開一二面面經(jīng),中國移動面試流程是 2 輪面試,面試的時長都不算長:

    第一輪技術面面了 30 分鐘,拷打了操作系統(tǒng)、網(wǎng)絡、Redis、Java 方面的知識第二輪則是技術面+hr 面一起了,時長 20 分鐘,技術問的問題比多,主要是拷打了 操作系統(tǒng)+數(shù)據(jù)結構方面的內容,剩下了就是聊天局了。

具體的面試題如下:

中國電信(一面)

1. 信號了解嗎,平時接觸過哪些信號?

信號是進程間通信的一種方式,它是操作系統(tǒng)向進程發(fā)送的一種異步通知機制,用于告知進程發(fā)生了某個特定事件。進程可以根據(jù)接收到的信號采取相應的行動,如暫停執(zhí)行、繼續(xù)執(zhí)行、終止進程等。

平時接觸過的信號有:

SIGINT(中斷信號)

    • :通常由用戶按下 Ctrl+C 組合鍵產(chǎn)生,用于通知進程需要中斷當前的操作并終止運行。例如,在命令行中運行一個程序時,按下 Ctrl+C 可以向該程序進程發(fā)送 SIGINT 信號,使其停止運行。

SIGTERM(終止信號)

    • :這是一種正常的終止信號,用于通知進程優(yōu)雅地結束運行。與 SIGINT 不同,SIGTERM 通常由系統(tǒng)或其他進程發(fā)送,而不是由用戶直接觸發(fā)。進程接收到 SIGTERM 信號后,應該進行一些清理工作,如關閉打開的文件、釋放資源等,然后再終止。許多服務程序在接收到 SIGTERM 信號后會逐步停止正在處理的任務,并關閉連接,以確保系統(tǒng)的穩(wěn)定性和數(shù)據(jù)的完整性。

SIGKILL(強制終止信號)

    :這是一種強制終止進程的信號,不允許進程進行任何清理操作,直接將進程終止。通常在進程出現(xiàn)嚴重錯誤或無法正常終止時使用。例如,當一個進程陷入死循環(huán)或占用大量系統(tǒng)資源且無法通過其他方式停止時,可以使用 SIGKILL 信號來強制結束該進程。不過,由于 SIGKILL 信號不會給進程留下清理資源的機會,可能會導致一些資源泄漏或數(shù)據(jù)不一致的問題,所以應該謹慎使用。

2. 操作系統(tǒng)中,進程同步與數(shù)據(jù)傳輸有什么方法,各自有什么特點?

進程同步的方法有下面這些:

信號量

    • :信號量是一個整數(shù)變量,用于控制多個進程對共享資源的訪問。它可以實現(xiàn)更復雜的同步策略,如控制并發(fā)訪問的進程數(shù)量。當信號量的值大于 0 時,進程可以獲取信號量并訪問資源,同時信號量的值減 1;當信號量的值為 0 時,進程需要等待。信號量可以分為二進制信號量(只能取 0 和 1)和計數(shù)信號量(可以取任意非負整數(shù))。優(yōu)點是能靈活控制資源的并發(fā)訪問,適用于多種復雜的同步場景。缺點是如果使用不當,也可能出現(xiàn)死鎖或資源分配不合理的情況。

互斥鎖

    • :互斥鎖是一種簡單的進程同步機制。當一個進程訪問共享資源時,它會獲取互斥鎖,其他進程則必須等待,直到該進程釋放鎖。這種方法能確保在任何時刻只有一個進程可以訪問共享資源,實現(xiàn)了對資源的互斥訪問。優(yōu)點是實現(xiàn)簡單,適用于對少量資源的短期鎖定。缺點是如果一個進程在持有鎖期間出現(xiàn)異?;蜷L時間不釋放鎖,可能導致其他進程長時間等待,甚至出現(xiàn)死鎖。

條件變量:

    條件變量通常與互斥鎖一起使用,用于實現(xiàn)進程間的條件等待。一個進程可以在某個條件滿足時通過條件變量通知其他等待的進程。它允許進程在等待特定條件發(fā)生時阻塞,避免了忙等待,從而提高了系統(tǒng)的效率。優(yōu)點是能有效實現(xiàn)進程間的協(xié)作,減少不必要的 CPU 開銷。缺點是需要與互斥鎖配合使用,編程相對復雜,且對條件的判斷和通知機制需要謹慎處理,否則可能導致程序出現(xiàn)邏輯錯誤。

進程傳輸數(shù)據(jù)方法:

管道:

    • 管道是一種半雙工的通信方式,用于在具有親緣關系的進程之間傳輸數(shù)據(jù)。通常由父進程創(chuàng)建管道,然后 fork 出子進程,子進程和父進程通過管道進行數(shù)據(jù)傳輸。數(shù)據(jù)在管道中是單向流動的,一端用于寫入數(shù)據(jù),另一端用于讀取數(shù)據(jù)。管道的優(yōu)點是簡單易用,能方便地實現(xiàn)進程間的通信。缺點是只能在有親緣關系的進程間使用,且半雙工的特性限制了數(shù)據(jù)傳輸?shù)撵`活性,同時管道的容量有限,如果寫入速度過快可能導致數(shù)據(jù)堵塞。

消息隊列:

    • 消息隊列是一種異步的通信機制,進程可以向消息隊列中發(fā)送消息,其他進程可以從消息隊列中讀取消息。消息隊列中的消息具有一定的格式和優(yōu)先級,不同進程可以根據(jù)自己的需求從隊列中獲取消息。它允許進程在不同的時間進行通信,不需要實時等待對方的響應。優(yōu)點是通信具有異步性和松耦合性,適用于不同步執(zhí)行的進程間通信。缺點是消息的大小和隊列的長度可能受到系統(tǒng)限制,而且如果消息處理不及時,可能導致隊列溢出。

共享內存:

    • 共享內存是一種高效的進程間通信方式,它允許多個進程共享同一塊內存區(qū)域。進程可以直接讀寫共享內存中的數(shù)據(jù),無需進行數(shù)據(jù)的復制。這種方式大大提高了數(shù)據(jù)傳輸?shù)男?,尤其適用于大量數(shù)據(jù)的共享。但是,由于多個進程可以同時訪問共享內存,因此需要配合同步機制(如互斥鎖、信號量等)來保證數(shù)據(jù)的一致性和完整性。優(yōu)點是數(shù)據(jù)傳輸效率高,能快速共享大量數(shù)據(jù)。缺點是需要復雜的同步機制來確保數(shù)據(jù)的正確性,編程難度較大,且對共享內存的訪問控制需要謹慎處理,否則可能導致數(shù)據(jù)混亂。

套接字:

    套接字是一種網(wǎng)絡通信機制,不僅可以用于不同主機上的進程間通信,也可以用于同一主機上的進程間通信。它提供了一種基于網(wǎng)絡協(xié)議的通信方式,支持多種通信協(xié)議,如 TCPUDP。通過套接字,進程可以發(fā)送和接收數(shù)據(jù)報,實現(xiàn)雙向的數(shù)據(jù)傳輸。套接字的優(yōu)點是具有很強的通用性和靈活性,能適應不同的網(wǎng)絡環(huán)境和通信需求。缺點是網(wǎng)絡通信存在一定的延遲和不確定性,而且需要處理網(wǎng)絡故障、數(shù)據(jù)丟失等問題,編程實現(xiàn)相對復雜。

3. 了解過哪些網(wǎng)絡協(xié)議?

4. 說一下https加密過程?

傳統(tǒng)的 TLS 握手基本都是使用 RSA 算法來實現(xiàn)密鑰交換的,在將 TLS 證書部署服務端時,證書文件其實就是服務端的公鑰,會在 TLS 握手階段傳遞給客戶端,而服務端的私鑰則一直留在服務端,一定要確保私鑰不能被竊取。

在 RSA 密鑰協(xié)商算法中,客戶端會生成隨機密鑰,并使用服務端的公鑰加密后再傳給服務端。根據(jù)非對稱加密算法,公鑰加密的消息僅能通過私鑰解密,這樣服務端解密后,雙方就得到了相同的密鑰,再用它加密應用消息。

我用 Wireshark 工具抓了用 RSA 密鑰交換的 TLS 握手過程,你可以從下面看到,一共經(jīng)歷了四次握手:

TLS 第一次握手

首先,由客戶端向服務器發(fā)起加密通信請求,也就是 ClientHello 請求。在這一步,客戶端主要向服務器發(fā)送以下信息:

    (1)客戶端支持的 TLS 協(xié)議版本,如 TLS 1.2 版本。(2)客戶端生產(chǎn)的隨機數(shù)(Client Random),后面用于生成「會話秘鑰」條件之一。(3)客戶端支持的密碼套件列表,如 RSA 加密算法。

TLS 第二次握手

服務器收到客戶端請求后,向客戶端發(fā)出響應,也就是 SeverHello。服務器回應的內容有如下內容:

    (1)確認 TLS 協(xié)議版本,如果瀏覽器不支持,則關閉加密通信。(2)服務器生產(chǎn)的隨機數(shù)(Server Random),也是后面用于生產(chǎn)「會話秘鑰」條件之一。(3)確認的密碼套件列表,如 RSA 加密算法。(4)服務器的數(shù)字證書。

TLS 第三次握手

客戶端收到服務器的回應之后,首先通過瀏覽器或者操作系統(tǒng)中的 CA 公鑰,確認服務器的數(shù)字證書的真實性。

如果證書沒有問題,客戶端會從數(shù)字證書中取出服務器的公鑰,然后使用它加密報文,向服務器發(fā)送如下信息:

    (1)一個隨機數(shù)(pre-master key)。該隨機數(shù)會被服務器公鑰加密。(2)加密通信算法改變通知,表示隨后的信息都將用「會話秘鑰」加密通信。(3)客戶端握手結束通知,表示客戶端的握手階段已經(jīng)結束。這一項同時把之前所有內容的發(fā)生的數(shù)據(jù)做個摘要,用來供服務端校驗。

上面第一項的隨機數(shù)是整個握手階段的第三個隨機數(shù),會發(fā)給服務端,所以這個隨機數(shù)客戶端和服務端都是一樣的。

服務器和客戶端有了這三個隨機數(shù)(Client Random、Server Random、pre-master key),接著就用雙方協(xié)商的加密算法,各自生成本次通信的「會話秘鑰」。

TLS 第四次握手

服務器收到客戶端的第三個隨機數(shù)(pre-master key)之后,通過協(xié)商的加密算法,計算出本次通信的「會話秘鑰」。

然后,向客戶端發(fā)送最后的信息:

    (1)加密通信算法改變通知,表示隨后的信息都將用「會話秘鑰」加密通信。(2)服務器握手結束通知,表示服務器的握手階段已經(jīng)結束。這一項同時把之前所有內容的發(fā)生的數(shù)據(jù)做個摘要,用來供客戶端校驗。

至此,整個 TLS 的握手階段全部結束。接下來,客戶端與服務器進入加密通信,就完全是使用普通的 HTTP 協(xié)議,只不過用「會話秘鑰」加密內容。

5. 使用緩存時可能會產(chǎn)生什么問題,如何解決?

    • 可能會出現(xiàn)緩存與數(shù)據(jù)庫數(shù)據(jù)不一致的問題,導致業(yè)務邏輯錯誤,比如更新數(shù)據(jù)庫后,緩存未同步或同步失敗。解決方式通過Canal監(jiān)聽數(shù)據(jù)庫Binlog,異步更新緩存,保證最終一致性。熱點 key 問題,某個Key的訪問量極高,導致緩存服務器單點壓力過大,解決方式將一個熱點Key拆分為多個子Key(如

hot_key:1

    • 、

hot_key:2

    ),分散到不同節(jié)點。大 key 的問題,單個Key存儲的數(shù)據(jù)過大(如10MB的List),導致網(wǎng)絡阻塞、查詢緩慢,解決方式將大Key拆分為多個小Key,或使用壓縮算法(如Gzip)減少體積。緩存異常的問題,比如緩存擊穿、穿透、雪崩的問題

6. 緩存擊穿,穿透,雪崩是什么,如何預防?

緩存雪崩:當大量緩存數(shù)據(jù)在同一時間過期(失效)或者 Redis 故障宕機時,如果此時有大量的用戶請求,都無法在 Redis 中處理,于是全部請求都直接訪問數(shù)據(jù)庫,從而導致數(shù)據(jù)庫的壓力驟增,嚴重的會造成數(shù)據(jù)庫宕機,從而形成一系列連鎖反應,造成整個系統(tǒng)崩潰,這就是緩存雪崩的問題。

緩存擊穿:如果緩存中的某個熱點數(shù)據(jù)過期了,此時大量的請求訪問了該熱點數(shù)據(jù),就無法從緩存中讀取,直接訪問數(shù)據(jù)庫,數(shù)據(jù)庫很容易就被高并發(fā)的請求沖垮,這就是緩存擊穿的問題。


緩存穿透:當用戶訪問的數(shù)據(jù),既不在緩存中,也不在數(shù)據(jù)庫中,導致請求在訪問緩存時,發(fā)現(xiàn)緩存缺失,再去訪問數(shù)據(jù)庫時,發(fā)現(xiàn)數(shù)據(jù)庫中也沒有要訪問的數(shù)據(jù),沒辦法構建緩存數(shù)據(jù),來服務后續(xù)的請求。那么當有大量這樣的請求到來時,數(shù)據(jù)庫的壓力驟增,這就是緩存穿透的問題。

緩存雪崩解決方案:

均勻設置過期時間:如果要給緩存數(shù)據(jù)設置過期時間,應該避免將大量的數(shù)據(jù)設置成同一個過期時間。我們可以在對緩存數(shù)據(jù)設置過期時間時,給這些數(shù)據(jù)的過期時間加上一個隨機數(shù),這樣就保證數(shù)據(jù)不會在同一時間過期。

互斥鎖:當業(yè)務線程在處理用戶請求時,如果發(fā)現(xiàn)訪問的數(shù)據(jù)不在 Redis 里,就加個互斥鎖,保證同一時間內只有一個請求來構建緩存(從數(shù)據(jù)庫讀取數(shù)據(jù),再將數(shù)據(jù)更新到 Redis 里),當緩存構建完成后,再釋放鎖。未能獲取互斥鎖的請求,要么等待鎖釋放后重新讀取緩存,要么就返回空值或者默認值。

實現(xiàn)互斥鎖的時候,最好設置超時時間,不然第一個請求拿到了鎖,然后這個請求發(fā)生了某種意外而一直阻塞,一直不釋放鎖,這時其他請求也一直拿不到鎖,整個系統(tǒng)就會出現(xiàn)無響應的現(xiàn)象。后臺更新緩存:業(yè)務線程不再負責更新緩存,緩存也不設置有效期,而是讓緩存“永久有效”,并將更新緩存的工作交由后臺線程定時更新。

緩存擊穿解決方案:

    互斥鎖方案,保證同一時間只有一個業(yè)務線程更新緩存,未能獲取互斥鎖的請求,要么等待鎖釋放后重新讀取緩存,要么就返回空值或者默認值。不給熱點數(shù)據(jù)設置過期時間,由后臺異步更新緩存,或者在熱點數(shù)據(jù)準備要過期前,提前通知后臺線程更新緩存以及重新設置過期時間;

緩存穿透解決方案:

    非法請求的限制:當有大量惡意請求訪問不存在的數(shù)據(jù)的時候,也會發(fā)生緩存穿透,因此在 API 入口處我們要判斷求請求參數(shù)是否合理,請求參數(shù)是否含有非法值、請求字段是否存在,如果判斷出是惡意請求就直接返回錯誤,避免進一步訪問緩存和數(shù)據(jù)庫。緩存空值或者默認值:當我們線上業(yè)務發(fā)現(xiàn)緩存穿透的現(xiàn)象時,可以針對查詢的數(shù)據(jù),在緩存中設置一個空值或者默認值,這樣后續(xù)請求就可以從緩存中讀取到空值或者默認值,返回給應用,而不會繼續(xù)查詢數(shù)據(jù)庫。布隆過濾器:我們可以在寫入數(shù)據(jù)庫數(shù)據(jù)時,使用布隆過濾器做個標記,然后在用戶請求到來時,業(yè)務線程確認緩存失效后,可以通過查詢布隆過濾器快速判斷數(shù)據(jù)是否存在,如果不存在,就不用通過查詢數(shù)據(jù)庫來判斷數(shù)據(jù)是否存在。即使發(fā)生了緩存穿透,大量請求只會查詢 Redis 和布隆過濾器,而不會查詢數(shù)據(jù)庫,保證了數(shù)據(jù)庫能正常運行,Redis 自身也是支持布隆過濾器的。

7. 有一組服務器,現(xiàn)在來了一個任務,希望實現(xiàn)一個均衡調度算法,有什么思路?

輪詢調度

    • :依次將任務分配給每臺服務器,簡單公平,但未考慮服務器負載差異

加權輪詢

    • :根據(jù)服務器性能分配不同權重,高性能服務器獲得更多任務,缺點權重值的設置需要根據(jù)服務器的實際情況進行調整,且難以動態(tài)適應服務器負載的變化。

最少連接

    • :將新任務分配給當前連接數(shù)最少的服務器,這樣可以確保任務被分配到相對空閑的服務器上,避免某些服務器過載

加權最少連接算法

    :加權最少連接算法結合了加權輪詢算法和最少連接算法的優(yōu)點。在考慮服務器當前連接數(shù)的同時,還考慮了服務器的性能權重。計算每臺服務器的 “加權連接數(shù)”(通常為當前連接數(shù)除以權重值),將新任務分配給加權連接數(shù)最小的服務器。

8. Java的容器了解嗎,用過哪些,適用的場景?

List是有序的Collection,使用此接口能夠精確的控制每個元素的插入位置,用戶能根據(jù)索引訪問List中元素。常用的實現(xiàn)List的類有LinkedList,ArrayList,Vector,Stack。

    ArrayList 是容量可變的非線程安全列表,其底層使用數(shù)組實現(xiàn)。當發(fā)生擴容時,會創(chuàng)建更大的數(shù)組,并把原數(shù)組復制到新數(shù)組。ArrayList支持對元素的快速隨機訪問,但插入與刪除速度很慢。LinkedList本質是一個雙向鏈表,與ArrayList相比,其插入和刪除速度更快,但隨機訪問速度更慢。Vector 與 ArrayList 類似,底層也是基于數(shù)組實現(xiàn),特點是線程安全,但效率相對較低,因為其方法大多被 synchronized 修飾

Map?是一個鍵值對集合,存儲鍵、值和之間的映射。Key 無序,唯一;value 不要求有序,允許重復。Map 沒有繼承于 Collection 接口,從 Map 集合中檢索元素時,只要給出鍵對象,就會返回對應的值對象。主要實現(xiàn)有TreeMap、HashMap、HashTable、LinkedHashMap、ConcurrentHashMap

    HashMap:JDK1.8 之前 HashMap 由數(shù)組+鏈表組成的,數(shù)組是 HashMap 的主體,鏈表則是主要為了解決哈希沖突而存在的(“拉鏈法”解決沖突),JDK1.8 以后在解決哈希沖突時有了較大的變化,當鏈表長度大于閾值(默認為 8)時,將鏈表轉化為紅黑樹,以減少搜索時間LinkedHashMap:LinkedHashMap 繼承自 HashMap,所以它的底層仍然是基于拉鏈式散列結構即由數(shù)組和鏈表或紅黑樹組成。另外,LinkedHashMap 在上面結構的基礎上,增加了一條雙向鏈表,使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作,實現(xiàn)了訪問順序相關邏輯。HashTable:數(shù)組+鏈表組成的,數(shù)組是 HashMap 的主體,鏈表則是主要為了解決哈希沖突而存在的,HashTable 是線程安全的,其方法使用 synchronized 修飾,且不允許 null 鍵和 null 值。TreeMap:紅黑樹(自平衡的排序二叉樹)實現(xiàn),Key 按自然順序或 Comparator 排序。ConcurrentHashMap:采用 Node 數(shù)組 + 鏈表 + 紅黑樹實現(xiàn),是線程安全的。JDK1.8 以前使用 Segment 鎖(分段鎖),JDK1.8 以后使用 volatile + CAS 或者 synchronized 保證線程安全。其中,Segment 鎖是將整個數(shù)據(jù)結構分成多個段,每個段有獨立的鎖,不同段的操作可以并發(fā)進行;volatile 保證變量的可見性,CAS 是一種無鎖算法,synchronized 用于對鏈表或紅黑樹進行加鎖操作。

Set不允許存在重復的元素,與List不同,Set中的元素是無序的(TreeSet 除外)。常用的實現(xiàn)有HashSet,LinkedHashSet和TreeSet。

    HashSet通過HashMap實現(xiàn),HashMap的Key即HashSet存儲的元素,所有Key都是用相同的Value,一個名為PRESENT的Object類型常量。使用Key保證元素唯一性,但不保證有序性。由于HashSet是HashMap實現(xiàn)的,因此線程不安全。LinkedHashSet繼承自HashSet,通過LinkedHashMap實現(xiàn),使用雙向鏈表維護元素插入順序。TreeSet通過TreeMap實現(xiàn)的,添加元素到集合時按照比較規(guī)則將其插入合適的位置,保證插入后的集合仍然有序。

9. Java的垃圾回收機制,你知道哪些?

標記-清除算法

    • :標記-清除算法分為“標記”和“清除”兩個階段,首先通過可達性分析,標記出所有需要回收的對象,然后統(tǒng)一回收所有被標記的對象。標記-清除算法有兩個缺陷,一個是效率問題,標記和清除的過程效率都不高,另外一個就是,清除結束后會造成大量的碎片空間。有可能會造成在申請大塊內存的時候因為沒有足夠的連續(xù)空間導致再次 GC。

復制算法

    • :為了解決碎片空間的問題,出現(xiàn)了“復制算法”。復制算法的原理是,將內存分成兩塊,每次申請內存時都使用其中的一塊,當內存不夠時,將這一塊內存中所有存活的復制到另一塊上。然后將然后再把已使用的內存整個清理掉。復制算法解決了空間碎片的問題。但是也帶來了新的問題。因為每次在申請內存時,都只能使用一半的內存空間。內存利用率嚴重不足。

標記-整理算法

    • :復制算法在 GC 之后存活對象較少的情況下效率比較高,但如果存活對象比較多時,會執(zhí)行較多的復制操作,效率就會下降。而老年代的對象在 GC 之后的存活率就比較高,所以就有人提出了“標記-整理算法”。標記-整理算法的“標記”過程與“標記-清除算法”的標記過程一致,但標記之后不會直接清理。而是將所有存活對象都移動到內存的一端。移動結束后直接清理掉剩余部分。

分代回收算法

    :分代收集是將內存劃分成了新生代和老年代。分配的依據(jù)是對象的生存周期,或者說經(jīng)歷過的 GC 次數(shù)。對象創(chuàng)建時,一般在新生代申請內存,當經(jīng)歷一次 GC 之后如果對還存活,那么對象的年齡 +1。當年齡超過一定值(默認是 15,可以通過參數(shù) -XX:MaxTenuringThreshold 來設定)后,如果對象還存活,那么該對象會進入老年代。

10. 項目和其他

    介紹項目經(jīng)歷,比較大的挑戰(zhàn),如何解決項目里有哪些優(yōu)化,后續(xù)有什么可以深一步拓展的未來的職業(yè)規(guī)劃反問

中國電信(二面)

1. 一個數(shù)組,原地建堆,時間復雜度?

原地建堆的時間復雜度為?O(n),具體分析如下。

假設數(shù)組的長度為?n,且堆是一棵完全二叉樹,節(jié)點總數(shù)與高度關系

設堆的高度為h,樹的層數(shù)為h = log?n。第k 層的節(jié)點數(shù)為n/(2^k),該層每個節(jié)點需要最多調整k 次(從下往上調整)。

總調整次數(shù)計算,公式如下:

等比數(shù)列求和結果為?O(2n),因此?T(n) = O(n)。

不同層級的調整次數(shù)

高度為1 的節(jié)點:調整次數(shù)為1 × n/2

高度為2 的節(jié)點:調整次數(shù)為2 × n/4。總和為n/2 + n/4 + n/8 + ... ≈ 2n ?O(n)。

Java 原地建堆的算法實現(xiàn)如下:

public?class?HeapBuilder?{
? ??// 下沉操作(以最大堆為例)
? ??private?static?void?siftDown(int[] arr,?int?i,?int?n)?{
? ? ? ??while?(i < n) {
? ? ? ? ? ??int?left =?2?* i +?1;
? ? ? ? ? ??int?right =?2?* i +?2;
? ? ? ? ? ??int?largest = i;

? ? ? ? ? ??if?(left < n && arr[left] > arr[largest]) {
? ? ? ? ? ? ? ? largest = left;
? ? ? ? ? ? }
? ? ? ? ? ??if?(right < n && arr[right] > arr[largest]) {
? ? ? ? ? ? ? ? largest = right;
? ? ? ? ? ? }

? ? ? ? ? ??if?(largest != i) {
? ? ? ? ? ? ? ??// 交換元素
? ? ? ? ? ? ? ??int?temp = arr[i];
? ? ? ? ? ? ? ? arr[i] = arr[largest];
? ? ? ? ? ? ? ? arr[largest] = temp;
? ? ? ? ? ? ? ? i = largest; ?// 繼續(xù)下沉
? ? ? ? ? ? }?else?{
? ? ? ? ? ? ? ??break; ?// 調整完成
? ? ? ? ? ? }
? ? ? ? }
? ? }

? ??// 原地建堆
? ??public?static?void?buildHeap(int[] arr)?{
? ? ? ??int?n = arr.length;
? ? ? ??// 從最后一個非葉節(jié)點開始反向遍歷
? ? ? ??for?(int?i = n /?2?-?1; i >=?0; i--) {
? ? ? ? ? ? siftDown(arr, i, n);
? ? ? ? }
? ? }

? ??public?static?void?main(String[] args)?{
? ? ? ??int[] arr = {3,?5,?1,?7,?2,?9,?4};
? ? ? ? buildHeap(arr); ?// 結果: [9,7,4,5,3,1,2]
? ? }
}

2. 操作系統(tǒng)的進程調度算法有哪些

先來先服務調度算法

最簡單的一個調度算法,就是非搶占式的先來先服務算法了。

顧名思義,先來后到,每次從就緒隊列選擇最先進入隊列的進程,然后一直運行,直到進程退出或被阻塞,才會繼續(xù)從隊列中選擇第一個進程接著運行。

這似乎很公平,但是當一個長作業(yè)先運行了,那么后面的短作業(yè)等待的時間就會很長,不利于短作業(yè)。 FCFS 對長作業(yè)有利,適用于 CPU 繁忙型作業(yè)的系統(tǒng),而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。

最短作業(yè)優(yōu)先調度算法

最短作業(yè)優(yōu)先調度算法同樣也是顧名思義,它會優(yōu)先選擇運行時間最短的進程來運行,這有助于提高系統(tǒng)的吞吐量。

這顯然對長作業(yè)不利,很容易造成一種極端現(xiàn)象。

比如,一個長作業(yè)在就緒隊列等待運行,而這個就緒隊列有非常多的短作業(yè),那么就會使得長作業(yè)不斷的往后推,周轉時間變長,致使長作業(yè)長期不會被運行。

高響應比優(yōu)先調度算法

前面的「先來先服務調度算法」和「最短作業(yè)優(yōu)先調度算法」都沒有很好的權衡短作業(yè)和長作業(yè)。

那么,高響應比優(yōu)先調度算法主要是權衡了短作業(yè)和長作業(yè)。

每次進行進程調度時,先計算「響應比優(yōu)先級」,然后把「響應比優(yōu)先級」最高的進程投入運行,「響應比優(yōu)先級」的計算公式:

從上面的公式,可以發(fā)現(xiàn):

    如果兩個進程的「等待時間」相同時,「要求的服務時間」越短,「響應比」就越高,這樣短作業(yè)的進程容易被選中運行;如果兩個進程「要求的服務時間」相同時,「等待時間」越長,「響應比」就越高,這就兼顧到了長作業(yè)進程,因為進程的響應比可以隨時間等待的增加而提高,當其等待時間足夠長時,其響應比便可以升到很高,從而獲得運行的機會;

時間片輪轉調度算法

最古老、最簡單、最公平且使用最廣的算法就是時間片輪轉調度算法。

每個進程被分配一個時間段,稱為時間片,即允許該進程在該時間段中運行。

    如果時間片用完,進程還在運行,那么將會把此進程從 CPU 釋放出來,并把 CPU 分配另外一個進程;如果該進程在時間片結束前阻塞或結束,則 CPU 立即進行切換;

另外,時間片的長度就是一個很關鍵的點:

    如果時間片設得太短會導致過多的進程上下文切換,降低了 CPU 效率;如果設得太長又可能引起對短作業(yè)進程的響應時間變長。將

通常時間片設為?20ms~50ms?通常是一個比較合理的折中值。

最高優(yōu)先級調度算法

前面的「時間片輪轉算法」做了個假設,即讓所有的進程同等重要,也不偏袒誰,大家的運行時間都一樣。

但是,對于多用戶計算機系統(tǒng)就有不同的看法了,它們希望調度是有優(yōu)先級的,即希望調度程序能從就緒隊列中選擇最高優(yōu)先級的進程進行運行,這稱為最高優(yōu)先級調度算法。 進程的優(yōu)先級可以分為,靜態(tài)優(yōu)先級或動態(tài)優(yōu)先級:

      • 靜態(tài)優(yōu)先級:創(chuàng)建進程時候,就已經(jīng)確定了優(yōu)先級了,然后整個運行時間優(yōu)先級都不會變化;動態(tài)優(yōu)先級:根據(jù)進程的動態(tài)變化調整優(yōu)先級,比如如果進程運行時間增加,則降低其優(yōu)先級,如果進程等待時間(就緒隊列的等待時間)增加,則升高其優(yōu)先級,也就是

    隨著時間的推移增加等待進程的優(yōu)先級

該算法也有兩種處理優(yōu)先級高的方法,非搶占式和搶占式:

    非搶占式:當就緒隊列中出現(xiàn)優(yōu)先級高的進程,運行完當前進程,再選擇優(yōu)先級高的進程。搶占式:當就緒隊列中出現(xiàn)優(yōu)先級高的進程,當前進程掛起,調度優(yōu)先級高的進程運行。

但是依然有缺點,可能會導致低優(yōu)先級的進程永遠不會運行。

多級反饋隊列調度算法

多級反饋隊列調度算法是「時間片輪轉算法」和「最高優(yōu)先級算法」的綜合和發(fā)展。

顧名思義:

    「多級」表示有多個隊列,每個隊列優(yōu)先級從高到低,同時優(yōu)先級越高時間片越短?!阜答仭贡硎救绻行碌倪M程加入優(yōu)先級高的隊列時,立刻停止當前正在運行的進程,轉而去運行優(yōu)先級高的隊列;

來看看,它是如何工作的:

設置了多個隊列,賦予每個隊列不同的優(yōu)先級,每個隊列優(yōu)先級從高到低,同時優(yōu)先級越高時間片越短;新的進程會被放入到第一級隊列的末尾,按先來先服務的原則排隊等待被調度,如果在第一級隊列規(guī)定的時間片沒運行完成,則將其轉入到第二級隊列的末尾,以此類推,直至完成;當較高優(yōu)先級的隊列為空,才調度較低優(yōu)先級的隊列中的進程運行。如果進程運行時,有新進程進入較高優(yōu)先級的隊列,則停止當前運行的進程并將其移入到原隊列末尾,接著讓較高優(yōu)先級的進程運行;

可以發(fā)現(xiàn),對于短作業(yè)可能可以在第一級隊列很快被處理完。

對于長作業(yè),如果在第一級隊列處理不完,可以移入下次隊列等待被執(zhí)行,雖然等待的時間變長了,但是運行時間也會更長了,所以該算法很好的兼顧了長短作業(yè),同時有較好的響應時間。

3. 進程,線程,協(xié)程是什么?

首先,我們來談談進程。進程是操作系統(tǒng)中進行資源分配和調度的基本單位,它擁有自己的獨立內存空間和系統(tǒng)資源。每個進程都有獨立的堆和棧,不與其他進程共享。進程間通信需要通過特定的機制,如管道、消息隊列、信號量等。由于進程擁有獨立的內存空間,因此其穩(wěn)定性和安全性相對較高,但同時上下文切換的開銷也較大,因為需要保存和恢復整個進程的狀態(tài)。

接下來是線程。線程是進程內的一個執(zhí)行單元,也是CPU調度和分派的基本單位。與進程不同,線程共享進程的內存空間,包括堆和全局變量。線程之間通信更加高效,因為它們可以直接讀寫共享內存。線程的上下文切換開銷較小,因為只需要保存和恢復線程的上下文,而不是整個進程的狀態(tài)。然而,由于多個線程共享內存空間,因此存在數(shù)據(jù)競爭和線程安全的問題,需要通過同步和互斥機制來解決。

最后是協(xié)程。協(xié)程是一種用戶態(tài)的輕量級線程,其調度完全由用戶程序控制,而不需要內核的參與。協(xié)程擁有自己的寄存器上下文和棧,但與其他協(xié)程共享堆內存。協(xié)程的切換開銷非常小,因為只需要保存和恢復協(xié)程的上下文,而無需進行內核級的上下文切換。這使得協(xié)程在處理大量并發(fā)任務時具有非常高的效率。然而,協(xié)程需要程序員顯式地進行調度和管理,相對于線程和進程來說,其編程模型更為復雜。

 

相關推薦