Disk Structure

• Magnetic Disk : HDD 등
  • Transfer Rate : 저장 장치 - 커뮤퍼 사이의 데이터 전송 속도
  • Positioning Time(random-access time) : 디스크 암이 목표 실린더에 도달하는 시간(seek time)과 목표 섹터에 도달하는 시간(rotational latency)
  • head crush : 디스크 암과 디스크가 맞닿는 현상
• Access Latency = Average access time = 평균 탐색 시간 + 평균 지연
• Average I/O time = average access time + (transfer amount / transfer rate) + controller overhead

• Logical block
  • 디스크는 1차원의 logical block의 배열로 관리
  • 논리적 주소가 물리적 주소를 의미하지는 않음
  • garbage collector : 쓰레기 값이 저장된 block을 초기홫

Disk Scheduling

• seek time의 최소화
• request queue에 실린더 위치가 순서대로 입장
  • ex) 98, 183, 37, 122, 14, 124, 65, 67
  • head 위치는 53이라고 가정
• FCFS : 큐에 들어오는 순서대로 접근
• SSTF : 현 위치에서 seek time이 가장 짧은 위치로 먼저 접근
  • SJF와 유사 : starvation 문제가 생길 수 있음
• SCAN : 디스크 암이 logical array의 양 끝 번갈아 왕복하며 처리
  • elevator algorithm이라고도 부름
  • 디스크 암과 실린더 위치에 따라 장시간 대기해야 하는 경우가 생길 수 있음
• C-SCAN
  • 실린더의 처음부터 끝까지 순서대로 처리
  • 실린더 끝까지 탐색하면 다시 처음으로 이동한 뒤 끝까지 이동하면서 처리
  • 실린더 양 끝을 왕복하는 SCAN의 단점이 어느정도 해결
• C-LOOK
  • Look : 큐의 최대/최소점에 도달하면 실린더는 반대 방향으로 탐색
  • C-Look : Look으로 동작하되, C-SCAN과 같이 큐 최대점 도달 시 다시 최소점으로 이동한 후 처리

Disk Management

• Low-Level Formatting
  • 물리적 포맷이라고도 함
  • 디스크를 R/W 동작이 가능한 섹터로 분할
  • 각 섹터는 정보, 데이터, ECC(Error Correction Code)가 저장
• 파티션 : 디스크를 논리적 단위로 분할
  • 논리적 포맷 혹은 "파일 시스템을 만든다" 라고도 함
  • 효율성을 위해 파일은 클러스터 단위로 처리 (디스크 > 블록, 파일 > 클러스터)
• 부팅 과정
  • 롬에 저장된 BootStrap이 부팅 시 호출됨
  • 디스크 0번 섹터(MBR)의 프로그램이 부트스트랩을 호출하는 기능을 함(Bootstrap Loader)

• Swap Space management
  • page 파일을 만들어 관리하거나, swap 파티션을 할당하여 관리
  • swap map : 커널은 swpap 사용 방식을 추적
  • swap 공간이 없다 = 메모리 가용량이 없음 >> process kill or crash

RAID

• 저가의 디스크를 다수 연결하여 고성능 구현 (scale - out)
  • mean time to failure : 고장 확률이 높아짐
  • mean time to repair : 추가적인 고장 확률이 높음
• 다수의 디스크를 병렬로 기록 시 : 읽는 속도가 증가
• ex. 디스크의 mean time to failure = 100000, mean time to repair = 10
  • mean time to data loss = 100000^2 / ( 2 * 10 ) = 500 * 10 ^ 6 (약 57000년)
  • 실제로는 저장장치가 완전히 독립적이지 않으므로 이보다는 짧아짐

• Disk striping : 여러 개의 저장 장치를 하나의 단위로 취급
• RAID를 통해 성능을 높이거나, 저장장치의 신뢰성을 높일 수 있음
• RAID 0
  • 큰 데이터를 각 저장장치로 분산
  • 디스크 중 하나가 고장나면 전체 데이터가 손실
• RAID 1
  • Mirroring 혹은 Shadowing으로 호칭
  • 각 디스크의 복사본을 저장
  • 한 쪽이 고장나도 안전한 대체 가능
• RAID 2 : ECC code를 사용
• RAID 3 : Bit Interleaved Pairty
• RAID 4 : Block Interleaved Parity / Parity disk가 고장 시 전체 데이터 손실
• RAID 5 : RAID 4에서 parity를 각 디스크로 분산
• RAID 6 : Parity 정보를 이중으로 기록
• RAID 1 + 0 / RAID 0 + 1
  

  

  • 전자는 Striped Mirror, 후자는 Mirrored stripe
  • 신뢰성과 성능 모두를 추구
  • 디스크 구조상 RAID 1 + 0이 더 안전
• hot-spare : 비상용 디스크 / RAID 중 디스크 고장 시 빠른 대체

Stable Storage Implementation

• 데이터를 저장할 때 안전하게 보관하는 상태
• 1개 이상의 비휘발성 저장소에 복원 가능하도록 데이터를 저장
• Disk Write의 결과
  • 정상 작동
  • 부분 실패
  • 완전 실패

Virtual address

