最新的一波Vue實戰技巧,不用則已,一用驚人

Vue中,不同的選項有不同的合併策略,比如 data,props,methods是同名屬性覆蓋合併,其他直接合併,而生命周期鈎子函數則是將同名的函數放到一個數組中,在調用的時候依次調用

Vue中,提供了一個api, Vue.config.optionMergeStrategies,可以通過這個api去自定義選項的合併策略。

在代碼中打印

console.log(Vue.config.optionMergeStrategies)

  

 通過合併策略自定義生命周期函數

背景

最近客戶給領導反饋,我們的系統用一段時間,瀏覽器就變得有點卡,不知道為什麼。問題出來了,本來想甩鍋到後端,但是瀏覽器問題,沒法甩鍋啊,那就排查吧。

後來發現頁面有許多定時器,ajax輪詢還有動畫,打開一個瀏覽器頁簽沒法問題,打開多了,瀏覽器就變得卡了,這時候我就想如果能在用戶切換頁簽時候將這些都停掉,不久解決了。百度裏面上下檢索,找到了一個事件visibilitychange,可以用來判斷瀏覽器頁簽是否显示。

有方法了,就寫唄

export default {
  created() {
    window.addEventListener('visibilitychange', this.$_hanldeVisiblityChange)
    // 此處用了hookEvent,可以參考小編前一篇文章
    this.$on('hook:beforeDestroy', () => {
      window.removeEventListener(
        'visibilitychange',
        this.$_hanldeVisiblityChange
      )
    })
  },
  methods: {
    $_hanldeVisiblityChange() {
      if (document.visibilityState === 'hidden') {
        // 停掉那一堆東西
      }
      if (document.visibilityState === 'visible') {
        // 開啟那一堆東西
      }
    }
  }
}

通過上面的代碼,可以看到在每一個需要監聽處理的文件都要寫一堆事件監聽,判斷頁面是否显示的代碼,一處兩處還可以,文件多了就頭疼了,這時候小編突發奇想,定義一個頁面显示隱藏的生命周期鈎子,把這些判斷都封裝起來

自定義生命周期鈎子函數

定義生命周期函數 pageHidden 與 pageVisible

import Vue from 'vue'

// 通知所有組件頁面狀態發生了變化
const notifyVisibilityChange = (lifeCycleName, vm) => {
  // 生命周期函數會存在$options中,通過$options[lifeCycleName]獲取生命周期
  const lifeCycles = vm.$options[lifeCycleName]
  // 因為使用了created的合併策略,所以是一個數組
  if (lifeCycles && lifeCycles.length) {
    // 遍歷 lifeCycleName對應的生命周期函數列表,依次執行
    lifeCycles.forEach(lifecycle => {
      lifecycle.call(vm)
    })
  }
  // 遍歷所有的子組件,然後依次遞歸執行
  if (vm.$children && vm.$children.length) {
    vm.$children.forEach(child => {
      notifyVisibilityChange(lifeCycleName, child)
    })
  }
}

// 添加生命周期函數
export function init() {
  const optionMergeStrategies = Vue.config.optionMergeStrategies
  // 定義了兩個生命周期函數 pageVisible, pageHidden
  // 為什麼要賦值為 optionMergeStrategies.created呢
  // 這個相當於指定 pageVisible, pageHidden 的合併策略與 created的相同(其他生命周期函數都一樣)
  optionMergeStrategies.pageVisible = optionMergeStrategies.beforeCreate
  optionMergeStrategies.pageHidden = optionMergeStrategies.created
}


// 將事件變化綁定到根節點上面
// rootVm vue根節點實例
export function bind(rootVm) {
  window.addEventListener('visibilitychange', () => {
    // 判斷調用哪個生命周期函數
    let lifeCycleName = undefined
    if (document.visibilityState === 'hidden') {
      lifeCycleName = 'pageHidden'
    } else if (document.visibilityState === 'visible') {
      lifeCycleName = 'pageVisible'
    }
    if (lifeCycleName) {
      // 通過所有組件生命周期發生變化了
      notifyVisibilityChange(lifeCycleName, rootVm)
    }
  })
}

應用

  1. main.js主入口文件引入
import { init, bind } from './utils/custom-life-cycle'

// 初始化生命周期函數, 必須在Vue實例化之前確定合併策略
init()

const vm = new Vue({
  router,
  render: h => h(App)
}).$mount('#app')

// 將rootVm 綁定到生命周期函數監聽裏面
bind(vm)

  2. 在需要的地方監聽生命周期函數

export default {
  pageVisible() {
    console.log('頁面显示出來了')
  },
  pageHidden() {
    console.log('頁面隱藏了')
  }
}

  

provideinject,不止父子傳值,祖宗傳值也可以

Vue相關的面試經常會被面試官問道,Vue父子之間傳值的方式有哪些,通常我們會回答,props傳值,$emit事件傳值,vuex傳值,還有eventbus傳值等等,今天再加一種provideinject傳值,離offer又近了一步。(對了,下一節還有一種)

使用過React的同學都知道,在React中有一個上下文Context,組件可以通過Context向任意後代傳值,而Vueprovideinject的作用於Context的作用基本一樣

先舉一個例子

使用過elemment-ui的同學一定對下面的代碼感到熟悉

<template>
  <el-form :model="formData" size="small">
    <el-form-item label="姓名" prop="name">
      <el-input v-model="formData.name" />
    </el-form-item>
    <el-form-item label="年齡" prop="age">
      <el-input-number v-model="formData.age" />
    </el-form-item>
    <el-button>提交</el-button>
  </el-form>
</template>
<script>
export default {
  data() {
    return {
      formData: {
        name: '',
        age: 0
      }
    }
  }
}
</script>

  

看了上面的代碼,貌似沒啥特殊的,天天寫啊。在el-form上面我們指定了一個屬性size="small",然後有沒有發現表單裏面的所有表單元素以及按鈕的 size都變成了small,這個是怎麼做到的?接下來我們自己手寫一個表單模擬一下

自己手寫一個表單

自定義表單custom-form.vue

<template>
  <form class="custom-form">
    <slot></slot>
  </form>
</template>
<script>
export default {
  props: {
    // 控製表單元素的大小
    size: {
      type: String,
      default: 'default',
      // size 只能是下面的四個值
      validator(value) {
        return ['default', 'large', 'small', 'mini'].includes(value)
      }
    },
    // 控製表單元素的禁用狀態
    disabled: {
      type: Boolean,
      default: false
    }
  },
  // 通過provide將當前表單實例傳遞到所有後代組件中
  provide() {
    return {
      customForm: this
    }
  }
}
</script>

  

在上面代碼中,我們通過provide將當前組件的實例傳遞到後代組件中,provide是一個函數,函數返回的是一個對象

自定義表單項custom-form-item.vue

沒有什麼特殊的,只是加了一個label,element-ui更複雜一些

<template>
  <div class="custom-form-item">
    <label class="custom-form-item__label">{{ label }}</label>
    <div class="custom-form-item__content">
      <slot></slot>
    </div>
  </div>
</template>
<script>
export default {
  props: {
    label: {
      type: String,
      default: ''
    }
  }
}
</script>

自定義輸入框 custom-input.vue

<template>
  <div
    class="custom-input"
    :class="[
      `custom-input--${getSize}`,
      getDisabled && `custom-input--disabled`
    ]"
  >
    <input class="custom-input__input" :value="value" @input="$_handleChange" />
  </div>
</template>
<script>
/* eslint-disable vue/require-default-prop */
export default {
  props: {
    // 這裏用了自定義v-model
    value: {
      type: String,
      default: ''
    },
    size: {
      type: String
    },
    disabled: {
      type: Boolean
    }
  },
  // 通過inject 將form組件注入的實例添加進來
  inject: ['customForm'],
  computed: {
    // 通過計算組件獲取組件的size, 如果當前組件傳入,則使用當前組件的,否則是否form組件的
    getSize() {
      return this.size || this.customForm.size
    },
    // 組件是否禁用
    getDisabled() {
      const { disabled } = this
      if (disabled !== undefined) {
        return disabled
      }
      return this.customForm.disabled
    }
  },
  methods: {
    // 自定義v-model
    $_handleChange(e) {
      this.$emit('input', e.target.value)
    }
  }
}
</script>

  


form中,我們通過
provide返回了一個對象,在
input中,我們可以通過
inject獲取
form中返回對象中的項,如上代碼
inject:['customForm']所示,然後就可以在組件內通過
this.customForm調用
form實例上面的屬性與方法了

在項目中使用

<template>
  <custom-form size="small">
    <custom-form-item label="姓名">
      <custom-input v-model="formData.name" />
    </custom-form-item>
  </custom-form>
</template>
<script>
import CustomForm from '../components/custom-form'
import CustomFormItem from '../components/custom-form-item'
import CustomInput from '../components/custom-input'
export default {
  components: {
    CustomForm,
    CustomFormItem,
    CustomInput
  },
  data() {
    return {
      formData: {
        name: '',
        age: 0
      }
    }
  }
}
</script>

  執行上面代碼,運行結果為:

<form class="custom-form">
  <div class="custom-form-item">
    <label class="custom-form-item__label">姓名</label>
    <div class="custom-form-item__content">
      <!--size=small已經添加到指定的位置了-->
      <div class="custom-input custom-input--small">
        <input class="custom-input__input">
      </div>
    </div>
  </div>
</form>

  

通過上面的代碼可以看到,input組件已經設置組件樣式為custom-input--small

inject格式說明

除了上面代碼中所使用的inject:['customForm']寫法之外,inject還可以是一個對象。且可以指定默認值

修改上例,如果custom-input外部沒有custom-form,則不會注入customForm,此時為customForm指定默認值

{
  inject: {
    customForm: {
      // 對於非原始值,和props一樣,需要提供一個工廠方法
      default: () => ({
        size: 'default'
      })
    }
  }
}

  

使用限制

1.provideinject的綁定不是可響應式的。但是,如果你傳入的是一個可監聽的對象,如上面的customForm: this,那麼其對象的屬性還是可響應的。

2.Vue官網建議provideinject 主要在開發高階插件/組件庫時使用。不推薦用於普通應用程序代碼中。因為provideinject在代碼中是不可追溯的(ctrl + f可以搜),建議可以使用Vuex代替。 但是,也不是說不能用,在局部功能有時候用了作用還是比較大的。

 

插槽,我要鑽到你的懷裡

插槽,相信每一位Vue都有使用過,但是如何更好的去理解插槽,如何去自定義插槽,今天小編為你帶來更形象的說明。

默認插槽

<template>
  <!--這是一個一居室-->
  <div class="one-bedroom">
    <!--添加一個默認插槽,用戶可以在外部隨意定義這個一居室的內容-->
    <slot></slot>
  </div>
</template>

  

<template>
  <!--這裏一居室-->
  <one-bedroom>
    <!--將傢具放到房間裏面,組件內部就是上面提供的默認插槽的空間-->
    <span>先放一個小床,反正沒有女朋友</span>
    <span>再放一個電腦桌,在家還要加班寫bug</span>
  </one-bedroom>
</template>
<script>
import OneBedroom from '../components/one-bedroom'
export default {
  components: {
    OneBedroom
  }
}
</script>

具名插槽

<template>
  <div class="two-bedroom">
    <!--這是主卧-->
    <div class="master-bedroom">
      <!---主卧使用默認插槽-->
      <slot></slot>
    </div>
    <!--這是次卧-->
    <div class="secondary-bedroom">
      <!--次卧使用具名插槽-->
      <slot name="secondard"></slot>
    </div>
  </div>
</template>

  

<template>
  <two-bedroom>
    <!--主卧使用默認插槽-->
    <div>
      <span>放一個大床,要結婚了,嘿嘿嘿</span>
      <span>放一個衣櫃,老婆的衣服太多了</span>
      <span>算了,還是放一個電腦桌吧,還要寫bug</span>
    </div>
    <!--次卧,通過v-slot:secondard 可以指定使用哪一個具名插槽, v-slot:secondard 也可以簡寫為 #secondard-->
    <template v-slot:secondard>
      <div>
        <span>父母要住,放一個硬一點的床,軟床對腰不好</span>
        <span>放一個衣櫃</span>
      </div>
    </template>
  </two-bedroom>
</template>
<script>
import TwoBedroom from '../components/slot/two-bedroom'
export default {
  components: {
    TwoBedroom
  }
}
</script>

作用域插槽

<template>
  <div class="two-bedroom">
    <!--其他內容省略-->
    <div class="toilet">
      <!--通過v-bind 可以向外傳遞參數, 告訴外面衛生間可以放洗衣機-->
      <slot name="toilet" v-bind="{ washer: true }"></slot>
    </div>
  </div>
</template>

  

<template>
  <two-bedroom>
    <!--其他省略-->
    <!--衛生間插槽,通過v-slot="scope"可以獲取組件內部通過v-bind傳的值-->
    <template v-slot:toilet="scope">
      <!--判斷是否可以放洗衣機-->
      <span v-if="scope.washer">這裏放洗衣機</span>
    </template>
  </two-bedroom>
</template>  

插槽默認值

<template>
  <div class="second-hand-house">
    <div class="master-bedroom">
      <!--插槽可以指定默認值,如果外部調用組件時沒有修改插槽內容,則使用默認插槽-->
      <slot>
        <span>這裡有一張水床,玩的夠嗨</span>
        <span>還有一個衣櫃,有點舊了</span>
      </slot>
    </div>
    <!--這是次卧-->
    <div class="secondary-bedroom">
      <!--次卧使用具名插槽-->
      <slot name="secondard">
        <span>這裡有一張嬰兒床</span>
      </slot>
    </div>
  </div>
