필기용 블로그

○Cache Memory

 ▷메인 메모리보다 빠르지만, 작고 매우 비싼 메모리 (SRAM)

 ▷사용자가 직접 읽거나 쓸 수 없고, 메모리 관리 시스템이 내부적으로 제어한다.

 ▷CPU가 데이터를 찾을 때 가장 먼저 찾는 곳이다.

 ▷메모리 계층 구조의 핵심이 된다.

 ▶구성

  ▶여러 개(S = 2^s)의 set이 모여 Cache를 구성한다. (주로 2의 멱수개)

   ▷set: 여러 개(E = 2^e)의 line이 모인것. (주로 2의 멱수개)

   ▷line: Cache Block. 여러 개(B = 2^B)의 bytes를 저장한다. 확인을 위한 tag와 valid bit이 존재한다.

  ▷Cache 크기: S × E × B Bytes.

 ▶Cache Read

  ▷1. set index로 찾는 line이 있는 set을 선택한다.

  ▷2. tag를 비교하여 해당 set에 우리가 찾는 line이 있는지 확인하고, 있다면 그 line이 valid한지 확인한다. -> hit

   ▷hit: tag가 같고, valid하다. 그냥 읽어들일 수 있다.

   ▷miss: tag가 같지 않지 않거나 valid하지 않다. 하위 계층에서 데이터를 가져와야한다.

  ▷3. block offset의 위치부터 찾는 데이터가 시작한다.

   ▶Directed Mapped Cache

    ▷Set에 line이 단 하나 있다.

    ▷tag비교를 한 번만 하면 된다. (불일치 -> 오래된 데이터?)

   ▶E-way Set Associative Cache

    ▷Set에 line이 E개있다.

    ▷tag비트

    ▷tag 비교를 E번 해야 한다.

 ▶Cache Write

  ▷여러 개의 데에터 복사본들이 각기 다른 계층에 존재한다. (Cache, Memory, Disk...)

  ▷write-through + No-write-allocate

  ▷write-back + no-write-allocate

  ▶write-hit 일 때

   ▷write-through: Cache에 갱신함과 동시에 Memory도 동시에 갱신한다.

   ▷write-back: Cache에 우선 갱신하고, Memory는 나중에 갱신한다.

  ▶write-miss 일 때

   ▷write-allocate: Cache로 Memory를 불러들이고, Cache에서 갱신한다.;

   ▷no-write-allocate: Memory에 직접 쓴다

 ▶Cache Performance

  ▶Miss Rate: Miss가 일어날 확률

   ▷보통 L1에서 3~10%, L2에서 1% 이하이다.

   ▷Miss시에 Main Memory까지 가서 메모리를 읽어야 하기 때문에, 작을수록 성능이 뛰어나다.

  ▶Hit Time: Hit시에 읽어오는데 걸리는 cycle

   ▷보통 L1에서 4, L2에서 10정도 된다.

   ▷작을수록 빠르게 읽어온다.

○DTD (Document Type Definition)

 ▷XML에서 태그들의 규칙을 정의해주는 문서

 ▶사용

  ▷XML문서에서 SYSTEM에서 사용할 dtd를 정의한다.

  ▷문서 내부에서도 DTD를 정의가능하지만, 잘 사용하지는 않는다.

 ▶DTD 문서 정의

  ▶기호

   ▶연결자

    ▷,으로 연결: 순서대로 있어야 한다.

    ▷|으로 연결: 여러개 중 하나만 있으면 된다.

   ▶후첨자

    ▷+: 최소 하나 이상 있어야 한다.

    ▷*: 있던 없던 상관없다.

    ▷?: 없거나 하나 있다.

  ▶가질 수 있는 값

   ▷#CDATA: 글자들 (letters)

   ▷#PCDATA: 해석 가능한 글자들 (letters, numbers, entity references)

    ▷<: &lt, >: &gt, &: &amp

   ▷EMPTY: 값이 올 수 없음

  ▶<!ELEMENT name ( ... )>

   ▷name 태그가 가질수 있는 값을 정의한다.

   ▷다른 태그가 올 수 있다. (계층구조)

   ▷내용이 오는것을 추천한다.

  ▶<!ATTLIST name attribute ( ... )>

   ▷name 태그가 가질 수 있는 속성을 정의한다.

   ▷Identifier (식별자)가 오는 것을 권장한다.

   ▶modifier

    ▷#REQUIRED: 반드시 가져야 하는 속성

    ▷#IMPLIED: 생략 가능한 속성

    ▷#FIXED: 고정된 값을 가지는 속성

  ◎Examples

   ▷letter.dtd