• virtual address space : 프로세스 내의 주소 표현을 논리적으로 나타냄
  • 0으로 시작하여 연속적으로 표현
• demand paging
  

  

  • 프로세스의 필요한 페이지만 필요할 때 할당하는 것
  • I/O가 덜 필요하거나 아예 쓸 필요가 없음
• page fault
  • logical memory에서 page table 접근 시 invalid한 경우
  • 다른 page table을 참조하게 되는 경우

• demand paging 단계
  • 레지스터와 프로세스 상태 저장
  • page fault로 인한 인터럽트 여부 확인
  • page table의 valid 여부, page 위치 확인
  • 저장소에서 frame으로 read 요청
    • 요청을 큐에 할당
    • 장치의 seek/latency time동안 대기
    • page를 free frame으로 전송
  • 대기 중일 때는 CPU는 다른 사용자에게 할당
• demand paging 시의 EAT
  • 주된 동작 : 인터럽트 서비스, page read, process restart
  • page fault rate p를 가정 (p=0 : no page fault)
  • EAT = (1 - p) * 메모리 접근 + p * (page fault overhead + swap In + swap Out)

Copy on Write

• 프로세스 fork 시 부모 - 자식 프로세스가 같은 page를 공유하게 하는 것
  • 자식 프로세스 생성 시에는 프로세스 공간을 복사하지 않음
  • 한 쪽의 프로세스가 write 동작 시 page 복사가 일어남
• page replace
  • page의 과한 할당을 방지
  • page overhead를 줄이기 위한 modify(dirty) bit 사용 - 수정된 page만 write

Page replace

• 제한된 메모리 상의 process 할당 시 page 전환이 필요
• 여유 공간이 없을 경우 page를 전환하여야 함
• page replace 단계
  • page 할당이 필요할 때, free frame을 탐색
  • free frame이 없을 경우, 제거될 frame(victim frame)을 선택
  • victim frame은 저장소로 swap out / 필요 데이터는 그 자리로 swap in
• replace algorithm
  • frame - allocation : 프로세스당 프레임을 얼마나 할당할지, 어떤 프레임을 재할당할지
  • page - replacement : page fault rate를 최소한으로 하도록
  • reference string : 접근한 page 기록을 저장하여 replace 알고리즘에 사용
• FIFO
  

  

  • 가장 먼저 들어온 page를 replace
  • page fault는 10번 발생 (처음부터 계속 page가 없어 replace함)
  • belady's anomaly : frame 수가 늘어나면 오히려 page fault가 많아질 수 있음
• Optimal algorithm
  

  

  • 가장 오래 사용될 페이지는 유지
• Least Recently Used(LRU)
  

  

  • 가장 사용되지 않은 데이터를 교체
  • 미래를 예측하는 Optimal과 달리 과거 데이터를 활용
• second chance algorithm
  

  

  • FIFO와 유사
  • reference bit가 0이면 교체
  • reference bit가 1이면 0으로 변경
  • enhanced second chance
    • (reference, modify)로 2개 bit 할당
    • (0, 0) : replace
    • (0, 1) : replace 전에 메모리 write
    • (1, 0), (1, 1) : 다음 접근 시 replace
    • ex. (1, 1) > (0, 1) > (0, 0) - 3번의 반복을 통해 victim frame이 됨

Buddy System

• $2^n$ allocater를 이용한 메모리 할당
• Slab : 1개 이상의 연속된 page
  • 캐시는 하나 이상의 Slab로 구성
• prepaging
  • page fault 방지를 위해 미리 page 할당
• program 구조
  • 2차원 array int[a, b]를 가정
  • 각 row에는 page가 저장됨
  • 위 코드는 col마다 접근하기 때문에 a * b번의 page fault가 발생하나, 아래 코드는 page fault가 row 개수만큼만 발생

for(j=0;j<a;j++)
    for(i=;i<b;i++)
        data[i, j]=0


for(i=;i<b;i++)
    for(j=0;j<a;j++)
        data[i, j]=0

• I/O Interlock
  • 프로세스가 I/O 장치를 접근할 때, 해당 프로세스가 swap되는 경우
  • 프로세스는 물리적 주소가 할당되기 전이지만, 데이터는 여전히 입력되어야 하는 상태가 됨
  • 이로 인한 문제를 방지하기 위해 프로세스의 해당 page를 swap되지 못하도록 함 (Pinning)

• 실행된 프로그램은 메모리에 적재됨
  • 메모리에 적재되는 데이터 : 명령어, parameter, parameter가 저장된 주소
• 메모리가 처리하는 data stream
  • read : address
  • write : address + data
• 보통 레지스터 접근은 1 clock 내에 처리
  • 메모리 접근은 레지스터 대비 긴 시간이 걸리기 때문에, 중간에 캐시 메모리를 이용하여 병목 현상을 보완
• 메모리 보호
  

  

  • 프로세스가 접근 가능한 주소에 제한
  • ex. 프로세스 할당 시 주소(base) 레지스터와 함께 할당 공간의 제한(limit) 레지스터를 같이 할당
  • base 아래 혹은 base + limit 위의 주소 접근 시 인터럽트를 호출하여 process 삭제

Address Binding

