728x90
CSAPP
6.1.2 디스크 저장장치
디스크의 구조
- 디스크는 원판(platter)로 구성된다. 각 원판들은 두개의 옆면 즉 표면으로 이루어져 있으며, 이들은 자성을 띤 기억 물질로 코팅 되어 있다. 원판의 중심부에 있는 회적하는 축(spindle)은 원판을 고정된 회전율로 돌려주며, 이 비율은 대개 분당 5,400 에서 15,000번 회전하는 비율(RPM)을 갖는다. 디스크는 일반적으로 밀봉된 저장기에 들어있는 한 개 이상의 원판들을 가진다.
- 디스크의 각 표면은 트랙이라고 하는 여러개의 동심원들로 이루어져있다. 각 트랙은 섹터들의 집합으로 나누어진다. 각 섹터는 섹터위에 자성물질로 인코딩 된 동일한 수의 데이터 비트(일반적으로 512바이트)를 가진다. 섹터들은 아무 데이터도 기록되지 않은 갭으로 분리되어있다. 갭은 섹터를 식별하는 포맷팅 비트를 저장한다.
- 디스크 용량 : 디스크 용량은 다음의 기술 요소들에 의해 결정된다.
- 기록밀도(bits/in) : 1인치의 트랙에 집어 넣을 수 있는 비트의 수
- 트랙밀도(tracks/in) : 원판 중심에서 반지름의 11인치 길이에 넣을 수 있는 트랙의 수
- 면전밀도(bit/in^2) : 기록밀도 * 트랙밀도
디스크의 동작
- 디스크는 구동팔의 끝에 연결된 읽기/쓰기 헤드를 사용해서 자성 표면에 저장된 비트를 읽거나 쓴다. 이와 같은 기계적 동작은 탐색(seek) 이라고 알려져 있다. 다중 원판을 갖는 디스크는 각 표면마다 별도의 읽기/쓰기 헤드를 가지며, 헤드들은 수직으로 정렬되며 같이 움직인다. 어떤 특정 시간에 모든 헤드들은 동일한 실린더에 위치한다.
- 디스크는 데이터를 섹터 크기의 블록으로 읽고 기록한다. 섹터에 접근하는 시간은 세 개의 주요 부분으로 이루어진다.
- 탐색시간
- 특정 타깃 섹터의 내용을 읽기 위해서 팔은 먼저 헤드를 타깃 섹터를 보유한 트랙 위로 위치시킨다. 팔을 이동하기 위해 소요되는 시간을 탐색시간이라고 부른다.
- 회전 지연 시간
- 헤드가 트랙 위에 위치하면 드라이브는 타킷 섹터의 첫 번째 비트가 헤드 아래로 지나가는것을 기다린다. 이 단계의 성능은 헤드가 타깃섹터에 도달할 때 표면의 위치와 디스크의 회전속도에 모두 관련된다.
- 전송시간
- 타킷섹터의 첫 번째 비트가 헤드 아래에 있을 때, 드라이브는 섹터의 내용을 읽거나 쓰기를 시작할 수 있다. 하나의 섹터를 전송하는 시간은 회전속도와 트랙당 섹터 수에 따라 달라진다.
- 탐색시간
- 하나의 디스크 섹터에 있는 512바이트에 접근하는 시간은 탐색시간과 회전 지연 시간이 가장 크게 영향을 준다. 섹터내의 첫 번째 바이트에 접근하는데 긴 시간이 걸리지만, 나머지 바이트들은 실질적으로 시간이 걸리지 않는다.
- 탐색 시간과 회전 지연 시간이 대략 같기 때문에 탐색시간을 두 배해서 간단히 디스크 접근 시간을 추정할 수 있다.
논리적 디스크 블록
- 디스크들은 다중 표면을 가지고, 표면에 여러 기록 영역을 가지는 복잡한 구조를 갖는다. 이러한 복잡성을 운영체제로 부터 감추기 위해 신형 디스크들은 0, 1, … , B-1로 번호를 붙인 B섹터 크기의 논리블록의 배열로 이들의 구조를 좀 더 단순한 모습으로 나타낸다. 디스크 패키지 안에 있는 디스크 컨트롤러 라고 하는 작은 하드웨어/펌웨어 디바이스는 논리 블록 수와 실제(물리적) 디스크 섹터와의 매핑을 유지한다.
- 운영체제 디스크섹터를 메인메모리로 읽어 들이는 것과 같은입출력 연산을 수행하려 할때, 디스크 컨트롤러로 명령을 보내서 특정 논리 블록 번호를 읽어들이게 한다. 컨트롤러의 펌웨어는 논리블록 번호를 해당 물리 섹터를 유일하게 식별하는(surface, track, sector) 쌍으로 번역하는 빠른 테이블 참조를 수행한다. 컨트롤러의 하드웨어는 이 쌍을 해석해서 헤드들을 적절한 실린더로 이동시킨 뒤, 섹터가 헤드 아래로 지나가기를 기다리고, 헤드가 검출한 비트들을 컨트롤러상의 작은 메모리 버퍼로 수집해서 이들을 메인메모리로 복사한다.
입출력장치 연결하기
- 그래픽카드, 모니터, 키보드, 디스크 같은 입출력 장치들을 입출력 버스로 CPU와 메인메모리에 연결된다. CPU에 특화된 메모리 버스와 시스템 버스와는 달리, PCI같은 입출력 버스는 하부 CPU에 독립적으로 설계된다.
디스크 접근하기
- 디스크 컨트롤러가 CPU에서 읽기 명령을 받은 후, 논리 블록 번호를 섹터 주소로 번역하고, 섹터의 내용을 읽어서 CPU의 개입없이 이것을 메인메모리에 직접 전송한다. 디바이스가 스스로 읽기 또는 쓰기 버스 트랜잭션을 수행하는 이 과정은 직접 메모리접근 DMA라고 알려져 있다. 이 데이터의 전송은 DMA 전송이라고 알려져 있다.
6.1.3 Soild State Disks
- 일종의 저장장치 기술로 플래시 메모리를 사용하며, 어떤 경우에 종래의 회전하는 디스크에 대한 매력적인 대체품이다.
- SSD 패키지는 종래의 회전하는 디스크에서 기계적인 드라이브를 대체한 하나 이상의 플래시 메모리 칩, 디스크 컨트롤러 같은 역할을 하는 하드웨어/펌웨어 장치이며, 논리 블록들에 대한 요청들을 하부 물리 디바이스에 대한 접근으로 번역하는 플래시 번역 계층으로 이루어져있다.
- SSD에서 읽어오기 작업이 쓰기 작업보다는 더 빠르다는 점에 주목해야 한다. 랜덤읽기와 쓰기 성능간의 차이는 하부 플레시 메모리의 기본적인 특성 때문이다.
- 랜덤쓰기는 두 가지 이유로 더 느리게 실행된다.
- 첫째, 한 개의 블록을 지우는 것은 1ms 단위로 상대적으로 긴 시간이 걸리며, 이것은 한 개의 페이지에 접근하기 위해 걸리는 시간보다 한 단위 더 걸린것이다.
- 둘째, 만일 어떤 쓰기 연산이 이미 존재하는 데이터를 포함하는 페이지p를 수정하려고 한다면, 유용한 데이터를 가지고 있던 같은 블록 내의 모든 페이지는 페이지 p에 쓰기 작업이 일어나기 전에 새로운(지워진) 블록으로 복사 되어야 한다.
- 랜덤쓰기는 두 가지 이유로 더 느리게 실행된다.
- SSD 장점
- 반도체 메모리로 만들어서 움직이는 부품이 없으며, 따라서 회전하는 디스크 보다 랜덤 접근 시간이 훨씬 빠르고 더 작은 전력을 소모하며 더 견고하다.
- 단점
- 플래시 블록이 반복적인 쓰기 작업 후에 노화해서 SSD도 노후할 가능성이 있다. 플래시 번역 계층의 노화 평균화 로직(wear leveling logic)은 소거 작업을 모든 블록에 균일하게 걸쳐서 분산하는 방법으로 각 블록의 수명을 극대화 하는 시도를 한다.
- 가격이 비싸고, 저장용량은 상당히 적다.
6.1.4 저장장치 기술 동향
- 여러가지 저장장치 기술은 서로 다른 가격과 성능간에 절충과정(trade-off)를 가진다.
6.2 지역성(Locality)
- 시간 지역성
- 좋은 시간 지역성을 갖는 프로그램에서는 한번 참조된 메모리 위치는 가까운 미래에 다시 여러번 참조 될 가능성이 높다.
- 공간 지역성
- 좋은 공간 지역성을 갖는 프로그램에서는 만일 어떤 메모리 위치가 일단 참조되면, 이 프로그램은 가까운 미래에 근처의 메모리 위치를 참조할 가능성이 높다.
- 운영체제 수준에서 지역성의 원리는 시스템이 메인 메모리를 가장 최근에 참조한 가상주소 공간 블록에 대한 캐시로 사용 될 수 있게 해준다.
6.2.1 프로그램 데이터 참조의 지역성
- 벡터의 각 원소를 순차적으로 방문하는 함수는 stride-1 참조 패턴을 갖는다고 말한다.(원소 크기에 대해서) 우리는 때때로 stride-1 참조 패턴을 순차 참조 패턴이라고 부를 것이다. 연속적인 벡터의 매 k번째 원소를 방문하는 것을 stride-k 참조 패턴이라고 부른다. stride-1 참조 패턴은 프로그램 내 보편적이고 중요한 공간 지역성의 원인이 된다. stride가 증가하면 공간 지역성은 감소한다.
- 보폭 stride은 또한 다 차원 배열을 참조하는 프로그램에 대해서도 중요한 문제다. 이중으로 중첩된 루프는 배열의 원소들을 행 우선 순서로 읽는다. 즉, 내부 루프는 첫 번째 행의 원소들을 읽으며, 다음으로 두 번째 행, 이런식으로 진행한다.
6.2.2 인스트럭션 선입의 지역성
- 프로그램 인스트럭션들은 메모리에 저장되어 있으며, CPU에 의해 선입되어야(읽어야)하기 떄문에 인스트럭션 선입에 관한 프로그램의 지역성도 평가할 수 있다.
- 코드를 프로그램 데이터와 구별하는 가장 중요한 특성은 코드는 런타임에 거의 수정되지 않는다는 점이다. 프로그램이 실행되는 동안 CPU는 메모리로 부터 자신의 인스트럭션들을 읽는다. CPU는 이 인스트럭션들을 거의 수정하거나 지우지 않는다.
6.2.3 지역성 요약
- 동일한 변수들을 반복적으로 참조하는 프로그램은 좋은 시간 지역성을 누린다.
- Stride-k 참조 패턴을 갖는 프로그램에 대해서 stride가 적으면 적을수록 공간 지역성도 좋아진다.
- 루프는 인스트럭션 선입에 대해 좋은시간 및 공간 지역성을 갖는다. 루프 본체가 작을록 루프 반복 실행수는 더 커지고 지역성도 더 좋다.
6.3 메모리 계층구조
6.3.1 메모리 계층구조에서의 캐시
- 일반적으로 캐시는 보다 크고 느린 디바이스에 저장된 데이터 객체를 위한 준비 영역으로 사용하는 작고 빠른 저장장치다. 캐시를 사용하는 과정은 캐싱으로 알려져있다.
- 메모리 계층구조의 중심개념은 각 k에 대해 레벨 k에 있는 보다 빠르고 더 작은 저장장치가 레벨k+1에 있는 더 크고 더 느린 저장장치를 위한 캐시서비스를 제공하는 것이다.
- 레벨 k+1에서 저장장치는 블록이라고 하는 연속된 데이터 객체 블록으로 나뉜다. 각 블록은 유일한 주소 또는 이름을 가지며, 이들은 자신을 다른 블록과 구분해준다. 마찬가지로, 레벨 k에서의 저장장치는 레벨 k+1에 있는 블록들과 같은 크기인 더 작은 집합의 블록들로 나뉜다. 시간상 아무때나 레벨 k에 있는 캐시는 레벨 k+1에서 온 블록들의 부분집합의 사본을 포함한다.
- 데이터는 항상 레벨 k와 k+1 사이에서 블록 크기의 전송 유닛 단위로 복사된다. 블록 크기가 계층구조의 인접한 모든 쌍들 사이에서 고정되어 있는 반면, 다른 레벨의 쌍들은 서로 다른 블록 크기를 가질 수 있다.
캐시 적중
- k+1로부터 객체d를 필요로 할때 k에 저장된 블록 중 d가 캐시되어 있다면 캐시적중이라고 한다.
캐시 미스
- 반면, 캐시되지 않는다면 캐시 미스가 발생한 것이다. 미스가 존재할 때 레벨 k에서의 캐시는 레벨 k+1에 있는 캐시로 부터 d를 포함하는 블록을 가져오며, 만일 k캐시가 이미 꽉 찬 상태라면 기존 블록에 덮어쓰기도 한다.
- 블록을 덮어 쓰는 과정은 블록을 교체하거나 추출하는 것으로 알려져 있다. 추출되는 블록은 때로 희생블록이라고 부른다. 캐시 교체 정책에 따라, 랜덤 교체정책이라면 랜덤으로 희생블록을 선택하고, LRU 교체 정책을 갖는 캐시는 가장 과거에 접근한 블록을 선택한다.
6.4 캐시 메모리
6.4.1 기본 캐시 메모리 구조
- 캐시의 구성은 순서쌍(S, E, B, m)으로 규정할 수 있다.
- S : S = 2^s 개의 캐시 집합 배열
- E : E개의 캐시 라인. 각 집합의 구성
- B : B = 2^b 바이트의 데이터 블록. 유효비트 한 개, 태그 비트로 구성.
- m : 주소의 크기
- 캐시의 크기 C는 SEB로 나타낸다.
6.4.2 직접 매핑 캐시
- 캐시는 집합 당 캐시 라인의 수 E에 의해 서로 다른 클래스로 구분된다. 집합당 정확히 한 개의 라인을 갖는 경우 직접 매핑 캐시라고 알려져 있다.
- 캐시가 어떤 요청이 적중인지 미스인지 결정하고, 요청한 워드를 뽑아내기 위해 수행하는 세 작업.
- 집합 선택
- 라인 매칭
- 워드 추출
- 태그와 인덱스 비트를 합치면 메모리 내 각 블록을 유일하게 지정한다.
- 여러 블록이 동일한 캐시 집합에 대응된다.
- 동일한 캐시 집합에 대응되는 블록들은 태그를 사용해서 유일하게 구별된다.
6.4.3 집합 결합성 캐시
- 각 집합이 하나 이상의 캐시 라인을 갖는다 1<E<C/B 인 캐시는 E-중 집합 결합성 캐시라고 부른다.
6.4.4 완전 결합성 캐시
- 모든 캐시 라인들을 갖는 하나의 집합으로 구성된다(E = C/B)
- 하나의 집합에 모든 라인이 들어간다. TLB 같이 작은 캐시에서만 그 사용이 적절하다.
6.4.5 쓰기와 관련된 이슈
- write - through
- w의 캐시 블록 전체를 다음 하위 레벨로 써준다.
- 매 쓰기 작업마다 버스 트래픽을 발생시킨다는 단점이 있다.
- write-back
- 한 갱신을 지연시켜 이 블록이 블록 교체 알고리즘에 의해 캐시에서 축출될 때에만 갱신된 블록을 하위레벨에 써준다.
- 지역성으로 버스트래픽을 상당해 줄일 수 있지만 좀 더 복잡하다는 단점이 있다.
- 캐시는 캐시블록이 수정되었는지 여부를 나타내는 dirty hit를 각 라인마다 추가로 유지해야한다.
쓰기 미스를 다루는 방식
- write - allocate
- 해당 블록을 다음 하위 레벨에서 캐시로 가져오고 난 뒤에 캐시블록을 갱신한다.
- write-back에서 사용한다.
- no - write - allocate
- 캐시를 통과하고 워드를 직접 다음 하위 레벨에 써준다.
- write - through 에서 사용한다.
6.5 캐시 친화적 코드 작성하기
- 공통적인 경우 빠르게 동작하게 만들어라
- 각 내부 루프의 캐시 미스 수를 최소화 하라
- 지역 변수들에 대한 반복적인 참조는 좋으며, 그 이유는 컴파일러가 이들을 레지스터 파일에 캐싱할 수 있기 때문이다(시간 지역성)
- stride-1 참조 패턴은 좋으며, 그 이유는 메모리 계층구조의 모든 레벨에서 데이터를 연속적인 블록들로 저장하기 때문이다(공간 지역성)
LinkedList 구현
insertsortedLL
int insertSortedLL(LinkedList *ll, int item)
{
ListNode *temp;
temp = ll->head;
int idx = 0;
if(temp == NULL)
{
insertNode(ll,0,item);
return 0;
}
int node_item = temp->item;
if (node_item>item)
{
ListNode* head = malloc(sizeof(ListNode));
head->next = ll->head;
head->item = item;
ll->head = head;
ll->size ++;
return 0;
}
else
{
for(int i = 1 ; i <= ll->size; ++i)
{
if(temp->item == item)
return -1;
temp = temp->next;
if(i == ll->size)
{
insertNode(ll,i,item);
return i;
}
if(temp->item >item)
{
insertNode(ll,i,item);
return i;
}
}
}
}
alternateMergeLinkedList
void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
int num_case = 0;
int li_size1 = ll1->size;
int li_size2 = ll2->size;
if (ll1->size == ll2->size)
num_case = 0;
else if (ll1->size < ll2->size)
num_case = 1;
else
num_case = 2;
switch (num_case)
{
case 0:
for (int i = 1; i <= li_size1; ++i)
{
if(i+1 == li_size1 *2)
break;
insertNode(ll1,i*2-1,findNode(ll2,0)->item);
removeNode(ll2,0);
}
break;
case 1:
for (int i = 1; i <= li_size1; ++i)
{
if(i+1 == li_size1 *2)
break;
insertNode(ll1, i*2-1, findNode(ll2,0)->item);
removeNode(ll2,0);
}
break;
case 2:
for (int i = 1; i <= li_size2; ++i)
{
insertNode(ll1,i*2-1,findNode(ll2,0)->item);
removeNode(ll2,0);
}
break;
default:
break;
}
}
moveOddItemsToBack
void moveOddItemsToBack(LinkedList *ll)
{
ListNode* temp;
temp = ll->head;
int ll_size = ll->size;
int j = 0;
for(int i = 0; i < ll_size; ++i)
{
if(0 == findNode(ll,j)->item % 2)
{
++j;
continue;
}
else
{
insertNode(ll,ll_size,findNode(ll,j)->item);
removeNode(ll,j);
}
}
}
moveEvenItemsToBack
void moveEvenItemsToBack(LinkedList *ll)
{
ListNode* temp;
temp = ll->head;
int ll_size = ll->size;
int j = 0;
for(int i = 0; i < ll_size; ++i)
{
if(0 != findNode(ll,j)->item % 2)
{
++j;
continue;
}
else
{
insertNode(ll,ll_size,findNode(ll,j)->item);
removeNode(ll,j);
}
}
}
frontBackSplitLinkedList
void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
int half;
int _case;
if(ll->size%2 == 1)
{
half = (ll->size/2)+1;
_case = 0;
}
else
{
half = ll->size/2;
_case = 1;
}
switch (_case)
{
case 0:
for (int i = 0; i < half; ++i)
{
insertNode(resultFrontList,i,findNode(ll,0)->item);
removeNode(ll,0);
}
for (int i = 0; i < half-1; ++i)
{
insertNode(resultBackList,i,findNode(ll,0)->item);
removeNode(ll,0);
}
break;
case 1:
for (int i = 0; i < half; ++i)
{
insertNode(resultFrontList,i,findNode(ll,0)->item);
removeNode(ll,0);
}
for (int i = 0; i < half; ++i)
{
insertNode(resultBackList,i,findNode(ll,0)->item);
removeNode(ll,0);
}
default:
break;
}
}
moveMaxToFront
int moveMaxToFront(ListNode **ptrHead)
{
ListNode* head = *ptrHead;
ListNode* temp = *ptrHead;
ListNode* pre;
ListNode* cur;
int max = temp->item;
while(temp->next != NULL)
{
if(max < temp->next->item)
{
max = temp->next->item;
pre = temp;
cur = temp->next;
temp = temp->next;
}
else
{
temp = temp->next;
}
}
pre->next = cur->next;
cur->next = head;
*ptrHead = cur;
}
RecursiveReverse
- 재귀 너무 힘들다 힘들어!
나는 반복문으로 풀었는데 현우의 재귀 설명을 들어보니 조아따조아써
그는 신이야!!
void RecursiveReverse(ListNode **ptrHead)
{
int size = 1;
ListNode* head = *ptrHead;
ListNode* temp = *ptrHead;
ListNode* pre;
while(temp->next != NULL)
{
temp = temp->next;
size ++;
}
for(int i = 1; i<size; ++i)
{
head = *ptrHead;
temp = *ptrHead;
int j = i;
while(j>0)
{
pre = temp;
temp = temp->next;
--j;
}
pre->next = temp->next;
temp->next = head;
*ptrHead = temp;
}
}
재귀
void RecursiveReverse(ListNode **ptrHead)
{
ListNode *first;
ListNode *rest;
first = *ptrHead;
if(*ptrHead == NULL) return;
rest = first->next;
if(rest == NULL) return;
RecursiveReverse(&rest);
first->next->next = first;
first->next = NULL;
*ptrHead = rest;
}
728x90
'Study > TIL(Today I Learned)' 카테고리의 다른 글
| 24.02.13 CSAPP 9 (3) | 2024.02.14 |
|---|---|
| 24.02.12 CSAPP 8, Stack & Queue 구현 (3) | 2024.02.13 |
| 24.02.08 CSAPP 6.1 (2) | 2024.02.09 |
| 24.02.07 C & C++ (0) | 2024.02.07 |
| 24.02.06 퀴즈, CSAPP 9.9, 9.11 (1) | 2024.02.07 |