○XML (eXtensible Markup Language)

 ▷여러 특수목적의 마크업 언어를 만드는 용도에서 권장되는 다목적 마크업 언어

 ▷DTD, schema를 통해 사용자가 마크업 언어를 만들고, 규칙을 설정할 수 있음.

 ▷<?xml version = "1.0"?> 을 통해 xml임을 알림. (1.0이후로 나오지 않았다.)

 ▶규칙

  ▷<~>  </~>의 태그들로 묶음.

  ▷태그들은 계층 구조를 어길 수 없음 (하위 계층이 모두 닫히고, 상위 계층이 닫힌다.)

  ▷이름에는 letters, underscores, hyphens, periods이 들어갈 수 있다.

   ▷처음에는 letters, underscores만 들어갈 수 있고, xml로 시작할 수 없다.

 ▶namespace

  ▷이름의 충돌을 방지하기 위해 namespace를 활용할 수 있다.

  ▷URI형태로 표현된다.

  ▷~: 을  통해 사용한다. (xmlns:~ = "URI"을 통해 정의)

  ▷default namespace를 정의할 수 있다. (xmlns = "URI"을 통해 정의)

○Regular Expression

 ▷alphabet Σ에 대한 Regular Expression을 다음과 같이 정의한다.

 ▷L(E): Regular Language (정규식이 표현하는 Language)

 ▶Base

  ▷E = Φ -> L(E) = Φ: empty Language이다.

  ▷E = λ -> L(E) = {λ}

  ▷E = a -> L(E) = {a}

 ▶Recursive Process (우선순위 대로)

  ▷Power: E = (E₁*) -> L(E) = L(E₁)*

  ▷Concatenation: E = (E₁ E₂) -> L(E) = L(E₁) L(E₂)

  ▷Union: E = (E₁ + E₂) -> L(E) = L(E₁) ∪ L(E₂)

 ▶Equivalence of Regular Expression

  ▷L(E₁) = L(E₂)이라면, E₁과 E₂는 equivalent하다.

  ▷다른 정규식이지만, 나타내는 Language가 같다.

 ◎예시들

  ▷짝수/홀수의 alphabet

  ▷1개 / 2개의 alphabet 포함.

  ▷substring을 포함 (ex) 11)

  ▷substring을 미포함 (ex) 11)

○Memory Hierarchy

 ▶메모리를 계층 구조로 설계함

  ▷빠른 메모리일수록, 단위당 가격이 비싸고, 전력을 많이 소모함 -> 용량이 작음.

  ▷Memory와 CPU의 속도 차이가 커지고있음.

  ▷잘 쓰여진 program은 좋은 locality를 가짐.

 ▷용량이 크고, 속도가 느린 메모리를 하위 계층에 위치 (CPU에 멀리 있음)

 ▷용량이 적고, 속도가 빠른 메로리를 상위 계층에 위치 (CPU에 가까이 있음)

 ▷자주 쓰이는 데이터를 상위 계층에 옮김으로써, 큰 용량을 빠른 속도로 관리 가능.

 ※Cache: 크지만 느린 device의 일부를 가져온다.

 ▶Memory -> Cache

  ▷Place policy: 가져온 데이터를 어디에 저장할지.

  ▷Replacement policy: 데이터가 가득 차있다면, 어떤 데이터와 바꿀지

 ▶Cache Miss

  ▷Cold (compulsory) Miss: 빈 공간을 참조함.

  ▷Capacity Miss: 불러들여오는 Block이 cache보다 큼.

  ▷Conflict miss: Block을 특정 level에만 저장 가능하지만, 들여온 데이터가 같은 level에 집중되는 경우

 ▶Caching Hierarchy