• 프로그램 생성마다의 address binding 단계
  • 소스 코드 : 변수 주소를 symbolic하게 표현
  • 컴파일된 코드는 주소를 relocatable address로 bind
    • relocatable addreess : 프로그램 시작 지점에서의 상대적 offset 주소
  • 링커 / 로더 : 메모리에 적재된 프로그램에 실제 주소 할당
• 주소가 결정되는 단계
  • compile time : 만약 이 단계에서 static한 주소 명시가 된 경우 compile 단계에서 주소 할당
  • Load time : compile time에서 할당되지 않은 주소를 relocatable address로 할당
  • Execution time : 실행 중 새롭게 할당되는 주소 관리

MMU(Memory-Management Unit)

• Logical Address : 프로세스가 바라보는 주소, 가상 주소라고도 함
• Physical Address : 메모리상의 실제 주소
• CPU에서 명령 수행 시 logical address에 접근
• MMU에서 logical address-physical address를 변환
• simple scheme
  • MMU에는 relocation register에 값이 할당
  • CPU에서 logical address 접근 시, relocation register 값만큼 offset을 주어 physical address에 접근하게 함
  • ex. relocation register에 10000이 저장, CPU에서 ld 365 명령 실행 시 실제로는 10365 주소의 메모리에 접근
  • dynamic relocation : 만약 해당 주소에 접근 불가할 경우 relocation register 값을 변경

• static linking
  • binary 코드 생성 시 라이브러리를 모두 포함
  • 프로그램이 무거워지고, 라이브러리가 중복 사용되는 경우 메모리 비효율성
• Dynamic Linking
  • 중복 사용되는 라이브러리는 메모리에 미리 적재
  • 해당 라이브러리를 사용하는 프로세스는 필요할 때마다 별도로 호출
  • stub : Dynmic link를 찾는 루틴

Variable Partition

• hole : 가능한 메모리 블럭
• 프로세스를 단순히 연속 할당 시 메모리 관리가 비효율적이 될 수 있음
• Dynamic Storage Allocation
  • First fit : 할당 가능한 첫번째 hole에 프로세스 할당
  • Best fit : 할당 가능한 최적의 hole에 프로세스 할당
  • Worst fit : 가장 큰 hole에 프로세스 할당
• Fragmentation : 할당으로 인해 생기는 메모리 비효율
  • external fragmentation : 전체 메모리 여유 공간은 충분하나, 연속적이지 않아 할당이 불가능한 경우
  • internal fragmentation : 요청받은 프로세스 크기보다 할당 공간이 약간 큰 경우, 메모리 차이만큼의 공간은 너무 작아서 활용이 불가능
  • 50% rule : 메모리를 N개 block으로 할당한다고 할 때, 절반 가량은 fragmentation에 의해 사용 불가
• Compactation : external fragmentation의 제거
  • 모든 hole을 하나의 공간으로 합침
  • relocation이 동적일 때, excution time에 동작함

Segmentation

• 메모리를 segment라는 논리적 단위로 할당
• segmentation 구조 : <segment-number, offset>
  • segment table : 각 segment의 base, limit 주소를 저장, segment number로 접근
    • base : segment의 시작 주소
    • limit : segment의 길이, 이 주소를 초과하여 접근시 error

• segment number(s)는 segment table로 접근
• offset은 segmnet table의 limit과 비교
  • limit 초과 시 addressing error
• segment table의 base와 offset이 합쳐져 실제 메모리로 접근하게 됨

Paging

• 메모리의 주소를 고정 크기로 나누어 할당하는 것
  • 연속적 할당이 아니므로 fragmentation 문제가 없음
• frame : 물리적 메모리에 접근하는 block 단위
• page : 가상의 메모리에 접근하는 block 단위
  • page 요청 > frame 요청 > OS는 빈 frame를 찾아 할당
• addresss translation
  • CPU에 의해 생성되는 주소는 page number / offset으로 구분
  • page number : page table에 접근하기 위한 index >> frame number를 탐색하여 page offset과 조합
  • page offset : 실제 메모리 주소에 접근하기 위해 사용
  • page size를 4kb(2^12)라 가정
  • 32bit system에서 page offset d = 12가 되고, page number p = 20이 됨
• CPU가 logical 접근
  • page table에 p index 값을 접근, 해당 값을 frame에 전달
  • offset d만큼의 주소를 더해 접근
  • frame offset d만큼의 주소를 더해 메모리 접근

• internal fragmentation = page size - page 할당 후 남는 크기만큼
• worst fragmentation = 1 frame - 1 byte
• average fragmentation = frame size * 0.5
• Page table
  • page table base register(PTBR) : page table 위치를 가리킴
  • page table length register(PTLR) : page table의 크기를 나타냄
• TLB(Transition look-aside buffer)
  • CPU에서 메모리 접근 시 page table을 거치기 때문에 속도 문제가 발생
  • associative memory라고도 하며, 논리 - 물리 메모리 주소의 변환 결과를 미리 저장
  • TLB에 데이터 존재시(hit) 메모리 접근, 없을 경우 page table 접근
• Effective Access TIme(EAT)
  • hit ratio : TLB에서 데이터를 찾아올 수 있는 비율 (ex. hit ratio 80% : 100번 탐색 중 80번은 TLB로 접근)
  • EAT = hit ratio * TLB access time + (1 - hit ratio) * memory access time
