標籤: 台北網頁設計

特性速覽| Apache Hudi 0.5.3版本正式發布

access_timePosted on by admin

1. 下載連接

  • 源代碼下載：Apache Hudi 0.5.3 Source Release (asc, sha512)
  • 0.5.3版本相關jar包地址：https://repository.apache.org/#nexus-search;quick~hudi

2. 遷移指南

  • 這是一個bugfix版本，從0.5.2升級時不需要任何特殊的遷移步驟。如果要從早期版本”X”升級，請閱讀”X”和0.5.3之間的每個後續版本的遷移指南。
  • 0.5.3是Hudi畢業后的第一個版本，因此所有hudi jar的版本名稱中不再帶有”-incubating”。在所有提及hudi版本的地方，請確保不再存在”-incubating”。

例如，hudi-spark-bundle pom依賴如下所示：

<dependency>
	<groupId>org.apache.hudi</groupId>
	<artifactId>hudi-spark-bundle_2.12</artifactId>
	<version>0.5.3</version>
</dependency>

3. 關鍵特性

  • Hudi內置支持 aliyun OSS 對象存儲。

  • 默認情況下將為delta-streamer和spark datasource寫入啟用Embedded Timeline Server。在此版本之前，此功能處於實驗模式，embeddedTimeline Server在Spark Driver中緩存文件列表，並提供Restful接口給Spark Writer任務調用來減少了每次寫入時的list文件列表的操作，此優化對雲上對象存儲非常友好。

  • 默認情況下為delta-streamer和Spark datasource寫入均啟用”增量清理(incremental cleaning)”。在此版本之前，此功能還處於實驗模式，在穩定狀態下，增量清理避免了掃描所有分區的昂貴步驟，而是使用Hudi元數據來查找要清理的文件，此優化也對雲上對象存儲非常友好。

  • 支持將Delta-Streamer配置文件放置在與實際數據不同的文件系統中。

  • Hudi Hive Sync現在支持按日期類型列分區的表。

  • Hudi Hive Sync現在支持直接通過Hive MetaStore進行同步。您只需要設置hoodie.datasource.hive_sync.use_jdbc = false。Hive Metastore Uri將從environment中隱式讀取。例如當通過Spark datasource寫入時，

     spark.write.format(“hudi”)
 .option(…)
 .option(“hoodie.datasource.hive_sync.username”, “<user>”)
 .option(“hoodie.datasource.hive_sync.password”, “<password>”)
 .option(“hoodie.datasource.hive_sync.partition_fields”, “<partition_fields>”)
 .option(“hoodie.datasource.hive_sync.database”, “<db_name>”)
 .option(“hoodie.datasource.hive_sync.table”, “<table_name>”)
 .option(“hoodie.datasource.hive_sync.use_jdbc”, “false”)
 .mode(APPEND)
 .save(“/path/to/dataset”)

  • 支持Presto查詢MoR表時Hudi側的改造。

  • 其他與Writer Performance相關的缺陷修復。

    • 現在DataSource Writer避免了寫入后不必要的數據加載。
    • Hudi Writer現在利用spark的併發來加速小文件查找。

4. 感謝

感謝如下貢獻者（排名不分先後）: @bhasudha，@yanghua ，@ddong ，@smarthi ，@afilipchik，@zhedoubushishi，@umehrot2，@varadar，@ffcchi，@bschell，@vinothchandar ，@shenh062326，@lamber-ken，@zhaomin1423，@EdwinGuo，@prashantwason ，@pratyakshsharma，@dengziming ，@AakashPradeep，@Jecarm ，@xushiyan ，@cxzl25，@garyli1019 ，@rolandjohann ，@nsivabalan，@leesf ，@jfrazee

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※別再煩惱如何寫文案,掌握八大原則!

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※超省錢租車方案

※教你寫出一流的銷售文案?

※網頁設計最專業,超強功能平台可客製化

※聚甘新

一起玩轉微服務（5）——分層架構

access_timePosted on by admin

領域驅動設計DDD（Domain Driven Design）提出了從業務設計到代碼實現一致性的要求，不再對分析模型和實現模型進行區分。也就是說從代碼的結構中我們可以直接理解業務的設計，命名得當的話，非程序人員也可以“讀”代碼。這與微服務設計中的約定優於配置不謀而合，如果你熟悉英文，那麼直接根據包名和類名就可以直接解讀出程序開發者所構建的業務的大概意圖。

領域模型包含一些明確定義的類型：

  • 實體是一個對象，它有固定的身份，具有明確定義的”連續性線索”或生命周期。通常列舉的示例是一個 Person（一個實體）。大多數系統都需要唯一地跟蹤一個 Person，無論姓名、地址或其他屬性是否更改。
  • l值對象沒有明確定義的身份，而僅由它們的屬性定義。它們通常不可變，所以兩個相等的值對象始終保持相等。地址可以是與 Person 關聯的值對象。
  • l集合是一個相關對象集群，這些對象被看作一個整體。它擁有一個特定實體作為它的根，並定義了明確的封裝邊界。它不只是一個列表。
  • l服務用於表示不是實體或值對象的自然部分的操作或活動。

領域模型在實現時可大可小，在業務的早期，在系統比較小的情況下，它有可能是一個類。當系統做大了以後，它可能是個庫。再做更大一點的時候，它可能是一個服務，給不同的應用去調用。

要將領域元素轉換為服務，可按照以下一般準則來完成此操作：

  • 使用值對象的表示作為參數和返回值，將集合和實體轉換為獨立的微服務。
  • 將領域服務（未附加到集合或實體的服務）與獨立的微服務相匹配。
  • 每個微服務應處理一個完整的業務功能。

領域模型又可以分為失血、貧血和充血3種。

  • 失血模型：基於數據庫的領域設計方式就是典型的失血模型，只關注數據的增刪改查。
  • 貧血模型：就是在domain object包含了不依賴於持久化的領域邏輯，而那些依賴持久化的領域邏輯被分離到server層。
  • 充血模型：充血模型跟貧血模型差不多，不同的是如何劃分業務邏輯，就是說，約大部分業務應該放到domain object裏面，而service應該是很薄的一層。

設計原則之分層架構

同一公司使用統一應用分層，以減少開發維護學習成本。應用分層這件事情看起來很簡單，但每個程序員都有自己的一套，哪怕是初學者，所以想實施起來並非那麼容易。

最早接觸分層架構的應該是我們最熟悉的MVC（Model-View-Controller）架構，將應用分成了模型、視圖和控制層，可以說引導了絕大多數開發者，而我們現在的應用中非常多的包括框架，架構設計都使用此模式。這后又演化出了MVP（Model-View-Presenter）和MVVM（Model-View-ViewModel）。這些可以說都是隨着技術的不斷髮展，為了應對不同場景所演化出來的模型。而微服務的每個架構都可以再細分成領域模型，下面看一下經典的領域模型架構。

它包括了Domain，Service Layer和Repositories。核心實體（Entity）和值對象（Value Object）應該在Domain層，定義的領域服務（Domain Service）在Service Layer，而針對實體和值對象的存儲和查詢邏輯都應該在Repositories層。值得注意的是，不要把Entity的屬性和行為分離到Domain和Service兩層中去實現，即所謂的貧血模型，事實證明這樣的實現方式會造成很大的維護問題。基於這種設計，工程的結構可以構造為：

– MicroService-Sample/src/

    domain

    gateways

    interface

    repositories

    services

當然，在微服務的架構中，每個微服務不必嚴格遵照這樣的規定，切忌死搬硬套，最重要的是理解，在不同的業務場合，架構的設計可以適當的做調整，畢竟適合的架構一定要具有靈活性。

分層的原則包括：

  • 文件夾分層法

應用分層採用文件夾方式的優點是可大可小、簡單易用、統一規範，可以包括 5 個項目，也可以包括 50 個項目，以滿足所有業務應用的多種不同場景。

  • 調用規約

在開發過程中，需要遵循分層架構的約束，禁止跨層次的調用。

  • 下層為上層服務

以用戶為中心，以目標為導向。上層（業務邏輯層）需要什麼，下層（數據訪問層）提供什麼，而不是下層（數據訪問層）有什麼，就向上層（業務邏輯層）提供什麼。

  • 實體層規約

Entity是數據表對象，不是數據訪問層對象；DTO 是網絡傳輸對象，不是表現層對象；BO 是內存計算邏輯對象，不是業務邏輯層對象，不是只能給業務邏輯層使用 。如果僅限定在本層訪問，則導致單個應用內大量沒有價值的對象轉換。以用戶為中心來設計實體類，可以減少無價值重複對象和無用轉換。

  • U 型訪問

下行時表現層是 Input，業務邏輯層是 Process，數據訪問層是 Output。上行時數據訪問層是 Input，業務邏輯層是 Process,  表現層就 Output。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※聚甘新

