는 리눅스 커널

Question

의 PID 해시 테이블을 이해

책 "이해 리눅스 커널 3 판"의이 섹션 대신 PID를 찾기 위해 프로세스 목록을 검색하는 커널이 4 개 해시 테이블을 소개한다고 설명 , PID의 각 유형에 대해 하나.

제가 알기 론, 테이블의 각 요소는 PID의 해시입니다. 하지만 어떻게하면 쉽게 검색 할 수 있을까요? 예를 들어 PID가 주어지면 모든 PID가 검색되는 대신 해당 PID 유형의 해시를 검색하는 것이 빠르기 때문에 4 개의 해시 테이블이 존재합니까? 또한 해시가 도움이되는 이유는 무엇입니까? 간단한 숫자를 검색하는 것보다 해시를 찾는 것이 어렵지 않습니까?

그래서이 4 개의 테이블 중 하나에 정확히 어떤 항목이 있습니까? 프로세스 설명자입니까? 나는 그들을 그것으로 이해했다. 각 프로세스 디스크립터에는 동일한 상태, 즉 예를 들어 같은 그룹 및 동일한 상태에있는 프로세스와 같은 다른 유사한 프로세스로 연결되는 구조가 있습니다.

이 내용은 아닙니까?

Answer 1

커널은 모든 프로세스를 작업 목록에 저장합니다. 작업 목록은 순환 이중 연결 목록입니다. 목록의 각 요소에 다음 요소와 이전 요소에 대한 포인터가 있음을 의미합니다. 첫 번째 항목은 마지막 항목에 링크하고 그 반대의 경우도 마찬가지입니다. 개념적으로 원으로 생각할 수 있습니다.

관심있는 PID 정보를 보유하고있는 프로세스 디스크립터가 각 작업 내에 있습니다. 일반적으로 당신이 죽이려고하는 프로세스를 찾으려면 작업 목록을 탐색해야합니다. 찾고자하는 것을 찾을 때까지 각 작업에 대한 각 프로세스 디스크립터의 PID 필드를 살펴 봅니다. 메모리가 어디에 있는지 모르기 때문에 PID로 직접 참조 할 수 없습니다. 그것이 바로 링크입니다. 따라서 작업 목록은 인접한 메모리 공간을 차지할 필요가 없습니다. 재 연결을 통해 간단하게 삽입 및 삭제를 할 수 있습니다. 각 프로세스는 IT가 어디에 있는지를 알고 있습니다. 그리고 그것은 그것이 찾고있는 프로세스를 찾을 때까지 링크를 따라 가기 위해 메모리에서의 위치를 ​​사용할 수 있습니다.

이것을 선형 시간 검색이라고합니다. 최악의 경우, N 개의 요소가 주어지면 결과를 찾기 위해 N 개의 작업이 필요합니다. 효율성을 설명 할 때 항상 최악의 경우를 가정합니다. 선형 시간은 상당한 양의 데이터가 있는지 검색 할 때 매우 비효율적입니다.

그들이 말한 것은 해시 함수를 통해 PID (의도 한 대상에 따라 다름)를 넣을 수있는 테이블이 4 개 있으며, 결과의 위치에서 테이블을 확인하고 정확히 메모리 주소를 알아야한다는 것입니다. 작업 목록의 작업. 그것은 하나의 작업입니다. 충돌을 완화시키는 것은 해시 함수의 작업입니다. 하지만 평균 최악의 경우는 일정 시간이라고합니다. 훨씬 더 빨리.

간단한 숫자를 검색하는 것과 같은 것은 없습니다. 서로 다른 메모리 위치에있는 데이터 구조를 탐색하고 있습니다. C 배열을 가지고 있다면, 연속 된 메모리 공간에 스택에 미리 할당됩니다. 따라서이 경우 배열 인덱스 번호는 즉시 필요한 메모리 덩어리를 가리 킵니다. 하지만 여기서는 그렇지 않습니다. 이러한 데이터 구조는 정적 또는 사전 할당되지 않습니다. 따라서 메모리 주소에서 메모리 주소로 점프 할 수있는 방법이 필요합니다. 이 데이터 구조가 처리하는 것은 무엇입니까.

나는 물건을 깨끗하게하는 것이 좋겠다.

출처 :이 일정 시간이 있기 때문에 https://en.wikipedia.org/wiki/Hash_table http://www.makelinux.net/books/lkd2/app01lev1sec1