• memory protection
  • page table에 read/write bit를 설정하여 프로세스 접근 시 읽기/쓰기 가능 여부를 설정
  • valid-invalid : 페이지가 프로세스의 주소 공간에 할당되었는지 여부를 확인

Page Table Structure

• hirearchial page table
  

  

  • page table 탐색의 overhead 감소
  • page table의 page table을 구성
  • logical address는 inner page + outer page + offset과 같이 구성
• hased page table
  

  

  • page table을 hash table로 구성
• inverted page table
  • 논리 주소가 아닌 물리적 주소로 page table 구성
  • virtual address를 이용하여 shared page 구현

Swapping

• 사용되지 않는 프로세스를 보조 저장장치에 저장하여 메모리를 관리
• context switching time = 전송 시각 * process 크기 * 2

Jacobi Iterative Method

• 행렬 Ax=b를 풀 때
  • 초기 가정 $x^0$을 가정하고, $x^k$에 대해 k의 극한 계산
• Jacobi Iterative method
  • $x_i=\sum_{j=1,j\not ={i}}(-\frac{a_{ij}x_j}{a_{ii}})+\frac{b_i}{a_{ii}}$
  • 2x2 행렬에 대해, $\\a_{11}x_1+a_{12}x_2=b_1\\a_{21}x_1+a_{22}x_2=b_2$
  • 위 식에서 $\\x_1=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}x_2\\x_2=\frac{b_2}{a_{22}}-\frac{a_{21}}{a_{22}}x_1$
  • $x_1^{n+1}=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}x_2^n\\x_2^{n+1}=\frac{b_2}{a_{22}}-\frac{a_{21}}{a_{22}}x_1^n$
  • 계산된 해에 대해 $\frac{||x^k-x^{k-1}||_\infty}{||x^k||_\infty}$가 일정 오차 이하가 될 때까지 반복
• More general representation
  • 행렬 A를 $A=D-L-U$로 분리
    • D : 대각행렬 / L : Lower Triangle / U : Upper Triangle
  • $Ax=b$를 계산하면 $x=D^{-1}(L+U)x+D^{-1}b$, 즉 $x=Tx+c$꼴로 변환
  • $\rho(T)<1$ 혹은 $||T||_\infty$임을 증명하면 $x^k=Tx^{k-1}+c$가 수렴함을 증명할 수 있다.

Gauss-Seidel Method

• $x_1^{n+1}=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}x_2^n\\x_2^{n+1}=\frac{b_2}{a_{22}}-\frac{a_{21}}{a_{22}}x_1^{n+1}$

• $x^n=x$로 수렴하기 위한 조건

  • $T^nx^0$가 0으로 수렴
  • $S^nc$는 x로 수렴
  • 즉 $\rho(T)<1,\ ||T||_2<1,\ ||T||_\infty<1$중 하나를 만족
    • 앞으로 갈수록 sharp한 수렴, 계산은 복잡
  • 한 열에서 사용한 결과값을 바로 다음 열에 사용하므로 계산 시간이 줄어듬
  • $\begin{bmatrix} b1\\ b2 \end{bmatrix}=\begin{bmatrix} a_{11}\ 0\\ a_{21}\ a_{22} \end{bmatrix}+\begin{bmatrix} 0\ a_{12}\\ 0\ 0 \end{bmatrix}$

• $Dx^{n+1}=Lx^{n+1}+Ux^n+b$

  • D : A행렬의 대각선 원소 / L : L행렬 대각원소의 아랫부분 / U : L행렬 대각행렬의 윗부분

• $\rho(T)<1$일 때, $(I-T)^{-1}$을 만족

  • $S_n=(I-T)^{-1}=I+T+T^n+...+T^n$
  • $(I-T)S_n=I-T^{n+1}$
  • n이 발산하면 S는 I로 수렴

• fixed-point iteration 형태의 표현
  • $x^k=Tx^{k-1}+c$
  • jacobi iteration : $T_j=D^{-1}(L+U)$
  • gauss-seidel : $T_g=(D-L)^{-1}U$

Successive Over Relatxation(SOR)

• $x^{n+1}=(1-w)x^n+wx_g^{n+1}$
  • w : relaxation parameger
  • $w_g$ : gauss-seidel로 계산한 값
• Residual Vector
  • gauss-seidel method에서 $x^{n+1}=\frac{1}{a_{11}}[-a_{12}x_2^n+b_1]$
  • 즉 $a_{11}x_1=a_{11}x_1^{n+1}-a_{11}x_1^n\\=-a_{11}x_1^n-a_{12}x_2^n+b_1=r_1^n$으로 정의
  • residual form : $x^{n+1}=x^n+D^{-1}r^n$
  • SOR residual form : $x^{n+1}=x^n+wD^{-1}r^n\\x^{n+1}=(1-w)x^n+wD^{-1}(Lx^{n+1}+Ux^n)$

support vector machine

• 임의 dataset의 decision boundary 설정 시, boundary와 가장 가까운 data point와의 간격(margin)을 최대로 하는 선을 정의
• $\theta^T\vec{x}=w^T\vec{x}+b$
  • $\theta_0=b$로 해석
  • $w^T\vec{x}=\theta_1x_1+...+\theta_nx_n$
  • y = -1 or 1로 나타남(binary classification)