循序漸進VUE+Element 前端應用開發(12）— 整合ABP框架的前端登錄處理,循序漸進VUE+Element 前端應用開發(5）— 表格列表頁面的查詢，列表展示和字段轉義處理,循序漸進VUE+Element 前端應用開發(9）— 界面語言國際化的處理,循序漸進VUE+Element 前端應用開發(11）— 圖標的維護和使用

access_timePosted on by admin

VUE+Element 前端是一個純粹的前端處理，前面介紹了很多都是Vue+Element開發的基礎，從本章隨筆開始，就需要進入深水區了，需要結合ABP框架使用（如果不知道，請自行補習一下我的隨筆：ABP框架使用），ABP框架作為後端，是一個非常不錯的技術方向，但是前端再使用Asp.NET 進行開發的話，雖然會快捷一點，不過可能顯得有點累贅了，因此BS的前端選項採用Vue+Element來做管理（後續可能會視情況加入Vue+AntDesign），CS前端我已經完成了使用Winform+ABP的模式了。本篇隨筆主要介紹Vue+Element+ABP的整合方式，先從登錄開始介紹。

 1、ABP開發框架的回顧

ABP是ASP.NET Boilerplate的簡稱，ABP是一個開源且文檔友好的應用程序框架。ABP不僅僅是一個框架，它還提供了一個最徍實踐的基於領域驅動設計(DDD)的體繫結構模型。

啟動Host的項目，我們可以看到Swagger的管理界面如下所示。

我們登錄獲得用戶訪問令牌token后，測試字典類型或者字典數據的接口，才能返迴響應的數據。

我根據ABP後端項目之間的關係，整理了一個架構的圖形。

應用服務層是整個ABP框架的靈魂所在，對內協同倉儲對象實現數據的處理，對外配合Web.Core、Web.Host項目提供Web API的服務，而Web.Core、Web.Host項目幾乎不需要進行修改，因此應用服務層就是一個非常關鍵的部分，需要考慮對用戶登錄的驗證、接口權限的認證、以及對審計日誌的記錄處理，以及異常的跟蹤和傳遞，基本上應用服務層就是一個大內總管的角色，重要性不言而喻。

對於通過Winform方式展示界面，以Web API方式和後端的ABP的Web API服務進行數據交互，是我們之前已經完成的項目，項目界面如下所示。

主體框架界面採用的是基於菜單的動態生成，以及多文檔的界面布局，具有非常好的美觀性和易用性。

左側的功能樹列表和頂部的菜單模塊，可以根據角色擁有的權限進行動態構建，不同的角色具有不同的菜單功能點，如下是測試用戶登錄后具有的界面。

 

2、Vue+Element整合ABP框架的前端登錄處理

之前我們開發完成的Vue+Element的前端項目，默認已經具有登錄系統的功能，不過登錄是採用mock方式進行驗證並處理的，本篇隨筆介紹是基於實際的ABP項目進行用戶身份的登錄處理，這個也是開發其他接口展示數據的開始步驟，必須通過真實的用戶身份登錄後台，獲得對應的token令牌，才能進行下一步接口的開發工作。

例如對應登錄界面上，界面效果如下所示。

在用戶登錄界面中，我們處理用戶登錄邏輯代碼如下所示。

    // 處理登錄事件
    handleLogin() {
      this.$refs.loginForm.validate(valid => {
        if (valid) {
          this.loading = true
          this.$store
            .dispatch('user/login', this.loginForm)
            .then(() => {
              this.$router.push({ path: this.redirect || '/' })
              this.loading = false
            })
            .catch(() => {
              this.loading = false
            })
        } else {
          console.log('error submit!!')
          return false
        }
      })
    }

這裏主要就是調用Store模塊裏面的用戶Action處理操作。

例如對於用戶store模塊裏面的登錄Action函數如下所示。

const actions = {
  // user login
  login({ commit }, userInfo) {
    const { username, password } = userInfo
    return new Promise((resolve, reject) => {
      login({ username: username.trim(), password: password }).then(response => {
        const { result } = response // 獲取返回對象的 result
 var token = result.accessToken var userId = result.userId // 記錄令牌和用戶Id
        commit('SET_TOKEN', token)
        commit('SET_USERID', userId)

        // 存儲cookie
        setToken(token)
        setUserId(userId)
        resolve()
      }).catch(error => {
        reject(error)
      })
    })
  },

而其中 login({ username: username.trim(), password: password }) 操作，是通過API封裝處理的調用，使用前在Store模塊中先引入API模塊，如下所示。

import { login, logout, getInfo } from '@/api/user'

 而其中 API模塊代碼如下所示。

export function login(data) {
  return request({
    url: '/abp/TokenAuth/Authenticate',
    method: 'post',
    data: {
      UsernameOrEmailAddress: data.username,
      password: data.password
    }
  })
}

這裏我們用了一個/abp的前綴，用來給WebProxy的處理，實現地址的轉義，從而可以實現跨站的處理，讓前端調用外部地址就和調用本地地址一樣，無縫對接。

我們來看看vue.config.js裏面對於這個代理的轉義操作代碼。

 而 http://localhost:21021/api 地址指向的項目，是我們本地使用ABP開發的一個後端Web API項目，我們可以通過地址 http://localhost:21021/swagger/index.html 進行接口的查看。

 我們打開獲取授權令牌的Authenticate接口，查看它的接口定義內容

 

通過標註的1,2，我們可以看到這個接口的輸入參數和輸出JSON信息，從而為我們封裝Web API的調用提供很好的參考。

ABP框架統一返回的結果是result，這個result裏面才是返回對應的接口內容，如上面的輸出JSON信息裏面的定義。

所以在登陸返回結果后，我們要返回它的result對象，然後在進行數據的處理。

const { result } = response // 獲取返回對象的 result

然後通過result來訪問其他屬性即可。

var token = result.accessToken // 用戶令牌
var userId = result.userId // 用戶id

用戶登錄成功后，並獲取到對應的數據，我們就可以把必要的數據，如token和userid存儲在State和Cookie裏面了。

// 修改State對象，記錄令牌和用戶Id
commit('SET_TOKEN', token)
commit('SET_USERID', userId)

// 存儲cookie
setToken(token)
setUserId(userId)

有了這些信息，我們就可以進一步獲取用戶的相關信息，如用戶名稱、介紹，包含角色列表和權限列表等內容了。

例如對應用戶信息獲取接口的ABP後端地址是 http://localhost:21021//api/services/app/User/Get 

 那麼我們前端就需要在API模塊裏面構建它的訪問地址（/abp/services/app/User/Get）和接口處理了。

export function getInfo(id) {
  return request({
    url: '/abp/services/app/User/Get',
    method: 'get',
    params: {
      id
    }
  })
}

如上所示，在Store模塊里引入API模塊，如下所示。

import { login, logout, getInfo } from '@/api/user'

然後在Store模塊中封裝一個Action用來處理用戶信息的獲取的。

  // 獲取用戶信息
  getInfo({ commit, state }) {
    return new Promise((resolve, reject) => {
      getInfo(state.userid).then(response => {
        const { result } = response
        console.log(result) // 輸出測試

        if (!result) {
          reject('Verification failed, please Login again.')
        }

        const { roles, roleNames, name, fullName } = result

        // 角色非空提醒處理
        if (!roles || roles.length <= 0) {
          reject('getInfo: roles must be a non-null array!')
        }

        commit('SET_ROLES', { roles, roleNames })
        commit('SET_NAME', name)
        // commit('SET_AVATAR', avatar) //可以動態設置頭像
        commit('SET_INTRODUCTION', fullName)
        resolve(result)
      }).catch(error => {
        reject(error)
      })
    })
  },

Vue + Element前端項目的視圖、Store模塊、API模塊、Web API之間關係如下所示。

 

 登錄后我們獲取用戶身份信息，在控制台中記錄返回對象信息，可以供參考，如下所示

  

有了token信息，我們就可以繼續其他接口的數據請求或者提交了，從而可以實現更多的管理功能了。

後續隨筆將基於ABP接口對接的基礎上進行更多界面功能的開發和整合。 

 

列出一下前面幾篇隨筆的連接，供參考：

循序漸進VUE+Element 前端應用開發(1）— 開發環境的準備工作

循序漸進VUE+Element 前端應用開發(2）— Vuex中的API、Store和View的使用

循序漸進VUE+Element 前端應用開發(3）— 動態菜單和路由的關聯處理

循序漸進VUE+Element 前端應用開發(4）— 獲取後端數據及產品信息頁面的處理

循序漸進VUE+Element 前端應用開發(5）— 表格列表頁面的查詢，列表展示和字段轉義處理

循序漸進VUE+Element 前端應用開發(6）— 常規Element 界面組件的使用

循序漸進VUE+Element 前端應用開發(7）— 介紹一些常規的JS處理函數

循序漸進VUE+Element 前端應用開發(8）— 樹列表組件的使用

循序漸進VUE+Element 前端應用開發(9）— 界面語言國際化的處理

循序漸進VUE+Element 前端應用開發(11）— 圖標的維護和使用

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!

※綠能、環保無空污,成為電動車最新代名詞，目前市場使用率逐漸普及化

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?

※聚甘新

ConcurrentHashMap源碼解析-Java7

access_timePosted on by admin

目錄

一.ConcurrentHashMap的模型圖

二.源碼分析-類定義

　　2.1 極簡ConcurrentHashMap定義

　　2.2 Segment內部類

　　2.3 HashEntry內部類

　　2.4 ConcurrentHashMap的重要常量

三.常用接口源碼分析

　　3.1 ConcurrentHashMap構造方法

　　3.2 map.put操作

　　3.3 創建新segment

　　3.4 segment.put操作

　　3.5 segment.rehash擴容

　　3.6 map.get操作

　　3.7 map.remove操作

　　3.8 map.size操作

 

　　原文地址：https://www.cnblogs.com/-beyond/p/13157083.html

一.ConcurrentHashMap的模型圖

　　之前看了Java8中的HashMap，然後想接着看Java8的ConcurrentHashMap，但是打開Java8的ConcurrentHashMap，瞬間就慫了，將近7k行代碼，而反觀一下Java7的Concurrent，也就在1500多行，那就先選擇少的看吧。畢竟Java7的ConcurrentHashMap更加簡單。下面所有的介紹都是針對Java7而言！！！！！

　　下面是ConcurrentHashMap的結構圖，ConcurrentHashMap有一個segments數組，每個segment中又有一個table數組，該數組的每個元素時HashEntry類型。

　　 

　　可以簡單的理解為ConcurrentHashMap是多個HashMap組成，每一個HashMap是一個segment，就如傳說中一樣，ConcurrentHashMap使用分段鎖的方式，這個“段”就是segment。

　　ConcurrentHashMap之所以能夠保證併發安全，是因為支持對不同segment的併發修改操作，比如兩個線程同時修改ConcurrentHashMap，一個線程修改第一個segment的數據，另一個線程修改第二個segment的數據，兩個線程可以併發修改，不會出現併發問題；但是多個線程同一個segment進行併發修改，則需要先獲取該segment的鎖后再修改，修改完后釋放鎖，然後其他要修改的線程再進行修改。

　　那麼，ConcurrentHashMap可以支持多少併發量呢？這個也就是問，ConcurrentHashMap最多能支持多少線程併發修改，其實也就是segment的數量，只要修改segment的這些線程不是修改同一個segment，那麼這些線程就可以并行執行，這也就是ConcurrentHashMap的併發量（segment的數量）。

　　注意，ConcurrentHashMap創建完成后，也就是segment的數量、併發級別已經確定，則segment的數量和併發級別都不能再改變了，即使發生擴容，也是segment中的table進行擴容，segment的數量保持不變。

 

二.源碼分析-類定義

2.1 極簡ConcurrentHashMap定義

　　下面是省略了大部分代碼的ConcurrentHashMap定義：

package java.util.concurrent;

import java.util.AbstractMap;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable {

    final Segment<K, V>[] segments;

    /**
     * segment分段的定義
     */
    static final class Segment<K, V> extends ReentrantLock implements Serializable {

        transient volatile HashEntry<K, V>[] table;
    }

    /**
     * 存放的元素節點
     */
    static final class HashEntry<K, V> {

    }
}

 

2.2 Segment內部類

　　ConcurrentHashMap內部有一個segments屬性，是Segment類型的數組，Segment類和HashMap很相似（Java7的HashMap)，維持一個數組，每個數組是一個HashEntry，當發生hash衝突后，則使用拉鏈法（頭插法）來解決衝突。

　　而Segment數組的定義如下，省略了方法：

static final class Segment<K, V> extends ReentrantLock implements Serializable {
    static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
    private static final long serialVersionUID = 2249069246763182397L;
    
    // segment的負載因子（segments數組中的所有segment負載因子都相同）
    final float loadFactor;
    
    // segment中保存元素的數組
    transient volatile HashEntry<K, V>[] table;
   
    // 該segment中的元素個數
    transient int count;
    
    // modify count，該segment被修改的次數
    transient int modCount;
    
    // segment的擴容閾值
    transient int threshold;
}

　　注意每個Segment都有負載因子、以及擴容閾值，但是後面可以看到，其實segments數組中的每一個segment，負載因子和擴容閾值都相同，因為創建的時候，都是使用0號segment的負載因子和擴容閾值。

 

2.3 HashEntry內部類

　　Segment類中有一個table數組，table數組的每個元素都是HashEntry類型，和HashMap的Entry類似，源碼如下：（省略了方法）

/**
 * map中每個元素的類型
 */
static final class HashEntry<K, V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K, V> next;
}

 

2.4 ConcurrentHashMap的一些常量

　　ConcurrentHashMap中有很多常量，

// 默認初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;

// 默認的負載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 默認的併發級別(同時支持多少線程併發修改)
// 因為JDK7中ConcurrentHashMap中是用分段鎖實現併發，不同分段的數據可以進行併發操作，同一個段的數據不能同時修改
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 每一個分段的數組容量初始值
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;

// 最多能有多少個segment
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

// 嘗試對整個map進行操作（比如說統計map的元素數量），可能需要鎖定全部segment；
// 這個常量表示鎖定所有segment前，嘗試的次數
static final int RETRIES_BEFORE_LOCK = 2;

　　

三.常用接口源碼分析

3.1 ConcurrentHashMap構造方法

　　ConcurrentHashMap有多個構造方法，但是內部其實都是調用同一個進行創建：

public ConcurrentHashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}

public ConcurrentHashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}

public ConcurrentHashMap(int initialCapacity, float loadFactor) {
    this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
}

/**
 * 統一調用的構造方法
 *
 * @param initialCapacity  初始容量
 * @param loadFactor       負載因子
 * @param concurrencyLevel 併發級別
 */
@SuppressWarnings("unchecked")
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
    // 校驗參數合法性
    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) {
        throw new IllegalArgumentException();
    }

    // 對併發級別進行調整，不允許超過segment的數量（超過segment其實是沒有意義的）
    if (concurrencyLevel > MAX_SEGMENTS) {
        concurrencyLevel = MAX_SEGMENTS;
    }

    // 根據concurrencyLevel確定sshift和ssize的值
    int ssize = 1; // ssize是表示segment的數量，ssize是不小於concurrencyLevel的數，並且是2的n次方
    int sshift = 0;// sshift是ssize轉換為2進制后的位數，比如ssize為16（1000），則sshift為4
    while (ssize < concurrencyLevel) {
        ++sshift;
        ssize <<= 1;
    }
    // 比如concurrencyLevel默認為16，走完循環，sshift為4，ssize為16
    // 如果concurrentLevel為8，則sshift為3，ssize為8

    // segment的shift偏移量
    this.segmentShift = 32 - sshift;
    // segment掩碼
    this.segmentMask = ssize - 1;

    // 對傳入的初始容量進行調整（不允許大於最大容量）
    if (initialCapacity > MAXIMUM_CAPACITY) {
        initialCapacity = MAXIMUM_CAPACITY;
    }

    // 假設傳入的容量為128，併發級別為16，則initialCapacity為128，ssize為16
    int c = initialCapacity / ssize;
    // c可以理解為根據傳入的初始容量，計算出每個segment中的數組容量
    if (c * ssize < initialCapacity) {
        ++c;
    }

    // cap表示的是每個segment中的數組容量
    int cap = MIN_SEGMENT_TABLE_CAPACITY;
    // 如果默認的每個segment中的數組長度小於上面計算出來的每個segment的數組長度，則將容量翻倍
    while (cap < c) {
        cap <<= 1;
    }

    // 創建一個segment，作為segments數組的第一個segment
    Segment<K, V> s0 = new Segment<K, V>(loadFactor, (int) (cap * loadFactor), new HashEntry[cap]);

    // 創建segments數組
    Segment<K, V>[] ss = (Segment<K, V>[]) new Segment[ssize];

    // 將s0賦值給segments數組的第一個元素（偏移量為0）
    UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]

    // 複製segment數組
    this.segments = ss;
}

/**
 * 傳入map，將map中的元素加入到ConcurrentHashMap中
 * 注意使用默認的負載因子（0.75）和默認的併發級別（16）
 * 初始容量取map容量和默認容量的較大值
 */
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY),
            DEFAULT_LOAD_FACTOR,
            DEFAULT_CONCURRENCY_LEVEL);
    putAll(m);
}

　　

3.2 map.put操作

　　map.put，map就是指ConcurrentHashMap，其實就是確定HashEntry應該放入哪個segment中的哪個位置，所以可分為3步：

　　1.首先需要確定放入哪個segment；

　　2.確定segment后，再確定HashEntry應該放入segment的哪個位置；

　　3.進行覆蓋覆蓋或者插入。

/**
 * put操作，注意key或者value為null時，會拋出NPE
 */
@SuppressWarnings("unchecked")
public V put(K key, V value) {
    Segment<K, V> s;
    if (value == null) {
        throw new NullPointerException();
    }

    // 計算key的hash
    int hash = hash(key);

    // hash值右移shift位后 與 mask掩碼進行取與，確定數據應該放到哪個segments數組的哪一個segment中
    int j = (hash >>> segmentShift) & segmentMask;

    // 判斷計算出的segment數組位置上的segment是否為null，如果為null，則進行創建segment
    if ((s = (Segment<K, V>) UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) {
        s = ensureSegment(j);
    }

    // 創建segment后，將數據put到segment中，調用的segment.put()
    return s.put(key, hash, value, false);
}

　　

3.3 創建新segment

　　上面put的時候，如果發現segment為null，則會進行調用ensureSegment進行創建segment，代碼如下：

/**
 * 擴容（創建）segment
 *
 * @param k 需要擴容或者需要創建的segment位置
 * @return 返回擴容后的segment
 */
@SuppressWarnings("unchecked")
private Segment<K, V> ensureSegment(int k) {
    final Segment<K, V>[] ss = this.segments;
    long u = (k << SSHIFT) + SBASE; // 傳入的index，對應的偏移量
    Segment<K, V> seg;

    // 判斷是否需要擴容或者創建segment，如果獲取到segment不為null，則返回segment
    if ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(ss, u)) == null) {
        Segment<K, V> proto = ss[0]; // “原型設計模式”，使用segments數組的0號位置segment
        int cap = proto.table.length;// 0號segment的table長度
        float lf = proto.loadFactor; // 0號segment的負載因子
        int threshold = (int) (cap * lf); // 0號segment的擴容閾值

        // 創建一個HashEntry的數組，數組容量和0號segment相同
        HashEntry<K, V>[] tab = (HashEntry<K, V>[]) new HashEntry[cap];

        // 再次檢測，指定的segment是不是為null，如果為null才進行下一步操作
        if ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck
            // 創建segment
            Segment<K, V> s = new Segment<K, V>(lf, threshold, tab);

            // 使用CAS將新創建的segment填入指定的位置
            while ((seg = (Segment<K, V>) UNSAFE.getObjectVolatile(ss, u)) == null) {
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s)) {
                    break;
                }
            }
        }
    }

    // 返回新增的segment
    return seg;
}

　　上面需要注意的是：

　　1.創建segment中的table數組時，是使用0號segment的table屬性（長度、負載因子、閾值）；

　　2.創建segment前會進行再check，check發現segment的確為null時，再進行創建segment；

　　3.利用CAS來將創建的segment填入segments數組中；

 

3.4 segment.put操作

　　當確定HashEntry應該放到哪個segment后，就開始調用segment的put方法，如下：

/**
 * 在確定應該存放到那個segment后，就segment.put()將k-v存入segment中
 *
 * @param key          put的key
 * @param hash         hash(key)的值
 * @param value        put的value
 * @param onlyIfAbsent true:key對應的Entry不進行覆蓋，false:key對應的entry存在與否，都進行put覆蓋
 * @return
 */
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // 先獲取鎖（ReentrantLock，內部使用非公平鎖）
    HashEntry<K, V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K, V>[] tab = table;

        // 根據hash值計算出在segment的table中的位置
        int index = (tab.length - 1) & hash;

        // 定位到segment的table的index位置（第一個節點）
        HashEntry<K, V> first = entryAt(tab, index);

        // 從第一個節點開始遍歷
        for (HashEntry<K, V> e = first; ; ) {
            // 節點不為空，則判斷是否key是否相同（相同HashEntry）
            if (e != null) {
                K k;
                // 比較是否key是否相等（判斷put的key是否已經存在）
                if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                    // 如果key已經存在，則進行覆蓋，如果onlyIsAbsent為false（不關心key對應的Entry是否存在）
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        // 覆蓋舊值，修改計數加1
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            } else {
                // 頭插法，將put的k-v創建新HashEntry，放到first的前面
                if (node != null) {
                    node.setNext(first);
                } else {
                    node = new HashEntry<K, V>(hash, key, value, first);
                }

                // segment中table元素數量加1
                int c = count + 1;

                // 加1后的size大於擴容閾值，且數組的長度小於最大容量，則進行rehash
                if (c > threshold && tab.length < MAXIMUM_CAPACITY) {
                    // 擴容，並進行rehash
                    rehash(node);
                } else {
                    // 將節點放入數組中的指定位置
                    setEntryAt(tab, index, node);
                }

                // 修改次數加一，修改segment的table元素個數
                ++modCount;
                count = c;

                // 舊值為null
                oldValue = null;
                break;
            }
        }
    } finally {
        // 釋放鎖
        unlock();
    }
    return oldValue;
}