</template>

  

<second-hand-house>
    <!--主卧使用默認插槽,只裝修主卧-->
    <div>
      <span>放一個大床,要結婚了,嘿嘿嘿</span>
      <span>放一個衣櫃,老婆的衣服太多了</span>
      <span>算了,還是放一個電腦桌吧,還要寫bug</span>
    </div>
  </second-hand-house>

dispatchbroadcast,這是一種有歷史的組件通信方式

dispatch
broadcast是一種有歷史的組件通信方式,為什麼是有歷史的,因為他們是
Vue1.0提供的一種方式,在
Vue2.0中廢棄了。但是廢棄了不代表我們不能自己手動實現,像許多UI庫內部都有實現。本文以
element-ui實現為基礎進行介紹。同時看完本節,你會對組件的
$parent,
$children,
$options有所了解。

方法介紹

$dispatch: $dispatch會向上觸發一個事件,同時傳遞要觸發的祖先組件的名稱與參數,當事件向上傳遞到對應的組件上時會觸發組件上的事件偵聽器,同時傳播會停止。

$broadcast: $broadcast會向所有的後代組件傳播一個事件,同時傳遞要觸發的後代組件的名稱與參數,當事件傳遞到對應的後代組件時,會觸發組件上的事件偵聽器,同時傳播會停止(因為向下傳遞是樹形的,所以只會停止其中一個恭弘=叶 恭弘子分支的傳遞)。

$dispatch實現與應用

1. 代碼實現

 // 向上傳播事件
 // @param {*} eventName 事件名稱
 // @param {*} componentName 接收事件的組件名稱
 // @param {...any} params 傳遞的參數,可以有多個
 
function dispatch(eventName, componentName, ...params) {
  // 如果沒有$parent, 則取$root
  let parent = this.$parent || this.$root
  while (parent) {
    // 組件的name存儲在組件的$options.componentName 上面
    const name = parent.$options.name
    // 如果接收事件的組件是當前組件
    if (name === componentName) {
      // 通過當前組件上面的$emit觸發事件,同事傳遞事件名稱與參數
      parent.$emit.apply(parent, [eventName, ...params])
      break
    } else {
      // 否則繼續向上判斷
      parent = parent.$parent
    }
  }
}

// 導出一個對象,然後在需要用到的地方通過混入添加
export default {
  methods: {
    $dispatch: dispatch
  }
}  

2. 代碼應用

  • 在子組件中通過$dispatch向上觸發事件

    import emitter from '../mixins/emitter'
    export default {
      name: 'Chart',
      // 通過混入將$dispatch加入進來
      mixins: [emitter],
       mounted() {
         // 在組件渲染完之後,將組件通過$dispatch將自己註冊到Board組件上
        this.$dispatch('register', 'Board', this)
      }
    }
  • Board組件上通過$on監聽要註冊的事件

$broadcast實現與應用

1. 代碼實現

  //向下傳播事件
  // @param {*} eventName 事件名稱
  // @param {*} componentName 要觸發組件的名稱
  // @param  {...any} params 傳遞的參數
 
function broadcast(eventName, componentName, ...params) {
  this.$children.forEach(child => {
    const name = child.$options.name
    if (name === componentName) {
      child.$emit.apply(child, [eventName, ...params])
    } else {
      broadcast.apply(child, [eventName, componentName, ...params])
    }
  })
}

// 導出一個對象,然後在需要用到的地方通過混入添加
export default {
  methods: {
    $broadcast: broadcast
  }
}  

2. 代碼應用

在父組件中通過$broadcast向下觸發事件

import emitter from '../mixins/emitter'
export default {
  name: 'Board',
  // 通過混入將$dispatch加入進來
  mixins: [emitter],
  methods:{
  	//在需要的時候,刷新組件
  	$_refreshChildren(params) {
  		this.$broadcast('refresh', 'Chart', params)
  	}
  }
}

在後代組件中通過$on監聽刷新事件

export default {
  name: 'Chart',
  created() {
    this.$on('refresh',(params) => {
      // 刷新事件
    })
  }
}

總結

通過上面的例子,同學們應該都能對$dispatch$broadcast有所了解,但是為什麼Vue2.0要放棄這兩個方法呢?官方給出的解釋是:”因為基於組件樹結構的事件流方式實在是讓人難以理解,並且在組件結構擴展的過程中會變得越來越脆弱。這種事件方式確實不太好,我們也不希望在以後讓開發者們太痛苦。並且 $dispatch$broadcast 也沒有解決兄弟組件間的通信問題。“

確實如官網所說,這種事件流的方式確實不容易讓人理解,而且後期維護成本比較高。但是在小編看來,不管黑貓白貓,能抓老鼠的都是好貓,在許多特定的業務場景中,因為業務的複雜性,很有可能使用到這樣的通信方式。但是使用歸使用,但是不能濫用,小編一直就在項目中有使用。

 

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

【其他文章推薦】

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

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

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

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

新北清潔公司,居家、辦公、裝潢細清專業服務

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

深入解讀Dictionary

Dictionary<TKey,TValue>是日常.net開發中最常用的數據類型之一,基本上遇到鍵值對類型的數據時第一反應就是使用這種散列表。散列表特別適合快速查找操作,查找的效率是常數階O(1)。那麼為什麼這種數據類型的查找效率能夠這麼高效?它背後的數據類型是如何支撐這種查找效率的?它在使用過程中有沒有什麼局限性?一起來探究下這個數據類型的奧秘吧。

本文內容針對的是.Net Framework 4.5.1的代碼實現,在其他.Net版本中或多或少都會有些差異,但是基本的原理還是相同的。

本文的內容主要分為三個部分,第一部分是從代碼的角度來分析並以圖文並茂的方式通俗的解釋Dictionary如何解決的散列衝突並實現高效的數據插入和查找。第二部分名為“眼見為實”,由於第一部分是從代碼層面分析Dictionary的實現,側重於理論分析,因此第二部分使用windbg直接分析內存結構,跟第一部分的理論分析相互印證,加深對於這種數據類型的深入理解。最後是從數據結構的時間複雜度的角度進行分析並提出了幾條實踐建議。

本文內容:

  • 第一部分 代碼分析
    • 散列衝突
    • Dictionary圖文解析
    • Dictionary的初始化
    • 添加第四個元素
  • 第二部分 眼見為實
    • 添加第一個元素后的內存結構
    • 添加第四個元素后的內存結構
  • 第三部分
    • 時間複雜度分析
    • 實踐建議

散列衝突

提到散列表,就不能不提散列衝突。由於哈希算法被計算的數據是無限的,而計算后的結果範圍有限,因此總會存在不同的數據經過計算后得到的值相同,這就是哈希衝突。(兩個不同的數據計算后的結果一樣)。散列衝突的解決方案有好幾個,比如開放尋址法、鏈式尋址法。

Dictionary使用的是鏈式尋址法,也叫做拉鏈法。拉鏈法的基本思想是將散列值相同的數據存在同一個鏈表中,如果有散列值相同的元素,則加到鏈表的頭部。同樣道理,在查找元素的時候,先計算散列值,然後在對應散列值的鏈表中查找目標元素。

用圖來表達鏈式尋址法的思想:

Dictionary<TKey,TValue>的內部數據結構

Dictionary的內部存儲數據主要是依賴了兩個數組,分別是int[] bucketsEntry[] entries。其中buckets是Dictionary所有操作的入口,類似於上文中解說拉鏈法所用的圖中的那個豎著的數據結構。Entry是一個結構體,用於封裝所有的元素並且增加了next字段用於構建鏈表數據結構。為了便於理解,下文中截取了一段相關的源代碼並增加了註釋。

//數據在Dictionary<TKey,TValue>的存儲形式,所有的鍵值對在Dictionary<TKey,TValue>都是被包裝成一個個的Entry保存在內存中
private struct Entry {
    public int hashCode;    // 散列計算結果的低31位數,默認值為-1
    public int next;        // 下一個Entry的索引值,鏈表的最後一個Entry的next為-1
    public TKey key;        // Entry對象的Key對應於傳入的TKey
    public TValue value;    // Entry對象的Value對應與傳入的TValue
}

private int[] buckets;      //hashCode的桶,是查找所有Entry的第一級數據結構
private Entry[] entries;    //保存真正的數據

下文中以Dictionary<int,string>為例,分析Dictionary在使用過程中內部數據的組織方式。

Dictionary初始化

初始化代碼:

Dictionary<int, string> dictionary = new Dictionary<int, string>();

Dictionary的初始化時,bucketsentries的長度都是0。

添加一個元素

dictionary.Add(1, "xyxy");

向Dictionary中添加這個新元素大致經過了7個步驟:

  1. 首先判斷數組長度是否需要擴容(原長度為0,需要擴容);
  2. 對於數組進行擴容,分別創建長度為3的bucket數組和entries數組(使用大於原數組長度2倍的第一個素數作為新的數組長度);
  3. 整數1的hashcode為1;
  4. 取低31位數值為1(計算公式:hashcode & 0x7FFFFFFF=1);
  5. 該key的hashcode落到bucket下標為1的位置(計算公式:hashCode % buckets.Length=1);
  6. 將hashcode、key、value包裝起來(封裝到entries數組下標為0的結構體中);
  7. 設置bucket[1]的值為0(因為新元素被封裝到了entries數組下標為0的位置);

當向Dictionary中添加一個元素后,內部數據結構如下圖(為了便於理解,圖上將bucket和entries中各個鏈表頭結點用線標出了關聯關係):

添加第二個元素

dictionary.Add(7, "xyxy");

向Dictionary中添加這個元素大致經過了6個步驟:

  1. 計算7的hashcode是7;
  2. 取低31位數值為7(計算公式:hashcode & 0x7FFFFFFF=1);
  3. 該key的hashcode落到bucket下標為1的位置(計算公式:hashCode % buckets.Length=1);
  4. 將hashcode、key、value包裝起來(封裝到entries數組下標為1的結構體中,跟步驟3計算得到的1沒有關係,只是因為entries數組下標為1的元素是空着的所以放在這裏);
  5. 原bucket[1]為0,所以設置當前結構體的Entry.next為0;
  6. 設置bucket[1]為1(因為鏈表的頭部節點位於entries數組下標為1的位置)

當向Dictionary中添加第二個元素后,內部數據結構是這樣的:

添加第三個元素

dictionary.Add(2, "xyxy");

向Dictionary添加這個元素經過了如下5個步驟:

  1. 整數2計算的hashcode是2;
  2. hashcode取低31位數值為2(計算公式:hashcode & 0x7FFFFFFF=2);
  3. 該key的hashcode落到bucket下標為2的位置(計算公式:hashCode % buckets.Length=2);
  4. 將hashcode、key、value包裝起來(封裝到entries數組下標為2的結構體中,到此entries的數組就存滿了);
  5. 原bucket[2]上為-1,所以bucket[2]節點下並沒有對應鏈表,設置當前結構體的Entry.next為-1;
  6. 設置bucket[2]為2(因為鏈表的頭部節點位於entries數組下標為2的位置)

當向Dictionary中添加第三個元素后,內部數據結構:

添加第四個元素

dictionary.Add(4, "xyxy");

通過前面幾個操作可以看出,當前數據結構中entries數組中的元素已滿,如果再添加元素的話,會發生怎樣的變化呢?

假如再對於dictionary添加一個元素,原來申請的內存空間肯定是不夠用的,必須對於當前數據結構進行擴容,然後在擴容的基礎上再執行添加元素的操作。那麼在解釋這個Add方法原理的時候,分為兩個場景分別進行:數組擴容和元素添加。

數組擴容

在發現數組容量不夠的時候,Dictionary首先執行擴容操作,擴容的規則與該數據類型首次初始化的規則相同,即使用大於原數組長度2倍的第一個素數7作為新數組的長度(3*2=6,大於6的第一個素數是7)。

