우선 순위 대기열에 힙을 사용하는 이유는 무엇입니까?
우선 순위가 높은 데이터를 반복할 때 힙이 매우 효율적이기 때문입니다.
데이터가 입력되고 출력될 때마다 최소한의 비용으로 이루어집니다. 데이터 우선순위머리에 위치를 지정하는 알고리즘의 효율성이 중요합니다.
무리
(최소값이 루트 노드라고 가정)
힙 순서 속성만족시키다 완전한 이진 트리
힙 순서 속성: 트리의 각 노드는 부모 노드보다 커야 합니다.
그러나 이진 검색은 이를 보장하지 않습니다. (BST와의 차이점)
보장되는 것은 힙에서 가장 작은 데이터를 가진 노드가 루트 노드라는 것입니다.
힙 삽입 작업
- 힙의 가장 높은 깊이에서 맨 오른쪽에 새 노드를 추가합니다. (완전한 이진 트리 보장)
- 값을 부모 노드와 비교
- 부모 노드보다 작은 경우 부모 노드와 위치를 바꿉니다.
힙 최소값 삭제
- 루트 노드 삭제(최소값 노드)
- 힙의 오른쪽에 있는 노드를 루트 노드로 이동합니다. (완전한 이진 트리 유지)
- 이동한 노드의 두 자식을 모두 비교하여 더 작은 자식과 위치 바꾸기 (새로 추가된 노드와 새로 추가된 노드의 자식 중 최소값을 가진 자식 노드를 스왑)
- 이동 중인 노드가 리프 노드가 되거나 값이 자식 노드보다 작은 경우 종료
힙 구현 시 규칙
2^n – 1에서 2^(n+1) – 2까지의 배열 범위에서 레벨 n 노드(깊이 n의 노드 집합)의 가능한 인덱스
인덱스 K의 자식 노드 인덱스: 2K+1, 2K+2
인덱스 K에서 노드의 부모 노드가 위치한 인덱스: (K-1) / 2의 몫
재할당 기능
동적으로 할당된 메모리의 내용을 보존하면서 할당된 메모리의 크기를 변경하는 함수입니다.
realloc 함수는 이전에 할당된 메모리 블록을 재사용하거나 이전에 할당된 메모리 영역의 내용을 복사하기 위해 새 메모리 블록을 할당합니다. 따라서 realloc 함수를 사용할 때 이전에 할당된 메모리 블록에 대한 포인터를 인수로 전달해야 하며, 이전에 할당된 메모리 블록이 해제되지 않도록 주의해야 합니다.
ALU 연산 결과를 레지스터에 저장하는 이유는 무엇입니까?
이는 메모리 액세스 횟수를 최대한 줄여 실행 속도를 높이기 위한 것입니다.
ALU에서 입력
레지스터 전체에서 피연산자를 허용합니다.
수행할 작업을 알리는 제어 장치로부터 제어 신호를 수신합니다.
ALU 종료
작업 결과는 레지스터에 임시로 저장됩니다. (즉시 메모리에 저장되지 않습니다.)
플래그(작업 결과에 대한 추가 정보) 예: 과다쇼
깃발도 플래그 레지스터라는 레지스터에 저장
오버플로: 연산 결과가 연산 결과를 포함하는 레지스터보다 큰 경우.
컨트롤
컴퓨터 구성 요소를 관리하고 작동하는 데 사용되는 전기 신호 제어 신호명령을 해석하십시오.
명령 레지스터에서 명령을 수락하고 해석한 후 제어 신호를 보냅니다.
기입
- 시계 신호
- 명령(명령 레지스터에서)
- 깃발
- 제어 신호(외부 I/O 장치의 제어 버스를 통해)
출구
- CPU 외부로 공급되는 제어 신호(제어 버스를 통해)
- 기억에
- 입출력장치, 보조기억장치로
- CPU 내부에 공급되는 제어 신호
- 수행할 작업을 ALU에 알리기 위해
- 레지스터에 저장된 명령을 해석하고 레지스터 간에 데이터를 이동하려면
시계 신호가 필요한 이유
시간의 단위를 만들기 위해.
특정 작업은 일정 시간(기간) 후에 실행됩니다.
프로그램 카운터를 명령어 포인터라고 부르는 이유
(명령 포인터)
(프로그램 카운터)
다음에 실행할 명령의 주소를 저장하고 있기 때문입니다.
메모리에서 가져올(가져올) 명령어의 주소를 저장합니다. (명령은 메모리에 저장됩니다.)
이 명령 명령 레지스터그 안에 저장된다
특정 레지스터를 사용한 명령 주소 지정
스택 주소 지정
스택 포인터라는 특수 레지스터를 사용합니다. POP 및 PUSH가 발생하는 스택의 맨 위 주소를 저장합니다.
즉, 스택 주소(유효 주소)는 명령어의 주소(피연산자) 필드에 지정됩니다.
시프트 주소 지정 체계
유효 주소는 피연산자 필드(변위)의 값과 특정 레지스터의 값을 더하여 얻습니다.
1. 상대 주소 지정
특수 레지스터는 프로그램 카운터입니다.
유효 주소는 피연산자와 프로그램 카운터의 값을 더한 결과입니다.
if 문과 같은 분기에 사용됩니다.
2. 베이스 레지스터 어드레싱 방법
기본 레지스터는 기본 주소입니다.
피연산자가 얼마나 떨어졌습니까?
베이스 레지스터의 값과 피연산자의 값을 더하여 유효 주소를 얻는 방법.
중단이 필요한 이유는 무엇입니까?
다른 작업을 급히 처리해야 하거나 어떤 이유로 작업을 일시 중지해야 하기 때문입니다.
CPU의 동작을 방해하는 신호. 방해하다그것은 말한다.
동기 인터럽트 = 예외
명령 처리 중 예상치 못한 이벤트(오류 등)가 발생한 경우
CPU에 의해 생성된 인터럽트.
예외 유형
실수
예외가 처리된 직후 예외가 발생한 문장부터 실행을 계속하는 예외.
예) 특정 명령을 수행하는데 필요한 데이터가 메모리가 아닌 보조메모리에 있는 경우 → 에러 발생 후 데이터를 메모리로 불러옴
잡다
예외가 처리된 직후 예외가 발생한 문장 다음 문장부터 실행을 계속하는 예외.
예) 디버깅
디버깅을 통해 실행 중인 프로그램의 상태를 확인하고 다음 명령에서 실행을 재개할 수 있습니다.
방해하다
강제철거
치명적 오류
비동기 인터럽트와 효율적인 명령 처리 간의 관계
전제: CPU는 매우 빠르지만 I/O 장치는 느립니다.
즉, 속도가 다르기 때문에 입출력 장치의 입출력이 언제 완료되는지 알 수 없습니다.
따라서 신고가 필요합니다.
따라서 CPU가 다른 작업을 수행하는 중에 비동기 인터럽트를 받으면 I/O를 처리할 수 있습니다.
I/O가 중단 없이 완료되기를 기다리는 것보다 훨씬 효율적입니다.
인터럽트 플래그가 필요한 이유
이는 인터럽트와 기존 태스크의 우선순위를 구별하는 역할을 합니다.
플래그 레지스터의 인터럽트 플래그
CPU가 인터럽트를 수락할지 여부를 결정합니다.
인터럽트 플래그가 ‘비활성화’되면 CPU 인터럽트 요청이 무시됩니다.
모든 인터럽트 요청을 무시할 수 있는 것은 아닙니다. 일부 인터럽트는 차단할 수 없습니다.
NMI(마스크 불가능 인터럽트)
예: 전원 장애, 하드웨어 장애
벡터를 인터럽트하는 이유는 무엇입니까?
이는 인터럽트 서비스 루틴을 구분하기 위함입니다.
왜 그렇게 많은 다른 인터럽트 서비스 루틴이 있습니까?
I/O 장치마다 인터럽트를 처리하는 방법이 다르기 때문에 인터럽트 서비스 루틴도 다릅니다.
인터럽트 서비스 루틴의 시작 주소는 인터럽트 벡터에서 알 수 있습니다.
인터럽트 서비스 루틴도 메모리에 로드됩니다. 인터럽트 서비스 루틴 프로그램종류이기 때문에
인터럽트 서비스 루틴을 실행한 후 CPU를 원래 작업으로 되돌리려면 어떻게 해야 합니까?
인터럽트를 처리하는 CPU 프로세스에는 인터럽트 서비스 루틴 실행과 원래 작업으로 돌아가는 작업이 모두 포함됩니다.
원래 작업에 필요한 프로그램 카운터 및 세부 정보(레지스터에 저장된 데이터)는 반환됩니다. 스택 메모리에게 백업을하기 위해해야한다.
백업 복사본을 만들고 인터럽트 서비스 루틴을 실행하여 프로그램 카운터 및 레지스터 값을 덮어씁니다.
인터럽트 서비스 루틴이 완료되면 스택 값이 로드되고 프로그램 카운터 및 레지스터 값이 원래 상태로 복원됩니다.