　　梳理一下，大致在做下面幾件事：

　　1.先獲取鎖（ReetrantLock，內部使用非公平鎖NonFairSync）；

　　2.獲取到鎖后根據hash計算出在table的位置；

　　3.遍歷table的HashEntry的鏈表，如果有相同key的，則進行覆蓋，如果沒有，在進行頭插法；

　　4.插入鏈表后，確定是否需要擴容，需要則執行rehash；

　　5.修改計數（count、modCount），並且釋放鎖。

 

3.5 segment.rehash擴容

　　segment擴容時，會將該segment的容量擴容為之前的2倍，並且將各位置的鏈表節點元素進行rehash。

/**
 * 將segment的table容量擴容一倍（newCap=oldCap*2），注意只會擴容該node所在的segment
 *
 * @param node segment[i]->鏈表的頭結點
 */
@SuppressWarnings("unchecked")
private void rehash(HashEntry<K, V> node) {
    HashEntry<K, V>[] oldTable = table;
    int oldCapacity = oldTable.length;

    // 新容量為舊容量的2倍
    int newCapacity = oldCapacity << 1;

    // 設置新的擴容閾值
    threshold = (int) (newCapacity * loadFactor);

    // 申請新數組，數組長度為新容量值
    HashEntry<K, V>[] newTable = (HashEntry<K, V>[]) new HashEntry[newCapacity];

    // 循環遍歷segment的數組（舊數組）
    int sizeMask = newCapacity - 1; // 新的掩碼
    for (int i = 0; i < oldCapacity; i++) {
        // 獲取第i個位置的HashEntry節點，如果該節點為null，則該位置為空，不作處理
        HashEntry<K, V> e = oldTable[i];
        if (e != null) {
            HashEntry<K, V> next = e.next;

            // 計算新位置
            int idx = e.hash & sizeMask;

            // next為null，表示該位置只有一個節點，直接將節點複製到新位置
            if (next == null) {   //  Single node on list
                newTable[idx] = e;
            } else { // Reuse consecutive sequence at same slot
                HashEntry<K, V> lastRun = e;
                int lastIdx = idx;
                for (HashEntry<K, V> last = next; last != null; last = last.next) {
                    int k = last.hash & sizeMask;
                    if (k != lastIdx) {
                        lastIdx = k;
                        lastRun = last;
                    }
                }
                newTable[lastIdx] = lastRun;
                // 從頭結點開始，開始將節點拷貝到新數組中
                for (HashEntry<K, V> p = e; p != lastRun; p = p.next) {
                    V v = p.value;
                    int h = p.hash;
                    int k = h & sizeMask;
                    HashEntry<K, V> n = newTable[k];
                    newTable[k] = new HashEntry<K, V>(h, p.key, v, n);
                }
            }
        }
    }

    // 將頭結點添加到segment的table中
    int nodeIndex = node.hash & sizeMask; // add the new node
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;
    table = newTable;
}

　　為啥擴容的時候沒有加鎖呀？

　　其實已經加鎖了，只不過不是在rehash中加鎖！！！因為rehash是在map.put中調用，put的時候已經加鎖了，所以rehash中不用加鎖。

　　

3.6 map.get操作

　　get操作，先定位到segment，然後定位到segment的具體位置，進行獲取

/**
 * 從ConcurrentHashMap中獲取key對應的value，不需要加鎖
 */
public V get(Object key) {
    Segment<K, V> s;
    HashEntry<K, V>[] tab;

    // 計算key的hash
    int h = hash(key);

    // 計算key處於哪一個segment中（index）
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;

    // 獲取數組中該位置的segment，如果該segment的table不為空，那麼就繼續在segment中查找，否則返回null，因為未找到
    if ((s = (Segment<K, V>) UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) {

        // tab指向segment的table數組，通過hash計算定位到table數組的位置（然後開始遍歷鏈表）
        HashEntry<K, V> e;
        for (e = (HashEntry<K, V>) UNSAFE.getObjectVolatile(tab, ((long) (((tab.length - 1) & h)) << TSHIFT) + TBASE);
             e != null; e = e.next) {
            K k;
            // 判斷key和hash是否匹配，匹配則證明找到要查找的數據，將數據返回
            if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                return e.value;
        }
    }
    
    return null;
}

　　

3.7 map.remove操作

　　 刪除節點，和get的流程差不多，先定位到segment，然後確定segment的哪個位置（哪條鏈表），遍歷鏈表，找到後進行刪除。

/**
 * 刪除map中key對應的元素
 */
public V remove(Object key) {
    // 計算key的hash
    int hash = hash(key);

    // 根據hash確定segment
    Segment<K, V> s = segmentForHash(hash);

    // 調用segment.remove進行刪除
    return s == null ? null : s.remove(key, hash, null);
}

/**
 * 刪除segment中key對應的hashEntry
 * 如果傳入的value不為空，則會在value匹配的時候進行刪除，否則不操作
 */
final V segmeng.remove(Object key, int hash, Object value) {
    // 獲取鎖失敗，則不斷自旋嘗試獲取鎖
    if (!tryLock()) {
        scanAndLock(key, hash);
    }

    V oldValue = null;
    try {
        HashEntry<K, V>[] tab = table;
        // 定位到segment中table的哪個位置
        int index = (tab.length - 1) & hash;
        HashEntry<K, V> e = entryAt(tab, index);
        HashEntry<K, V> pred = null;

        // 遍歷鏈表
        while (e != null) {
            K k;
            HashEntry<K, V> next = e.next;
            // 如果key和hash都匹配
            if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                V v = e.value;
                // 如果沒有傳入value，則直接刪除該節點
                // 如果傳入了value，比如調用的map.remove(key,value)，則要value匹配才會刪除，否則不操作
                if (value == null || value == v || value.equals(v)) {
                    if (pred == null) { // 頭結點就是要找刪除的元素，next為null，則將null賦值數組的該位置
                        setEntryAt(tab, index, next);
                    } else { // 
                        pred.setNext(next);
                    }

                    // 修改次數加一，map數量減一
                    ++modCount;
                    --count;
                    oldValue = v;
                }
                break;
            }

            // 不匹配時，pred保存當前一次檢測的節點，e指向下一個節點
            pred = e;
            e = next;
        }
    } finally {
        unlock();// 釋放鎖
    }
    return oldValue;
}

　　

3.8 map.size操作

　　ConcurrentHashMap的size()，需要統計每一個segment中的元素數量（也就是count值），因為不同的segment允許併發修改，統計過程中可能會出現修改操作，導致統計不準確，所以要想準確統計整個map的元素數量，可以這樣做：通過加鎖的方式來解決（將所有的segment都加鎖），這樣就能保證元素不會變化了，這是我們的想法。

　　而ConcurrentHashMap是這樣解決的，先嘗試不加鎖進行統計兩次，這兩次統計，不止會統計每個segment的元素數量，還會統計每個segment的modCount(修改次數），進行匯總；如果兩次統計的modCount總量相同，也就說明兩次統計期間沒有修改操作，證明統計的元素總量正確；如果兩次modCount總量不相同，表示有修改操作，則進行重試，如果重試后，發現還是不準確（modCount不匹配），那麼就嘗試為所有的segment加鎖，再進行統計。

　　源碼如下：

/**
 * 獲取ConcurrentHashMap中的元素個數，如果元素個數超過Integer.MAX_VALUE，則返回Integer.MAX_VALUE
 */
public int size() {
    final Segment<K, V>[] segments = this.segments;
    int size;           // 返回元素數量（統計結果->元素的總量）
    boolean overflow;   // 標誌是否溢出（是否超過Integer.MAX_VALUE）
    long sum;           // 所有segment的modCount總量次數（整個map的修改次數）
    long last = 0L;     // previous sum，上一輪統計的modCount總量
    int retries = -1;   // 記錄重試的次數

    try {
        // 此處for循環主要用於控制重試
        for (; ; ) {
            // 重試的次數如果達到RETRIES_BEFORE_LOCK，則強制獲取所有segment的鎖
            if (retries++ == RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j) {
                    ensureSegment(j).lock();
                    // 強制獲取segment的table第i個位置，並加鎖
                }
            }

            sum = 0L;
            size = 0;
            overflow = false;
            // 開始對segments中的每一個segment中進行統計
            for (int j = 0; j < segments.length; ++j) {
                // 獲取第j個segment
                Segment<K, V> seg = segmentAt(segments, j);
                // 如果segment不為空，則進行統計
                if (seg != null) {
                    sum += seg.modCount;
                    int c = seg.count;
                    // size累加
                    if (c < 0 || (size += c) < 0)
                        overflow = true;
                }
            }

            // 如果本次統計的modCount總量和上次一樣，則表示在這兩次統計之間沒有進行過修改，則不再重試
            if (sum == last) {
                break;
            }
            // 記錄本次統計的modCount總量
            last = sum;
        }
    } finally {
        // 判斷是否加了鎖（如果retries大於RETRIES_BEFORE_LOCK），則證明加了鎖，於是進行釋放鎖
        if (retries > RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j)
                segmentAt(segments, j).unlock();
        }
    }
    return overflow ? Integer.MAX_VALUE : size;
}

　　

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司“嚨底家”!

※推薦評價好的iphone維修中心

※聚甘新

Redis系列（五）：數據結構List雙向鏈表源碼解析和API實現

access_timePosted on by admin

1.介紹

Redis中List是通過ListNode構造的雙向鏈表。

特點：

1.雙端：獲取某個結點的前驅和後繼結點都是O(1)

2.無環：表頭的prev指針和表尾的next指針都指向NULL，對鏈表的訪問都是以NULL為終點

3.帶表頭指針和表尾指針：獲取表頭和表尾的複雜度都是O(1)

4.帶鏈表長度計數器：len屬性記錄，獲取鏈表長度O(1)

5.多態：鏈表結點使用void*指針來保存結點的值，並且可以通過鏈表結構的三個函數為結點值設置類型特定函數，所以鏈表可以保存各種不同類型的值

雙向鏈表詳解：https://www.cnblogs.com/vic-tory/p/13140779.html

中文網：http://redis.cn/commands.html#list

2.源碼解析

// listNode 雙端鏈表節點
typedef struct listNode {

    // 前置節點
    struct listNode *prev;

    // 後置節點
    struct listNode *next;

    // 節點的值
    void *value;

} listNode;

 

// list 雙端鏈表
typedef struct list { // 在c語言中,用結構體的方式來模擬對象是一種常見的手法

    // 表頭節點
    listNode *head;

    // 表尾節點
    listNode *tail;

    // 節點值複製函數
    void *(*dup)(void *ptr);

    // 節點值釋放函數
    void(*free)(void *ptr);

    // 節點值對比函數
    int(*match)(void *ptr, void *key);

    // 鏈表所包含的節點數量
    unsigned long len;

} list;

 

/* 作為宏實現的函數 */
//獲取長度
#define listLength(l) ((l)->len)
//獲取頭節點
#define listFirst(l) ((l)->head)
//獲取尾結點
#define listLast(l) ((l)->tail)
//獲取前一個結點
#define listPrevNode(n) ((n)->prev)
//獲取后一個結點
#define listNextNode(n) ((n)->next)
//獲取結點的值 是一個void類型指針
#define listNodeValue(n) ((n)->value)

/* 下面3個函數主要用來設置list結構中3個函數指針，參數m為method的意思 */
#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