擴容步驟:

  1. 新申請一個容量為7的數組,並將原數組的元素拷貝至新數組(代碼:Array.Copy(entries, 0, newEntries, 0, count);
  2. 重新計算原Dictionary中的元素的hashCode在bucket中的位置(注意新的bucket數組中數值的變化);
  3. 重新計算鏈表(注意entries數組中結構體的next值的變化);

擴容完成后Dictionary的內容數據結構:

添加元素

當前已經完成了entriesbucket數組的擴容,有了充裕的空間來存儲新的元素,所以可以在新的數據結構的基礎上繼續添加元素。

當向Dictionary中添加第四個元素后,內部數據結構是這樣的:

添加這個新的元素的步驟:

  1. 整數4計算的hashcode是4;
  2. hashcode取低31位數值為4(計算公式:hashcode & 0x7FFFFFFF=4);
  3. 該key的hashcode落到bucket下標為4的位置(計算公式:hashCode % buckets.Length=4);
  4. 將hashcode、key、value包裝起來;(封裝到entries數組下標為3的結構體中);
  5. 原bucket[4]上為-1,所以當前節點下並沒有鏈表,設置當前結構體的Entry.next為-1;
  6. 設置bucket[4]為3(因為鏈表的頭部節點位於entries數組下標為3的位置)

眼見為實

畢竟本文的主題是圖文並茂分析Dictionary<Tkey,Tvalue>的原理,雖然已經從代碼層面和理論層面分析了Dictionary<Tkey,Tvalue>的實現,但是如果能夠分析這個數據類型的實際內存數據結果,可以獲得更直觀的感受並且對於這個數據類型能夠有更加深入的認識。由於篇幅的限制,無法將Dictionary<Tkey,Tvalue>的所有操作場景結果都進行內存分析,那麼本文中精選有代表性的兩個場景進行分析:一是該數據類型初始化后添加第一個元素的內存結構,二是該數據類型進行第一次擴容后的數據結構。

Dictionary添加第一個元素后的內存結構

執行代碼:

Dictionary<int, string> dic = new Dictionary<int, string>();
dic.Add(1, "xyxy");
Console.Read();

打開windbg附加到該進程(由於使用的是控制台應用程序,當前線程是0號線程,因此如果附加進程后默認的不是0號線程時執行~0s切換到0號線程),執行!clrstack -l查看當前線程及線程上使用的所有變量:

0:000> !clrstack -l
OS Thread Id: 0x48b8 (0)
        Child SP               IP Call Site
0000006de697e998 00007ffab577c134 [InlinedCallFrame: 0000006de697e998] Microsoft.Win32.Win32Native.ReadFile(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)
0000006de697e998 00007ffa96abc9c8 [InlinedCallFrame: 0000006de697e998] Microsoft.Win32.Win32Native.ReadFile(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)
0000006de697e960 00007ffa96abc9c8 *** ERROR: Module load completed but symbols could not be loaded for C:\WINDOWS\assembly\NativeImages_v4.0.30319_64\mscorlib\5c1b7b73113a6f079ae59ad2eb210951\mscorlib.ni.dll
DomainNeutralILStubClass.IL_STUB_PInvoke(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)

0000006de697ea40 00007ffa972d39ec System.IO.__ConsoleStream.ReadFileNative(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte[], Int32, Int32, Boolean, Boolean, Int32 ByRef)
    LOCALS:
        <no data>
        <no data>
        <no data>
        <no data>
        <no data>
        <no data>

0000006de697ead0 00007ffa972d38f5 System.IO.__ConsoleStream.Read(Byte[], Int32, Int32)
    LOCALS:
        <no data>
        <no data>

0000006de697eb30 00007ffa96a882d4 System.IO.StreamReader.ReadBuffer()
    LOCALS:
        <no data>
        <no data>

0000006de697eb80 00007ffa97275f23 System.IO.StreamReader.Read()
    LOCALS:
        <no data>

0000006de697ebb0 00007ffa9747a2fd System.IO.TextReader+SyncTextReader.Read()

0000006de697ec10 00007ffa97272698 System.Console.Read()

0000006de697ec40 00007ffa38670909 ConsoleTest.DictionaryDebug.Main(System.String[])
    LOCALS:
        0x0000006de697ec70 = 0x00000215680d2dd8

0000006de697ee88 00007ffa97ba6913 [GCFrame: 0000006de697ee88] 

通過對於線程堆棧的分析很容易看出當前線程上使用了一個局部變量,地址為:0x000001d86c972dd8,使用!do命令查看該變量的內容:

0:000> !do 0x00000215680d2dd8
Name:        System.Collections.Generic.Dictionary`2[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513328
EEClass:     00007ffa9662f610
Size:        80(0x50) bytes
File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
              MT    Field   Offset                 Type VT     Attr            Value Name
00007ffa964a8538  4001887        8       System.Int32[]  0 instance 00000215680d2ee8 buckets
00007ffa976c4dc0  4001888       10 ...non, mscorlib]][]  0 instance 00000215680d2f10 entries
00007ffa964a85a0  4001889       38         System.Int32  1 instance                1 count
00007ffa964a85a0  400188a       3c         System.Int32  1 instance                1 version
00007ffa964a85a0  400188b       40         System.Int32  1 instance               -1 freeList
00007ffa964a85a0  400188c       44         System.Int32  1 instance                0 freeCount
00007ffa96519630  400188d       18 ...Int32, mscorlib]]  0 instance 00000215680d2ed0 comparer
00007ffa964c6ad0  400188e       20 ...Canon, mscorlib]]  0 instance 0000000000000000 keys
00007ffa977214e0  400188f       28 ...Canon, mscorlib]]  0 instance 0000000000000000 values
00007ffa964a5dd8  4001890       30        System.Object  0 instance 0000000000000000 _syncRoot

從內存結構來看,該變量中就是我們查找的Dic存在buckets、entries、count、version等字段,其中buckets和entries在上文中已經有多次提及,也是本文的分析重點。既然要眼見為實,那麼buckets和entries這兩個數組的內容到底是什麼樣的呢?這兩個都是數組,一個是int數組,另一個是結構體數組,對於這兩個內容分別使用!da命令查看其內容:

首先是buckets的內容:

0:000> !da -start 0 -details 00000215680d2ee8 
Name:        System.Int32[]
MethodTable: 00007ffa964a8538
EEClass:     00007ffa966160e8
Size:        36(0x24) bytes
Array:       Rank 1, Number of elements 3, Type Int32
Element Methodtable: 00007ffa964a85a0
[0] 00000215680d2ef8
    Name:        System.Int32
    MethodTable: 00007ffa964a85a0
    EEClass:     00007ffa96616078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  40005a2        0             System.Int32      1     instance                   -1     m_value
[1] 00000215680d2efc
    Name:        System.Int32
    MethodTable: 00007ffa964a85a0
    EEClass:     00007ffa96616078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  40005a2        0             System.Int32      1     instance                    0     m_value
[2] 00000215680d2f00
    Name:        System.Int32
    MethodTable: 00007ffa964a85a0
    EEClass:     00007ffa96616078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  40005a2        0             System.Int32      1     instance                   -1     m_value


當前buckets中有三個值,分別是:-1、0和-1,其中-1是數組初始化后的默認值,而下錶為1的位置的值0則是上文中添加dic.Add(1, "xyxy");這個指令的結果,代表其對應的鏈表首節點在entries數組中下標為0的位置,那麼entries數組中的數值是什麼樣子的呢?

0:000> !da -start 0 -details 00000215680d2f10 
Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]][]
MethodTable: 00007ffa965135b8
EEClass:     00007ffa9662d1f0
Size:        96(0x60) bytes
Array:       Rank 1, Number of elements 3, Type VALUETYPE
Element Methodtable: 00007ffa96513558
[0] 00000215680d2f20
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    1     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    1     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000215680d2db0     value
[1] 00000215680d2f38
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value
[2] 00000215680d2f50
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value

通過對於entries數組的分析可以看出,這個數組也有三個值,其中下標為0的位置已經填入相關內容,比如hashCode為1,key為1,其中value的內容是一個內存地址:000001d86c972db0,這個地址指向的就是字符串對象,它的內容是xyxy,使用!do指令來看下具體內容:

0:000> !do  00000215680d2db0
Name:        System.String
MethodTable: 00007ffcc6b359c0
EEClass:     00007ffcc6b12ec0
Size:        34(0x22) bytes
File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
String:      xyxy
Fields:
              MT    Field   Offset                 Type VT     Attr            Value Name
00007ffcc6b385a0  4000283        8         System.Int32  1 instance                4 m_stringLength
00007ffcc6b36838  4000284        c          System.Char  1 instance               78 m_firstChar
00007ffcc6b359c0  4000288       e0        System.String  0   shared           static Empty

簡要分析擴容后的內存結構

此次執行的代碼為:

Dictionary<int, string> dic = new Dictionary<int, string>();
dic.Add(1, "xyxy");
dic.Add(7, "xyxy");
dic.Add(2, "xyxy");
dic.Add(4, "xyxy");
Console.Read();

同樣採取附加進程的方式分析這段代碼執行后的內存結構,本章節中忽略掉如何查找Dictionary變量地址的部分,直接分析buckets數組和entries數組的內容。

首先是buckets數組的內存結構:

0:000> !da -start 0 -details 0000019a471a54f8 
Name:        System.Int32[]
MethodTable: 00007ffcc6b38538
EEClass:     00007ffcc6ca60e8
Size:        52(0x34) bytes
Array:       Rank 1, Number of elements 7, Type Int32
Element Methodtable: 00007ffcc6b385a0
[0] 0000019a471a5508
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    1     m_value
[1] 0000019a471a550c
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    0     m_value
[2] 0000019a471a5510
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    2     m_value
[3] 0000019a471a5514
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                   -1     m_value
[4] 0000019a471a5518
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    3     m_value
[5] 0000019a471a551c
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                   -1     m_value
[6] 0000019a471a5520
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                   -1     m_value

然後是entries的內存結構:

0:000> !da -start 0 -details 00000237effb2fa8 
Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]][]
MethodTable: 00007ffa965135b8
EEClass:     00007ffa9662d1f0
Size:        192(0xc0) bytes
Array:       Rank 1, Number of elements 7, Type VALUETYPE
Element Methodtable: 00007ffa96513558
[0] 00000237effb2fb8
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    1     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    1     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[1] 00000237effb2fd0
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    7     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    7     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[2] 00000237effb2fe8
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    2     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    2     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[3] 00000237effb3000
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    4     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    4     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[4] 00000237effb3018
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value
[5] 00000237effb3030
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value
[6] 00000237effb3048
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value

從內存的結構來看,擴容后bucket數組中使用了下標為0、1、2和4這四個位置,entries中使用了0~3存儲了示例中添加的數據,符合前文中理論分析的結果,兩者相互之間具有良好的印證關係。

時間複雜度分析

時間複雜度表達的是數據結構操作數據的時候所消耗的時間隨着數據集規模的增長的變化趨勢。常用的指標有最好情況時間複雜度、最壞情況時間複雜度和均攤時間複雜度。那麼對於Dictionary<Tkey,TValue>來說,插入和查找過程中這些時間複雜度分別是什麼樣的呢?

最好情況時間複雜度:對於查找來說最好的是元素處於鏈表的頭部,查找效率不會隨着數據規模的增加而增加,因此該複雜度為常量階複雜度,即O(1);插入操作最理想的情況是數組中有空餘的空間,不需要進行擴容操作,此時時間複雜度也是常量階的,即O(1);

最壞情況時間複雜度:對於插入來說,比較耗時的操作場景是需要順着鏈表查找符合條件的元素,鏈表越長,查找時間越長(下文稱為場景一);而對於插入來說最壞的情況是數組長度不足,需要動態擴容並重新組織鏈表結構(下文稱為場景二);

場景一中時間複雜度隨着鏈表長度的增加而增加,但是Dictionary中規定鏈表的最大長度為100,如果有長度超過100的鏈表就需要擴容並調整鏈表結構,所以順着鏈表查找數據不會隨着數據規模的增長而增長,最大時間複雜度是固定的,因此時間複雜度還是常量階複雜度,即O(1);

場景二中時間複雜度隨着數組中元素的數量增加而增加,如果原來的數組元素為n個,那麼擴容時需要將這n個元素拷貝到新的數組中並計算其在新鏈表中的位置,因此該操作的時間複雜度是隨着數組的長度n的增加而增加的,屬於線性階時間複雜度,即O(n)。

綜合場景一和場景二的分析結果得出最壞情況時間複雜度出現在數據擴容過程中,時間複雜度為O(n)。

最好情況時間複雜度和最壞情況時間複雜度都過於極端,只能描述最好的情況和最壞的情況,那麼在使用過程中如何評價數據結構在大部分情況下的時間複雜度?通常對於複雜的數據結構可以使用均攤時間複雜度來評價這個指標。均攤時間複雜度適用於對於一個數據進行連續操作,大部分情況下時間複雜度都很低,只有個別情況下時間複雜度較高的場景。這些操作存在前後連貫性,這種情況下將較高的複雜度攤派到之前的操作中,一般均攤時間複雜度就相當於最好情況時間複雜度。

通過前面的分析可以看出Dictionary恰好就符合使用均攤時間複雜度分析的場景。以插入操作為例,假設預申請的entries數組長度為n,在第n+1次插入數據時必然會遇到一次數組擴容導致的時間消耗較高的場景。將這次較為複雜的操作的時間均攤到之前的n次操作后,每次操作時間的複雜度也是常量階的,因此Dictionary插入數據時均攤時間複雜度也是O(1)。

實踐建議

首先,Dictionary這種類型適合用於對於數據檢索有明顯目的性的場景,比如讀寫比例比較高的場景。其次,如果有大數據量的場景,最好能夠提前聲明容量,避免多次分配內存帶來的額外的時間和空間上的消耗。因為不進行擴容的場景,插入和查找效率都是常量階O(1),在引起擴容的情況下,時間複雜度是線性階O(n)。如果僅僅是為了存儲數據,使用Dictionary並不合適,因為它相對於List<T>具有更加複雜的數據結構,這樣會帶來額外的空間上面的消耗。雖然Dictionary<TKey,TValue>的TKey是個任意類型的,但是除非是對於判斷對象是否相等有特殊的要求,否則不建議直接使用自定義類作為Tkey。

總結

C#中的Dictionary<TKey,TValue>是藉助於散列函數構建的高性能數據結構,Dictionary解決散列衝突的方式是使用鏈表來保存散列值存在衝突的節點,俗稱拉鏈法。本文中通過圖文並茂的方式幫助理解Dictionary添加元素和擴容過程這兩個典型的應用場景,在理論分析之後使用windbg分析了內存中的實際結構,以此加深對於這種數據類型的深入理解。隨後在此基礎上分析了Dictionary的時間複雜度。Dictionary的最好情況時間複雜度是O(1),最壞情況複雜度是O(n),均攤時間複雜度是O(1),Dictionary在大多數情況下都是常量階時間複雜度,在內部數組自動擴容過程中會產生明顯的性能下降,因此在實際實踐過程中最好在聲明新對象的時候能夠預估容量,儘力避免數組自動擴容導致的性能下降。

參考資料

  • Dictionary<TKey,TValue>源代碼(.net framework4.8版本)
  • .NET中Dictionary<TKey, TValue>淺析
  • 解決hash衝突的三個方法
  • 算法複雜度分析(下):最好、最壞、平均、均攤等時間複雜度概述

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

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

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

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

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

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

香港環保署:去年及今年首9月 空氣中二噁英濃度沒異常

摘錄自2019年11月17日香港電台網站、頭條日報報導

港警近月大量使用催淚彈,其中催淚彈不時出現大量火光,有民眾關注高溫會產生二噁英。二噁英是常見的持久性環境污染物,能在環境中長存數十年,不受破壞,毒性極高,會導致生育和發育問題、破壞免疫系統、干擾荷爾蒙分泌以及致癌。

香港環保署在中西區和荃灣設監測站,監測空氣中二噁英的濃度,但上月數字至今未更新。香港環保署表示,去年及今年至9月的數據顯示,二噁英日均濃度是每立方米0.009至0.086皮克,並沒發現有異常情況出現。香港環保署表示,現在沒有空氣中二噁英的濃度指引,但過去3年香港取得的二噁英濃度,遠低於加拿大安大略省的二噁英每立方米0.1皮克,和日本每立方米0.6皮克的指標。

參選「啟德中及南」選區候選人梁咏欣表示,近日收到居民反映,指有大量懷疑含有「二噁英」的雜物,被棄置在距離啟德約400米的宏照道路政署地盤內。她要求當局提供環境調查報告及實地分析數據,以確保附近環境不被有害物質污染。

香港環保署稱已將上月份收集的二噁英樣本,送交政府化驗所作化學分析,一般需數星期,預期於本月(11月)底會完成,收到報告後會盡快公布。

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【【其他文章推薦】

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

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

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

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

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

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

印尼蘇門答臘象身首異處慘死 象牙遭盜採

摘錄自2019年11月8日自由時報屏東報導

印尼保育官員今天表示,1頭列為極危(critically endangered)物種的蘇門答臘象屍體被發現,牠的頭被砍下且象牙被拔走,顯然是一宗盜獵案件。

蘇門答臘島廖內省(Riau)一名農園工人昨天發現這頭40歲公象腐爛的屍體。當地保育機關主管蘇哈尤諾(Suharyono)在聲明中說:「大象的頭被砍下,切斷的象鼻落在距離象身1公尺處。」當局正在追查犯案人士。

森林濫伐造成蘇門答臘象的天然棲地縮減,導致牠們和人類的衝突加劇。另一方面,蘇門答臘象象牙在野生動物黑市交易中價值連城。

去年在印尼亞齊省(Aceh)也發現一具顯然被毒死的蘇門答臘象屍體,當時牠的象牙也不見。印尼環境部估計,境內野生蘇門答臘象只剩不到2000頭。

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

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

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

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

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

新北清潔公司,居家、辦公、裝潢細清專業服務

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

無視巴黎氣候協定 全球化石燃料產量遠高於限制

摘錄自2019年11月20日中央通訊社報導

聯合國和頂尖研究團體今天(20日)發布報告警告,全球已規劃或準備進行的石油、天然氣和煤炭產量,將遠遠超越抑制全球暖化讓地球維持適合人居所需的產量目標。

聯合國環境規劃署(UN Environment Programme)和4個氣候變遷研究中心聯合發布報告指出,全球預計生產的化石燃料總量,較為了讓地表溫度較工業革命前水準升高不超過攝氏2度所容許的燃燒量,超出達50%。

若將地表升溫幅度限制在攝氏1.5度,則計劃中的化石燃料產量將較容許數量超出1倍多。2015年達成的巴黎氣候協定,要求將全球暖化限制在遠低於攝氏2度水準,可能的話僅升溫攝氏1.5度。

儘管截至目前全球僅升溫攝氏1度,但全世界已出現逐漸增強的致命熱浪、洪災和超級風暴,而超級風暴因海平面加速上升而破壞力更強大。研究人員警告,煤炭、石油和天然氣供應的「過度投資」,與未來數十年必須大幅縮減溫室氣體排放的目標,兩者直接相衝突。

聯合國去年發布的報告斷定,若要抑制地表升溫僅攝氏1.5度,則全球二氧化碳排放必須在2030年底前減少45%,並於2050年底前達到「淨零排放」。

斯德哥爾摩環境研究所(Stockholm Environment Institute)美國中心主任賴薩魯斯(Michael Lazarus)表示:「我們首次展現,巴黎(氣候協定的)溫度目標,和各國煤炭、石油和天然氣的生產計畫及政策,兩者間落差有多巨大。」

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

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

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

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

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

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

前端工程師必備:從瀏覽器的渲染到性能優化

摘要:本文主要講談及瀏覽器的渲染原理、流程以及相關的性能問題。

問題前瞻

1. 為什麼css需要放在頭部?
2. js為什麼要放在body後面?
3. 圖片的加載和渲染會阻塞頁面DOM構建嗎?
4. dom解析完才出現頁面嗎?
5. 首屏時間根據什麼來判定?

瀏覽器渲染

1.瀏覽器渲染圖解

[來自google開發者文檔]

瀏覽器渲染頁面主要經歷了下面的步驟:

1.處理 HTML 標記並構建 DOM 樹。
2.處理 CSS 標記並構建 CSSOM 樹。
3.將 DOM 與 CSSOM 合併成一個渲染樹。
4.根據渲染樹來布局,以計算每個節點的幾何信息。
5.將各個節點繪製到屏幕上。

為構建渲染樹,瀏覽器大體上完成了下列工作:

從 DOM 樹的根節點開始遍歷每個可見節點。

某些節點不可見(例如腳本標記、元標記等),因為它們不會體現在渲染輸出中,所以會被忽略。
某些節點通過 CSS 隱藏,因此在渲染樹中也會被忽略,例如,上例中的 span 節點---不會出現在渲染樹中,---因為有一個顯式規則在該節點上設置了“display: none”屬性。
對於每個可見節點,為其找到適配的 CSSOM 規則並應用它們。

發射可見節點,連同其內容和計算的樣式。

根據以上解析,DOM樹和CSSOM樹的構建對於頁面性能有非常大的影響,沒有DOM樹,頁面基本的標籤塊都沒有,沒有樣式,頁面也基本是空白的。所以具體css的解析規則是什麼?js是怎麼影響頁面渲染的?了解了這些,我們才能有的放矢,對頁面性能進行優化。

2.css解析規則

1
<div id="div1">
2
<div class="a">
3
<div class="b">
4
...
5
</div>
6
<div class="c">
7
<div class="d">
8
...
9
</div>
10
<div class="e">
11
...
12
</div>
13
</div>
14
</div>
15
<div class="f">
16
<div class="c">
17
<div class="d">
18
...
19
</div>
20
</div>
21
</div>
22
</div>

 

1
#div1 .c .d {}
2
.f .c .d {}
3
.a .c .e {}
4
#div1 .f {}
5
.c .d{}

從左向右的匹配規則

從右向左的匹配規則

如果css從左向右解析,意味着我們需要遍歷更多的節點。不管樣式規則寫得多細緻,每一個dom結點仍然需要遍歷,因為整個style rules還會有其它公共樣式影響。如果從右向左解析,因為子元素只有一個父元素,所以能夠很快定位出當前dom符不符合樣式規則。

3.js加載和執行機制

首先明確一點,我們可以通過js去修改網頁的內容,樣式和交互等,這一意味着js會影響頁面的dom結構,如果js和dom構建并行執行,那麼很容易會出現衝突,所以js在執行時必然會阻塞dom和cssom的構建過程,不論是外部js還是內聯腳本。

js的位置是否影響dom解析?

首先我們為什麼提倡把js放在body標籤的後面去加載,因為從demo上看無論是放在head還是放在body后加載js,頁面domcontentload的時間都是一樣的:

我們從圖中可以看出js的加載和執行是阻塞dom解析的,但是因為頁面並不是一次就渲染完成,所以我們需要做的是盡量讓用戶看到首屏的部分被渲染出來,js放在頭部,則頁面的內容區域還沒有解析到就被阻塞了,導致用戶看到的是白屏,而js放在body後面,儘管此時頁面dom仍然沒有解析完成,但是已經渲染出一部分樓層了,這也是為什麼我們比較看重頁面的首屏時間。

只有DOM和CSSOM樹構建好后併合並成渲染樹才能開始繪製頁面圖形,那是不是把整個DOM樹和CSSOM樹構建好后才能開始繪製頁面?這顯然是不符合我們平時訪問頁面的認知的,實際上:

為達到更好的用戶體驗,呈現引擎會力求儘快將內容显示在屏幕上。它不必等到整個 HTML 文檔解析完畢之後,就會開始構建呈現樹和設置布局。在不斷接收和處理來自網絡的其餘內容的同時,呈現引擎會將部分內容解析並显示出來。

具體瀏覽器什麼時候進行首次繪製?可以查看本文對瀏覽器首次渲染時間點的探究。

4.圖片的加載和渲染機制

首先我們解答一下上面的問題:圖片的加載與渲染會不會阻塞頁面渲染?答案是圖片的加載和渲染不會影響頁面的渲染。

那麼標籤中的圖片和樣式中的圖片的加載和渲染時間是什麼樣的呢?

解析HTML【遇到標籤加載圖片】 —> 構建DOM樹
加載樣式 —> 解析樣式【遇到背景圖片鏈接不加載】 —> 構建樣式規則樹
加載javascript —> 執行javascript代碼
把DOM樹和樣式規則樹匹配構建渲染樹【遍歷DOM樹時加載對應樣式規則上的背景圖片】
計算元素位置進行布局
繪製【開始渲染圖片】

當然把DOM樹和樣式規則樹匹配構建渲染樹時,只會把可見元素和它對應的樣式規則結合一起產出到渲染樹,這就意味有不可見元素,當匹配DOM樹和樣式規則樹時,若發現一個元素的對應的樣式規則上有display:none,瀏覽器會認為該元素是不可見的,因此不會把該元素產出到渲染樹上。

性能優化

css優化

1.盡量減少層級

1
#div p.class {
2
color: red;
3
}
4

5
.class {
6
color: red;
7
}

層級減少,意味者匹配時遍歷的dom就少。
關於less嵌套的書寫規範也基於這個道理。

2.使用類選擇器而不是標籤選擇器

減少匹配次數

3.按需加載css

1
(function(){
2
window.gConfig = window.gConfig || {};
3
window.gConfig.isMobile = /iPhone|iPad|iPod|Android/i.test(navigator.userAgent);
4
var hClassName;
5
if(window.gConfig.isMobile){
6
hClassName = ' phone';
7

8
document.write('<link rel="stylesheet" href="https://res.hc-cdn.com/cpage-pep-discount-area-v6/2.0.24/m/index.css" />');
9
document.write('<link rel="preload" href="//res.hc-cdn.com/cpage-pep-discount-area-v6/2.0.24/m/index.js" crossorigin="anonymous" as="script" />');
10

11
}else{
12
hClassName = ' pc';
13

14
document.write('<link rel="stylesheet" href="https://res.hc-cdn.com/cpage-pep-discount-area-v6/2.0.24/pc/index.css" />');
15
document.write('<link rel="preload" href="//res.hc-cdn.com/cpage-pep-discount-area-v6/2.0.24/pc/index.js" crossorigin="anonymous" as="script" />');
16

17
}
18
var root = document.documentElement;
19
root.className += hClassName ;
20

21
})();

async 與 defer

[來自https://www.growingwiththeweb.com/2014/02/async-vs-defer-attributes.html]

使用

  • 如果腳本是模塊化的並且不依賴於任何腳本,請使用async。
  • 如果該腳本依賴於另一個腳本或由另一個腳本所依賴,則使用defer。

減少資源請求

瀏覽器的併發數量有限,所以為了減少瀏覽器因為優先加載很多不必要資源,以及網絡請求和響應時間帶來的頁面渲染阻塞時間,我們首先應該想到的是減少頁面加載的資源,能夠盡量用壓縮合併,懶加載等方法減少頁面的資源請求。

延遲加載圖像

儘管圖片的加載和渲染不會影響頁面渲染,但是為了盡可能地優先展示首屏圖片和減少資源請求數量,我們需要對圖片做懶加載。

1
document.addEventListener("DOMContentLoaded", function() {
2
let lazyImages = [].slice.call(document.querySelectorAll("img.lazy"));
3
let active = false;
4

5
const lazyLoad = function() {
6
if (active === false) {
7
active = true;
8

9
setTimeout(function() {
10
lazyImages.forEach(function(lazyImage) {
11
if ((lazyImage.getBoundingClientRect().top <= window.innerHeight && lazyImage.getBoundingClientRect().bottom >= 0) && getComputedStyle(lazyImage).display !== "none") {
12
lazyImage.src = lazyImage.dataset.src;
13
lazyImage.srcset = lazyImage.dataset.srcset;
14
lazyImage.classList.remove("lazy");
15

16
lazyImages = lazyImages.filter(function(image) {
17
return image !== lazyImage;
18
});
19

20
if (lazyImages.length === 0) {
21
document.removeEventListener("scroll", lazyLoad);
22
window.removeEventListener("resize", lazyLoad);
23
window.removeEventListener("orientationchange", lazyLoad);
24
}
25
}
26
});
27

28
active = false;
29
}, 200);
30
}
31
};
32

33
document.addEventListener("scroll", lazyLoad);
34
window.addEventListener("resize", lazyLoad);
35
window.addEventListener("orientationchange", lazyLoad);
36
});

詳情參考延遲加載圖像和視頻

大促活動實踐

2.1 懶加載與異步加載

懶加載與異步加載是大促活動性能優化的主要手段,直白的說就是把用戶不需要或者不會立即看到的頁面數據與內容全都挪到頁面首屏渲染完成之後去加載,極限減小頁面首屏渲染的數據加載量與js,css執行帶來的性能損耗。

2.1.1 導航下拉的異步加載

導航的下拉內容是一塊結構非常複雜的html片段,如果直接加載,瀏覽器渲染的時間會拖慢頁面整體的加載時間:

所有我們需要通過異步加載方式來獲取這段html片段,等頁面首屏渲染結束后再添加到頁面上,大致的代碼如下:

1
$.ajax({
2
url: url, async: false, timeout: 10000,
3
success: function (data) {
4
container.innerHTML = data;
5
var appendHtml = $('<div class="footer-wrapper">' + container.querySelector('#footer').innerHTML + '</div>');
6
var tempHtml = '<div style="display:none;">' + '<script type="text/html" id="header-lazyload-html-drop" class="header-lazyload-html" data-holder="#holder-drop">' + appendHtml.find('#header-lazyload-html-drop').html() + '<\/script><script type="text/html" id="header-lazyload-html-mbnav" class="header-lazyload-html" data-holder="#holder-mbnav">' + appendHtml.find('#header-lazyload-html-mbnav').html() + '<\/script></div>';
7
$('#footer').append(tempHtml);
8
feloader.onLoad(function () {
9
feloader.use('@cloud/common-resource/header', function () {
10
});
11
$('#footer').css('display', 'block');
12
});
13
},
14
error: function (XMLHttpRequest, textStatus, errorThrown) {
15
console.log(XMLHttpRequest.status, XMLHttpRequest.readyState, textStatus);
16
},
17
});

2.1.2 圖片懶加載

官網的cui套件中已經有lazyload的插件支持圖片懶加載,使用方法頁非常簡單:

1
<div class="list">
2
<img class="lazyload" data-src="http://www.placehold.it/375x200/eee/444/1" src="佔位圖片URL" />
3
<img class="lazyload" data-src="http://www.placehold.it/375x200/eee/444/2" src="佔位圖片URL" />
4
<img class="lazyload" data-src="http://www.placehold.it/375x200/eee/444/3" src="佔位圖片URL" />
5
<div class="lazyload" data-src="http://www.placehold.it/375x200/eee/444/3"></div>
6
...
7
</div>

從代碼我們差不多可以猜出圖片懶加載的原理,其實就是我們通過覆蓋img標籤src屬性,使得img標籤開始加載時由於沒有src的具體圖片地址而不去加載圖片,等到重要資源加載完之後,通過監聽onload的時間或者滾動條的滾動時機再去重寫對應標籤的src值來達到圖片懶加載:

1
/**
2
* load image
3
* @param {HTMLElement} el - the image element
4
* @private
5
*/
6
_load(el) {
7
let source = el.getAttribute(ATTR_IMAGE_URL);
8
if (source) {
9
let processor = this._config.processor;
10
if (processor) {
11
source = processor(source, el);
12
}
13

14
el.addEventListener('load', () => {
15
el.classList.remove(CLASSNAME);
16
});
17
// 判斷是否是什麼元素
18
if (el.tagName === 'IMG') {
19
el.src = source;
20
} else {
21
// 判斷source是不是一個類名,如果是類名的話,則加到class裏面去
22
if (/^[A-Za-z0-9_-]+$/.test(source)) {
23
el.classList.add(source);
24
} else {
25
let styles = el.getAttribute('style') || '';
26
styles += `;background-image: url(${source});`;
27
el.setAttribute('style', styles);
28
el.style.backgroundImage = source; // = `background-image: url(${source});`;
29
}
30
}
31

32
el.removeAttribute(ATTR_IMAGE_URL);
33
}
34
}

具體的插件代碼大家可以查看https://git.huawei.com/cnpm/lazyload

同時官網的頁腳部分也採用了採用其它的加載方式也實現了懶加載的效果,頁腳的圖片都在css中引用,想要延遲加載頁腳圖片就需要延遲加載頁腳的css,但是延遲加載css造成的後果就是頁面加載的一瞬間頁腳會因為樣式確實而显示錯亂,所以我們可以在css樣式加載前強勢隱藏掉頁腳部分,等css加載完成后,頁腳dom自帶的display:block會自動显示頁腳。(==因為頁腳的seo特性沒有對其進行懶加載==)

2.1.3 樓層內容的懶加載

基於xtpl自帶的懶加載能力,配合pep定製頁面模板的邏輯,我們可以實現html的懶加載。在頁面初次渲染的時候,只有每個樓層的大體框架和標題等關鍵信息,如果需要的話可以給默認圖片等佔位,或設置最小高度佔位,防止錨點定位失效。
當頁面滾動到該樓層的位置,js代碼方會執行,在初始化函數中,對該樓層的html進行加載,渲染,實現樓層圖片和html的懶加載,減少了首屏時間。
具體代碼如下:

1
<div class="nov-c6-cards j-content">
2
</div>

 

1
public render(){
2
this.$el.find('.j-content').html(new Xtemplate(tpl).render(mockData))
3
...
4
}

2.1.4 套餐數據懶加載

套餐數據的加載一直以來都是令人頭疼的,本次雙十一對於套餐腳本也做了優化,不僅對數據進行了緩存,同時也可以在指定的範圍進行套餐數據的渲染——和上述所說的樓層懶加載配合,可以做到未展示的樓層,套餐數據不請求,下拉框不渲染,詢價接口不調用,在首屏不出現大量套餐的情況下,可以大大提升首屏加載的性能。

2.2.資源整合

2.2.1.頁頭頁尾資源統一維護

基礎模板的優化涉及到資源的合併,壓縮與異步加載,dom的延遲加載和圖片的懶加載。首先我們給出官網基礎模板引用的一部分js資源的表格:

這部分js存在問題是分散在pep的各個資產庫路徑維護,有些壓縮了,有些沒有壓縮,js的加載也基本是順序執行,所以我們對這個部分的js和css資源進行了一個整合,進行的操作是遷移,合併,壓縮。

建立common-resource倉庫去統一維護管理頁頭頁腳及公共資源代碼。

2.2.2.合併加載方式相同的基礎功能js並壓縮

common.js

1
import './common/js/AGrid';
2
import './common/js/jquery.base64';
3
import './common/js/lang-tips';
4
import './common/js/setLocaleCookie';
5
import './common/js/pepDialog';

如上面代碼,將官網中用的分散的基礎功能js合併成一個common.js,經過伏羲流水線發布,cui套件會自動將js壓縮,這樣做的效果當然是減少官網頁面請求資源數,減小資源大小。

2.2.3.資源異步加載

觀察2.2.1中的表格可以發現,官網大部分js都是放在頭部或者是body后順序加載的,這些資源的加載時間必定是在DOMOnLoad之前

這些js都是會阻塞頁面的渲染,導致頁面首屏加載變慢,我們需要做的就是通過之前頭尾資源的整理得出哪些資源是可以在onload之後去加載的,這些我們就可以把頁面加載時不需要執行的js和css全部移到頁面渲染完成後去加載,少了這部分的js邏輯執行時的阻塞,頁面首屏渲染的時間也會大大降低。

通過cui套件中的feloader插件,我們可以比較便捷的控制js和css加載的時機:

1
feloader.onLoad(function () {
2
feloader.use([
3
'@cloud/link-to/index',
4
'@cloud/common-resource/uba',
5
'@cloud/common-resource/footer',
6
'@cloud/common-resource/header',
7
'@cloud/common-resource/common',
8
'@cloud/common-resource/prompt.css',
9
'@cloud/common-resource/footer.css',
10
]);
11
});

下圖可以明顯看到js的加載都轉移到onload之後了:

2.2.4 圖片壓縮

除了對設計給出的圖片有壓縮要求外,我們還通過對一部分不常更新的小圖標圖片進行base64編碼來減少頁面的圖片請求數量。

2.3預解析與預加載

除了延遲加載外,基礎模板還進行了諸如dns預解析,資源預加載的手段來提前解析dns和加載頁面資源。

2.3.1 DNS 預解析

當用戶訪問過官網頁面后,DNS預解析能夠使用戶在訪問雙十一活動頁之前提前進行DNS解析,從而減少雙十一活動頁面的dns解析時間,提高頁面的訪問性能,其實寫法也很簡單:

1
<link rel="dns-prefetch" href="//res.hc-cdn.com">
2
<link rel="dns-prefetch" href="//res-static1.huaweicloud.com">
3
<link rel="dns-prefetch" href="//res-static2.huaweicloud.com">
4
<link rel="dns-prefetch" href="//res-static3.huaweicloud.com">

2.3.2 preload 預加載

活動頁的部分js還使用了preload預加載的方式來提升頁面加載性能,preload的為什麼可以達到這種效果,我們需要看下面這段摘錄:

Preloader 簡介

HTML 解析器在創建 DOM 時如果碰上同步腳本(synchronous script),解析器會停止創建 DOM,轉而去執行腳本。所以,如果資源的獲取只發生在解析器創建 DOM時,同步腳本的介入將使網絡處於空置狀態,尤其是對外部腳本資源來說,當然,頁面內的腳本有時也會導致延遲。

預加載器(Preloader)的出現就是為了優化這個過程,預加載器通過分析瀏覽器對 HTML 文檔的早期解析結果(這一階段叫做“令牌化(tokenization)”),找到可能包含資源的標籤(tag),並將這些資源的 URL 收集起來。令牌化階段的輸出將會送到真正的 HTML 解析器手中,而收集起來的資源 URLs 會和資源類型一起被送到讀取器(fetcher)手中,讀取器會根據這些資源對頁面加載速度的影響進行有次序地加載。

基於以上原理,我們對官網相對重要的js資源進行preload預加載,以使得瀏覽器可以儘快地加載頁面所需的重要資源。

1
<link rel="preload" href="//res.hc-cdn.com/cnpm-feloader/1.0.6/feloader.js" as="script"/>
2
<link rel="preload" href="//polyfill.alicdn.com/polyfill.min.js?features=default,es6" as="script"/>
3
<link rel="preload" href="https://res-static3.huaweicloud.com/content/dam/cloudbu-site/archive/commons/3rdlib/jquery/jquery-1.12.4.min.js" as="script"/>
4
<link rel="preload" href="//res.hc-cdn.com/cnpm-wpk-reporter/1.0.6/wpk-performance.js" as="script"/>
5

6
<link rel="preload" href="//res.hc-cdn.com/cpage-pep-2019nov-promotion/1.1.15/components/activity-banner/images/banner_mb.jpg" as="image" media="(max-width: 767px)">

優化效果

3.總結

前端性能優化的方法手段並不僅限於文章陳述,官網前端團隊還會在前端性能優化的道路上學習更多,探索更多,將華為雲官網頁面的加載性能做到極致!

 

點擊關注,第一時間了解華為雲新鮮技術~

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

【【其他文章推薦】

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

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

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

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

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

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

痞子衡嵌入式:利用i.MXRT1xxx系列ROM提供的FlexSPI driver API可輕鬆IAP

  大家好,我是痞子衡,是正經搞技術的痞子。今天痞子衡給大家介紹的是i.MXRT系列ROM中的FlexSPI驅動API實現IAP

  痞子衡的技術交流群里經常有群友提問: i.MXRT中的FlexSPI驅動API到底怎麼用啊?這個問題已經出現過好幾次了,本來痞子衡不打算專門為這個寫文章的,因為這部分內容在芯片手冊System Boot章節里的最後一節ROM APIs里其實介紹得非常詳細了,但是既然還是有不少朋友在問這個,看起來手冊里的內容藏得有點深,這麼好的東西被埋沒太可惜了,那麼今天痞子衡就跟大家再認真聊一聊。

一、ROM API簡介

1.1、API產生背景

  i.MXRT系列都是Flashless(沒有內置NVM)的芯片,所以BootROM必不可少。BootROM是個很特殊的東西,本質上它是一個完整的C代碼寫成的系統級App,這個系統級App專門用於從外部存儲器中加載用戶級App執行。簡單地說,BootROM就是PC機里的BIOS。

  BootROM代碼是存放在專門的ROM區域的(前面講i.MXRT系列沒有內置NVM,其實不夠準確,其實是有內部ROM空間的,只不過這個ROM區域用戶無法下載程序使用,因此等效於沒有NVM),ROM顧名思義Readonly,所以BootROM代碼只能隨着芯片一起Tapeout,代碼無法更改(其實也有ROM patch機制,以後再介紹)。

  ROM空間其實挺大的,從64KB到512KB不等,因芯片啟動功能複雜程度而異。下圖是i.MXRT1050系列的BootROM所佔空間,ROM起始地址是0x200000(起始地址在i.MXRT上都一樣),ROM大小為96KB(這是標準啟動功能所要的代碼長度。在i.MXRT1010上是64KB – 精簡啟動功能,在i.MXRT1170上是256KB – 複雜啟動功能)。

  BootROM代碼其實並沒有佔滿全部ROM空間,總有些剩餘空間(因為工藝原因,ROM空間都是8/16KB倍數),這部分空間浪費了着實可惜。如果我們能把SDK里的一些常用模塊驅動(比如WDOG)順便放進去供用戶調用,既充分利用ROM空間,也為用戶節省Flash空間,豈不是一舉兩得。此外,BootROM功能代碼中也有一些現成模塊驅動(比如各種啟動設備存儲器驅動接口)可以一併導出,這便是API由來。

1.2、API設計實現

  有了API想法,現在就是設計實現了。其實i.MXRT ROM API設計並不是重頭開始的,在這個MCU系列被主推之前,Kinetis系列也曾當紅過,Kinetis中也內置了ROM,並且提供了ROM API,痞子衡之前為此寫過一篇文章 《飛思卡爾Kinetis系列MCU啟動那些事(11)- KBOOT特性(ROM API)》。 i.MXRT ROM API設計思路完全復用了Kinetis ROM API的設計。

  API說到底就是一個個功能函數的結合,我們知道工程代碼都是由鏈接器自動分配的,因此每個函數實際鏈接地址是無法預期的(在鏈接文件里給每個函數分配固定地址鏈接這種方法不在考慮範疇,當函數數量眾多時,這種方法太麻煩),業界上一個比較通用的做法是定義成員是函數指針的結構體,i.MXRT ROM API就是採用的業界通用方式,下面bootloader_api_entry_t便是i.MXRT1060中API原型,g_bootloaderTree就是實例:

typedef struct
{
    const uint32_t version;
    const char *copyright;
    void (*runBootloader)(void *arg);
    const hab_rvt_t *habDriver;

    //!< FlexSPI NOR Flash API
    const flexspi_nor_driver_interface_t *flexSpiNorDriver;

    const nand_ecc_driver_interface_t *nandEccDriver;
    const clock_driver_interface_t *clockDriver;
    const rtwdog_driver_interface_t *rtwdogDriver;
    const wdog_driver_interface_t *wdogDriver;
    const stdlib_driver_interface_t *stdlibDriver;
} bootloader_api_entry_t;

// Bootloader API Tree
const bootloader_api_entry_t g_bootloaderTree = {
    .copyright = "Copyright 2018 NXP",
    .version = MAKE_VERSION(1, 0, 0),
    .runBootloader = run_bootloader,
    .habDriver = &hab_rvt,

    .flexSpiNorDriver = &g_flexspiNorDriverInterface,

    .nandEccDriver = &g_nandEccDriverInterface,
    .clockDriver = &g_clockDriverInterface,
    .rtwdogDriver = &g_rtwdogDriverInterface,
    .wdogDriver = &g_wdogDriverInterface,
    .stdlibDriver = &g_stdlibDriverInterface,
};

  從上面代碼我們可以看出,bootloader_api_entry_t成員好像並不是函數指針,是的,為了分組方便,bootloader_api_entry_t成員還是一個個結構體,它的這些結構體成員(比如flexspi_nor_driver_interface_t)才是真正包含一個個函數指針的結構體。API從功能來分一共提供了7類:HAB、FlexSPI NOR、NAND ECC、Clock、RT-WDOG、WDOG、stdlib。

  設計到這裏,我們通過g_bootloaderTree結構體常量就可以調用所有的API函數了,最後剩下的問題就是如何在ROM里找一個確定的地方保存隨機鏈接的g_bootloaderTree地址(只要4字節即可)。是的,還是Kinetis ROM API用的那個巧妙的方法,下面是BootROM工程的startup文件(Keil版),BootROM將g_bootloaderTree的地址放到了中斷向量表第8個向量的位置處(該向量為ARM Cortex-M未定義的系統向量),因此0x20001c處開始的4bytes便固定是g_bootloaderTree地址。

                PRESERVE8
                THUMB

; Vector Table Mapped to Address 0 at Reset

                AREA    RESET, DATA, READONLY
                EXPORT  __Vectors
                EXPORT  __Vectors_End
                EXPORT  __Vectors_Size
                IMPORT  |Image$$ARM_LIB_STACK$$ZI$$Limit|
                IMPORT  g_bootloaderTree

__Vectors       DCD     |Image$$ARM_LIB_STACK$$ZI$$Limit|
                DCD     Reset_Handler
                DCD     DefaultISR
                DCD     HardFault_Handler
                DCD     DefaultISR
                DCD     DefaultISR
                DCD     DefaultISR
                DCD     g_bootloaderTree
                DCD     0
                DCD     0
                DCD     0
                DCD     SVC_Handler
                DCD     DefaultISR
                DCD     0
                DCD     DefaultISR
                DCD     DefaultISR
		        ;; ...

1.3、API調用方法

  了解了前面介紹的ROM API產生背景與設計實現,它的調用方法就非常簡單了,以WDOG API調用為例,只需要如下簡單3句代碼:

// 找到API根結構體
#define g_bootloaderTree (*(bootloader_api_entry_t **)0x0020001c)
// 定義WDOG模塊配置變量
wdog_config_t config;
// 調用API中WDOG_Init()
g_bootloaderTree->wdogDriver->WDOG_Init(WDOG1, config);

1.4、支持API的i.MXRT型號

  截止目前,i.MXRT1xxx系列一共出了7款型號,但並不是每個型號都開放了ROM API,最早誕生的三款型號(105x、1021、1015)就並沒有開放API(不是沒有API,而是沒有嚴格測試),其餘型號都支持API。

RT芯片型號 是否支持ROM API
i.MXRT117x 支持
i.MXRT1064 支持
i.MXRT106x 支持
i.MXRT105x 未開放
i.MXRT1021 未開放
i.MXRT1015 未開放
i.MXRT1011 支持

二、API之FlexSPI驅動

  前面鋪墊了太多ROM API設計細節,到這裏才算進入正題,本文其實主要是要跟大家聊如何利用API里的FlexSPI NOR驅動實現IAP。痞子衡在前面鋪墊那麼多的原因其實主要是想告訴大家,API里的每個驅動都是經過完善測試的,尤其是這個FlexSPI NOR驅動,更是經過了千錘百鍊,無論是易用性、運行穩定性還是Flash型號的支持度上都是首屈一指的。

  對於JESD216標準下的串行SPI接口Flash驅動,大家知道更多的可能是RT-Thread技術總監朱天龍大神的開源 SFUD 項目,但痞子衡告訴你,i.MXRT ROM API里的這個串行Flash驅動也毫不遜色(持續維護與優化了近6年,歷經多款MCU的ROM,是真正的產品級),只是不如開源項目那麼知名,不過它的源代碼也是開源在SDK里的(\SDK\middleware\mcu-boot\src\drivers\flexspi_nor),BSD-3-Clause許可證。

2.1 FlexSPI驅動原型

  flexspi_nor_driver_interface_t便是FlexSPI NOR驅動的原型,尋常的讀寫擦功能自然不在話下,除此以外,API裏面還有一個非常厲害的xfer()函數,這個函數可以用來實現其他定製化的Flash操作函數,有興趣的朋友可以進一步去研究。

typedef struct
{
    uint32_t version;
    status_t (*init)(uint32_t instance, flexspi_nor_config_t *config);
    status_t (*program)(uint32_t instance, flexspi_nor_config_t *config, uint32_t dst_addr, const uint32_t *src);
    status_t (*erase_all)(uint32_t instance, flexspi_nor_config_t *config);
    status_t (*erase)(uint32_t instance, flexspi_nor_config_t *config, uint32_t start, uint32_t lengthInBytes);
    status_t (*read)(uint32_t instance, flexspi_nor_config_t *config, uint32_t *dst, uint32_t addr, uint32_t lengthInBytes);
    void (*clear_cache)(uint32_t instance);
    status_t (*xfer)(uint32_t instance, flexspi_xfer_t *xfer);
    status_t (*update_lut)(uint32_t instance, uint32_t seqIndex, const uint32_t *lutBase, uint32_t seqNumber);
    status_t (*get_config)(uint32_t instance, flexspi_nor_config_t *config, serial_nor_config_option_t *option);
} flexspi_nor_driver_interface_t;

2.2 FlexSPI驅動使用示例

  FlexSPI驅動使用基本三步走,先調用get_config()獲取完整FlexSPI模塊配置,然後調用init()函數去初始化FlexSPI以及訪問Flash獲取SFDP表信息,最後就是調用Flash操作函數(比如erase())。

// 找到API根結構體
#define g_bootloaderTree (*(bootloader_api_entry_t **)0x0020001c)

// 定義FlexSPI, Flash配置變量
flexspi_nor_config_t config;
serial_nor_config_option_t option;
option.option0.U = 0xC0000008; // QuadSPI NOR, Frequency: 133MHz
uint32_t instance = 0;

// 調用API中get_config()函數
g_bootloaderTree->flexSpiNorDriver->get_config(instance, &config, &option);
// 調用API中init()函數
g_bootloaderTree->flexSpiNorDriver->init(instance, &config);
// 調用API中erase()函數
g_bootloaderTree->flexSpiNorDriver->erase(instance, &config, 0x40000, 0x1000);

2.3 FlexSPI驅動特點

  因為FlexSPI NOR驅動API來自於BootROM,因此其在使用上有一些小小的限制,也算是其特點吧。FlexSPI驅動API里並沒有提供Flash連接的Pinmux配置,其Pinmux配置已經寫死在init()函數中,就是ROM支持啟動的FlexSPI PORTA上的那些pin(片選是SS0)。

  在上面的使用示例代碼中,你會看到option.option0.U = 0xC0000008代碼,這算是FlexSPI驅動最大的特點了,這是一個簡化的option配置word(其原型可在芯片手冊里找到),通過這個簡化的option,用戶可以輕鬆配置來訪問不同廠商的Flash,下面是常用的Flash模式配置值。

• QuadSPI NOR - Quad SDR Read: option0 = 0xc0000008 (133MHz)
• QuadSPI NOR - Quad DDR Read: option0 = 0xc0100003 (60MHz)
• HyperFLASH 1V8: option0 = 0xc0233009 (166MHz)
• HyperFLASH 3V0: option0 = 0xc0333006 (100MHz)
• MXIC OPI DDR (OPI DDR enabled by default): option=0xc0433008(133MHz)
• Micron Octal DDR: option0=0xc0600006 (100MHz)
• Micron OPI DDR: option0=0xc0603008 (133MHz), SPI->OPI DDR
• Micron OPI DDR (DDR read enabled by default): option0 = 0xc0633008 (133MHz)
• Adesto OPI DDR: option0=0xc0803008(133MHz)

2.4 FlexSPI驅動用作IAP

  IAP其實就是在App中實現Flash擦寫,單純從技術上來說並不是一個很難的東西。但i.MXRT上很多時候App代碼本身也在同一片Flash里執行(也叫XIP),而市面上很多Flash都是不支持RWW(Read-While-Write)的,這就導致一個問題,當你調用Flash操作函數去擦寫Flash時,CPU又需要繼續去Flash獲取指令,違反了RWW,因此你只能把Flash相關操作函數全部放在RAM中去執行(這涉及分散加載了,對於初級嵌入式用戶來說稍微有點難)。

  現在我們有了ROM API,FlexSPI驅動代碼體全部都在ROM空間里,並不佔用Flash空間,因此不存在RWW問題,真是天然為IAP而生,再也不用再管什麼分散加載這麼麻煩的事了。

三、FlexSPI API業界應用

  最後再介紹一下i.MXRT FlexSPI API在業界的應用,這個API其實並不小眾,目前已被主流IDE和調試工具用作i.MXRT Flash下載算法。

3.1 用於IAR下載算法

  如果你的IAR版本夠新,能夠支持i.MXRT1060等型號,隨便打開一個i.MXRT1060 SDK工程,在工程Option里找到Debugger,然後進入Flashloader配置,你會看到頁面里有Extra parameters一欄,在下面的解釋里有這個參數的示例,它就是前面2.3節里介紹的option0。有了這種方式設計的Flash下載算法,你再也不用手動更新下載算法文件去支持不同的Flash了,改參數就行了。

3.2 用於J-Link下載算法

  目前最新的Jlink驅動里的下載算法也是基於ROM API的,痞子衡有一個開源項目,收集了i.MXRT所有型號的下載算法源代碼工程,其中jlink算法是最全的,其他IDE算法還在陸續完善中。

https://github.com/JayHeng/imxrt-tool-flash-algo

  至此,i.MXRT系列ROM中的FlexSPI驅動API實現IAP痞子衡便介紹完畢了,掌聲在哪裡~~~

歡迎訂閱

文章會同時發布到我的 博客園主頁、CSDN主頁、微信公眾號 平台上。

微信搜索”痞子衡嵌入式“或者掃描下面二維碼,就可以在手機上第一時間看了哦。

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

【其他文章推薦】

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

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

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

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

新北清潔公司,居家、辦公、裝潢細清專業服務

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

寫給大忙人看的死鎖全詳解

前言

計算機系統中有很多獨佔性的資源,在同一時刻只能每個資源只能由一個進程使用,我們之前經常提到過打印機,這就是一個獨佔性的資源,同一時刻不能有兩個打印機同時輸出結果,否則會引起文件系統的癱瘓。所以,操作系統具有授權一個進程單獨訪問資源的能力。

兩個進程獨佔性的訪問某個資源,從而等待另外一個資源的執行結果,會導致兩個進程都被阻塞,並且兩個進程都不會釋放各自的資源,這種情況就是 死鎖(deadlock)

死鎖可以發生在任何層面,在不同的機器之間可能會發生死鎖,在數據庫系統中也會導致死鎖,比如進程 A 對記錄 R1 加鎖,進程 B 對記錄 R2 加鎖,然後進程 A 和 B 都試圖把對象的記錄加鎖,這種情況下就會產生死鎖。

下面我們就來討論一下什麼是死鎖、死鎖的條件是什麼、死鎖如何預防、活鎖是什麼等。

首先你需要先了解一個概念,那就是資源是什麼

資源

大部分的死鎖都和資源有關,在進程對設備、文件具有獨佔性(排他性)時會產生死鎖。我們把這類需要排他性使用的對象稱為資源(resource)。資源主要分為 可搶佔資源和不可搶佔資源

可搶佔資源和不可搶佔資源

資源主要有可搶佔資源和不可搶佔資源。可搶佔資源(preemptable resource) 可以從擁有它的進程中搶佔而不會造成其他影響,內存就是一種可搶佔性資源,任何進程都能夠搶先獲得內存的使用權。

不可搶佔資源(nonpreemtable resource) 指的是除非引起錯誤或者異常,否則進程無法搶佔指定資源,這種不可搶佔的資源比如有光盤,在進程執行調度的過程中,其他進程是不能得到該資源的。

死鎖與不可搶佔資源有關,雖然搶佔式資源也會造成死鎖,不過這種情況的解決辦法通常是在進程之間重新分配資源來化解。所以,我們的重點自然就會放在了不可搶佔資源上。

下面給出了使用資源所需事件的抽象順序

如果在請求時資源不存在,請求進程就會強制等待。在某些操作系統中,當請求資源失敗時進程會自動阻塞,當自資源可以獲取時進程會自動喚醒。在另外一些操作系統中,請求資源失敗並显示錯誤代碼,然後等待進程等待一會兒再繼續重試。

請求資源失敗的進程會陷入一種請求資源、休眠、再請求資源的循環中。此類進程雖然沒有阻塞,但是處於從目的和結果考慮,這類進程和阻塞差不多,因為這類進程並沒有做任何有用的工作。

請求資源的這個過程是很依賴操作系統的。在一些系統中,一個 request 系統調用用來允許進程訪問資源。在一些系統中,操作系統對資源的認知是它是一種特殊文件,在任何同一時刻只能被一個進程打開和佔用。資源通過 open 命令進行打開。如果文件已經正在使用,那麼這個調用者會阻塞直到當前的佔用文件的進程關閉文件為止。

資源獲取

對於一些數據庫系統中的記錄這類資源來說,應該由用戶進程來對其進行管理。有一種管理方式是使用信號量(semaphore) 。這些信號量會初始化為 1 。互斥鎖也能夠起到相同的作用。

這裏說一下什麼是互斥鎖(Mutexes):

在計算機程序中,互斥對象(mutex) 是一個程序對象,它允許多個程序共享同一資源,例如文件訪問權限,但並不是同時訪問。需要鎖定資源的線程都必須在使用資源時將互斥鎖與其他線程綁定(進行加鎖)。當不再需要數據或線程結束時,互斥鎖設置為解鎖。

下面是一個偽代碼,這部分代碼說明了信號量的資源獲取、資源釋放等操作,如下所示

typedef int semaphore;
semaphore aResource;

void processA(void){
  
  down(&aResource);
	useResource();
  up(&aResource);
  
}

上面显示了一個進程資源獲取和釋放的過程,但是一般情況下會存在多個資源同時獲取鎖的情景,這樣該如何處理?如下所示

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void){
  
  down(&aResource);
  down(&bResource);
	useAResource();
  useBResource();
  up(&aResource);
  up(&bResource);
  
}

對於單個進程來說,並不需要加鎖,因為不存在和這個進程的競爭條件。所以單進條件下程序能夠完好運行。

現在讓我們考慮兩個進程的情況,A 和 B ,還存在兩個資源。如下所示

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void){
  
  down(&aResource);
  down(&bResource);
	useBothResource();
  up(&bResource);
  up(&aResource);
  
}

void processB(void){
  
  down(&aResource);
  down(&bResource);
	useBothResource();
  up(&bResource);
  up(&aResource);
  
}

在上述代碼中,兩個進程以相同的順序訪問資源。在這段代碼中,一個進程在另一個進程之前獲取資源,如果另外一個進程想在第一個進程釋放之前獲取資源,那麼它會由於資源的加鎖而阻塞,直到該資源可用為止。

在下面這段代碼中,有一些變化

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void){
  
  down(&aResource);
  down(&bResource);
	useBothResource();
  up(&bResource);
  up(&aResource);
  
}

void processB(void){
  
  down(&bResource); // 變化的代碼 
  down(&aResource); // 變化的代碼
	useBothResource();
  up(&aResource); // 變化的代碼 
  up(&bResource); // 變化的代碼 
  
}

這種情況就不同了,可能會發生同時獲取兩個資源並有效地阻塞另一個過程,直到完成為止。也就是說,可能會發生進程 A 獲取資源 A 的同時進程 B 獲取資源 B 的情況。然後每個進程在嘗試獲取另一個資源時被阻塞。

在這裏我們會發現一個簡單的獲取資源順序的問題就會造成死鎖,所以死鎖是很容易發生的,所以下面我們就對死鎖做一個詳細的認識和介紹。

死鎖

如果要對死鎖進行一個定義的話,下面的定義比較貼切

如果一組進程中的每個進程都在等待一個事件,而這個事件只能由該組中的另一個進程觸發,這種情況會導致死鎖

簡單一點來表述一下,就是每個進程都在等待其他進程釋放資源,而其他資源也在等待每個進程釋放資源,這樣沒有進程搶先釋放自己的資源,這種情況會產生死鎖,所有進程都會無限的等待下去。

換句話說,死鎖進程結合中的每個進程都在等待另一個死鎖進程已經佔有的資源。但是由於所有進程都不能運行,它們之中任何一個資源都無法釋放資源,所以沒有一個進程可以被喚醒。這種死鎖也被稱為資源死鎖(resource deadlock)。資源死鎖是最常見的類型,但不是所有的類型,我們後面會介紹其他類型,我們先來介紹資源死鎖

資源死鎖的條件

針對我們上面的描述,資源死鎖可能出現的情況主要有

  • 互斥條件:每個資源都被分配給了一個進程或者資源是可用的
  • 保持和等待條件:已經獲取資源的進程被認為能夠獲取新的資源
  • 不可搶佔條件:分配給一個進程的資源不能強制的從其他進程搶佔資源,它只能由佔有它的進程显示釋放
  • 循環等待:死鎖發生時,系統中一定有兩個或者兩個以上的進程組成一個循環,循環中的每個進程都在等待下一個進程釋放的資源。

發生死鎖時,上面的情況必須同時會發生。如果其中任意一個條件不會成立,死鎖就不會發生。可以通過破壞其中任意一個條件來破壞死鎖,下面這些破壞條件就是我們探討的重點

死鎖模型

Holt 在 1972 年提出對死鎖進行建模,建模的標準如下:

  • 圓形表示進程
  • 方形表示資源

從資源節點到進程節點表示資源已經被進程佔用,如下圖所示

在上圖中表示當前資源 R 正在被 A 進程所佔用

由進程節點到資源節點的有向圖表示當前進程正在請求資源,並且該進程已經被阻塞,處於等待這個資源的狀態

在上圖中,表示的含義是進程 B 正在請求資源 S 。Holt 認為,死鎖的描述應該如下

這是一個死鎖的過程,進程 C 等待資源 T 的釋放,資源 T 卻已經被進程 D 佔用,進程 D 等待請求佔用資源 U ,資源 U 卻已經被線程 C 佔用,從而形成環。

總結一點:吃着碗里的看着鍋里的容易死鎖

那麼如何避免死鎖呢?我們還是通過死鎖模型來聊一聊

假設有三個進程 (A、B、C) 和三個資源(R、S、T) 。三個進程對資源的請求和釋放序列如下圖所示

操作系統可以任意選擇一個非阻塞的程序運行,所以它可以決定運行 A 直到 A 完成工作;它可以運行 B 直到 B 完成工作;最後運行 C。

這樣的順序不會導致死鎖(因為不存在對資源的競爭),但是這種情況也完全沒有并行性。進程除了在請求和釋放資源外,還要做計算和輸入/輸出的工作。當進程按照順序運行時,在等待一個 I/O 時,另一個進程不能使用 CPU。所以,嚴格按照串行的順序執行並不是最優越的。另一方面,如果沒有進程在執行任何 I/O 操作,那麼最短路徑優先作業會優於輪轉調度,所以在這種情況下串行可能是最優越的

現在我們假設進程會執行計算和 I/O 操作,所以輪詢調度是一種合理的調度算法。資源請求可能會按照下面這個順序進行

下圖是針對上面這六個步驟的資源分配圖。

這裏需要注意一個問題,為什麼從資源出來的有向圖指向了進程卻表示進程請求資源呢?筆者剛開始看也有這個疑問,但是想了一下這個意思解釋為進程佔用資源比較合適,而進程的有向圖指向資源表示進程被阻塞的意思。

在上面的第四個步驟,進程 A 正在等待資源 S;第五個步驟中,進程 B 在等待資源 T;第六個步驟中,進程 C 在等待資源 R,因此產生了環路並導致了死鎖。

然而,操作系統並沒有規定一定按照某種特定的順序來執行這些進程。遇到一個可能會引起死鎖的線程后,操作系統可以乾脆不批准請求,並把進程掛起一直到安全狀態為止。比如上圖中,如果操作系統認為有死鎖的可能,它可以選擇不把資源 S 分配給 B ,這樣 B 被掛起。這樣的話操作系統會只運行 A 和 C,那麼資源的請求和釋放就會是下面的步驟

下圖是針對上面這六個步驟的資源分配圖。

在第六步執行完成后,可以發現並沒有產生死鎖,此時就可以把資源 S 分配給 B,因為 A 進程已經執行完畢,C 進程已經拿到了它想要的資源。進程 B 可以直接獲得資源 S,也可以等待進程 C 釋放資源 T 。

有四種處理死鎖的策略:

  • 忽略死鎖帶來的影響(驚呆了)
  • 檢測死鎖並回復死鎖,死鎖發生時對其進行檢測,一旦發生死鎖后,採取行動解決問題
  • 通過仔細分配資源來避免死鎖
  • 通過破壞死鎖產生的四個條件之一來避免死鎖

下面我們分別介紹一下這四種方法

鴕鳥算法

最簡單的解決辦法就是使用鴕鳥算法(ostrich algorithm),把頭埋在沙子里,假裝問題根本沒有發生。每個人看待這個問題的反應都不同。數學家認為死鎖是不可接受的,必須通過有效的策略來防止死鎖的產生。工程師想要知道問題發生的頻次,系統因為其他原因崩潰的次數和死鎖帶來的嚴重後果。如果死鎖發生的頻次很低,而經常會由於硬件故障、編譯器錯誤等其他操作系統問題導致系統崩潰,那麼大多數工程師不會修復死鎖。

死鎖檢測和恢復

第二種技術是死鎖的檢測和恢復。這種解決方式不會嘗試去阻止死鎖的出現。相反,這種解決方案會希望死鎖盡可能的出現,在監測到死鎖出現后,對其進行恢復。下面我們就來探討一下死鎖的檢測和恢復的幾種方式

每種類型一個資源的死鎖檢測方式

每種資源類型都有一個資源是什麼意思?我們經常提到的打印機就是這樣的,資源只有打印機,但是設備都不會超過一個。

可以通過構造一張資源分配表來檢測這種錯誤,比如我們上面提到的

的算法來檢測從 P1 到 Pn 這 n 個進程中的死鎖。假設資源類型為 m,E1 代表資源類型1,E2 表示資源類型 2 ,Ei 代表資源類型 i (1 <= i <= m)。E 表示的是 現有資源向量(existing resource vector),代表每種已存在的資源總數。

現在我們就需要構造兩個數組:C 表示的是當前分配矩陣(current allocation matrix) ,R 表示的是 請求矩陣(request matrix)。Ci 表示的是 Pi 持有每一種類型資源的資源數。所以,Cij 表示 Pi 持有資源 j 的數量。Rij 表示 Pi 所需要獲得的資源 j 的數量

一般來說,已分配資源 j 的數量加起來再和所有可供使用的資源數相加 = 該類資源的總數。

死鎖的檢測就是基於向量的比較。每個進程起初都是沒有被標記過的,算法會開始對進程做標記,進程被標記后說明進程被執行了,不會進入死鎖,當算法結束時,任何沒有被標記過的進程都會被判定為死鎖進程。

上面我們探討了兩種檢測死鎖的方式,那麼現在你知道怎麼檢測后,你何時去做死鎖檢測呢?一般來說,有兩個考量標準:

  • 每當有資源請求時就去檢測,這種方式會佔用昂貴的 CPU 時間。
  • 每隔 k 分鐘檢測一次,或者當 CPU 使用率降低到某個標準下去檢測。考慮到 CPU 效率的原因,如果死鎖進程達到一定數量,就沒有多少進程可以運行,所以 CPU 會經常空閑。

從死鎖中恢復

上面我們探討了如何檢測進程死鎖,我們最終的目的肯定是想讓程序能夠正常的運行下去,所以針對檢測出來的死鎖,我們要對其進行恢復,下面我們會探討幾種死鎖的恢復方式

通過搶佔進行恢復

在某些情況下,可能會臨時將某個資源從它的持有者轉移到另一個進程。比如在不通知原進程的情況下,將某個資源從進程中強製取走給其他進程使用,使用完后又送回。這種恢復方式一般比較困難而且有些簡單粗暴,並不可取。

通過回滾進行恢復

如果系統設計者和機器操作員知道有可能發生死鎖,那麼就可以定期檢查流程。進程的檢測點意味着進程的狀態可以被寫入到文件以便後面進行恢復。檢測點不僅包含存儲映像(memory image),還包含資源狀態(resource state)。一種更有效的解決方式是不要覆蓋原有的檢測點,而是每出現一個檢測點都要把它寫入到文件中,這樣當進程執行時,就會有一系列的檢查點文件被累積起來。

為了進行恢復,要從上一個較早的檢查點上開始,這樣所需要資源的進程會回滾到上一個時間點,在這個時間點上,死鎖進程還沒有獲取所需要的資源,可以在此時對其進行資源分配。

殺死進程恢復

最簡單有效的解決方案是直接殺死一個死鎖進程。但是殺死一個進程可能照樣行不通,這時候就需要殺死別的資源進行恢復。

另外一種方式是選擇一個環外的進程作為犧牲品來釋放進程資源。

死鎖避免

我們上面討論的是如何檢測出現死鎖和如何恢復死鎖,下面我們探討幾種規避死鎖的方式

單個資源的銀行家算法

銀行家算法是 Dijkstra 在 1965 年提出的一種調度算法,它本身是一種死鎖的調度算法。它的模型是基於一個城鎮中的銀行家,銀行家向城鎮中的客戶承諾了一定數量的貸款額度。算法要做的就是判斷請求是否會進入一種不安全的狀態。如果是,就拒絕請求,如果請求后系統是安全的,就接受該請求。

比如下面的例子,銀行家一共為所有城鎮居民提供了 15 單位個貸款額度,一個單位表示 1k 美元,如下所示

城鎮居民都喜歡做生意,所以就會涉及到貸款,每個人能貸款的最大額度不一樣,在某一時刻,A/B/C/D 的貸款金額如下

上面每個人的貸款總額加起來是 13,馬上接近 15,銀行家只能給 A 和 C 進行放貸,可以拖着 B 和 D、所以,可以讓 A 和 C 首先完成,釋放貸款額度,以此來滿足其他居民的貸款。這是一種安全的狀態。

如果每個人的請求導致總額會超過甚至接近 15 ,就會處於一種不安全的狀態,如下所示

這樣,每個人還能貸款至少 2 個單位的額度,如果其中有一個人發起最大額度的貸款請求,就會使系統處於一種死鎖狀態。

這裏注意一點:不安全狀態並不一定引起死鎖,由於客戶不一定需要其最大的貸款額度,但是銀行家不敢抱着這種僥倖心理。

銀行家算法就是對每個請求進行檢查,檢查是否請求會引起不安全狀態,如果不會引起,那麼就接受該請求;如果會引起,那麼就推遲該請求。

類似的,還有多個資源的銀行家算法,讀者可以自行了解。

破壞死鎖

死鎖本質上是無法避免的,因為它需要獲得未知的資源和請求,但是死鎖是滿足四個條件后才出現的,它們分別是

  • 互斥
  • 保持和等待
  • 不可搶佔
  • 循環等待

我們分別對這四個條件進行討論,按理說破壞其中的任意一個條件就能夠破壞死鎖

破壞互斥條件

我們首先考慮的就是破壞互斥使用條件。如果資源不被一個進程獨佔,那麼死鎖肯定不會產生。如果兩個打印機同時使用一個資源會造成混亂,打印機的解決方式是使用 假脫機打印機(spooling printer) ,這項技術可以允許多個進程同時產生輸出,在這種模型中,實際請求打印機的唯一進程是打印機守護進程,也稱為後台進程。後台進程不會請求其他資源。我們可以消除打印機的死鎖。

後台進程通常被編寫為能夠輸出完整的文件后才能打印,假如兩個進程都佔用了假脫機空間的一半,而這兩個進程都沒有完成全部的輸出,就會導致死鎖。

因此,盡量做到盡可能少的進程可以請求資源。

破壞保持等待的條件

第二種方式是如果我們能阻止持有資源的進程請求其他資源,我們就能夠消除死鎖。一種實現方式是讓所有的進程開始執行前請求全部的資源。如果所需的資源可用,進程會完成資源的分配並運行到結束。如果有任何一個資源處於頻繁分配的情況,那麼沒有分配到資源的進程就會等待。

很多進程無法在執行完成前就知道到底需要多少資源,如果知道的話,就可以使用銀行家算法;還有一個問題是這樣無法合理有效利用資源

還有一種方式是進程在請求其他資源時,先釋放所佔用的資源,然後再嘗試一次獲取全部的資源。

破壞不可搶佔條件

破壞不可搶佔條件也是可以的。可以通過虛擬化的方式來避免這種情況。

破壞循環等待條件

現在就剩最後一個條件了,循環等待條件可以通過多種方法來破壞。一種方式是制定一個標準,一個進程在任何時候只能使用一種資源。如果需要另外一種資源,必須釋放當前資源。對於需要將大文件從磁帶複製到打印機的過程,此限制是不可接受的。

另一種方式是將所有的資源統一編號,如下圖所示

進程可以在任何時間提出請求,但是所有的請求都必須按照資源的順序提出。如果按照此分配規則的話,那麼資源分配之間不會出現環。

儘管通過這種方式來消除死鎖,但是編號的順序不可能讓每個進程都會接受。

其他問題

下面我們來探討一下其他問題,包括 通信死鎖、活鎖是什麼、飢餓問題和兩階段加鎖

兩階段加鎖

雖然很多情況下死鎖的避免和預防都能處理,但是效果並不好。隨着時間的推移,提出了很多優秀的算法用來處理死鎖。例如在數據庫系統中,一個經常發生的操作是請求鎖住一些記錄,然後更新所有鎖定的記錄。當同時有多個進程運行時,就會有死鎖的風險。

一種解決方式是使用 兩階段提交(two-phase locking)。顧名思義分為兩個階段,一階段是進程嘗試一次鎖定它需要的所有記錄。如果成功后,才會開始第二階段,第二階段是執行更新並釋放鎖。第一階段並不做真正有意義的工作。

如果在第一階段某個進程所需要的記錄已經被加鎖,那麼該進程會釋放所有鎖定的記錄並重新開始第一階段。從某種意義上來說,這種方法類似於預先請求所有必需的資源或者是在進行一些不可逆的操作之前請求所有的資源。

不過在一般的應用場景中,兩階段加鎖的策略並不通用。如果一個進程缺少資源就會半途中斷並重新開始的方式是不可接受的。

通信死鎖

我們上面一直討論的是資源死鎖,資源死鎖是一種死鎖類型,但並不是唯一類型,還有通信死鎖,也就是兩個或多個進程在發送消息時出現的死鎖。進程 A 給進程 B 發了一條消息,然後進程 A 阻塞直到進程 B 返迴響應。假設請求消息丟失了,那麼進程 A 在一直等着回復,進程 B 也會阻塞等待請求消息到來,這時候就產生死鎖

儘管會產生死鎖,但是這並不是一個資源死鎖,因為 A 並沒有佔據 B 的資源。事實上,通信死鎖並沒有完全可見的資源。根據死鎖的定義來說:每個進程因為等待其他進程引起的事件而產生阻塞,這就是一種死鎖。相較於最常見的通信死鎖,我們把上面這種情況稱為通信死鎖(communication deadlock)

通信死鎖不能通過調度的方式來避免,但是可以使用通信中一個非常重要的概念來避免:超時(timeout)。在通信過程中,只要一個信息被發出后,發送者就會啟動一個定時器,定時器會記錄消息的超時時間,如果超時時間到了但是消息還沒有返回,就會認為消息已經丟失並重新發送,通過這種方式,可以避免通信死鎖。

但是並非所有網絡通信發生的死鎖都是通信死鎖,也存在資源死鎖,下面就是一個典型的資源死鎖。

當一個數據包從主機進入路由器時,會被放入一個緩衝區,然後再傳輸到另外一個路由器,再到另一個,以此類推直到目的地。緩衝區都是資源並且數量有限。如下圖所示,每個路由器都有 10 個緩衝區(實際上有很多)。

假如路由器 A 的所有數據需要發送到 B ,B 的所有數據包需要發送到 D,然後 D 的所有數據包需要發送到 A 。沒有數據包可以移動,因為在另一端沒有緩衝區可用,這就是一個典型的資源死鎖。

活鎖

你會發現一個很有意思的事情,死鎖就跟榆木腦袋一樣,不會轉彎。我看過古代的一則故事:

如果說死鎖很痴情的話,那麼活鎖用一則成語來表示就是 弄巧成拙

某些情況下,當進程意識到它不能獲取所需要的下一個鎖時,就會嘗試禮貌的釋放已經獲得的鎖,然後等待非常短的時間再次嘗試獲取。可以想像一下這個場景:當兩個人在狹路相逢的時候,都想給對方讓路,相同的步調會導致雙方都無法前進。

現在假想有一對并行的進程用到了兩個資源。它們分別嘗試獲取另一個鎖失敗后,兩個進程都會釋放自己持有的鎖,再次進行嘗試,這個過程會一直進行重複。很明顯,這個過程中沒有進程阻塞,但是進程仍然不會向下執行,這種狀況我們稱之為 活鎖(livelock)

飢餓

與死鎖和活鎖的一個非常相似的問題是 飢餓(starvvation)。想象一下你什麼時候會餓?一段時間不吃東西是不是會餓?對於進程來講,最重要的就是資源,如果一段時間沒有獲得資源,那麼進程會產生飢餓,這些進程會永遠得不到服務。

我們假設打印機的分配方案是每次都會分配給最小文件的進程,那麼要打印大文件的進程會永遠得不到服務,導致進程飢餓,進程會無限制的推后,雖然它沒有阻塞。

總結

死鎖是一類通用問題,任何操作系統都會產生死鎖。當每一組進程中的每個進程都因等待由該組的其他進程所佔有的資源而導致阻塞,死鎖就發生了。這種情況會使所有的進程都處於無限等待的狀態。

死鎖的檢測和避免可以通過安全和不安全狀態來判斷,其中一個檢測方式就是銀行家算法;當然你也可以使用鴕鳥算法對死鎖置之不理,但是你肯定會遭其反噬。

也可以在設計時通過系統結構的角度來避免死鎖,這樣能夠預防死鎖;也可以破壞死鎖的四個條件來破壞死鎖。資源死鎖並不是唯一性的死鎖,還有通信間死鎖,可以設置適當的超時時間來完成。

活鎖和死鎖的問題有些相似,它們都是一種進程無法繼續向下執行的狀態。由於進程調度策略導致嘗試獲取進程的一方永遠無法獲得資源后,進程會導致飢餓的出現。

尾聲

提出一個勘誤,已反饋給出版社

關於我

我自己現在寫了三本 PDF,讀者回復都非常不錯,現在免費分享出來,關注我的公眾號即可領取

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

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

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

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

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

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

日本國土百萬年的惡夢 每日數百噸的福島輻射污染水

文:宋瑞文(媽媽監督核電廠聯盟特約撰述)

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【【其他文章推薦】

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

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

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

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

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

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

印度環境部長:解決首都空污時間 會比北京短

摘錄自2019年11月23日中央通訊社印度報導

印度環境、森林與氣候變遷部部長賈瓦德卡爾昨天(22日)在印度國會下院答詢時聲稱,空污需要大規模運動來解決,「北京花了15年的時間,我們將花費更少時間(解決空污問題)」。

印度包含新德里在內國家首都區每年冬天因農民焚燒農田殘梗、車輛排放、建築工地揚塵、6000家餐廳用炭火燒烤雞肉、窮人焚燒垃圾取暖等諸多因素,陷入嚴重空氣污染,但印度政府一直無法拿出有效解決對策。空污在今年11月更有惡化趨勢,引發民眾不滿。

賈瓦德卡爾指出,政府已針對城市制定監測空氣污染計畫,目前在全印度355個城市監測空污。此外,政府正每天展開工作以消除空污威脅,包括2018年啟用東、西部外環高速公路,且已把碳排放降低了22%;在第6期汽車廢氣排放標準(BS VI)明年4月實施後,汽車廢氣排放量將可減少80%。

他還把空污問題與氣候變遷聯繫起來,並說印度的總發電量在2030年之前,將有40%是來自可再生能源;而且印度的綠地覆蓋率不斷增加,使印度成為可達到綠地覆蓋率標準的少數國家之一,更五度在國家首都區種植更多樹木,以替代因興建地鐵而砍伐掉的樹木。

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

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

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

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

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

新北清潔公司,居家、辦公、裝潢細清專業服務