• 벡터 $\vec{p}=x_n-x$에 대해
  • $\frac{\vec{w}^T}{||w||}\vec{p}=\frac{1}{||w||}[\vec{w}^Tx_n+b-(wx^T+b)]=\frac{1}{||w||}$
  • $|\vec{w}^Tx_n+b|=1$인 조건 하에 $\frac{1}{||w||}$를 최대화
    • $|\vec{w}^Tx_n+b|=y_n(\vec{w}^Tx_n+b)$, $\vec{w}^Tx_n+b$의 부호에 의해 +1 혹은 -1로 값이 결정됨
    • 벡터 $\vec{w}$에 대해 $||\vec{w}||^2=w^Tw$
    • $\frac{1}{||w||}$의 최대화 = $||w||$의 최소화, 즉 미분값을 최소화하게 되므로 $||w||=\frac{1}{2}w^Tw$

Lagrange multiplier

• $f(x, y) = ax + by = k$, $g(x, y) = x^2+y^2 = r^2$인 함수 f, g를 가정
  • f와 g가 접하게 되면 gradient가 동일 : $\nabla f = \lambda\nabla g$
  • $\lambda$ : lagrange multiplier
  • $L(x,y,\lambda) = f(x,y) - \lambda(g(x,y) + c)$
• $\nabla L=\frac{\partial L}{\partial x} = \frac{\partial f}{\partial x} - \lambda\frac{\partial g}{\partial x} = 0$
  • $\frac{\partial f}{\partial x}=\lambda\frac{\partial g}{\partial x}$
• SVM 계산에 있어 $f=\frac{1}{2}w^Tw$, $g=y_n(x^Tx_n+b)-1\geq0$
  • $L(w,b,\lambda) = \frac{1}{2}w^Tw+\sum\lambda_i[-y_i(w^Tx_i+b)-1]$
  • $\frac{\nabla L}{\partial w}=0=w-\sum\lambda_iy_ix_i\\\rArr w=\sum\lambda_iy_ix_i$로 SVM weight w 계산
  • $\frac{\nabla L}{\partial b}=0=\sum\lambda_iy_i$
• $L(w,b,\lambda) = \frac{1}{2}w^Tw+\sum\lambda_i[-y_i(w^Tx_i+b)-1]$에서
  • $w=\sum\lambda_iy_ix_i$
  • $\sum\lambda_iy_i=0$
  • $L(w,b,\lambda)=\sum\lambda_i+\frac{1}{2}w^Tw-\sum\lambda_iy_iw^Tx_i\\=\sum\lambda_i-\frac{1}{2}w^Tw$

How to solve SVM

• SVM : $y(w^Tx_i+b)\geq1$일 때 $\frac{1}{2}w^Tw$의 최소값을 계산하는 것
• Lagre multiplier : $L(w, b, \lambda) = \frac{1}{2}w^Tw-\sum\lambda[y_i(w_i^Tx_i+b)-1]$
  • $sup_\lambda L(x, \lambda)$ : $\lambda$에 대해 가질 수 있는 L의 최댓값을 찾는 것
• SVM의 해 $p^*=inf_\lambda sup_\lambda L(x, \lambda)$ : L이 가질 수 있는 최댓값 중 하한선
  • $sup_\lambda L(x, \lambda)$는 $\sum$식이 음수일 땐 $\frac{1}{2}w^Tw$지만, 양수일 땐 무한으로 발산
  • sup값이 가질 수 있는 하한선은 즉 $\frac{1}{2}w^Tw$이 됨
• Lagrange dual function : $g(\lambda)=inf_{w,b}L(w,b,\lambda)$인 함수 g를 정의
  • $\lambda \geq0$일 때 $g(\lambda)\leq p^*$ : $g=inf\ L\leq L(x, \lambda)$이기 때문
  • $p^*$를 구하기 어렵다면 $g(\lambda)$를 구한 후 $p^*=sup_\lambda g(\lambda)$를 계산하는 방법도 있음
• $g(\lambda)=inf_{w,b}L(w,b,\lambda)$
  • $\frac{\partial L}{\partial w}=w-\sum\lambda_i y_ix_i=0$
  • $\frac{\partial L}{\partial b}=\sum\lambda_iy_i=0$
  • 즉 $g(\lambda)=-\frac{1}{2}w^Tw+\sum\lambda_i$

안드로이드 스튜디오 4.0 사용 중 뜬금없이 실행이 안되는 문제가 발생했다.

원인이 도저히 보이지 않아 그냥 4.1 업데이트 후 실행을 했더니 이번에는 이런 오류가 뜬다 ㅜㅜ...