/* 下面3個函數主要用來獲取list結構的單個函數指針 */
#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

3.API實現

listCreate函數：創建一個不包含任何結點的新鏈表

/*
 * listCreate 創建一個新的鏈表
 *
 * 創建成功返回鏈表，失敗返回 NULL 。
 *
 * T = O(1)
 */
list *listCreate(void)
{
    struct list *list;

    // 分配內存
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;//內存分配失敗則返回NULL

    // 初始化屬性
    list->head = list->tail = NULL;//空鏈表
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;

    return list;
}

listAddNodeHead函數：將一個包含給定值的新結點添加到給定鏈表的表頭

/*
 * listAddNodeHead 將一個包含有給定值指針 value 的新節點添加到鏈表的表頭
 *
 * 如果為新節點分配內存出錯，那麼不執行任何動作，僅返回 NULL
 *
 * 如果執行成功，返回傳入的鏈表指針
 *
 * T = O(1)
 */
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;

    // 為節點分配內存
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;

    // 保存值指針
    node->value = value;

    // 添加節點到空鏈表
    if (list->len == 0) {
        list->head = list->tail = node;
        //該結點的前驅和後繼都為NULL
        node->prev = node->next = NULL;
    }
    else { // 添加節點到非空鏈表
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }

    // 更新鏈表節點數
    list->len++;

    return list;
}

listAddNodeTail函數：將一個包含給定值的新結點插入到給定鏈表的表尾

/*
 * listAddNodeTail 將一個包含有給定值指針 value 的新節點添加到鏈表的表尾
 *
 * 如果為新節點分配內存出錯，那麼不執行任何動作，僅返回 NULL
 *
 * 如果執行成功，返回傳入的鏈表指針
 *
 * T = O(1)
 */
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;

    // 為新節點分配內存
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;

    // 保存值指針
    node->value = value;

    // 目標鏈表為空
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    }//目標鏈非空
    else {
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }

    // 更新鏈表節點數
    list->len++;

    return list;
}

listInsertNode函數：將一個給定值的新結點插入到給定結點之前或者之後

/*
 * listInsertNode 創建一個包含值 value 的新節點，並將它插入到 old_node 的之前或之後
 *
 * 如果 after 為 0 ，將新節點插入到 old_node 之前。
 * 如果 after 為 1 ，將新節點插入到 old_node 之後。
 *
 * T = O(1)
 */
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;

    // 創建新節點
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;

    // 保存值
    node->value = value;

    // 將新節點添加到給定節點之後
    if (after) {
        node->prev = old_node;
        node->next = old_node->next;
        // 給定節點是原表尾節點
        if (list->tail == old_node) {
            list->tail = node;
        }
    }
    // 將新節點添加到給定節點之前
    else {
        node->next = old_node;
        node->prev = old_node->prev;
        // 給定節點是原表頭節點
        if (list->head == old_node) {
            list->head = node;
        }
    }

    // 更新新節點的前置指針
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    // 更新新節點的後置指針
    if (node->next != NULL) {
        node->next->prev = node;
    }

    // 更新鏈表節點數
    list->len++;

    return list;
}

listDelNode函數：從指定的list中刪除給定的結點

/*
 * listDelNode 從鏈表 list 中刪除給定節點 node
 *
 * 對節點私有值(private value of the node)的釋放工作由調用者進行。該函數一定會成功.
 *
 * T = O(1)
 */
void listDelNode(list *list, listNode *node)
{
    // 調整前置節點的指針
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;

    // 調整後置節點的指針
    if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;

    // 釋放值
    if (list->free) list->free(node->value);

    // 釋放節點
    zfree(node);

    // 鏈表數減一
    list->len--;
}

listRelease函數：釋放給定鏈表以及鏈表中所有結點

 

/*
 * listRelease 釋放整個鏈表，以及鏈表中所有節點, 這個函數不可能會失敗.
 *
 * T = O(N)
 */
void listRelease(list *list)
{
    unsigned long len;
    listNode *current, *next;

    // 指向頭指針
    current = list->head;
    // 遍歷整個鏈表
    len = list->len;
    while (len--) {
        next = current->next;

        // 如果有設置值釋放函數，那麼調用它
        if (list->free) list->free(current->value);

        // 釋放節點結構
        zfree(current);

        current = next;
    }

    // 釋放鏈表結構
    zfree(list);
}

 

該函數不僅釋放了表結點的內存還釋放了表結構的內存

 listGetIterator函數：為給定鏈表創建一個迭代器

在講這個函數之前，我們應該先看看鏈表迭代器的結構：

// listIter 雙端鏈表迭代器
typedef struct listIter {

    // 當前迭代到的節點
    listNode *next;

    // 迭代的方向
    int direction;

} listIter;

迭起器只有兩個重要的屬性：當前迭代到的結點，迭代的方向

下面再看看鏈表的迭代器創建函數

/*
 * listGetIterator 為給定鏈表創建一個迭代器，
 * 之後每次對這個迭代器調用 listNext 都返回被迭代到的鏈表節點,調用該函數不會失敗
 *
 * direction 參數決定了迭代器的迭代方向：
 *  AL_START_HEAD ：從表頭向表尾迭代
 *  AL_START_TAIL ：從表尾想表頭迭代
 *
 * T = O(1)
 */
listIter *listGetIterator(list *list, int direction)
{
    // 為迭代器分配內存
    listIter *iter;
    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;

    // 根據迭代方向，設置迭代器的起始節點
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;

    // 記錄迭代方向
    iter->direction = direction;

    return iter;
}

listReleaseIterator函數：釋放指定的迭代器

/*
 * listReleaseIterator 釋放迭代器
 *
 * T = O(1)
 */
void listReleaseIterator(listIter *iter) {
    zfree(iter);
}

listRewind函數和listRewindTail函數：迭代器重新指向表頭或者表尾的函數

 

/*
 * 將迭代器的方向設置為 AL_START_HEAD,
 * 並將迭代指針重新指向表頭節點。
 *
 * T = O(1)
 */
void listRewind(list *list, listIter *li) {
    li->next = list->head;
    li->direction = AL_START_HEAD;
}

/*
 * 將迭代器的方向設置為 AL_START_TAIL,
 * 並將迭代指針重新指向表尾節點。
 *
 * T = O(1)
 */
void listRewindTail(list *list, listIter *li) {
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}

listNext函數：返回當前迭代器指向的結點

 

/*
 * 返回迭代器當前所指向的節點。
 *
 * 刪除當前節點是允許的,但不能修改鏈表裡的其他節點。
 *
 * 函數要麼返回一個節點,要麼返回 NULL,常見的用法是：
 *
 * iter = listGetIterator(list,<direction>);
 * while ((node = listNext(iter)) != NULL) {
 *     doSomethingWith(listNodeValue(node));
 * }
 *
 * T = O(1)
 */
listNode *listNext(listIter *iter)
{
    listNode *current = iter->next;

    if (current != NULL) {
        // 根據方向選擇下一個節點
        if (iter->direction == AL_START_HEAD)
            // 保存下一個節點，防止當前節點被刪除而造成指針丟失
            iter->next = current->next;
        else
            // 保存下一個節點，防止當前節點被刪除而造成指針丟失
            iter->next = current->prev;
    }

    return current;
}

 

 

 

該函數保持了當前結點的下一個結點，避免了當前結點被刪除而迭代器無法繼續迭代的尷尬情況

 listDup函數：複製整個鏈表，返回副本

 

/*
 * 複製整個鏈表。
 *
 * 複製成功返回輸入鏈表的副本，
 * 如果因為內存不足而造成複製失敗，返回 NULL 。
 *
 * 如果鏈表有設置值複製函數 dup ，那麼對值的複製將使用複製函數進行，
 * 否則，新節點將和舊節點共享同一個指針。
 *
 * 無論複製是成功還是失敗，輸入節點都不會修改。
 *
 * T = O(N)
 */
list *listDup(list *orig)
{
    list *copy;//鏈表副本
    listIter *iter;//鏈表迭代器
    listNode *node;//鏈表結點

    // 創建新的空鏈表
    if ((copy = listCreate()) == NULL)
        return NULL;//創建空的鏈表失敗則返回NULL

    // 設置副本鏈表的節點值處理函數
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;

    //獲取輸入鏈表的迭代器
    iter = listGetIterator(orig, AL_START_HEAD);
    
    //遍歷整個輸入鏈表進行複製
    while ((node = listNext(iter)) != NULL) {
        
        //副本結點值
        void *value;

        // 存在複製函數
        if (copy->dup) {
            
            //調用複製函數複製
            value = copy->dup(node->value);
         
            //複製結果為空，說明複製失敗
            if (value == NULL) {
                
                //複製失敗則釋放副本鏈表和迭代器，避免內存泄漏
                listRelease(copy);
                listReleaseIterator(iter);
            
                return NULL;
            }
        }
        //不存在複製函數 則直接指針指向
        else
            value = node->value;

        // 將節點添加到副本鏈表 
        if (listAddNodeTail(copy, value) == NULL) {
                
            //如果不能成功添加，則釋放副本鏈表和迭代器，避免內存泄漏
            listRelease(copy);
            listReleaseIterator(iter);
        
            return NULL;
        }
    }

    // 釋放迭代器
    listReleaseIterator(iter);

    // 返回副本
    return copy;
}

 

如果複製失敗則要注意釋放副本鏈表和迭代器，避免內存泄漏

 listSearchKey函數：查找list中值和key匹配的結點

  

/*
 * 查找鏈表 list 中值和 key 匹配的節點。
 *
 * 對比操作由鏈表的 match 函數負責進行，
 * 如果沒有設置 match 函數，
 * 那麼直接通過對比值的指針來決定是否匹配。
 *
 * 如果匹配成功，那麼第一個匹配的節點會被返回。
 * 如果沒有匹配任何節點，那麼返回 NULL 。
 *
 * T = O(N)
 */
listNode *listSearchKey(list *list, void *key)
{
    listIter *iter;//鏈表迭代器
    listNode *node;//鏈表結點

    //獲得鏈表迭代器
    iter = listGetIterator(list, AL_START_HEAD);

    //遍歷整個鏈表查詢
    while ((node = listNext(iter)) != NULL) {

        //存在比較函數
        if (list->match) {

            //利用比較函數進行比較
            if (list->match(node->value, key)) {

                //返回目標結點之前釋放迭代器空間，避免內存泄漏
                listReleaseIterator(iter);

                return node;
            }
        }
        //不存在比較函數
        else {
            //直接比較
            if (key == node->value) {

                //返回目標結點之前釋放迭代器空間，避免內存泄漏
                listReleaseIterator(iter);
                // 找到
                return node;
            }
        }
    }

    //返回目標結點之前釋放迭代器空間，避免內存泄漏
    listReleaseIterator(iter);

    // 未找到
    return NULL;
}

listIndex函數：返回鏈表在給定索引上的值

 

/*
 * 返回鏈表在給定索引上的值。
 *
 * 索引以 0 為起始，也可以是負數， -1 表示鏈表最後一個節點，諸如此類。
 *
 * 如果索引超出範圍(out of range),返回 NULL 。
 *
 * T = O(N)
 */
listNode *listIndex(list *list, long index) {
    
    listNode *n;//鏈表結點

    
    /* n不用設置成NULL的原因：
    如果索引超出範圍，
    那肯定是找到表頭或者表尾沒有找到，
    表頭的前驅和表尾的後繼都是NULL，
    所以這裏n不用設置為NULL，直接設置也可以*/
    
    // 如果索引為負數，從表尾開始查找
    if (index < 0) {
        
        //變成正數，方便索引
        index = (-index) - 1;
    
        //從尾部開始找
        n = list->tail;
        
        //尋找 因為從尾部開始找，所以是前驅
        while (index-- && n) n = n->prev;
        
    }
    
    // 如果索引為正數，從表頭開始查找
    else {
        
        //從頭部開始找
        n = list->head;
    
        //尋找 因為從頭部開始找，所以是後繼
        while (index-- && n) n = n->next;
    }

    return n;
}

listRotate函數：取出鏈表的表尾結點放到表頭，成為新的表頭結點

/*
 * 取出鏈表的表尾節點，並將它移動到表頭，成為新的表頭節點。
 *
 * T = O(1)
 */
void listRotate(list *list) {
    
    //表尾結點
    listNode *tail = list->tail;

    //如果鏈表中只有一個元素，那麼表頭就是表尾，可以直接返回
    if (listLength(list) <= 1) return;

    // 重新設置表尾節點
    list->tail = tail->prev;
    list->tail->next = NULL;

    // 插入到表頭
    list->head->prev = tail;
    tail->prev = NULL;
    tail->next = list->head;
    list->head = tail;
}

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※回頭車貨運收費標準

※聚甘新

機器學習——打開集成方法的大門，手把手帶你實現AdaBoost模型

access_timePosted on by admin

本文始發於個人公眾號：TechFlow，原創不易，求個關注

今天是機器學習專題的第25篇文章，我們一起來聊聊AdaBoost。

我們目前為止已經學過了好幾個模型，光決策樹的生成算法就有三種。但是我們每次進行分類的時候，每次都是採用一個模型進行訓練和預測。我們日常在做一個決策的時候，往往會諮詢好幾個人，綜合採納他們的意見。那麼有沒有可能把這個思路照搬到機器學習領域當中，創建多個模型來綜合得出結果呢？

這當然是可以的，這樣的思路就叫做集成方法（ensemble method）。

集成方法

集成方法本身並不是某種具體的方法或者是算法，只是一種訓練機器學習模型的思路。它的含義只有一點，就是訓練多個模型，然後將它們的結果匯聚在一起。

根據這個思路，業內又衍生出了三種特定的方法，分別是Bagging、Boosting和Stacking。

Bagging

Bagging是bootstrap aggregating的縮寫，我們從字面上很難理解它的含義。我們記住這個名字即可，在Bagging方法當中，我們會通過有放回隨機採樣的方式創建K個數據集。對於每一個數據集來說，可能有一些單個的樣本重複出現，也可能有一些樣本從沒有出現過，但整體而言，每個樣本出現的概率是相同的。

