CFQ 스케줄링 알고리즘

Question

CFQ 알고리즘은 요청을 한 프로세스의 I/O 우선 순위에 따라 순서화 된 큐 집합을 사용합니다. 즉, 우선 순위에 대한 대기열, 우선 순위 2에 대한 대기열이 있음을 의미합니다.

이 알고리즘은 각 대기열의 첫 번째 요청을 받아 들여 (불필요한 헤드 이동을 방지하기 위해) 핸들링을 위해 디스패치 큐에 배치하십시오. 그러나 단일 요청에는 읽을 블록이 많을 수 있으므로 (연속적 일 필요는 없음)이 정렬은 어떻게 가능합니까? I가있는 경우 나, 같은 의미

Request1 = [1,2,345,6,423] 

및

Request2 = [3,4,2344,664] 

중인 [A, B, C]에 배치 resquests 1 및 2 얼마나 A, B 및 C 블록의리스트 디스패치 대기열? 보시다시피 그들은 비어 있지 않은 교차점을 가지고 있습니다 (예를 들어 블록 6은 블록 3과 4 뒤에 있습니다)

다른 요청은 요청에 배수 블록을 읽을 수 있기 때문에 무엇입니까? 스케줄링의 종류가 내부에 만들어져 있습니까? FCFS? 또는 블록을 주문합니까?

[1,23,5,76,3] 

어떻게 알고리즘이 처리 할 : 예를 들어

,의 우리가 읽을 블록의 다음 목록을 포함하는 요청이 있다고 가정 해 보자? FCFS에 의해

:

[1,23,5,76,3] 

또는 블록을 정렬하여

:

[1,3,4,23,76] 

어쩌면 내가 알고리즘을 이해하지 못했다는 충분히 문서를 찾을 수 없습니다. 누구든지 더 자세한 설명이 담긴 종이 링크가 있으면 나를 참조하십시오.

Answer 1

CFQ는 단일 트랙 요청을 예약하지 않지만 여러 요청에 대해 시간 분할을 예약합니다. IA64wiki에서 인용구 :

CFQ 스케줄러는 디스크에 액세스하기위한 경쟁 프로세스 사이에 상당히 디스크 시간을 배포하는 것을 목표로하고있다. 또한 성능을 향상시키기 위해 예상 및 마감 시간을 으로 설정하고 지연 시간을 시도합니다.

I/O를 실행하는 각 프로세스는 동기화 요청에 대해 배타적 액세스가있는 시간 조각을 가져옵니다. 시간 슬라이스는 두 개의 매개 변수에 의해 으로 제한됩니다. slice_sync은 프로세스의 I/O 우선 순위에 따라 조정됩니다. 각 슬라이스의 길이를 밀리 초 단위로 나타냅니다. quantum은 발행 할 수있는 요청 수를 으로 나타냅니다.

모든 프로세스는 비동기 I/O를위한 17 개의 큐 세트를 공유하며, 하나는 각각의 유효한 I/O 우선 순위 인 입니다. 각 큐는 우선 순위에 따라 slice_async을 기준으로 시간 조각을 가져 오며 큐는 라운드 로빈으로 처리됩니다.각 슬라이스 내에서

는 요청은 (앞면과 뒷면 모두) 합병하고, 역으로 허용 back_seek_max 까지 추구, 스캔에 따른 을 발행하지만, 앞으로 는 노력에 비해 back_seek_penalty으로 치우친. CFQ는 프로세스에서 I/O를 더 많이 사용하기 위해 슬라이스 내에서 slice_idle ms까지 기다립니다. 이것은 예상을 허용하고 프로세스가 bursty I/O를 발행 할 때 공정성을 개선합니다. 일반적으로는 성능을 감소시킵니다.