Internal error. Please refer to https://code.google.com/p/android/issues
java.lang.NoSuchMethodError: com.intellij.ide.plugins.PluginManagerCore.loadDedeleted ors()[Lcom/intellij/ide/plugins/IdeaPluginDedeleted orImpl;
    at com.a.a.b.b.ar.a(ar.java:121)
    at com.a.a.b.b.ar.a(ar.java:71)
    at com.intellij.idea.MainImpl.start(MainImpl.java:19)
    at com.intellij.idea.StartupUtil.startApp(StartupUtil.java:303)
    at com.intellij.idea.StartupUtil.prepareApp(StartupUtil.java:245)
    at com.intellij.ide.plugins.MainRunner.lambda$start$0(MainRunner.java:47)
    at java.lang.Thread.run(Thread.java:748)
-----
JRE 1.8.0_242-release-1644-b01 amd64 by JetBrains s.r.o
C:\Program Files\Android\Android Studio\jre\jre

한참을 찾다 겨우 발견.(Android Studio Start Failed when updated to 4.1 - Stack Overflow)

%Appdata%\Roaming\Google에 있는 AndroidStudio 폴더를 아예 지운 후 재시작하면 다시 실행이 된다.

Memory hierarchy

• 주 메모리에는 프로그램과 데이터가 저장
• 한편 모든 프로그램을 할당하기에는 메모리 용량이 모자람
• 주 메모리는 CPU와 연결
  • 현 시점에서 사용되는 프로그램/데이터가 주 메모리에 저장
• 보조 저장소에는 그 외의 데이터가 저장
• 싸고 빠를수록 CPU에 가깝고(레지스터, 메모리, ...), 느리고 쌀수록 주변장치에 저장(HDD, SSD, ...)

Main memory

• CPU가 동작시키는 프로그램과 데이터가 저장
• Static RAM / Dynamic RAM
  • 비용, 전력, 접근 시간 등에서 차이
• ROM : 초기 프로그램(부트로더)가 저장
• 전원 인가 후
  • 컴퓨터는 부트로더 맨 앞 주소의 데이터를 불러옴
  • 부트로더는 디스크에서 메인 메모리로 데이터를 가져옴

• ROM
  

  

  • 읽기 기능이 없어 Chip select와 주소 입력만이 존재
  • 칩에 따라 read 입력이 있을 수도 있음
• RAM
  

  

  • ROM에서 read, write 신호 입력이 추가
  • chip select 입력이 맞지 않거나, read/write 신호가 모두 low인 경우 high-z상태로 사용되지 않는 상태가 됨

Hard Disk

• HDD의 구성 단위
  • Track : hdd에서 지름이 같은 하나의 동신원 구역
  • Sector : hdd를 중심을 기준으로 n등분했을 때 1개 구역
  • Cylinder : HDD는 여러 개의 판(platter)로 구성되는데, 플래터들의 같은 트랙의 집합을 실린더라고 칭한다.
• HDD의 데이터 저장 : 헤드가 자기장을 가하면 데이터가 1, 가하지 않으면 0으로 인식

Assiciative memory(CAM)

• 메모리 내용 자체가 주소 역할
• RAM 대비 고기이나, 탐색 시 시간이 매우 빠름

  

• CAM 동작
  • m개 word, n개 bit
  • Argument register에 데이터가 입력
  • 해당 데이터가 존재 시 Match register의 인덱스가 set
  • Argument register과 메모리 내용 사이에서 탐색할 범위를 Key register로 설정 (Masking)
  • 데이터를 쓸 때는 tag register가 사용 : 데이터의 저장 여부를 판단

Cache memory

• 캐시 메모리의 동작
  • CPU가 데이터를 필요로 할 때, 캐시로 먼저 접근
  • 캐시 데이터 존재시 읽음
  • 캐시에 데이터가 존재하지 않을 경우 메모리 접근
• hit ratio
  • CPU가 찾는 데이터가 캐시에 있을 확률
  • (1 - hit ratio) * main memory 접근시간 + cache memory 접근시간 = 평균 접근 시간
  • 반대어 : miss ratio(없을 확률)
• mapping
  • RAM 데이터를 캐시로 옮기는 과정
  • Associative mapping
    

    

    • CAM을 이용한 addressing - 주소 | data로 된 표 형태로 저장
  • direct mapping
    

    

    • 주소 필드의 일부를 cache memory 접근 시 사용
    • cache memory의 tag register과 주소 필드의 tag register를 비교하여 동일할 경우 데이터를 가져옴
    • 불일치 시 원래 캐시 정보를 메인메모리로 갱신하고, 새로운 메인메모리 정보의 tag와 데이터 갱신
  • set associative mapping
    

    

    • direct mapping의 개선
    • 캐시의 tag-data 표가 2중으로 존재
• replacement policy
  • 캐시 메모리의 용량이 제한되어 있기 때문에, miss로 인한 새 데이터 진입 시 갱신 알고리즘이 필요
  • LRU(Least Recently Used) : 가장 과거에 사용된 데이터가 갱신됨
  • FIFO : 가장 먼저 들어온 데이터가 갱신됨

• cache의 read/write 정책
  • CPU가 캐시 word를 읽을 때 : 메인 메모리에 접근 x
  • 캐시에 쓸 때 : 메인 메모리는 갱신된 데이터를 저장해야 함 (coherency problem)
    • write through
      • 캐시 업데이트시마다 메모리 갱신
      • 이동하는 데이터가 많아짐(traffic problem)
    • write back : 캐시에 replace 발생 시 메모리 갱신
  • cache initialize
    • 캐시 각 주소에는 valid, dirty의 2가지 bit가 할당
    • valid는 데이터의 가용성을, dirty는 데이터의 변형 여부(coherence problem 여부)를 나타냄
    • write-back 정책의 경우 dirty bit가 설정되어 있으면 갱신하게 됨

Virtual Memory

• 프로그램 실행 시 보조 장치(ex. HDD)의 데이터를 주 메모리에 적재 후 실행하게 됨
• 이때 주 메모리의 크기보다 큰 프로그램은 다 적재할 수 없게되는 문제가 존재
  • 보조 저장 장치의 Controller를 이용하여 저장소 주소를 주 메모리로 Mapping함
  • 캐시 - 주 메모리의 관계와 유사하게 동작
• 가상 메모리 존재 시 주소 space 크기는 실제 메모리 공간보다 크게 할당
  • 임베디드 등 가상메모리가 사용되지 않는 경우 주소필드와 메모리 영역은 동일

• page를 이용한 주소 매핑
  

  

  • 실제 메모리는 일정 크기의 block으로 분할
  • 가상 메모리 주소는 일정 크기의 page로 분할 = 프로그램 실행 시 page 단위로 나누어 메모리에 적재
  • virtual address = page number + page line

• virtual address 중 page number는 memory page table에 접근
  • page table의 주소로 접근하여 address를 반환
• virtual address의 line number와 mem.page table에서 반환받은 값을 합쳐 실제 메모리로 접근
• 실제 메모리가 할당 가능한 block 크기에 따라 memory page table도 갱신을 거쳐야 함(FIFO or LRU)
  • 경우에 따라 associative memory table을 이용하여 page / block을 대응시켜 mapping하기도 함

Memory management

• segment : 논리적으로 연관 있는 명령어나 데이터의 집합
  • 서브루틴, 데이터 배열, symbol, 프로그램 등
  • 세그먼트 관리 시 인증되지 않은 접근에서 보호할 필요 존재

    

• logical address는 segment, page, word로 구성됨
  • segment는 table을 거쳐 page와 합쳐짐
  • page table에서 block 위치를 탐색하여 word와 함께 실제 주소를 탐색
  • 최대 접근 가능한 메모리 주소는 page와 word 개수의 곱으로 나타남 $2^{pagebit}\times2^{wordbit}$

Kaggle 데이터분석 캠프 3주차 - 모델과 앙상블

• 빅데이터 / 4차 산업혁명 시대에 가장 중요한 것 ? : Data

• Data가 중요한 이유

  • 기존의 결정 방식에 영향을 주던 것 : 경험과 직관
  • 최근에는 결정에 데이터가 중요한 비중을 차지

• Data Driven Approach : '패턴' 이 중요

  • 어떻게 전처리를 해서
  • 어떻게 분석한 후(EDA, feature engineering)
  • 좋은 모델을 만들어낼 것인가?

• 머신러닝 : 데이터 속의 pattern recognition

  • 목표(최소 오차)를 위해
  • 일반적인 함수(조건)을 만드는 것
  • feature - feature / feature - target 사이의 상관관계를 학습

• 데이터의 분석 과정

  1. 문제 설정
  2. 데이터 수집, 전처리
  3. EDA
  4. 인사이트 얻기
  5. feature engineering
  6. 모델 개발
  7. 모델 평가
  8. kernel 참고
  9. 3~8 무한반복…
  • 보통 Kaggle에서는 3~8의 과정만을 다루게 됨

• 머신러닝을 공부하려면 : 데이터와 사람(=자료) 이 많은 곳으로!

Scikit-learn 분류 모델 만들기

• logistic regression
  • 선형 회귀모델 (y = ax + b)의 변형
  • 확률 개념(odds)를 도입
  • $ln [Y / (1-Y) ] = wx + b >> y = [ 1 + exp[ -(wx + b) ] ] ^-1$
  • maximum likelihood estimation을 이용하여 학습
• support vector machine
  • 주어진 데이터의 클래스 그룹 사이의 margin이 최대가 되는 support vector를 탐색
  • support vector와 수직인 경계(결정 경계, descision boundary)를 찾는 알고리즘
  • 경험적 위험 최소화(ERM)
    • 주어진 훈련 데이터에 대해서만 손실 최소화
    • 새로 추가된 데이터의 경우 오차가 발생할 수 있음
    • 신경망, 선형회귀 등
  • 구조적 위험 최소화(SRM)
    • 관찰하지 않은 데이터에 대해서도 손실 최소화
    • 일반화된 최소 오차를 계산
    • Support Vector Machine의 목표
  • soft margin
    • 유연한 경계면
    • 경계를 넘어가는 데이터를 감수하더라도 최선의 경계선 탐색
  • har margin
    • 데이터를 분명하게 가르는 경계선
  • Kernel Trick
    • 저차원에서는 분리가 안될 수 있지만, 고차원으로 보낼 경우 가능할 수 있음
    • Kernel 함수라는 매핑 함수를 이용 : 저차원 연산에서도 고차원 연산처럼 만들어주기 때문에 Kernel trick이라고 부름
    • ex. Linear, Poly, RBF(방사기저함수), Hyper-Tangent(쌍곡선)
• decision tree
  • if-then 분류를 이용한 데이터 분류
    • greedy algorithm(최적의 트리 생성을 보장하지 않음)
    • 변수가 가진 정보량에 따라 분류
    • tree 깊이가 깊어지면 overfitting 가능성 존재
    • SVM 등 다른 모델 대비 빠른 편
• random forest
  • 결정 트리를 여러 개 만들어 학습
  • 데이터 row, column의 일부를 샘플링하여 각 모델에 학습
  • 생성된 각 결정 트리를 앙상블
  • 간단하고 빠른 알고리즘
  • 변수 소거 없이 많은 입력 변수를 다룰 수 있음
  • 일반화 성능이 좋음 (참고 : 모델의 분산과 편향)
• XGBoost
  • Extreme Gradient Boosting Tree 알고리즘
  • 균형 트리 분할로 인한 과적합 규제
  • 가지치기, 자체 교차 검증 기능 제공
  • 결측치를 자체 처리
  • Early Stopping : 검증 Score가 일정 수준에 도달하면 학습을 멈춤
  • LightGBM : XGBoost의 장점을 취하되, 리프 중심의 트리 분할로 가볍고 빠르면서 나은 성능 제공 / But 적은 데이터에서는 과적합 우려

k-Fold Cross Validation

• 기존의 데이터 학습 과정
  • 샘플된 데이터로 모델 학습
  • 나머지 데이터로 모델 검증
• k-fold cross validation
  • 데이터를 k개 그룹(fold)으로 나눔
  • 임의의 1개 그룹은 검증에, 나머지 데이터는 모델 학습에 사용, 총 k회 반복
  • 각 fold에 대한 score 계산
  • 검증 횟수를 늘려 다소 일반화된 모델을 생성 가능

Out-of-Fold / Stacking 앙상블

• Out-of-Fold
  • K-Fold에서 추론 과정을 추가
  • 모델 출력은 label 대신 확률로 나타냄
  • 각 모델의 확률값의 평균 계산
• Stacking 앙상블
  • 추가 모델 구성 없이 기존 모델 성능을 극대화
  • 학습 데이터 외에 검증용으로 쓰는 fold 데이터 역시 추론 과정에 활용
  • 학습 fold와 검증 fold의 추론 결과를 각각 저장
  • 충분한 모델이 생성되지 않으면 오히려 정확도가 낮아질 수 있음
    • 어느 정도 성능이 나오는 모델들을 합칠 때 효과가 나타나는 편

www.bookjournalism.com/news/24686

 확고한 대체제가 없다는 점이 구글이 적극적으로 나설 수 있는 가장 확실한 이유가 아닌가 싶다. 국내만 해도 갤럭시 / 원스토어 등 다른 어플리케이션 마켓이 있기는 하지만, 구글 플레이스토어보다 확고히 나은 점이 있냐고 하면 그닥이라는 생각밖에 들지 않는다. 차라리 애플 앱스토어처럼 확실히 품질이 보장된 어플리케이션만 업로드되는 앱스토어가 출시될 수 있다면 좀 나아질 수 있을까?

www.bookjournalism.com/news/24669

 분명 우리나라의 대응 및 현황이 타국 대비 현저히 좋다는 건 알겠지만, 실물 경제는 엄청나게 타격을 입고 있는 상황에 주식시장만 역대급 호황을 맞는 모습은 아무리 봐도 부자연스럽게 느껴진다. 차라리 빠르게 이번 사태가 종결을 맞고 회복하면서 두 시장 사이의 갭을 최대한 줄일 수 있게 된다면 좋겠는데...

www.bookjournalism.com/news/24586

쿠르츠게작트(Kurzgesagt)의 유튜브 영상에서 우주 쓰레기로 인해 우리의 우주 시대가 끝을 맞이할 수도 있다는 영상을 본 적이 있다. 지금이야 단순한 위협 정도로 끝날 수 있다지만, 어느 시점에서 우주 쓰레기가 파급 효과를 일으키게 되면 눈에 보이지 않을 크기임에도 각종 장비에 큰 파손을 일으킬 수 있는 파편들이 우주 공간을 가득 메워 우주 밖으로 나갈 수 없게 될 수도 있다는 내용이었다.
 우주라는 공간 특성을 생각해보면 쓰레기 문제는 가급적 빨리 해결되어야 할 문제라고 생각한다. 지금이야 다른 산업 대비 그 속도가 느리다 해도, 우주 단위의 개발을 시작하기 전 반드시 넘어야 할 관문이 될 것이라고 생각한다.

www.bookjournalism.com/news/24588

 공무원들이 양복 일색에서 반바지 차림 등으로 복장이 변화한 것처럼, 타투 역시 문제가 될 수준이 아니라면 완화하는 쪽으로 변화하는 것 가체는 문제가 될 일은 없다고 생각한다.
 문제는 아직까지도 법제화되지 않은 타투이스트 문제이다. 이전보다 사회적 인식도 다소 많이 나아진 상태라고 생각하는데, 의료 법률 문제 때문인걸까? 피부에 직접 시술을 하는 만큼 오히려 관련 법률이 제대로 규정되지 않았을 때 생길 수 있는 문제가 더 클 것 같은 우려가 생긴다.