之後，我們用抽樣出來的K個數據集訓練K個模型，這裏的模型沒有做限制，我們可以使用任何機器學習方模型。K個模型自然會得到K個結果，那麼我們採取民主投票的方式對這K個模型進行聚合。

舉個例子說，假設K=25，在一個二分類問題當中。有10個模型預測結果是0，15個模型預測結果是1。那麼最終整個模型的預測結果就是1，相當於K個模型民主投票，每個模型投票權一樣。大名鼎鼎的隨機森林就是採取的這種方式。

Boosting

Boosting的思路和Bagging非常相似，它們對於樣本的採樣邏輯是一致的。不同的是，在Boosting當中，這K個模型並不是同時訓練的，而是串行訓練的。每一個模型在訓練的時候都會基於之前模型的結果，更加關注於被之前模型判斷錯誤的樣本。同樣，樣本也會有一個權值，錯誤判斷率越大的樣本擁有越大的權值。

並且每一個模型根據它能力的不同，會被賦予不同的權重，最後會對所有模型進行加權求和，而不是公平投票。由於這個機制，使得模型在訓練的時候的效率也有差異。因為Bagging所有模型之間是完全獨立的，我們是可以採取分佈式訓練的。而Boosting中每一個模型會依賴之前模型的效果，所以只能串行訓練。

Stacking

Stacking是Kaggle比賽當中經常使用的方法，它的思路也非常簡單。我們選擇K種不同的模型，然後通過交叉驗證的方式，在訓練集上進行訓練和預測。保證每個模型都對所有的訓練樣本產出一個預測結果。那麼對於每一條訓練樣本，我們都能得到K個結果。

之後，我們再創建一個第二層的模型，它的訓練特徵就是這K個結果。也就是說Stacking方法當中會用到多層模型的結構，最後一層模型的訓練特徵是上層模型預測的結果。由模型自己去訓練究竟哪一個模型的結果更值得採納，以及如何組合模型之間的特長。

我們今天介紹的AdaBoost顧名思義，是一個經典的Boosting算法。

模型思路

AdaBoost的核心思路是通過使用Boosting的方法，通過一些弱分類器構建出強分類器來。

強分類器我們都很好理解，就是性能很強的模型，那麼弱分類器應該怎麼理解呢？模型的強弱其實是相對於隨機結果來定義的，比隨機結果越好的模型，它的性能越強。從這點出發，弱分類器也就是只比隨機結果略強的分類器。我們的目的是通過設計樣本和模型的權重，使得可以做出最佳決策，將這些弱分類器的結果綜合出強分類器的效果來。

首先我們會給訓練樣本賦予一個權重，一開始的時候，每一條樣本的權重均相等。根據訓練樣本訓練出一個弱分類器並計算這個分類器的錯誤率。然後在同一個數據集上再次訓練弱分類器，在第二次的訓練當中，我們將會調整每個樣本的權重。其中正確的樣本權重會降低，錯誤的樣本權重會升高。

同樣每一個分類器也會分配到一個權重值，權重越高說明它的話語權越大。這些是根據模型的錯誤率來計算的。錯誤率定義為：

這裏的D表示數據集表示分類錯誤的集合，它也就等於錯誤分類的樣本數除以總樣本數。

有了錯誤率之後，我們可以根據下面這個公式得到。

得到了之後，我們利用它對樣本的權重進行更新，其中分類正確的權重更改為：

分類錯誤的樣本權重更改為：

這樣，我們所有的權重都更新完了，這也就完成了一輪迭代。AdaBoost會反覆進行迭代和調整權重，直到訓練錯誤率為0或者是弱分類器的數量達到閾值。

代碼實現

首先，我們來獲取數據，這裏我們選擇了sklearn數據集中的乳腺癌預測數據。和之前的例子一樣，我們可以直接import進來使用，非常方便：

import numpy as np
import pandas as pd
from sklearn.datasets import load_breast_cancer

breast = load_breast_cancer()
X, y = breast.data, breast.target
# reshape，將一維向量轉成二維
y = y.reshape((-1, 1))

接着，我們將數據拆分成訓練數據和測試數據，這個也是常規做法了，沒有難度：

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=23)

在AdaBoost模型當中，我們選擇的弱分類器是決策樹的樹樁。所謂的樹樁就是樹深為1的決策樹。樹深為1顯然不論我們怎麼選擇閾值，都不會得到特別好的結果，但是由於我們依然會選擇閾值和特徵，所以結果也不會太差，至少要比隨機選擇要好。所以這就保證了，我們可以得到一個比隨機選擇效果略好一些的弱分類器，並且它的實現非常簡單。

在我們實現模型之前，我們先來實現幾個輔助函數。

def loss_error(y_pred, y, weight):
    return weight.T.dot((y_pred != y_train))

def stump_classify(X, idx, threshold, comparator):
    if comparator == 'lt':
        return X[:, idx] <= threshold
    else:
        return X[:, idx] > threshold
    
def get_thresholds(X, i):
    min_val, max_val = X[:, i].min(), X[:, i].max()
    return np.linspace(min_val, max_val, 10)

這三個函數應該都不難理解，第一個函數當中我們計算了模型的誤差。由於我們每一個樣本擁有一個自身的權重，所以我們對誤差進行加權求和。第二個函數是樹樁分類器的預測函數，邏輯非常簡單，根據閾值比較大小。這裡有兩種情況，有可能小於閾值的樣本是正例，也有可能大於閾值的樣本是正例，所以我們還需要第三個參數記錄這個信息。第三個函數是生成閾值的函數，由於我們並不需要樹樁的性能特別好，所以我們也沒有必要去遍歷閾值的所有取值，簡單地把特徵的範圍劃分成10段即可。

接下來是單個樹樁的生成函數，它等價於決策樹當中選擇特徵進行數據拆分的函數，邏輯大同小異，只需要稍作修改即可。

def build_stump(X, y, weight):
    m, n = X.shape
    ret_stump, ret_pred = None, []
    best_error = float('inf')

    # 枚舉特徵
    for i in range(n):
        # 枚舉閾值
        for j in get_thresholds(X, i):
            # 枚舉正例兩種情況
            for c in ['lt', 'gt']:
                # 預測並且求誤差
                pred = stump_classify(X, i, j, c).reshape((-1, 1))
                err = loss_error(pred, y, weight)
                # 記錄下最好的樹樁
                if err < best_error:
                    best_error, ret_pred = err, pred.copy()
                    ret_stump = {'idx': i, 'threshold': j, 'comparator': c} 
    return ret_stump, best_error, ret_pred

接下來要做的就是重複生成樹樁的操作，計算和，並且更新每一條樣本的權重。整個過程也沒有太多的難點，基本上就是照着實現公式：

def adaboost_train(X, y, num_stump):
    stumps = []
    m = X.shape[0]
    # 樣本權重初始化，一開始全部相等
    weight = np.ones((y_train.shape[0], 1)) / y_train.shape[0]
    # 生成num_stump個樹樁
    for i in range(num_stump):
        best_stump, err, pred = build_stump(X, y, weight)
        # 計算alpha
        alpha = 0.5 * np.log((1.0 - err) / max(err, 1e-10))
        best_stump['alpha'] = alpha
        stumps.append(best_stump)

        # 更新每一條樣本的權重
        for j in range(m):
            weight[j] = weight[j] * (np.exp(-alpha) if pred[j] == y[j] else np.exp(alpha))
        weight = weight / weight.sum()
        # 如果當前的準確率已經非常高，則退出
        if err < 1e-8:
            break
    return stumps

樹樁生成結束之後，最後就是預測的部分了。整個預測過程依然非常簡單，就是一個加權求和的過程。這裏要注意一下，我們在訓練的時候為了突出錯誤預測的樣本，讓模型擁有更好的能力，維護了樣本的權重。然而在預測的時候，我們是不知道預測樣本的權重的，所以我們只需要對模型的結果進行加權即可。

def adaboost_classify(X, stumps):
    m = X.shape[0]
    pred = np.ones((m, 1))
    alphs = 0.0
    for i, stump in enumerate(stumps):
        y_pred = stump_classify(X, stump['idx'], stump['threshold'], stump['comparator'])
        # 根據alpha加權求和
        pred = y_pred * stump['alpha']
        alphs += stump['alpha']
    pred /= alphs
    # 根據0.5劃分0和1類別
    return np.sign(pred).reshape((-1, 1))

到這裏，我們整個模型就實現完了，我們先來看下單個樹樁在訓練集上的表現：

可以看到準確率只有0.54，只是比隨機預測略好一點點而已。

然而當我們綜合了20個樹樁的結果之後，在訓練集上我們可以得到0.9的準確率。在預測集上，它的表現更好，準確率有接近0.95！

這是因為AdaBoost當中，每一個分類器都是弱分類器，它根本沒有過擬合的能力，畢竟在訓練集的表現都很差，這就保證了分類器學到的都是實在的泛化能力，在訓練集上適用，在測試集上很大概率也適用。這也是集成方法最大的優點之一。

總結

集成方法可以說是機器學習領域一個非常重要的飛躍，集成方法的出現，讓設計出一個強分類器這件事的難度大大降低，並且還保證了模型的效果。

因為在一些領域當中，設計一個強分類器可能非常困難，然而設計一個弱一些的分類器則簡單得多，再加上模型本身性能很好，不容易陷入過擬合。使得在深度學習模型流行之前，集成方法廣泛使用，幾乎所有機器學習領域的比賽的冠軍，都使用了集成學習。

集成學習當中具體的思想或許各有不同，但是核心的思路是一致的。我們理解了AdaBoost之後，再去學習其他的集成模型就要容易多了。

如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也方便獲取更多文章。

本文使用 mdnice 排版

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※網頁設計公司推薦不同的風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家公司費用,距離,噸數怎麼算?達人教你簡易估價知識!

※教你寫出一流的銷售文案?

※超省錢租車方案

※聚甘新

從linux源碼看epoll

access_timePosted on by admin

從linux源碼看epoll

前言

在linux的高性能網絡編程中，繞不開的就是epoll。和select、poll等系統調用相比,epoll在需要監視大量文件描述符並且其中只有少數活躍的時候，表現出無可比擬的優勢。epoll能讓內核記住所關注的描述符，並在對應的描述符事件就緒的時候,在epoll的就緒鏈表中添加這些就緒元素，並喚醒對應的epoll等待進程。
本文就是筆者在探究epoll源碼過程中，對kernel將就緒描述符添加到epoll並喚醒對應進程的一次源碼分析(基於linux-2.6.32內核版本)。由於篇幅所限，筆者聚焦於tcp協議下socket可讀事件的源碼分析。

簡單的epoll例子

下面的例子，是從筆者本人用c語言寫的dbproxy中的一段代碼。由於細節過多，所以做了一些刪減。

int init_reactor(int listen_fd,int worker_count){
	......
	// 創建多個epoll fd，以充分利用多核
	for(i=0;i<worker_count;i++){
		reactor->worker_fd = epoll_create(EPOLL_MAX_EVENTS);
	}
	/* epoll add listen_fd and accept */
	// 將accept后的事件加入到對應的epoll fd中
	int client_fd = accept(listen_fd,(struct sockaddr *)&client_addr,&client_len)));
	// 將連接描述符註冊到對應的worker裏面
	epoll_ctl(reactor->client_fd,EPOLL_CTL_ADD,epifd,&event);
}
// reactor的worker線程
static void* rw_thread_func(void* arg){
	......

	for(;;){
		  // epoll_wait等待事件觸發
        int retval = epoll_wait(epfd,events,EPOLL_MAX_EVENTS,500);
        if(retval > 0){
        	for(j=0; j < retval; j++){
        		// 處理讀事件
        	   if(event & EPOLLIN){
                 handle_ready_read_connection(conn);
                 continue;
             }
             /* 處理其它事件 */
        	}
        }
	}
	......
}

上述代碼事實上就是實現了一個reactor模式中的accept與read/write處理線程，如下圖所示:

epoll_create

Unix的萬物皆文件的思想在epoll裏面也有體現，epoll_create調用返回一個文件描述符，此描述符掛載在anon_inode_fs(匿名inode文件系統)的根目錄下面。讓我們看下具體的epoll_create系統調用源碼:

SYSCALL_DEFINE1(epoll_create, int, size)
{
	if (size <= 0)
		return -EINVAL;

	return sys_epoll_create1(0);
}

由上述源碼可見，epoll_create的參數是基本沒有意義的，kernel簡單的判斷是否為0，然後就直接就調用了sys_epoll_create1。由於linux的系統調用是通過(SYSCALL_DEFINE1,SYSCALL_DEFINE2……SYSCALL_DEFINE6)定義的，那麼sys_epoll_create1對應的源碼即是SYSCALL_DEFINE(epoll_create1)。
(注:受限於寄存器數量的限制，(80×86下的)kernel限制系統調用最多有6個參數。據ulk3所述，這是由於32位80×86寄存器的限制)
接下來，我們就看下epoll_create1的源碼:

SYSCALL_DEFINE1(epoll_create1, int, flags)
{
	// kzalloc(sizeof(*ep), GFP_KERNEL),用的是內核空間
	error = ep_alloc(&ep);
	// 獲取尚未被使用的文件描述符，即描述符數組的槽位
	fd = get_unused_fd_flags(O_RDWR | (flags & O_CLOEXEC));
	// 在匿名inode文件系統中分配一個inode,並得到其file結構體
	// 且file->f_op = &eventpoll_fops
	// 且file->private_data = ep;
	file = anon_inode_getfile("[eventpoll]", &eventpoll_fops, ep,
				 O_RDWR | (flags & O_CLOEXEC));
	// 將file填入到對應的文件描述符數組的槽裏面
	fd_install(fd,file);			 
	ep->file = file;
	return fd;
}

最後epoll_create生成的文件描述符如下圖所示:

struct eventpoll

所有的epoll系統調用都是圍繞eventpoll結構體做操作,現簡要描述下其中的成員:

/*
 * 此結構體存儲在file->private_data中
 */
struct eventpoll {
	// 自旋鎖，在kernel內部用自旋鎖加鎖，就可以同時多線(進)程對此結構體進行操作
	// 主要是保護ready_list
	spinlock_t lock;
	// 這個互斥鎖是為了保證在eventloop使用對應的文件描述符的時候，文件描述符不會被移除掉
	struct mutex mtx;
	// epoll_wait使用的等待隊列，和進程喚醒有關
	wait_queue_head_t wq;
	// file->poll使用的等待隊列，和進程喚醒有關
	wait_queue_head_t poll_wait;
	// 就緒的描述符隊列
	struct list_head rdllist;
	// 通過紅黑樹來組織當前epoll關注的文件描述符
	struct rb_root rbr;
	// 在向用戶空間傳輸就緒事件的時候，將同時發生事件的文件描述符鏈入到這個鏈表裡面
	struct epitem *ovflist;
	// 對應的user
	struct user_struct *user;
	// 對應的文件描述符
	struct file *file;
	// 下面兩個是用於環路檢測的優化
	int visited;
	struct list_head visited_list_link;
};

本文講述的是kernel是如何將就緒事件傳遞給epoll並喚醒對應進程上，因此在這裏主要聚焦於(wait_queue_head_t wq)等成員。

epoll_ctl(add)

我們看下epoll_ctl(EPOLL_CTL_ADD)是如何將對應的文件描述符插入到eventpoll中的。
藉助於spin_lock(自旋鎖)和mutex(互斥鎖),epoll_ctl調用可以在多個KSE(內核調度實體,即進程/線程)中併發執行。

SYSCALL_DEFINE4(epoll_ctl, int, epfd, int, op, int, fd,
		struct epoll_event __user *, event)
{
	/* 校驗epfd是否是epoll的描述符 */
	// 此處的互斥鎖是為了防止併發調用epoll_ctl,即保護內部數據結構
	// 不會被併發的添加修改刪除破壞
	mutex_lock_nested(&ep->mtx, 0);
	switch (op) {
		case EPOLL_CTL_ADD:
			...
			// 插入到紅黑樹中
			error = ep_insert(ep, &epds, tfile, fd);
			...
			break;
		......
	}
	mutex_unlock(&ep->mtx);	
}

上述過程如下圖所示：

ep_insert

在ep_insert中初始化了epitem，然後初始化了本文關注的焦點,即事件就緒時候的回調函數，代碼如下所示:

static int ep_insert(struct eventpoll *ep, struct epoll_event *event,
		     struct file *tfile, int fd)
{
	/* 初始化epitem */
	// &epq.pt->qproc = ep_ptable_queue_proc
	init_poll_funcptr(&epq.pt, ep_ptable_queue_proc);
	// 在這裏將回調函數注入
	revents = tfile->f_op->poll(tfile, &epq.pt);
	// 如果當前有事件已經就緒，那麼一開始就會被加入到ready list
	// 例如可寫事件
	// 另外，在tcp內部ack之後調用tcp_check_space,最終調用sock_def_write_space來喚醒對應的epoll_wait下的進程
	if ((revents & event->events) && !ep_is_linked(&epi->rdllink)) {
		list_add_tail(&epi->rdllink, &ep->rdllist);
		// wake_up ep對應在epoll_wait下的進程
		if (waitqueue_active(&ep->wq)){
			wake_up_locked(&ep->wq);
		}
		......
	}	
	// 將epitem插入紅黑樹
	ep_rbtree_insert(ep, epi);
	......
}

tfile->f_op->poll的實現

向kernel更底層註冊回調函數的是tfile->f_op->poll(tfile, &epq.pt)這一句，我們來看一下對於對應的socket文件描述符，其fd=>file->f_op->poll的初始化過程：

    // 將accept后的事件加入到對應的epoll fd中
    int client_fd = accept(listen_fd,(struct sockaddr *)&client_addr,&client_len)));
    // 將連接描述符註冊到對應的worker裏面
    epoll_ctl(reactor->client_fd,EPOLL_CTL_ADD,epifd,&event);

回顧一下上述user space代碼，fd即client_fd是由tcp的listen_fd通過accept調用而來，那麼我們看下accept調用鏈的關鍵路徑:

accept
      |->accept4
            |->sock_attach_fd(newsock, newfile, flags & O_NONBLOCK);
                  |->init_file(file,...,&socket_file_ops);
                        |->file->f_op = fop;
                              /* file->f_op = &socket_file_ops */
            |->fd_install(newfd, newfile); // 安裝fd

那麼，由accept獲得的client_fd的結構如下圖所示:

(注:由於是tcp socket,所以這邊sock->ops=inet_stream_ops,這個初始化的過程在我的另一篇博客<<從linux源碼看socket的阻塞和非阻塞>>中，博客地址如下:
https://my.oschina.net/alchemystar/blog/1791017)
既然知道了tfile->f_op->poll的實現，我們就可以看下此poll是如何將安裝回調函數的。

回調函數的安裝

kernel的調用路徑如下:

sock_poll /*tfile->f_op->poll(tfile, &epq.pt)*/;
	|->sock->ops->poll
		|->tcp_poll
			/* 這邊重要的是拿到了sk_sleep用於KSE(進程/線程)的喚醒 */
			|->sock_poll_wait(file, sk->sk_sleep, wait);
				|->poll_wait
					|->p->qproc(filp, wait_address, p);
					/* p為&epq.pt,而且&epq.pt->qproc= ep_ptable_queue_proc*/
						|-> ep_ptable_queue_proc(filp,wait_address,p);

繞了一大圈之後，我們的回調函數的安裝其實就是調用了eventpoll.c中的ep_ptable_queue_proc,而且向其中傳遞了sk->sk_sleep作為其waitqueue的head,其源碼如下所示:

static void ep_ptable_queue_proc(struct file *file, wait_queue_head_t *whead,
				 poll_table *pt)
{
	// 取出當前client_fd對應的epitem
	struct epitem *epi = ep_item_from_epqueue(pt);
	// &pwq->wait->func=ep_poll_callback，用於回調喚醒
	// 注意，這邊不是init_waitqueue_entry,即沒有將當前KSE(current,當前進程/線程)寫入到
	// wait_queue當中，因為不一定是從當前安裝的KSE喚醒，而應該是喚醒epoll\_wait的KSE
	init_waitqueue_func_entry(&pwq->wait, ep_poll_callback);
	// 這邊的whead是sk->sk_sleep,將當前的waitqueue鏈入到socket對應的sleep列表
	add_wait_queue(whead, &pwq->wait);	
}

這樣client_fd的結構進一步完善，如下圖所示:

ep_poll_callback函數是喚醒對應epoll_wait的地方，我們將在後面一起講述。

epoll_wait

epoll_wait主要是調用了ep_poll:

SYSCALL_DEFINE4(epoll_wait, int, epfd, struct epoll_event __user *, events,
		int, maxevents, int, timeout)
{
	/* 檢查epfd是否是epoll\_create創建的fd */
	// 調用ep_poll
	error = ep_poll(ep, events, maxevents, timeout);
	...
}

緊接着，我們看下ep_poll函數:

static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events,
		   int maxevents, long timeout)
{
	......
retry:
	// 獲取spinlock
	spin_lock_irqsave(&ep->lock, flags);
	// 將當前task_struct寫入到waitqueue中以便喚醒
	// wq_entry->func = default_wake_function;
	init_waitqueue_entry(&wait, current);
	// WQ_FLAG_EXCLUSIVE，排他性喚醒，配合SO_REUSEPORT從而解決accept驚群問題
	wait.flags |= WQ_FLAG_EXCLUSIVE;
	// 鏈入到ep的waitqueue中
	__add_wait_queue(&ep->wq, &wait);
	for (;;) {
		// 設置當前進程狀態為可打斷
		set_current_state(TASK_INTERRUPTIBLE);
		// 檢查當前線程是否有信號要處理，有則返回-EINTR
		if (signal_pending(current)) {
			res = -EINTR;
			break;
		}
		spin_unlock_irqrestore(&ep->lock, flags);
		// schedule調度，讓出CPU
		jtimeout = schedule_timeout(jtimeout);
		spin_lock_irqsave(&ep->lock, flags);
	}
	// 到這裏，表明超時或者有事件觸發等動作導致進程重新調度
	__remove_wait_queue(&ep->wq, &wait);
	// 設置進程狀態為running
	set_current_state(TASK_RUNNING);
	......
	// 檢查是否有可用事件
	eavail = !list_empty(&ep->rdllist) || ep->ovflist != EP_UNACTIVE_PTR;
	......
	// 向用戶空間拷貝就緒事件
	ep_send_events(ep, events, maxevents)
}

上述邏輯如下圖所示:

ep_send_events

ep_send_events函數主要就是調用了ep_scan_ready_list,顧名思義ep_scan_ready_list就是掃描就緒列表:

static int ep_scan_ready_list(struct eventpoll *ep,
			      int (*sproc)(struct eventpoll *,
					   struct list_head *, void *),
			      void *priv,
			      int depth)
{
	...
	// 將epfd的rdllist鏈入到txlist
	list_splice_init(&ep->rdllist, &txlist);
	...
	/* sproc = ep_send_events_proc */
	error = (*sproc)(ep, &txlist, priv);
	...
	// 處理ovflist,即在上面sproc過程中又到來的事件
	...
}

其主要調用了ep_send_events_proc:

static int ep_send_events_proc(struct eventpoll *ep, struct list_head *head,
			       void *priv)
{
	for (eventcnt = 0, uevent = esed->events;
	     !list_empty(head) && eventcnt < esed->maxevents;) {
	   // 遍歷ready list 
		epi = list_first_entry(head, struct epitem, rdllink);
		list_del_init(&epi->rdllink);
		// readylist只是表明當前epi有事件，具體的事件信息還是得調用對應file的poll
		// 這邊的poll即是tcp_poll,根據tcp本身的信息設置掩碼(mask)等信息 & 上興趣事件掩碼，則可以得知當前事件是否是epoll_wait感興趣的事件
		revents = epi->ffd.file->f_op->poll(epi->ffd.file, NULL) &
			epi->event.events;
		if(revents){
			/* 將event放入到用戶空間 */
			/* 處理ONESHOT邏輯 */
			// 如果不是邊緣觸發，則將當前的epi重新加回到可用列表中，這樣就可以下一次繼續觸發poll,如果下一次poll的revents不為0，那麼用戶空間依舊能感知 */
			else if (!(epi->event.events & EPOLLET)){
				list_add_tail(&epi->rdllink, &ep->rdllist);
			}
			/* 如果是邊緣觸發，那麼就不加回可用列表，因此只能等到下一個可用事件觸發的時候才會將對應的epi放到可用列表裡面*/
			eventcnt++
		}
		/* 如poll出來的revents事件epoll_wait不感興趣(或者本來就沒有事件)，那麼也不會加回到可用列表 */
		......
	}
	return eventcnt;
}

上述代碼邏輯如下所示:

事件到來添加到epoll就緒隊列(rdllist)的過程

經過上述章節的詳述之後，我們終於可以闡述，tcp在數據到來時是怎麼加入到epoll的就緒隊列的了。

可讀事件到來

首先我們看下tcp數據包從網卡驅動到kernel內部tcp協議處理調用鏈:

step1:

網絡分組到來的內核路徑，網卡發起中斷後調用netif_rx將事件掛入CPU的等待隊列，並喚起軟中斷(soft_irq)，再通過linux的軟中斷機制調用net_rx_action，如下圖所示:

注:上圖來自PLKA(<<深入Linux內核架構>>)

step2:

緊接着跟蹤next_rx_action

next_rx_action
	|-process_backlog
		......
			|->packet_type->func 在這裏我們考慮ip_rcv
					|->ipprot->handler 在這裏ipprot重載為tcp_protocol
						(handler 即為tcp_v4_rcv)

我們再看下對應的tcp_v4_rcv

tcp_v4_rcv
      |->tcp_v4_do_rcv
            |->tcp_rcv_state_process
                  |->tcp_data_queue
                        |-> sk->sk_data_ready(sock_def_readable)
                              |->wake_up_interruptible_sync_poll(sk->sleep,...)
                                    |->__wake_up
                                          |->__wake_up_common
                                                |->curr->func
                                                /* 這裏已經被ep_insert添加為ep_poll_callback,而且設定了排它標識WQ_FLAG_EXCLUSIVE*/
                                                      |->ep_poll_callback

這樣，我們就看下最終喚醒epoll_wait的ep_poll_callback函數:

static int ep_poll_callback(wait_queue_t *wait, unsigned mode, int sync, void *key)
{
	// 獲取wait對應的epitem	
	struct epitem *epi = ep_item_from_wait(wait);
	// epitem對應的eventpoll結構體
	struct eventpoll *ep = epi->ep;
	// 獲取自旋鎖，保護ready_list等結構
	spin_lock_irqsave(&ep->lock, flags);
	// 如果當前epi沒有被鏈入ep的ready list,則鏈入
	// 這樣，就把當前的可用事件加入到epoll的可用列表了
	if (!ep_is_linked(&epi->rdllink))
		list_add_tail(&epi->rdllink, &ep->rdllist);
	// 如果有epoll_wait在等待的話，則喚醒這個epoll_wait進程
	// 對應的&ep->wq是在epoll_wait調用的時候通過init_waitqueue_entry(&wait, current)而生成的
	// 其中的current即是對應調用epoll_wait的進程信息task_struct
	if (waitqueue_active(&ep->wq))
		wake_up_locked(&ep->wq);
}

上述過程如下圖所示:

最後wake_up_locked調用__wake_up_common,然後調用了在init_waitqueue_entry註冊的default_wake_function,調用路徑為:

wake_up_locked
	|->__wake_up_common
		|->default_wake_function
			|->try_wake_up (wake up a thread)
				|->activate_task
					|->enqueue_task    running

將epoll_wait進程推入可運行隊列，等待內核重新調度進程,然後epoll_wait對應的這個進程重新運行后，就從schedule恢復，繼續下面的ep_send_events(向用戶空間拷貝事件並返回)。
wake_up過程如下圖所示:

可寫事件到來

可寫事件的運行過程和可讀事件大同小異:
首先，在epoll_ctl_add的時候預先會調用一次對應文件描述符的poll，如果返回事件里有可寫掩碼的時候直接調用wake_up_locked以喚醒對應的epoll_wait進程。
然後，在tcp在底層驅動有數據到來的時候可能攜帶了ack從而可以釋放部分已經被對端接收的數據，於是觸發可寫事件，這一部分的調用鏈為:

tcp_input.c
tcp_v4_rcv
	|-tcp_v4_do_rcv
		|-tcp_rcv_state_process
			|-tcp_data_snd_check
				|->tcp_check_space
					|->tcp_new_space
						|->sk->sk_write_space
						/* tcp下即是sk_stream_write_space*/

最後在此函數裏面sk_stream_write_space喚醒對應的epoll_wait進程

void sk_stream_write_space(struct sock *sk)
{
	// 即有1/3可寫空間的時候才觸發可寫事件
	if (sk_stream_wspace(sk) >= sk_stream_min_wspace(sk) && sock) {
		clear_bit(SOCK_NOSPACE, &sock->flags);

		if (sk->sk_sleep && waitqueue_active(sk->sk_sleep))
			wake_up_interruptible_poll(sk->sk_sleep, POLLOUT |
						POLLWRNORM | POLLWRBAND)
		......
	}
}

關閉描述符(close fd)

值得注意的是，我們在close對應的文件描述符的時候，會自動調用eventpoll_release將對應的file從其關聯的epoll_fd中刪除，kernel關鍵路徑如下:

close fd
      |->filp_close
            |->fput
                  |->__fput
                        |->eventpoll_release
                              |->ep_remove

所以我們在關閉對應的文件描述符后，並不需要通過epoll_ctl_del來刪掉對應epoll中相應的描述符。

總結

epoll作為linux下非常優秀的事件觸發機製得到了廣泛的運用。其源碼還是比較複雜的，本文只是闡述了epoll讀寫事件的觸發機制，探究linux kernel源碼的過程非常快樂_。

公眾號

關注筆者公眾號，獲取更多乾貨文章:

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※網頁設計公司推薦不同的風格，搶佔消費者視覺第一線

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※別再煩惱如何寫文案,掌握八大原則!

※網頁設計最專業,超強功能平台可客製化

※聚甘新

html/css 滾動到元素位置，显示加載動畫

access_timePosted on by admin

每次滾動到元素時，都显示加載動畫，如何添加？

 

元素添加初始參數

以上圖中的動畫為例，添加倆個左右容器，將內容放置在容器內部。

添加初始數據，默認透明度0、左右分別移動100px。

 1   //左側容器
 2   .item-leftContainer {
 3     opacity: 0;
 4     transform: translateX(-100px);
 5   }
 6   //右側容器
 7   .item-rightContainer {
 8     opacity: 0;
 9     transform: translateX(100px);
10   }

添加動畫數據

在less中添加動畫數據。這裏只設置了to，也可以省略第1步中的初始參數設置而在動畫里設置from。

執行后，透明度由0到1，倆個容器向中間移動100px回到原處。

 1   //動畫
 2   @keyframes showLeft {
 3     to {
 4       opacity: 1;
 5       transform: translateX(0px);
 6     }
 7   }
 8   @keyframes showRight {
 9     to {
10       opacity: 1;
11       transform: translateX(0px);
12     }
13   }
14   @keyframes hideLeft {
15     to {
16       opacity: 0;
17       transform: translateX(-100px);
18     }
19   }
20   @keyframes hideRight {
21     to {
22       opacity: 0;
23       transform: translateX(100px);
24     }
25   }

觸發動畫

頁面加載/刷新觸發 – 在componentDidMount中執行

頁面滾動時觸發 – 在componentDidMount、componentWillUnmount添加監聽/註銷頁面滾動的事件

校驗當前滾動高度與元素的位置差異：

window.pageYOffset（滾動距離） + windowHeight（窗口高度） > leftElement.offsetTop （元素的相對位置）+ parentOffsetTop（父元素的相對位置） + 200

  1. 真正的滾動視覺位置 – window.pageYOffset（滾動距離） + windowHeight（窗口高度）
  2. 元素距離頂部的高度 – 這裏使用了leftElement.offsetTop + parentOffsetTop，原因是父容器使用了absolute絕對定位。如果是正常布局的話，使用元素當前的位置leftElement.offsetTop即可
  3. 額外添加200高度，是為了優化視覺體驗。當超出200高度時才觸發動畫

當頁面滾動到下方，觸發显示動畫；當頁面重新滾動到上方，觸發隱藏動畫。

 1     componentDidMount() {
 2         this.checkScrollHeightAndLoadAnimation();
 3         window.addEventListener('scroll', this.bindHandleScroll);
 4     }
 5     componentWillUnmount() {
 6         window.removeEventListener('scroll', this.bindHandleScroll);
 7     }
 8     bindHandleScroll = (event) => {
 9         this.checkScrollHeightAndLoadAnimation();
10     }
11     checkScrollHeightAndLoadAnimation() {
12         const windowHeight = window.innerHeight;
13         let parentEelement = document.getElementById("softwareUsingWays-container") as HTMLElement;
14         const parentOffsetTop = parentEelement.offsetTop;
15         let leftElement = (parentEelement.getElementsByClassName("item-leftContainer") as HTMLCollectionOf<HTMLElement>)[0];
16         if (window.pageYOffset + windowHeight > leftElement.offsetTop + parentOffsetTop + 200) {
17             leftElement.style.animation = "showLeft .6s forwards" //添加動畫  
18         } else {
19             leftElement.style.animation = "hideLeft 0s forwards" //隱藏動畫 
20         }
21         let rightElement = (parentEelement.getElementsByClassName(".item-rightContainer") as HTMLCollectionOf<HTMLElement>)[0];
22         if (window.pageYOffset + windowHeight > rightElement.offsetTop + parentOffsetTop + 200) {
23             rightElement.style.animation = "showRight .6s forwards" //添加動畫  
24         } else {
25             rightElement.style.animation = "hideRight 0s forwards" //隱藏動畫 
26         }
27     }

 

關鍵字：React 滾動、加載/出現動畫

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計公司推薦不同的風格，搶佔消費者視覺第一線

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※南投搬家公司費用需注意的眉眉角角，別等搬了再說!

※教你寫出一流的銷售文案?

※聚甘新

六、線程池（一）

access_timePosted on by admin

線程池

通過建立池可以有效的利用系統資源，節約系統性能。Java 中的線程池就是一種非常好的實現，從 JDK1.5 開始 Java 提供了一個線程工廠 Executors 用來生成線程池，通過 Executors 可以方便的生成不同類型的線程池。

線程池的優點

  • 降低資源消耗。線程的開啟和銷毀會消耗資源，通過重複利用已創建的線程降低線程創建和銷毀造成的消耗。
  • 提高響應速度。當任務到達時，任務可以不需要的等到線程創建就能立即執行。
  • 提高線程的可管理性。線程是稀缺資源，如果無限制的創建，不僅會消耗系統資源，還會降低系統的穩定性，使用線程池可以進行統一的分配，調優和監控。

常見的線程池

  • CachedThreadPool：可緩存的線程池，該線程池中沒有核心線程，非核心線程的數量為 Integer.max_value，就是無限大，當有需要時創建線程來執行任務，沒有需要時回收線程，適用於耗時少，任務量大的情況。
  • SecudleThreadPool：周期性執行任務的線程池，按照某種特定的計劃執行線程中的任務，有核心線程，但也有非核心線程，非核心線程的大小也為無限大。適用於執行周期性的任務。
  • SingleThreadPool：只有一條線程來執行任務，適用於有順序的任務的應用場景。
  • FixedThreadPool：定長的線程池，有核心線程，核心線程的即為最大的線程數量，沒有非核心線程
  • Executors.newFixedThreadPool()、Executors.newSingleThreadExecutor() 和 Executors.newCachedThreadPool() 等方法的底層都是通過 ThreadPoolExecutor 實現的。

ThreadPoolExecutor

public ThreadPoolExecutor(int corePoolSize,
                          int maximumPoolSize,
                          long keepAliveTime,
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue,
                          ThreadFactory threadFactory,
                          RejectedExecutionHandler handler) {
    if (corePoolSize < 0 ||
        // maximumPoolSize 必須大於 0，且必須大於 corePoolSize
        maximumPoolSize <= 0 ||
        maximumPoolSize < corePoolSize ||
        keepAliveTime < 0)
        throw new IllegalArgumentException();
    if (workQueue == null || threadFactory == null || handler == null)
        throw new NullPointerException();
    this.acc = System.getSecurityManager() == null ?
            null :
            AccessController.getContext();
    this.corePoolSize = corePoolSize;
    this.maximumPoolSize = maximumPoolSize;
    this.workQueue = workQueue;
    this.keepAliveTime = unit.toNanos(keepAliveTime);
    this.threadFactory = threadFactory;
    this.handler = handler;
}

參數介紹：

  • corePoolSize

    • 線程池的核心線程數。在沒有設置 allowCoreThreadTimeOut 為 true 的情況下，核心線程會在線程池中一直存活，即使處於閑置狀態。
    • 如果設置為 0，則表示在沒有任何任務時，銷毀線程池；如果大於 0，即使沒有任務時也會保證線程池的線程數量等於此值。
    • 但需要注意，此值如果設置的比較小，則會頻繁的創建和銷毀線程，如果設置的比較大，則會浪費系統資源，所以需要根據自己的實際業務來調整此值。

  • maximumPoolSize

    • 線程池所能容納的最大線程數。當活動線程(核心線程+非核心線程)達到這個數值后，後續任務將會根據 RejectedExecutionHandler 來進行拒絕策略處理。
    • 官方規定此值必須大於 0，也必須大於等於 corePoolSize，此值只有在任務比較多，且不能存放在任務隊列時，才會用到。

  • keepAliveTime

    • 非核心線程閑置時的超時時長。超過該時長，非核心線程就會被回收。
    • 若線程池通過 allowCoreThreadTimeOut() 方法設置 allowCoreThreadTimeOut 屬性為 true，則該時長同樣會作用於核心線程，AsyncTask 配置的線程池就是這樣設置的。

  • unit

    • keepAliveTime 時長對應的單位。

  • workQueue

    • 表示線程池執行的任務隊列，當線程池的所有線程都在處理任務時，如果來了新任務就會緩存到此任務隊列中排隊等待執行。
    • 是一個阻塞隊列 BlockingQueue，雖然它是 Queue 的子接口，但是它的主要作用並不是容器，而是作為線程同步的工具，他有一個特徵，當生產者試圖向 BlockingQueue 放入(put)元素，如果隊列已滿，則該線程被阻塞；當消費者試圖從 BlockingQueue 取出(take)元素，如果隊列已空，則該線程被阻塞。

  • ThreadFactory

    • 線程的創建工廠，功能很簡單，就是為線程池提供創建新線程的功能。
    • 也可以自定義一個線程工廠，通過實現 ThreadFactory 接口來完成，這樣就可以自定義線程的名稱或線程執行的優先級了。
    • 通常在創建線程池時不指定此參數，它會使用默認的線程創建工廠的方法來創建線程，源代碼如下：
    public ThreadPoolExecutor(int corePoolSize,
                          int maximumPoolSize,
                          long keepAliveTime,
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue) {
    // Executors.defaultThreadFactory() 為默認的線程創建工廠
    this(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue,
         Executors.defaultThreadFactory(), defaultHandler);
}
public static ThreadFactory defaultThreadFactory() {
    return new DefaultThreadFactory();
}
// 默認的線程創建工廠，需要實現 ThreadFactory 接口
static class DefaultThreadFactory implements ThreadFactory {
    private static final AtomicInteger poolNumber = new AtomicInteger(1);
    private final ThreadGroup group;
    private final AtomicInteger threadNumber = new AtomicInteger(1);
    private final String namePrefix;

    DefaultThreadFactory() {
        SecurityManager s = System.getSecurityManager();
        group = (s != null) ? s.getThreadGroup() :
                              Thread.currentThread().getThreadGroup();
        namePrefix = "pool-" +
                      poolNumber.getAndIncrement() +
                     "-thread-";
    }
    // 創建線程
    public Thread newThread(Runnable r) {
        Thread t = new Thread(group, r,
                              namePrefix + threadNumber.getAndIncrement(),
                              0);
        if (t.isDaemon()) 
            t.setDaemon(false); // 創建一個非守護線程
        if (t.getPriority() != Thread.NORM_PRIORITY)
            t.setPriority(Thread.NORM_PRIORITY); // 線程優先級設置為默認值
        return t;
    }
}

  • RejectedExecutionHandler

    • 表示指定線程池的拒絕策略，當線程池的任務已經在緩存隊列 workQueue 中存儲滿了之後，並且不能創建新的線程來執行此任務時，就會用到此拒絕策略.
    • 它屬於一種限流保護的機制，這裡有四種任務拒絕類型：
      1. AbortPolicy: 不執行新任務，直接拋出異常，提示線程池已滿，涉及到該異常的任務也不會被執行，線程池默認的拒絕策略就是該策略。
      2. DisCardPolicy: 不執行新任務，也不拋出異常，即忽略此任務；
      3. DisCardOldSetPolicy: 將消息隊列中的第一個任務(即等待時間最久的任務)替換為當前新進來的任務執行，忽略最早的任務（最先加入隊列的任務）；
      4. CallerRunsPolicy: 把任務交給當前線程來執行；
    /**
 * 線程池的拒絕策略
 */
@Test
public void test1() {
    // 創建線程池 核心線程為1，最大線程為3，任務隊列大小為2
    ThreadPoolExecutor poolExecutor = new ThreadPoolExecutor(1, 3, 10,
            TimeUnit.SECONDS,
            new LinkedBlockingDeque<>(2),
            new ThreadPoolExecutor.AbortPolicy() // 添加 AbortPolicy 拒絕策略
    );


    for (int i = 0; i < 6; i++) {
        poolExecutor.execute(() -> {
            System.out.println(Thread.currentThread().getName());
        });
    }
    
}
    • 自定義線程池拒絕策略
    /**
 * 自定義線程池的拒絕策略
 * 實現接口 RejectedExecutionHandler
 */
@Test
public void test2() {
    ThreadPoolExecutor executor = new ThreadPoolExecutor(1, 3, 10,
            TimeUnit.SECONDS,
            new LinkedBlockingDeque<>(2),
            new RejectedExecutionHandler() {

                @Override
                public void rejectedExecution(Runnable r, ThreadPoolExecutor executor) {
                    // 業務處理方法
                    System.out.println("執行自定義拒絕策略");
                }
            }
    );

    for (int i = 0; i < 6; i++) {
        executor.execute(() -> {
            System.out.println(Thread.currentThread().getName());
        });
    }

}

線程池工作原理

線程池的工作流程要從它的執行方法 execute() 說起，源碼如下：

public void execute(Runnable command) {
    if (command == null)
        throw new NullPointerException();
    int c = ctl.get();
    // 當前工作的線程數小於核心線程數
    if (workerCountOf(c) < corePoolSize) {
        // 創建新的線程執行此任務
        if (addWorker(command, true))
            return;
        c = ctl.get();
    }
    // 檢查線程池是否處於運行狀態，如果是則把任務添加到隊列
    if (isRunning(c) && workQueue.offer(command)) {
        int recheck = ctl.get();
        // 再出檢查線程池是否處於運行狀態，防止在第一次校驗通過後線程池關閉
        // 如果是非運行狀態，則將剛加入隊列的任務移除
        if (! isRunning(recheck) && remove(command))
            reject(command);
        // 如果線程池的線程數為 0 時（當 corePoolSize 設置為 0 時會發生）
        else if (workerCountOf(recheck) == 0)
            addWorker(null, false); // 新建線程執行任務
    }
    // 核心線程都在忙且隊列都已爆滿，嘗試新啟動一個線程執行失敗
    else if (!addWorker(command, false)) 
        // 執行拒絕策略
        reject(command);
}

execute() VS submit()

  • execute() 和 submit() 都是用來執行線程池任務的，它們最主要的區別是，submit() 方法可以接收線程池執行的返回值，而 execute() 不能接收返回值。
  • sumbit 之所以可以接收返回值，是因為參數中可以傳遞：Callable task，而通過 callable 創建的線程任務有返回值並且可以拋出異常。 
/**
 * execute VS sumbin
 * execute 提交任務沒有返回值
 * submit 提交任務有返回值
 */
@Test
public void test3() throws ExecutionException, InterruptedException {
    ThreadPoolExecutor executor = new ThreadPoolExecutor(2, 10, 10, TimeUnit.SECONDS, new LinkedBlockingDeque<>(20));
    // execute
    executor.execute(new Runnable() {
        @Override
        public void run() {
            System.out.println("Hello, execute");
        }
    });

    // submit 使用
    Future<String> future = executor.submit(new Callable<String>() {
        @Override
        public String call() throws Exception {
            System.out.println("Hello, submit");
            return "submit success";
        }
    });
    System.out.println(future.get());
}
  • 它們的另一個區別是 execute() 方法屬於 Executor 接口的方法，而 submit() 方法則是屬於 ExecutorService 接口的方法。

線程池的使用：

import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author xiandongxie
 */
public class ThreadPool {

    //參數初始化 返回Java虛擬機可用的處理器數量
//    private static final int CPU_COUNT = Runtime.getRuntime().availableProcessors();
    private static final int CPU_COUNT = 2;
    //核心線程數量大小
    private static final int corePoolSize = Math.max(2, Math.min(CPU_COUNT - 1, 4));
    //線程池最大容納線程數
    private static final int maximumPoolSize = CPU_COUNT * 2 + 1;
    //線程空閑后的存活時長
    private static final int keepAliveTime = 30;

    //任務過多后，存儲任務的一個阻塞隊列
    BlockingQueue<Runnable> workQueue = new SynchronousQueue<>();

    //線程的創建工廠
    ThreadFactory threadFactory = new ThreadFactory() {
        private final AtomicInteger mCount = new AtomicInteger(1);

        public Thread newThread(Runnable r) {
            return new Thread(r, "AdvacnedAsyncTask #" + mCount.getAndIncrement());
        }
    };

    //線程池任務滿載后採取的任務拒絕策略: 不執行新任務，直接拋出異常，提示線程池已滿
    RejectedExecutionHandler rejectHandler = new ThreadPoolExecutor.AbortPolicy();

    //線程池對象，創建線程
    ThreadPoolExecutor mExecute = new ThreadPoolExecutor(
            corePoolSize,
            maximumPoolSize,
            keepAliveTime,
            TimeUnit.SECONDS,
            workQueue,
            threadFactory,
            rejectHandler
    );

    public static void main(String[] args) {
        System.out.println("main start ..... \nCPU_COUNT = " + CPU_COUNT + "\tcorePoolSize=" + corePoolSize + "\tmaximumPoolSize=" + maximumPoolSize);
        
        ThreadPool threadPool = new ThreadPool();
        ThreadPoolExecutor execute = threadPool.mExecute;
        // 預啟動所有核心線程
        execute.prestartAllCoreThreads();

        for (int i = 0; i < 5; i++) {
            execute.execute(new Runnable() {
                @Override
                public void run() {
                    System.out.println(Thread.currentThread().getName() + "\tstart..." + System.currentTimeMillis());
                    try {
                        Thread.sleep(2000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println(Thread.currentThread().getName() + "\tend..." + System.currentTimeMillis());
                }
            });
        }
        execute.shutdown();
        
        System.out.println("main end .....");
    }
}

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※想知道最厲害的網頁設計公司“嚨底家”!

※別再煩惱如何寫文案,掌握八大原則!

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※聚甘新

Java 從入門到進階之路（二十四）

access_timePosted on by admin

在之前的文章我們介紹了一下 Java 中的  集合框架中的Collection 的泛型，本章我們來看一下 Java 集合框架中的Collection 的子接口 List。

Collection 接口有 3 種子類型，List、Set 和 Queue，其中 List 和 Set 的區別是 Set 中不能存放相同的元素，而 List 中可以，本章我們就來介紹一下 List。

 

 

 從上圖我們可以知道 List 有兩個實例類，ArrayList 和 LinkedList，

ArrayList 是數組實現，查找快，增上慢，由於是數組實現，在增和刪的時候牽扯到數組的增容，以及靠背元素，所以慢，數組是可以直接按索引查找，所以查找時較快。

LinkedList 是鏈表實現，增刪快，查找慢，由於鏈表實現，增加時只要讓前一個元素記住自己就可以了，刪除時讓前一個元素記住后一個元素，后一個元素記住前一個元素，這樣的增刪效率高但查詢時需要一個一個遍歷，所以效率低。

LinkedList 我們可以形象的比作老式手錶的鏈子，一節扣一節，增刪時只需要打開兩個之間的節扣即可，不需要牽扯到其他節扣。

ArrayList 和 LinkedList 都有各自的優缺點，在用的時候可以根據需求自行選擇，避免性能消耗。在現在計算機計算能力越來越強，做的也不是大型項目的時候，這兩個之間的性能差異我們其實是可以忽略的。

接下來我們就來看一下 List 接口的一些基礎用法，如下：

 1 import java.util.ArrayList;
 2 import java.util.List;
 3 
 4 /**
 5  * java.util.List
 6  * 可重複集合，並且有序
 7  * 特點是可以根據下錶操作元素
 8  * ArrayList：使用數組實現，查詢更快
 9  * LinkedList：使用鏈表實現，增刪更快（收尾增刪效果更明顯）
10  */
11 
12 public class Main {
13     public static void main(String[] args) {
14         List<String> list = new ArrayList<String>();
15         list.add("one");
16         list.add("two");
17         list.add("three");
18         list.add("four");
19         /**
20          * E set(int index, E e)
21          * 將給定元素設置到制定位置上，返回原位置的元素
22          * 所以是替換元素操作
23          * 如果超出了元素的長度，則使用 add 添加，否則編譯錯誤
24          * */
25         String old = list.set(1, "2"); // 將下標為 1 的元素改為 2，返回值則是被替換的元素
26         System.out.println(old); // two
27         System.out.println(list); // [one, 2, three, four]
28 
29         /**
30          * E get(int index)
31          * 獲取給定下標對應的元素
32          * */
33         String two = list.get(1); // 獲取第二個元素
34         System.out.println(two); // 2
35 
36         /**
37          * 可以通過傳統的循環遍歷 List 集合
38          * */
39         for (int i = 0; i < list.size(); i++) {
40             System.out.println(list.get(i)); // one 2 three four
41         }
42     }
43 }

在上面的代碼中，我們通過 set 和 get 方法來設置和獲取我們想要的下標的元素，當然還有其他方法，如下：

 1 /**
 2  * List 集合提供了一對重載的 add，remove 方法
 3  * void add(int index, E e)
 4  * 將給定元素插入到指定位置，
 5  * 如果不指定下標，則插入到末尾
 6  * <p>
 7  * E remove(int index)
 8  * 從集合中刪除指定位置的元素，並將其返回
 9  */
10 
11 public class Main {
12     public static void main(String[] args) {
13         List<String> list = new ArrayList<String>();
14         list.add("one");
15         list.add("two");
16         list.add("three");
17         list.add("four");
18 
19         list.add(1, "2"); // 將下標為 1 的元素插入 2
20         System.out.println(list); // [one, 2, two, three, four]
21 
22         String string = list.remove(1); // 將下標為 1 的元素刪除，返回值為該元素
23         System.out.println(string); // 2
24         System.out.println(list); // [one, two, three, four]
25     }
26 }

我們在將 Collection 的時候講過 add 和 remove 方法，在 List 中這兩個方法被重載了，可以根據需求插入和刪除想要刪除的下標的元素，那如果我們想要獲取兩個下標之間的元素和刪除兩個下標之間的元素該怎麼辦呢，如下：

 1 import java.util.ArrayList;
 2 import java.util.List;
 3 
 4 public class Main {
 5     public static void main(String[] args) {
 6         List<Integer> list = new ArrayList<Integer>();
 7         for (int i = 0; i < 10; i++) {
 8             list.add(i);
 9         }
10         System.out.println(list); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
11         List<Integer> subList = list.subList(2, 5); // 獲取下標從 2 到 5 的元素，含 2 不含 5
12         System.out.println(subList); // [2, 3, 4]
13         // 將 subList 中每個元素擴大 10 倍
14         for (int i = 0; i < subList.size(); i++) {
15             subList.set(i, subList.get(i) * 10);
16         }
17         System.out.println(subList); // [20, 30, 40]
18         /**
19          * 對子集的修改，就是修改原集合相應內容
20          * */
21         System.out.println(list); // [0, 1, 20, 30, 40, 5, 6, 7, 8, 9]
22         /**
23          * 刪除集合中 2-5 的元素
24          * */
25         list.subList(2, 5).clear();
26         System.out.println(list); // [0, 1, 5, 6, 7, 8, 9]
27     }
28 }

我們說集合和數組有很多相似的地方，那課可以進行相互轉換呢，當然是可以的，如下：

 1 import java.util.ArrayList;
 2 import java.util.Collection;
 3 
 4 public class Main {
 5     public static void main(String[] args) {
 6         Collection<String> collection = new ArrayList<String>();
 7         collection.add("one");
 8         collection.add("two");
 9         collection.add("three");
10         collection.add("four");
11         System.out.println(collection); // [one, two, three, four]
12         /**
13          * 集合提供了一個 toArray，可以將當前集合轉換為數組
14          * */
15         // Object[] array = collection.toArray(); // 不常用
16         /**
17          * collection.size() 表示要轉換的數組的 length
18          * 如果大於給定的 collection 的 size，則自動填充完整 array
19          * 如果小於給定的 collection 的 size，則自動創建給你一樣長度的 size
20          * */
21         String[] array = collection.toArray(new String[collection.size()]);
22         System.out.println(array.length); // 4
23         for (String string : array) {
24             System.out.println(string); // one two three four
25         }
26 
27         String[] array1 = collection.toArray(new String[6]);
28         System.out.println(array.length); // 4
29         for (String string : array1) {
30             System.out.println(string); // one two three four null null
31         }
32 
33         String[] array2 = collection.toArray(new String[1]);
34         System.out.println(array.length); // 4
35         for (String string : array2) {
36             System.out.println(string); // one two three four
37         }
38     }
39 }

在上面的代碼中我們實現了集合轉換為數組的方法，接下來我們再看一下數組轉換為集合的方法：

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.List;
 4 
 5 /**
 6  * 數組轉換為集合
 7  * 需要注意，轉換隻能轉換為 List 集合
 8  * 使用的是數組的工具類 Arrays 的靜態方法 asList
 9  * 只能轉換為 List 集合的主要原因是：Set 不能存放重複元素
10  * 所以若轉換為 Set 集合可能會出現丟失元素的情況
11  */
12 public class Main {
13     public static void main(String[] args) {
14         String[] array = {"one", "two", "three", "four"};
15         List<String> list = Arrays.asList(array);
16         System.out.println(list); // [one, two, three, four]
17 
18         /**
19          * 向集合中添加元素，會出現編譯錯誤
20          * 相當於在原數組添加元素
21          * 該集合時由數組轉換過來的，那麼該集合就表示原來的數組
22          * 所以對集合的操作就是對數組的操作
23          * 那麼添加元素會導致原數組擴容
24          * 那麼久不能表示原來的數組了
25          * 所以不允許向該集合添加元素
26          */
27         // list.add("five"); // 編譯錯誤 Exception in thread "main" java.lang.UnsupportedOperationException
28 
29         /**
30          * 若希望增刪元素，需要另外創建一個集合
31          * */
32         /**
33          * 所有的集合都提供了一個帶有 Collection 類型參數的構造方法
34          * 該構造方法稱為：複製構造器
35          * 作用是在創建當前集合的同時，
36          * 集合中包含給定集合中的所有元素
37          * */
38         // List<String> list1 = new ArrayList<String>(list); // 複製構造器，一步到位
39         List<String> list1 = new ArrayList<String>();
40         list1.addAll(list);
41         list1.add("five");
42         System.out.println(list1); // [one, 2, three, four, five]
43 
44         /**
45          * 修改集合元素，數組元素也會改變
46          * */
47         list.set(1, "2");
48         System.out.println(list); // [one, 2, three, four]
49         for (String string : array) {
50             System.out.println(string); // one 2 three four
51         }
52     }
53 }

    

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

※FB行銷專家,教你從零開始的技巧

※聚甘新