지밍이 블로그

ARM System Developer's Guide  

- Designing and Optimizaing System Software

# ARM  ? 

ARM 유한회사(Adbanced RISC Machines)는 RISC 프로세서를 설계하고 라이센싱하는 회사로,

ARM 아키텍처는 ARM사에 의해 개발한 CPU 디자인의 한 종류이다.

(wiki)

# ARM Architecture ?

ARM 아키텍처는 임베디드 기기에서 많이 사용되는 RISC 프로세서이다. 저전력을 사용하도록 설계하여 ARM CPU는 모바일 시장에서 뚜렷한 강세를 보인다.

- 1985년 4월 26일 영국의 캠브리지에 있는 에이콘 컴퓨터(Acorn Computers)에 의해서 탄생.

- 1990년 11월에 애플과 VLSI의 조인트 벤처 형식으로 Advanced RISC Machines Ltd.)가 생김

(wiki)

### 1.1. RISC의 특징

# RISC 

 : 매우 빠른 속도로 한 클럭안에 실행 될 수 있는 간결하면서도 막강한 명령어들을 가지고 있는 아키텍처를 의미

# RISC vs CISC

# RISC의 4가지 Design rules

1. Instructions : 명령어의 복잡도를 줄여 성능을 향상

- 적은수의 명령어 클래스를 가짐

- single cycle에서 실행가능한 simple operations 제공

- simple operation 몇 개를 조합하여 복잡한 연산(나눗셈 연산 등)들을 구현

- 일정한 길이의 명령어를 가지며 파이프라인을 구현(decode, fetch)

* CISC : 가변길이의 instructions, 실행을 위해 많은 사이클이 걸림

2. Pipelines : 명령어 처리의 속도를 높임

- instructions의 수행은 파이프라인에 의해 병렬로 수행될 수 있는 작은 units으로 쪼개져서 수행 됨

- 이상적인 파이프라인에서는 한 사이클에 각 명령어를 한 단계씩 앞서 처리

- 명령어들은 한 파이프라인 단계에서 decode 될 수 있음

- 마이크로 코드는 필요하지 않음

* CISC는 미니 프로그램에 의해 실행될 명령어인 마이크로 코드가 필요

3. Registers : 데이터 저장을 위한 거대한 레지스터군을 제공

- 빠른 데이터 처리를 위해 로컬 메모리처럼 동작하는 레지스터로 데이터와 주소가 저장

* CISC는 특정 목적을 위한 전용 레지스터를 가짐

4. Load-store architecture 사용

- 메모리와 레지스터사이에 발생하는 데이터 이동에 따른 비용을 줄이기 위해 메모리를 여러번 access하지 않고, 데이터를 여러번 access.

- 데이터 처리 동작과 메모리 access 동작을 분리

### 1.2. ARM 프로세서의 특징

# ARM 프로세서의 고려사항

1. 저전력, 작은 die 사이즈로 설계

2. 제한된 메모리를 고려한 코드 직접도

3. 저가격의 메모리 소자 사용

4. 설계 및 제조비용. 주변장치 공간을 위해 임베디드 프로세서가 차지하는 다이 사이즈 줄이기

# 프로세서나에 하드웨어 디버그 기술 포함

: 신속한 문제해결로 전체적 개발 비용 줄이기

# 순수 RISC의 개념을 벗어남

: 프로세서 자체의 속도보다는 효율적인 시스템 성능과 전력 소모를 중요하게 봄

## 1.2.1. 임베디드 시스템을 위한 명령어 세트

1. 가변 사이클로 실행되는 명령어

: 전력소모, 실리콘 면적, 코드 사이즈를 줄이기 위해 여러 사이클에 실행되는 명령어를 만듬

ex. "multiple load-store"

- 전송될 레지스터의 수에 따라 실행 사이클이 달라지고 메모리에 linear한 access가 이루어짐

- random access 보다 빠르니까 성능 향상

2. 복잡한 명령어 처리를 위한 Inline Barrel Shifter (2장, 3장)

: 명렁어에 의해 사용되기 전, 입력 레지스터 중의 하나를 미리 처리하는 하드웨어 컴포넌트 

: 성능과 코드 집적도 향상

3. 16bit Thumb 명령어

: 코드 직접도 향상

4. 조건부 실행

: 특정 조건의 경우 실행며 분기 명령어의 사용을 줄여주므로 성능 향상 및 코드직접도 향상

5. DSP 확장 명령어

: 기존 DSP와 프로세서가 수행하던 일을 "Digital Signal Process"가 처리

: 16x16비트의 곱셈 처리를 지원하고자 추가

### 1.3. ARM 하드웨어 임베디드 시스템 아키텍처

# ARM 기반 임베디드 하드웨어의 의 4가지 중요 컴포넌트

1. ARM Processors : 임베디드 디바이스 제어. (코어+주변장치 = Memory Management, Caches, ...)

2. Controllers : 시스템의 주요 기능을 담당하는 블록. (Interrupt Controller, Memory Controller, ...)

3. Peripherals : 칩 외부로의 입출력 기능 제공. 메모리 매핑된 레지스터를 통해 주변장치를 제어함

4. Bus : 주변 장치간의 통신 담당

## 1.3.1. ARM 버스 기술

> 칩 내부 버스 사용

> Bus에 연결될 수 있는 디바이스 타입 

- Bus Master : 다른 디바이스로 데이터를 전송할 수 있는 논리 장치 (ARM Processor Core)

- Bus Slave : 버스 마스터로부터 전송 요청이 있는 경우에만 동작 (Peripherals)

> 2-level Bus Architecture 

- 전기적인 특성과 버스폭(16, 32, 64비트)을 담당하는 물리적 단계

- 프로토콜의 처리단계

## 1.3.2. AMBA Bus Protocol

- Advanced Microcontroller Bus Architecture

- 프로세서와 주변 장치를 연결해주는 역할을 담당

- ARM 프로세서의 On-chip Bus Arhcitecture로 채택

- ASB(ARM System Bus), APB(ARM Peripheral BUS)

- AHB(ARM High Performance Bus)

: 하나에 집중된 multiprex bus를 기반으로 빠른 속도를 제공, 64/128bit 폭 지원, 한번에 하나의 버스 마스터를 활성화

- Multi-layter AHB : 동시에 여러개의 버스 마스터를 활성화. 멀티프로세서 시스템에 적합함

- AHB-lite : 기본 AHB 버스의 하위셋으로, 하나의 버스 마스터로 한정시켜 AHB 버스의 특성을 축약시킴

- 다양한 주변장치의 지원을 위한 인터페이스 제공

## 1.3.3. 메모리

# Memory Hierarcy

> Memory의 trade-off : 

- 위치 :  ARM 프로세서 코어 - 캐시 - 메인메모리 - 보조기억장치

- 성능 및 가격 : 캐시 > 메인메모리 > 보조기억장치

- 용량 : 캐시 < 메인메모리 < 보고기억장치

* 대다수의 임베디드 시스템은 캐시의 성능이 불필요함

: 전반적인 성능향상은 도움이 되지만 실시간 시스템 응답에는 도움이 되지 않음

> Memory Width

: 한번에 access 할 수 있는 비트 수. 8, 16, 32, 64 비트

* 32bit ARM 명령어,  16bit width의 메모리 칩에서 캐시가 없는 경우에서는 2번의 Memory Access는 성능의 저하를 가져오지만, 16bit 메모리 값이 상대적으로 저렴

> Types

## 1.3.4 Peripherals

- 각 주변장치는 보통 하나의 기능만을 수행. 칩 내에 존재

- 모든 ARM 주변장치는 memory-mapped되어있으며, Controll Register들이 메모리 상에 위치함

- 주변장치를 제어하는 2가지 주요 컨트롤러 : 메모리 컨트롤러, 인터럽트 컨트롤러

# Memory Controller

: 메모리를 프로세서 버스에 연결

- 메모리 디바이스의 사용 가능한 상태를 위한 소프트웨어적인 초기 설정

- 메모리 디바이스는 초기화 코드를 실행

* ex. DRAM : 메모리 타이밍, 리프레시 비율, ...

# Interrupt Controller

: 주변장치나 디바이스가 실행될 때, 프로세서에게 인터럽트를 발생 (인터럽트 발생에 대한 소프트웨어 정책을 제공)

  Interrupt Controller Regitster의 해당 비트를 1로 설정

- Standard Interrupt Controller : 외부 디바이스의 요청에 대한 인터럽트를 프로세서 코어에게 보냄. (요청을 수렴할지 결정)

Interrupt Handler는 Interrupt Controller 내부의 Device Bitmap Regitster를 확인 후 해당 디바이스를 알아냄

- VIC(Vector Interrupt Controller) : 디바이스 혹은 주변장치가 특정시간에 인터럽ㅌ를 발생시켰는지를 결정

### 1.4. Embedded System Software

# Embedded System을 제어하기 위한 4가지 S/W Component

- Initialization Code 

- Operating Systems

- Device Drivers

- Applications

* firmware : 디바이스에 고정되어 있는 ROM code (ex. Initialization code, ...)

## 1.4.1. Initialization Code 

: OS가실행될 수 있는 상태로 만들어 주는 코드.

  OS에게 제어권을 넘기기전 타겟보드(혹은 특정 타켓 그룹)의 동작을 위한 최소한의 부분을 설정

# 초기화코드의 3단계

- initial hardware configuration 

: 초기 하드웨어 설정 코드. 이미지 부팅을 위한 타겟 플랫폼을 설정

(타겟플랫폼의 일반적 설정정, 부팅 이미지의 요구사항에 따른 수정사항, ...)

- diagnostics 

: 진단 코드. 초기화 프로그램에 내장되어 결점을 찾아 수정하는 것을 목표로 함

HW System이 작업 순서에 맞는 처리를 하는지 테스트

표준 시스템 관련 문제 찾기

- booting 

: 부팅 코드. 이미지를 *로드한 후 그 이미지로 제어권을 넘겨주는 작업을 수행

PC를 부팅이미지(OS)의 시작 위치로 옮김

* loading : 코드와 데이터를 포함하여 모든 프로그램과 변수를 포함한 데이터영역을 RAM으로 복사하는 작업

* OS이미지가 압축된 경우 road과정 또는 제어권을 가질 대 압축을 해제함

> Example 1.1.   Memory Layout <

: 메모리 초기화 과정의 필요성

전원공급 시 바로 초기화 코드가 실행되야 함

=> ARM 기반의 임베디드 시스템에서는 일반적으로 Memory remapping을 수행

RAM을 0x00000000 주소로 변경시킴 (Exception Vector Table이 RAM에 존재 하도록 재프로그래밍 될 수 있기 때문임. 2.4절)

## 1.4.2. Operating System 

: 하드웨어 리소스와 infrastructure를 사용하기 위한 일반적인 프로그래밍 환경을 제공

:  OS 환경에서 효율적인 시스템의 사용을 위해 시스템 리소스를 조직 (Memory, Peripheral, ...)

# ARM 프로세서가 지원하는 운영체제의 타입

: ARM 프로세서는 50개가 넘는 OS를 지원. 크게 2가지로 분류

> RTOS : Real Time Operating System. 실시간 운영체제.

이벤트에 대한 반응시간을 보장해야 함. 

반응 시간 초과시엔 성능이 서서히 줄어듬.

일반적으로 보조 저장 장치를 가지지 않음.

- Hard Real-time Applications : 모든 작업에 대한 반응시간을 보장

- Soft Real-time Applications : 충부한 반응 시간을 보장

> Platform OS

규모가 크고 실시간이 필요없는 applications를 관리위해 MMU를 필요로 함

일반적으로 보조기억장치를 가짐 (ex. 리눅스 OS)

> 기타....

## 1.4.3. Applications

: 임베디드 시스템의 특정 작업을 수행

## Device Drivers

: 주변 장치와의 표준 인터페이스를 제공

### 참고

# ARM 명령어 세트 

(ISA : Instruction Set Architecture)

http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0204ik/Cegbgefe.html

http://www.jkelec.co.kr/img/lecture/arm_arch/arm_arch_4.html#7.1

# ARM7, ARM9 

http://www.jkelec.co.kr/img/lecture/arm_arch/arm_arch_1.html

# 라즈베리파이

https://www.raspberrypi.org/

------------------------------------------------------------------------------------------

ARM System Developer's Guide 

- Designing and Optimizaing System Software

#####

Advanced DSP and SIMD Support in ARMv6

- SIMD Arithmetic Operations

Future Technologies Beyond ARMv6

- TrustZone

### 15.1. ARMv6 에서의 DSP 및 SIMD 명령어

## 15.1.1. SIMD 산술 연산

### 15.4. 향후 새로운 기술

## 15.4.1. TrustZone

# S5FS

- System V File System 

- 하나의 볼륨(하나의 disk drive, 하나의 partition)당 하나의 파일시스템을 갖음

- 하나의 파일시스템은 Stand alone 시스템 : 파일에 대한 모든 컨텐츠와 정보들이 하나의 볼륨안에 저장이 됨

-  하나의 partition에 존재하는 block의 크기는 512 bytes (512, 1024, 2048)

- Sector들의 linear array = block의 linear array

- Boot Area : 0번째 block에 위치하며, Boot Program을 저장하고 있음.

Boot Area에서 Boot Program을 메모리로 로드하여 하드웨어 디바이스를 부팅시킴

- Super Block : 볼륨에 대한 파일시스템의 모든 메타데이터.

- inode list 

=> 전통적인 초창기 모델이므로 성능과 안정상에 문제를 가지고 있음

- 파일의 inode와 data block간의 물리적인 거리가 멀기 때문에 파일에 접근 시 과도한 Seek Operation이 발생

- Data Block의 할당/해제를 반복할수록 free block이 산재하게 되어 sequential block을 읽을 때 과도한 Seek Operation이 발생

- super block이 한곳에만 저장되어 있으므로 손상될 경우 파일시스템을 사용할 수 없음

- 컴퓨터 시스템에서 빈번하게 사용하는 operation에 최적화 되어있지 않음. 중구난방으로 흩어져 있음

# FFS

- UFS : Unix File System

- self-contained file system

-  cylinder group이라는 개념을 도입

: 인접한 cylinder를 묶어서 그룹화, 지역적으로 비슷한 곳에 있는 정보는 같은 cylinder group에 저장

- cylinder group마다 super block을 가짐(super block을 여러개 두어 recoverry를 도모)

- block안에 fragment라는 더 작은 단위를 도입. fragment단위로 allocation

- 하나의 cylinder group에 저장하기 힘든 사이즈가 큰 파일들은 인전 cylinder group으로 넘어감. (48KB 이상이 되면)

<장점>

- seek optimization.  적절한 spreading으로 동일한 파일의 Block들이 멀리 떨어져 저장되는 것을 방지

- lotational Delay optimization.

: seek operation에서 sector를 읽으려면 disk driver에서 read request 만들어서 날려야 할 때, 2 sector가 지나가는 시간이 걸린다고 가정.

0번 sector를 읽고 1번 sector를 읽어야 할 때, 한번 resquest를 하면 2개의 sector가 지나가면 1번 sector를 읽기위해서는 다시 한바퀴를 돌아야 함.

=> 이런 문제를 방지하기 위해 lotational delay를 계산하여 sector에 저장하도록 함

- long file name의 지원. 256characters.

- symbolic links의 도입

- Disk quota 도입

<한계>

- sequential read의 한계

- crash recovery가 느려지는 문제 발생. disk storage의 block size가 굉장히 빠르게 증가. 

=> 적절한 부팅 시스템을 무시하고 시스템을 power off하면 rebooting할 때 파일시스템의 inconsistency를 확인.

=> "fsck", file system check라는 command를 수행하는데 굉장한 시간이 걸림

=> log structured file system을 사용하게 됨

# LFS

: Log-structured File System 

> Crash recovery의 필요

- 성능향상을 위해 inode cache를 가지는 구조에서 문제가 발생하면 disk의 inode의 값과 메모리의 inode값이 일치하지 않게 될 수 있음

- disk에 대한 operation은 transaction과 같아 synchronous write를 수행하게 됨 

> fsck의 수행동작

- 시스템에 존재하는 inode들을 체크하여 used block들을 확인

- used block들의 구조에서 각각의 directory 별로 file contents를 모두 확인하여 파일의 inode를 확인

- inode indexdp mapping된 데이터가 제대로 있는지 확인. 찾을수 없는 파일이나 연결이 안된 디렉토리들... 

- lost + found directory에 보내기

> LFS 구현

- 새로 생성될, 새로 추가될 정보만 파일의 정보 뒤에 붙이게 됨

- log : Operations나 values, redo/undo log, 

- garbage collection : 어느 시점이 되어서 로그가 너무 방대해지면 sequential read operation이 굉장히 느려지게 됨

- group commit

- retrieval

# Disk Scheduling

- Request Queue : disk에 대한 I/O request를 저장하는 queue

- device drivers와 devices 사이에 request Queue가 위치

- device driver에 I/O Scheduler가 스케쥴링을 수행

- Request Ordering을 수행하여 시간을 줄임

FIFO/FCFS (x)

SSTF (x)

Scan like Elevator (x)    => 양방향에 위치한 애들만 너무 불리해

Circular Scan (o)

> Flash memory 등의 경우에는 disk보다 더 복잡한 스케쥴링이 필요하게 됨

: bus share, multi processor, 공정의 여러 제약 등 

# Files and Directories

# File System

# File Structures

# Disk Space Management

# Unix File System

# Disk Scheduling

# Conclusion

# File 

: 이름을 가지는 디스크에 저장되는 바이트의 집합

> Views 

- OS가 보는 File : Block Sequence. Disk는 Block Storage 이므로 Block 단위로 저장 (내부)

- User가 보는 File : Bytes Sequence  (외부)

=> OS의 File System은 User가 보는Bytes 단위를 시스템 OS가 보는 Block 단위로 mapping 해야 함

* Naming 

: Disk 상에 존재하는 File은 addressing할 수 있어야 하는 이유로 인해 외부적으로는 Text Name을 가져야 함. 내부적으로는 File Identify를 가져야 함.

(*OS는 Naming을 File 뿐만아니라 I/O Devices 에도 적용시킴)

* File Descriptors 

: 파일의 내용에 접근하기 위해 필요한 메타데이터들을 저장하는 자료구조. 

* Operations on Files

- create and delete files

- open files for reading and writing 

- seek within a file

- read from and write to a file

- close files 

- create directories to hold groups of files

- List the contents of a directory

- Removes files from a directory

# File Descriptors

- unix에서는 index node라고도 부름

- 파일의 메타데이터를 저장하는 자료구조

- 파일의 크기, 소유자, 소유 그룹, 액세스 타임, 접근 권한, ...

- inode : unix의 file system에서 파일에 대한 메타데이터를 저장하는 자료구조

- i-node의 index :  i-number, file descriptor의 ID. 

> FIle Descriptors의  저장

과거: array의 형태로 만들어 disk에 특정 block을 할당하여 저장.    

=> 과거 disk는 bad block이 많고 취약했기 때문에, single copy로는 데이터 보호를 제대로 할 수 없음

=> File Descriptor들을 디스크의 특정 영역에 모아두면 성능저하가 발생

: 디스크 스토리지 상에서 File Contents와 File Descriptors를 나누면 물리적인 거리가 멀기때문에 Seek Time이 커짐

현재 : data contents 근처로 file descriptors를 가까이 두어 분산시키거나, data recovery를 위해 data의 copies를 여러개로 만듬

-  in memory cache : 성능의 향상을 위해 File Descriptor의 복사본을 Main memory에 유지

=> 부작용이 생길 수 있음. File Desciptor의 값을 수정할 때, Disk와 Main Memory에저장된 File Descriptor의 값이 달라질 수 있음

- 과거, Main Memory의 Cache에 복사한 file descriptor의 값을 안전하게 Disk에 옮기지 않고 시스템을 종료하면,
    시스템 재부팅 시에 OS는 해당 내용을 Disk의 file descriptor의 내용을 재구성해야함.

but,  현재는 디스크의 용량이 굉장히 커져 복구하기가 어렵고, 재부팅이 시스템을 정상화 하게 하는 경우가 많아짐(스마트 폰...)

=> log structured file system으로 진화

# Directories

- bytes sequence

- File 및 sub directories를 가지고있는 entity

- 내부적으로 File과 동일하게 관리

- File과는 다르게 data content로 contains(text file name, descriptor index) 값을 가짐. 

=> file의 text name을 file id로 mapping하기 위한 기본 데이터

> Unix File System의 구조

- tree 구조

- root directory, 하위 디렉토리는 각 leaf가 root로 부터 unique

- root directory의 inode number : 2

* why? http://stackoverflow.com/questions/12768371/why-root-directory-is-always-stored-in-inode-number-two

- name parsing 

# 부가사항

> Working Directory : 현재 위치한 디렉터리

> Link : 선택적으로 필요에따라 back-door path를 지정하는 기능

* inode의 i-number 값은 system wide하게, unique 하게 부여하는 것이 아니라, 볼륨 단위로 부여를 함

- Symbolic Link : 링크시킬 파일의 full path 값을 새로 링크시켜줄 디렉터리에 복사

원본 파일 A에 대해 심볼릭 링크를 생성하면, A라는 가리키는 파일을 생성

( "symbolic_link_file_B -> original_file_A" )

원본파일 A를 삭제하면 A를 가리키던 심볼릭링크파일도 삭제 됨됨(수정도 마찬가지)

- Hard Link : 링크시킬 파일의 contains pair 값을 새로 링크시켜줄 디렉토리에 그대로 복사. 

원본 파일 A에 대해 하드링크를 생성하면, A라는 파일을 가리키는 "이름"을 하나 더 만듬.

즉, 둘 중 하나의 파일을 삭제하더라도 이름 뿐인 녀석을 삭제하였으므로 내용은 그래도 남게 됨. 한 녀석은 그대로 존재하게 됨

=> symbolic link가 더 유연함. i-node의 number는 볼륨 단위로만 unique 하므로 Hard Link에 사용하는 contains pair값은 system wide하게 unique하지 않음.

즉, Hard Link는 같은 볼륨내에서만 사용이 가능

=> symbolic Link는 full path를 가지고 구현하기 때문에 모든 link는 system wide하게 unique 함

즉, 다른 볼륨간에도 사용할 수 있음

# Big Picture

> File System 기능

1. logical file name(logical resource name)을 physical address로 변환하기 위해 naming 기능을 제공

2. 사용자의 데이터를 저장장치로부터 read/write 하는 기능을 제공

> Views on Files

- User

file name + byte offset

: file pointer로 offset을 움직이며 파일 읽기

* file 단위의 sequence of bytes

* 주요 file access 패턴

- sequention access : file pointer를 한 칸씩(bytes) 움직이면서 파일의 내용을 읽기

- random access : file pointer를 임의로 이동하면서 파일의 내용을 읽기

- Kernel 

ino + logical block number

* file안에 존재하는 sequence of block

* bytes단위가 아닌 block 단위로 내용을 읽기

* kernel의 file system은 밑에 device driver와 interface 해야 함

* file descriptor, = index node

- Device Driver

Physical block number

* disk volume 단위로 관리, sector들의 linear sequence

* volume : 단일 file system으로 관리되는 저장 장치 상의 영역

* sector들의 number

- Device

cylinder number

head number

sector number

* drive number 이미 minor number로 사용 중

> File System in the Kernel (linux case)

user space            : file I/O    (system call : create, read, write, open, I/O contol)

--------------------------------------------------------------------------------

kernel space         : Virtual File System (VFS)  -> individual한 파일 시스템을 유니폼하게 사용자에게 제공하기 위해 필요

Individual Filesystems(EXT3, EXT4, JFFS2, VFAT, ...)

Buffer Cache(Page Cache) -> 최근 접근한 file의 Data Block의 내용을 Main Memory에 저장해 두는 공간으로 

디스크로 부터 한번 읽어온 파일의 내용에 다시 접근할 때, 빠른 속도를 제공함

(buffer cache도 swapping함. LRU같은 Policy를 적용)

I/O Schedulers

*Request Queue / Response Queue

Block Drivers   ,     Block Driver(FTL)

--------------------------------------------------------------------------------

Storage Media     : Disk ...... Flash

# File Structures

- Sequential access. ex. 방대한 코드를 컴파일 할 때,

- Random access.  ex. 데이터베이스에서 특정 데이터를 읽을 때, demanding paging에서 특정 page를 읽을 때, 

- keyed access. ex. 특정 key로 데이터를 읽을 때, (OS에서는 처리하지 않음)

* 과거 디스크는 fragmentation의 문제가 있음

=>  비연속적인 block단위로 allcation을 수행하여 fragmentation의 문제를 해결

1. Linked File 구조

: 해당 파일 디스크리터에 기록된 파일의 첫번째 블록의 주소를 통하여 파일에 접근

: fragmentation의 문제는 해결

: sequential access는 문제가 없으나, random access의 경우에는 seek time이 굉장히 오래 걸리게 됨

: 1970년대..

2. Indexed File 구조

: Unix의 기본 file 구조

: file descriptor에 파일이 가지고있는 block들에 대한 포인터를 index array로 저장

: sequential access, random access 둘다 용이함

: data block들은 file system의 sector array 중 임의의 block을 할당. 각 file의 file descriptor들이 해당 block들을 가리키는 구조

: file descriptor는 일정한 크기를 갖는 descriptor들의 array로 구성. 

=> 그안에 넣을수 있는 index의 갯수가 제한. 한 파일의 크기는 index의 갯수만큼 제한된다는 단점!

=> double indirect block 구조를 사용하여 큰 사이즈의 파일도 수용할 수 있음

 (but, 이중으로 처리하는 이러한 구조는 기존에 비해 데이터를 더 액세스해야하므로 seek time이 증가)

# Related Mechanisms

1. Block buffer cache

2. bit map operation  : 디스크 블락을 할당할 때, 꼭 sequential한 위치에 할당하지 않아도 되지만, seek time을 줄이기 위해 같은 실린더안에 있는 block을 할당하거나 하는 등의 인접한 위치의 block을 할당하는 방법

=>  OS의 File System에선 비어있는 연속된 block의 위치를 bit map을 통해서 알 수 있음

=> block들에게 1bit씩을 할당하여 1이면 이미 할당됨을, 0이면 할당되지 않고 비어있음을 나타내게 함함

=> 소프트웨어적으로도 구현이 가능하나 대부분의 마이크로 프로세서가 해당 기능을 제공

* Bit Map을 사용한 디스크의 free block 관리

: 각 bit가 디스크의 block이 사용 중인지 아닌지를 나타내는 Array. 

 HW/SW String Search 기법을 사용해 연속적인 사용 가능한 block을 쉽게 찾을 수 있음

> File의 구조를 결정하는 요소

: sequention access, random access를 효율적으로 지원해야함

작은 file, 큰 file 모두 효율적으로 지원해야 함

> must have items

1. Naming

2. Protection

3. Reliability

4. Disk Space Management 

# Disk Space Management

: File이 생성되거나 확장될 때, 어떻게 disk sector들을 file에 할당해 줄것인가를 결정

- 오버헤드가 적게

- 파일에 빠른 액세스가 가능하게 등등

- 파일의 각 block들

- matadata : user에게는 보이지는 않지만 커널이 각 파일별로 관리. 

in-memory cache를 유지하고, system이 shutdown될 때는 consistency를 잘 유지해야 함

- crash policies

> Disk space allocation policies

1. contiguous allocation

2. Block-based allocation

3. Extent-based allocation : block들을 그룹으로 묶고 각 그룹에 semantics를 부여함으로써 최적화를 달성하는 정책

=> block 단위로 allocation을 하면 sequential read를 할 때 seek가 많이 발생하므로 큰 단위로 할당해야하는 필요가 있음

# Unix File Systems

- System V file system : s5fs

: 완전 기본적 전통적인 파일시스템

- Berkeley fast file system (FFS) - often called UFS, 1980 년대 s5fs를 개선

- Sun's network file system (NFS) - 분산 operation과 file system을 접목

- Sun's virtual file system (VFS) - 다양한 파일시스템을 지원하기 위한

- Log-structured file system (LFS) 

# I/O Hardware

# Device Drivers

# Colision

# I/O Hardware

CPU, Memory, HardDisk, Network card, ...

<Bus>

- System Bus, I/O Bus, 

- Address Bus, Data Bus, Control Bus 

- ISA, PCI, EISA, SCSI ...

> I/O Device 

- Controller, logic

- Register set

> I/O Device 내부의 Registers

- Status Register : 장치의 상태를 보여주는 Register

- Control Register : 장치의 동작을 결정하는 Register

- Data Register : 입출력할 데이터를 잠시 보관하는 Register

- Instruction Register ...

> I/O Device의 Register에 접근하는 두가지 방법

- Memory-Mapped I/O : 별도의 I/O address space를 갖지 않고, Physical address space의 일부를 할당하여 사용

* register를 access 하기위해 load/store 명령어를 사용 (모토롤라...),

- Port-Mapped I/O : 메모리의 주소와는 다른 방식의 주소를 할당하여 사용

* register를 access 하기위해 in/out 명령어를 사용 (Intel processor...), 

> Device Control

- device control = device의 register들을 프로그래밍

- OS는 I/O Bus의 address line에 특정 register의 address를 보낸 후 read/write같은 명령을 보내 수행하게 함

# I/O Devices의 분류

: unix OS는 굉장히 단순화 시키려고 노력하였으며 이런 환경에서 I/O Devices를 특성에따라 모델을 나누게 됨

- Character Devices : 입출력을 Character 단위로 수행. mouse, terminal, ...

- Block Devices : 입출력을 block이라는 임의의 단위로 수행. Disk Drive, Flash Drive, ...

- Network Devices : NIC, ...

> Character Devies

* ex. 

<Mouse driver의 역할 요약>

- Mouse Interrupt 발생 시, Mouse의 Data Register에서 값을 읽어오는 역할

- interrupt를 Event로 바꾸어 주는 역할

<Keyboard Driver의 역할>

- 키보드로부터 들오오는 각 캐릭터들을 Line buffer에게 순서대로 저장

- End-of-Line Character가 들어오면 전체 Line Buffer에 있는 데이터를  OS에게 전달

> Block Devices

- spindle

- arm assembly, arm, read-write head

- Track : 한 디스크 표면에서 스핀들로부터의 거리가 동일한 환형의 저장 공간

- cylinder : 여러장의 디스크를 수직으로 쌓여있는 동일한 반지름의 Track들의 집합

* cylinder 단위의 데이터 접근이 중요한 이유 (왜 cylinder라는 개념이 있는건가?)

: Arm Assembly가 고정된 상태에서 여러 platter에 걸쳐있는 한, 실린더의 트랙들을 동시에 읽을 수 있기 때문

- sector : 각각의 track을 분할하는 디스크 read/write 단위의 영역

> Disk Operation

* Sector : 디스크를 읽을 때 data transfer가 일어나는 최소 unit.

Sector에 접근하기 : cylinder number, track number in the cylinder, sector number in the cylinder

1. read/write head 선택

2. "seek", arm assembly를 해당 cylinder로 이동. (Move heads to the correct track)

* seek time : arm을 목표한 지점(해당 cyliner)까지 이동하는데 걸리는 시간

3. 해당 sector가 돌아올때까지 기다림 (spindle의 회전수에 비례, RPM-Rotation Per Minute)

* Rotational Delay : 디스크가 회전하여 목표한 지점(해당 섹터)이 head에 도착하는 시간

> Disk Performance

- seek time : 0-50 ms (avg 10-20 ms)

- rotational delay : 0-16ms

- typical drive spins at 3600-5400 RPM

> Flash Drive

- NAND flash memory : RAM과 Access pattern이 굉장히 다름. data tranper가 bytes단위가 아닌 block 단위로 일어남

- Page : Read/Write를 수행할 때 대상이되는 Data block. 2KB, 4KB, 8KB

* Page의 일부분은 Data를 저장하는 공간과 Spare Area라는 패리티, 에러처리 등 부수적인 정보 등을 저장하는 공간으로 나뉨

- Block : 64 pages, 128 pages

* Flash Memory > Blocks in a Flash Memory > pages in a Block > Spare areas in a page

* Flash Operations

- read : 하나의 페이지를 통째로 읽어옴

- write/program : flash의 해당 영역을 굽기

- erase : block 지우기. flash는 rom이므로 rewrite할 수 없음. 우선 지우고 다시 써야함.

<특성, 제약사항>

* Erase-before-write : NAND Flash 메모리는 데이터의 덮어쓰기가 불가능 하기 때문에 먼저 Erase로 초기화 한 후 write 해야 함.

* Worn-out : Erase 가능한 횟수가 제한적임

* Wear-leveling : NAND Flash의 한 영역에 Erase가 집중되어 worn-out이 발생하는 것을 막기위해 전체 영역을 고루 사용하도록 조절하는 기술

* read/write의 단위는 page, erase의 단위는  block

- Flash Memory를 Storage로 사용해 file system 구성하려면, Erase-before-write라는 제약조건 때문에 

반드시 Log Structure Architecture가 필요함

> Page단위로 write를 수행하다가 Erase를 수행할 때, 단위가 block으로 page보다 크므로 지우려는 page 외에도 다른 page의 데이터가 모두 지워짐

> 로그를 남겨 관리를 해야함. page remapping after update.

=> Log-structured file system

# Device Drivers

:  I/O Devices의 Control. 다른 프로그램들이 어떤 하드웨어 디바이스를 잘 사용할 수 있게 컨트롤 해주는 컴퓨터 프로그램

- 하드웨어 적인 측면을 관리하며, 기능을 사용자에게 추상화 시켜 사용하기 편하게 도와주는 역할을 함

- Application과 Device, OS와 Device  사이에 위치하며, User들이 Device를 사용하기위해 함수들을 제공

* SW System의 구성

- 정적인 구성요소 : structure(process)

- 동적인 구성요소 : behavior(program)

- Device Drives의 요소

정적 구성요소 : Device Drives를 User Program이 사용하기 위해 호출하는 APIs, Operations...

동적 구성요소 : Interrupt Service Routin. 

=> 즉, Device Drives는 라이브러리이며 어떤 구성요소는 Interrupt에 의해 호출되며, 어떤 구성요소는 User Programs에 의해 호출됨

- UNIX 계열의 Device Drivers

* Unix 

- 시스템의 단순화, portability 높이기.

- portability를 높이기
 : machine dependent 한 부분을 정형화 시켜서 정리해야 함

 : micro processor에 micro architecture specipy한 부분(MMU, context)이나, Memory layout, system bus architecture, Device관련 부분 들

* Unix Device Drivers의 대표적인 5가지 함수

- Open : 디바이스를 initialization. OS관점에서 레지스터와 디바이스 드라이버가 필요한 데이터 스트럭쳐를 잡아주는 역할 등

- Close : release

- read/write

- I/O CTL : I/O Contol

* Type of Unix/Linux Device

- Character Devices : data transfer unit이 캐릭터 단위. 시퀀셜 엑세스에 사용

일반적으로 사람과 상호작용 하므로 보통 slow device.

- Block Devices : 데이터 트랜스퍼 유닛이 블럭단위. 랜덤 엑세스에 사용

* block buffer cache : Large scale의 볼륨을 단위로 high speed가 필요함. 캐시로 CPU에 비해 상대적으로 속도가 느린 block device의 성능을 보완한 것.

- Network Devices

> File System의 역할

1. 디스크에에 있는 데이터를 읽거나 쓸 쑤 있는 여러 기능을 제공

2. File이나 Device 같은 시스템에 존재하는 자원에게 Name Space(simbolic name)를 제공(Unix/Linux에서는 path와 같은 형태..)

> Device File : 일종의 스페셜 파일을 생성하여 파일과 디바이스를 연결시키기

- 일반 데이터 파일로 관리

- /dev 밑에 file의 형태로 존재

- 하나의 디바이스에 여러 이름의 파일을 붙일 수 있음

ex. /dev/psaux, /deb/psmouse = serial mouse

* File의 데이터

- Real Data

- Metadata : file의 특성을 표현하는 부가적인 데이터

: 생성일, 수정일, 엑세스 권한 등

- Device File의 metadata

- Device Type : block, charactor

- Major Number : 어떤 타입의 디바이스인지 나타내는 필드. tty, 

- Minor Number : 대상이 되는 디바이스를 구별하기 위해 디바이스 드라이버에게로 보내는 argument. (Kernel don't care)

# Trashing 

> Trashing이 발생하는 과정

1. 시스템에 충분히 많은 Process가 동작 중

2. 동작중인 프로세스가 요구하는 메모리가 가용한 물리 메모리보다 많아서 Page Fault 발생

3. page fault를 처리하는 동안 프로세스는 block 당하고 CPU Utilization이 낮아짐

4. CPU Scheduler는 시스템이 한가한 것으로 판단하고 더 많은 프로세스를 실행하려고 함

5. Memory는 점점 부족하게 됨

=> Trashing은 모든 프로세스가 하나의 physical memory pool을 공유(global page replacement)하기 떄문에 발생하게 됨 

=> Local Allocation(per-process, per-job)을 통해 Thrashing을 해결할 수 있는가?

: 해결할 수 없음. 특정 프로세스가 과도하게 메모리를 사용하여 다른 프로세스가 영향을 받는 현상은 막을 수 없음.

하지만, 시스템의 메모리가 부족한 상황인 경우 어떤 프로세스가 충분한 메모리를 확보하고 있더라도 메모리가 부족한 다른 프로세스에 의해 페이지 폴트 처리가 지연됨에 따라라 성능이 급격히 나빠지는 현상이 발생

> Trashing이 발생하는 본질적인 이유?

현재 active하게 사용되는 메모리보다, physical memory가 부족하기 때문에 발생

* 결국 해결법은, 불필요한 프로세스를 suspend(swapping)나 terminate시키기. (degree of multiprogramming을 낮추기)

* Smartphone 처럼 Swap Device가 없는 경우 많은 프로세스로 인해 메모리가 부족하게된다면?

: suspend(swapping)을 할 수 없으므로, Android의 Low Memory Killer등을 사용하여 프로세스를 Terminate.

* Trashing을 체계적으로 극복하는 방법은?!

# Working Set

: 어느 시점에 특정 프로세스가 Access하는 page들의 집합(프로세스의 locality)

- 1960년대, Peter Demming이라는 사람이 생각해낸 아이디어

- 특정 프로세스이 수행되는 전체 life time동안 working set은 변함 (sub-routin call, jump)

=> locality도 변하게 됨

* Prepaging(Prefetching) : 실제 page 요청이 있기 전에 향후 Access 될 것으로 예상되는 페이지를 미리 메모리에 로드하는 것

> Working Set을 이용한 Prepaging

* Longterm Scheduler : degree of multiprogramming을 낮추기 위해 프로세스를 계속 모니터링하여 메모리의 사용이 없는 프로세스를 선정하는 스케줄러

  Shorterm Scheduler : 다음에 돌아야하는 프로세스를 선정하는 스케줄러

- How ?? Working Set Parameter - 현재부터 과거동안 access된 page 들

- working set param들의 갯수가 너무 적으면 충분한 working set을 확보하기 어렵고,

working set의 windows 사이즈가 너무 크면 불필요한 page들도 포함하게 됨

=> 적합한 working set을 찾아내야 하는 필요가 있음

> Working Set의 단위

- 시간? 어떤 프로세스가 항상 동작하는 것이 아니므로 시간으로 단위를 잡기는 어려움

-  Page Reference 패턴? Page Reference 횟수?  어떤 페이지는 여러 프로세스에서 엑세스 되므로 불필요하게 Working Set으로 잡힐 수 있음

=> working set을 잡는건 어려운 일임

# Working Set의 approximation

- 가정 : 현재 수행중인 프로세스에서 Trashing이 일어나지 않고 잘 수행중이면, 현재 할당된 page들은 그 프로세스의 working set일 가능성이 높음

-  OS는 프로세스의 Page fault를 가지고 현재 프로세스의 수행 상태를 알 수 있음

=> key point !!

> Resident Set

: 어떤 프로세스가 어느 시점에 메인메모리에 가지고있는 페이지 들

* Resident Set이 의미를 가지려면!?

- 프로세스가 fork되는 시점에 프로세스에서 일정한 양의 page frame을 allocation 

- system wide하게 upper bound를 설정.  page fault가 upper bound를 넘어서 발생된다면 해당 프로세스에게 좀 더 많은 frame을 할당(high watermark)

- low bound를 설정. page fault가 low bound보다 낮게 발생된다면 working set windows가 불필요하게 많이 할당되었다는 의미. (low watermark)

<Page Fault 발생 횟수에 따른 운영체제의 Memory 할당 정책>

- Threshold 보다 많이 발생하는 경우 : 해당 프로세스에게 더 많은 메모리를 할당

- Threshold 보다 적게 발생하는 경우 : 해당 프로세스에게 할당된 메모리를 회수

# Memory Management의 Trends

<이슈>

1. Physical Memory의 크기가 커짐

- Page Frame이 넉넉해짐

- Page replacement의 중요도가 줄어들고

- 하드웨어적 서포트가 줄고, 소프트웨어적으로 처리하게 됨

- page의 크기가 커지며,  커버하는 instruction의 크기도 늘어나며 hit rate이 높아지게 됨

2. Virtual Memory의 크기가 커짐

- 64bits with 4K page

-  Large Virtual Memory Management의 중요도가 높아짐

3. Memory Management가 OS의 다른 요소들과 결합

- 과거에 없던 색다른 서비스를 제공 : File System과 접목...

4. Large Page Table의 Handling

- 문제 :

1. page table을 유지하기위해 필요한 공간이 너무 큼

2. page table의 물리 메모리에 연속적인 공간에 존재해야 함 

=> 조각의 단위로 쪼개어 관리하는 기술이 필요

<해결방법>

1. Hierarchical page table ; table space를 줄이진 못하지만 , physical memory상에 조각으로 나누어 적재될 수 있도록

<Two-Level Page Table>

- 32bit 환경에서,

Page Number(22bits), offset(10bits)

=> Page Number = First Level Index(14bits) + Second Level Index(8bits)

* First Level Index == Outer Level Index

- Page Table Entry : 1 word size, 4bytes

- Page Table Size : 2^22 X 4 bytes = 16MB

- 한 page에 존재하는 Page Table Entry의 수 : 256 entries (8 bit)

- 한 Page Table에 존재하는 Page들의 수 : 16K (14 bit)

- First Level Page Table의 크기 : 16K x 4bytes = 64KB

- 공간상의 문제에서 장점을 보이나, 속도면에서의 단점이 있음

2. Hashed page table : page table space의 사이즈를 엄청나게 줄일수 있도록

: hashing기법을 사용하여 page table을 구성

page number를 hash table에서 얻어오기.

3. Inverted page table : page table space의 사이즈를 엄청나게 줄일수 있도록

: 모든 user Process는 독립적인 공간을 같기 떄문에 관리를 위해 별도로 큰 page table을 갖음

- address space 만큼 page table을 갖는게아니라 physical memory만큼 page table을 갖자.

* virtual address space사이즈가 아닌, 실제 시스템에 존재하는 page frame의 갯수만큼 page table을 갖는다.

# Page Replacement Policies

> Page replacement Algorithms

1. Random - 주로 하드웨어 적으로 구현할 때 사용

2. FIFO

- Linked List로 구현

3. Optimal - 가장 먼 미래까지 전혀 사용되지 않을 페이지를 교체. 

* Reference String : Sequenced of Referenced Pages. 어떤 프로세스가 수행하는데 프로세스가 ref했던 시퀀스.

4. LRU - Least Recently Used. 최근에 가장 사용되지 않은 페이지들을 교체. 

Temporal Locality에 기반한 Page Replacement 정책.

Timestamp 사용하여 page frame 하나하나마다 count 정보를 저장해야 하지만 굉장히 오버헤드 크기때문에 Counter 대신 Reference Bit를 사용하기로 함

<Memory Management에서 사용되는 flag bit 종류>

* Reference Bit : Use Bit, Main Memory에 로드된 페이지가 엑세스 되면 Set되는 Bit Flag.

* Resident Bit : 내가 사용려는 page가 1이면 현재 Ram에 존재하고 있을때, 0이면 swap device에 있을 때

* Dirty Bit

> Belay's anomaly : FIFO의 문제점을 명시. 메모리를 늘렸음에도 불구하고 페이지폴트가 더 많이 발생하는 현상

* Stack Algorithm : N개의 Frame으로 구성된 메모리에 로드된 Page들이 항상 N+1개의 Frame으로 구성된 메모리에 로드된 page들의 부분집합이 되는 알고리즘.

절대 Belay's anomaly를 나타나지 않음

ex. LRU ...

(이름이 stack algorithm인 이유는 항상 나가고들어오는 부분이 stack처럼 어느 부분에서만 일어나기 때문에 stack에 비유)

* Page Replacement를 수행할 때, 미래를 예측하여 수행하면 굉장히 효율적일 것이나, 현실적으로는 불가능.

하지만 프로그램은 Locality라는 속성을 가지므로 과거를 통해 미래를 어느정도 예측할 수 있음.

=> LRU algorithm

> LRU

1. reference bits algorithm(8bits)

: reference bits를 하나 두고 8개의 8bits 짜리 register를 붙인 후, 일정한 간격으로 reference bits을 shift right하여 가장 사용이 안된 것을 고름. 

=>  사용여부 체크(00000000이 0이므로 가장 작겠지)

액세스의 여부만으로는 정확한 우선순위를 정하기 어렵기 떄문에, OS는 시간을 일정 간격으로 시간을 나눈 후 해당 interval에서 사용이 되었는지의 여부를 체크

2. Clock Algorithm

: linear한 frame들을 clock처럼 wrap around 형태로 연결 시킨 후, 현재 가리키고있는 임의의 페이지를 가리키는 clock hand로 페이지를 교체할 시점엔 어느페이지를 선택할 지 결정해야 함

* Clock Algorithm에서 교체할 Page를 선택하는 방법 

: Clock Hand가 가리키는 page의 reference bit이 1인경우, 0으로 바꾸고 Clock Hand가 다음 page를 가리키도록 함(최근에 사용되었다는 의미이므로 skip). 이 과정을 반복하다가 reference bit이 0인 page를 만나면 최근에 사용되지 않은 page이므로 해당 page를 교체체.

(UNIX OS 에서 많이 사용되는 알고리즘)

- 모든 reference bit이 1이면 모든 page가 reference 되고 있다는 의미이므로 main memory가 현재 overcommit되고 있다는 의미이며, 모든 페이지가 빈번하게 access되고 있으며 skip구간이 굉장히 많이 되므로 clock hand도 빠르게 회전하게 됨

=> clock algorithm은 LRU algorithm을 기반으로 업그레이드 한 것이지만, 메모리 Over Commit이 일어나게되면 FIFO algorithm으로 전환됨

3. Enhanced clock algorithm

- reference 안됐고 clean한 page

- reference 안됐고 dirty한 page

- reference 됐고 clean한 page

- reference 됐고 dirty한 page

* 기본적으로 clean한 페이지를 dirty한 페이지보다 우선적으로 처리한다. clean하면 swapping시 따로 지워주지 않아도 되므로 비교적 처리가 쉬움.

=> but, clean page라고해서 무조건 내보내는게 좋은 건 아니다. code page일 수 있다?

* Micro Architecture의 MMU기능의 단순화로 reference bit을 지원하지 않는다면?

> FIFO 사용

> Frame Buffering : 단순 FIFO를 기반으로 빈번하게 사용되는 frame을 다이나믹하게 관리하여 유용하게 사용하기 위해 free list를 사용

- used page frame list (linked list)

- free page frame list (linked list)

* Optimization : clean page와 dirty page가 섞여있는 free list에서, swap device와 DMA Controller가 IDLE 하다면, dirty page를 Swap-out하여 clean하게 해주기!

# Page Replacement Style

: allocation style

1. Global replacement

: 시스템 단위로 replacement

- 단점 : 메모리를 지나치게 사용하는 동작이 있다면 메모리를 효율적으로 사용하기 어렵다.

- 장점 : 메모리를 모두 고르게 분배하여 사용하면 메모리를 낭비없이 효율적으로 사용할 수 있다.

2. Per-process replacement

3. Per-job replacement(per-user replacement)

* 2,3번의 경우에는 Process나 Job단위로 나누어 replacement되므로 

간섭을 받지 않는다는 장점이 있지만, 어떤 부분은 메모리가 모자를수도, 어떤 부분은 메모리가 남아돌수도 있는 단점이 나타날 수 있음.

=> 할당되는 메모리를 dynamic하게 조절해 줄 수 있는 기능이 추가적으로 필요

: 단위시간동안 Page Fault횟수를 확인하여 메모리가 남는지 부족한지를 판단하여 이용한다.

# Demanding Paging

: 메모리 관리 매커니즘(MMU 매커니즘)을 사용해서 여러 프로세스가 시스템 메모리를 효율적으로 공유할 수 있도록 하는 기술

: 어떤 프로세스가 수행될 때, 집중되는 page들을 필요할 때 읽어들이기.

: 페이지가 요구될 때, 메모리에 불러오는 정책

* Principle of Locality(Locality of Reference)

: 프로그램이 가장 최근에 접근했던 데이터를 다시 접근하거나(Temporal Locality), 

최근에 참조했던 데이터 근처의 주소를 참조하는 경향이 있음(Spatial Locality)

* 90/10 Rule

: 불과 10%의 코드가 프로그램 총 수행시간의 90%를 차지함. (loop)

* Swap Device

: Physical Memory에 저장되지 못한 Page들을 저장하는 디스크의 공간

: 저장 단위인 file은 I/O시에 OS의 여러 기능이 동작해야하므로 굉장히 느리기 떄문에 File과 별도로 direct access가 가능한 low disk block.

: swap device가 가득찬 경우는 file을 swap 영역으로 사용할 수 있음

> Demand Paging의 Policy

: Physical Memory와 Swap Device 사이의 데이터 전송을 최소한으로 발생하도록 함

* Memory Access Latency

레지스터(1 사이클) < L1 캐시(수 사이클) < L2 캐시(수십 사이클) < Main Memory(수백 사이클) < Disk (수백만 사이클)

* Thrashing 

: 프로세스들이 사용하는 페이지들의 크기보다 사용이 가능한 물리 메모리의 크기가 작을 때, 사용하려고 swap-in하는 페이지들에 의해 앞으로 사용할 페이지가 swap-out되면서 반복적으로 Page Fault가 발생하는 현상

> page table entry가 virtual memory management를 지원하려면,

target 주소가 ram이 아닐때를 구분할 수 있는 flag가 필요. 

* Resident Bit 

: 대상 페이지가 물리 메모리에 있는지, 스왑디바이스에 있는지 구별해주는 플래그

> Virtual Memory 사용의 key!

: 값싼 Disk를 사용하여 비싼 메모리를 사용하는 것처럼 구현하여 사용하자.

> Demanding Paging 구현의 기술적 이슈

- Page Fault :  virtual address가 가리키는 page가 physical memory에 없어서 프로세그가 더 이상 진행할 수 없는 상태를 OS에게 알려주는 일종의 소프트웨어 인터럽트

* page fault handler : 인터럽트 서비스 루틴을 수행

<Page Fault Handling>

1. DMA Controller에게 해당 페이지의 주소를 전달

2. DMA Controller는 해당 페이지를 physical memory로 로드

3. DMA Controller의 작업이 끝나면 인터럽트 발생

4. OS는 page fault를 일으킨 프로세스의 수행을 재개

> Page Fault Handling이 다른 인터럽트 처리보다 어려운 경우

: 인터럽트는 수행중인 instruction에 의해 변화된 상태를 되돌렸다가 page fault 처리가 끝난 후 해당 instruction을 재개해야하기 때문

=> page fault 모든 수행에 일어날 수 있으므로 instruction 재개가 굉장히 어렵기 때문에 에외적으로 처리하게 됨 (virtual memory를 지원하기가 어려움)

* MOVE (SP)+, -(R2)

: SP가 가리키는 메모리 location의 값을 R2의 값을 하나 감소시킨후 copy하라.

* VAX의 경우는 애초부터 virtual memory를 지원하도록 설계하였는데 

CISC Instructiond은 restart가 어렵기 때문에 마이크로 코드로 다시 프로그램되어있으므로 마이크로 코드로 리버스 시킴(페이지폴트 발생시 인스트럭션 수행중의 변화시켰던 모든 레지스터 state를 복구하고 핸들링이 끝나면 다시 이전의 instruction이 restart되도록)

* 요즘은 RISC 방식으로 구현되며, RISC는 restartable하게 구현

> 정리

과거에는 프로그램이 수행될 떄, 프로그램과 관련한 모든 메모리가 전부 물리메모리에 있어야 하므로 비싼 메모리의 가격이 문제가 되었음.

비싼 메모리를 줄이고 싼 디스크를 swap device로 사용하는 virtual memory management라는 기술이 발전하였음.

Virual Memory Management는 virtual memory address를 physical memory address로 전환해주는 하드웨어인 MMU의 지원이 꼭 필요함

> HW 트렌드가 변화되면서 여러가지 대응해야 할 이슈

swap device를 쓸 수 없는 과거상황으로 돌아가는 경우

"스마트폰" 디스크가 없고  solid state disk(flash memory)를 secondary disk로 사용

flash memory는 ROM으로 Erase횟수가 제한이 있으므로 swap device로 사용할 경우 수명이 급격히 줄어들게 됨

> Demanding Paging은 페이지가 요구될 때 메모리에서 불러오므로 페이지가 요구되는 시점에 ram regident하지 않고 그 때 요청을 하게되면 page fault가 발생할 수 있으며 속도가 매우 느려질 수 있음 => 미리 예측하는 policy를 갖도록 하자!

* 이상적인 Page Selection Policies

:  앞으로 사용될 페이지를 미리 메인메모리로 가져와서 페이지 폴트가 발생하지 않도록 하는 방법

1. Demand paging : 

- pure demanding paging

- 프로세스가 시작할 때 메모리에 0개의 페이지로 시작하며, 엔트리 포인트에 들어갈 때 처음 인스트럭션부터 page fault가 발생하여 초반부에 엄청난 page fault가 일어나게 됨. 이후 충분한 페이지를 잡으면 원활하게 프로세스가 동작하게 됨.

- 가장 단순하지만, 프로세스가 생성되서 시작을 할 때 너무 오랜 시간이 소요됨.

2. Prepaging : 앞으로 사용될 페이지를 예측해서 미리 Main Memory로 로드하는 방법

- 한페이가 요청되면 인접한 페이지까지 로드

   => 효과적인 prepaging 방안 : Spatial Locality에 기반하여 page fault가 발생한 근처에 있는 페이지들을 Main Memory에 로드

3. Request Paging : 논리적으로 연관성이 있는 페이지들을 미리 Main Memory에 로드

- 과거에 사용했던 기법

- 예. Overay

=> 사용자가 결정해서 사용해야하는 불편함이 있음.

=> Working Set 대두!

> 여러가지 관점

1. 어떤 페이지를 언제 물리메모리로 불러올 것인지. Page selection policy

2. 스와핑 대상을 고르기. Page replacement policy

3. replacement를 수행할 때, 전체 프로세스들 중에서 고를지, 특정 그룹의 프로세스들에서 고를지. Page replacement style

4. page들을 어떤프로세스에게 page frame을 할당할때. Page placement style

> 카페

  http://cafe.naver.com/ojsag

> 네이버 SVN

  http://dev.naver.com

  * 멤버등록

  * 암호설정

> 이클립스

  * plug-in  

  * SVN Repository

https://dev.naver.com/svn/ojsag20

subclipe 설치 > SVN  설정 > checkout

> 소프트웨어 개발 패러다임

구조적     >     정보공학     >     객체지향 >                 Contents Based Development?                 >     SOA     >     ROA

"절차"            "데이터"                "클래스"                                - Controller - Suvlet

    멤버(필드, 메소드)                         - View - html, xml

  - Model - JSON

* library와 Contents의 차이

: library는 그냥 모듈화, Contents는 MVC 모델을 포함하는 모듈화

> 프토토콜

비연결지향 (HTTP)

연결지향(FTP)

> 웹

"비연결지향 프로토콜의 단점을 해결하기 위한 기술"

1. Client Side

쿠키

2. Server Side (서버상태를 저장하기위한 객체 4가지)

PageContext 페이지

HttpServletRequest

HttpSession 웹브라우저

ServletContext 톰캣

3. File

4. DBMS

 > 요청 (Client Side - HTML5 + CSS + JavaScript + jQuery + Ajax)

URL

> 응답 (Server Side - Controller + View + Model Service + Model Entity)

HTML, XML, JSON, Text, ...

> 소프트웨어 공학

95년도 4학년 과정으로 선택과목으로 등장

2000년도 이후 필수과목으로 채택

"품질" - ISO 9126(6가지 품질), IEEE 1471(아키텍처 표준), ISO 52000(테스트 표준)

"객체지향"

> 소프트웨어 위기

"스파게이티 소스"

> 클래스 vs 객체지향

1. 저장위치

- 클래스 : 파일이므로 하드디스크

- 객체 : 파일의 클래스 로더가 클래스를 로딩하여 메모리에 올림. 값을 담기위해 만들어진 구조체.

2. 값의유무

> 객체 라이프 사이클

1. 클래스 정의

2. 객체참조변수 선언

3. 객체생성

4. 생성자호출

5. 주소할당

6. 객체사용

7. 객체소멸

"    Student st = new Student();   "

1. 클래스 정의 : Student. Student는 이미 정의되어 있어야 함.

2. 객체 선언 : st, 

3. 객체 생성 : new, 개발자가 직접 객체를 생성하느냐, Controller에게 객체생성을 위임하느냐(IoC), 

* has a, is a 관계

dependency, association, composition, aggregation

4. 생성자 호출 : (). 

5. 주소할당 heap메모리를 "st" 객체참조 변수에 assignment :  =. call by value, call by reference, call by name(없어짐)

6. 객체사용. polymorphism

7. 객체소멸.  java performance tuning 

java - " fojo, annoation "

> OOSD 기본 개념 7가지

<Object-Oriented Design concepts>

Cohesion 응집도. 하나의 클래스가 하나의 기능에 얼마큼 충실하는지 나타내는 척도. 높을수록 좋음.

Encapsulation. 

Coupling 결합도. 응집도를 높이기위해 클래스를 잘게 나누면, 원래 하나였던 클래스는 서로의 결합도를 높이게 됨. 모듈화의 결정 포인트를 잘 맞춰야 함. 낮을수록 좋음.

*Looser Abstract Coupling

Implementation ingeritance .

Composition

Interface ingeritance

Polymorphism

<java method 5가지>

> *Looser Abstract Coupling

---------------------------

client  -->   <<interface>>

Service

^

|

|

ServiceImpl

---------------------------

interface Service {

}

class ServiceImpl implements Service {

}

class Client {

Service s;

}

cf. looser couping

 http://tadhg88.blogspot.kr/

> 클래스 간의 관계

* Is-a

* has-a

> OOSD 원리 3가지

> 디자인 패턴

> 웹 서비스

-----------------------------------------------------

홍창윤 강사님 / 010-3206-4184 / hiroad@naver.com

OJSAG 오라클자바소프트웨어아키테트그룹

# Paged Segmentation

: paging + segmentation

: 먼저 Segmentation 한 후, 그 다음 Paging을 수행

* why ?

: paging을 통해서 segment의 fragmentation의 문제는 해결할 수 있으나, 프로세스에게 multiple segment를 제공하고자하는 부분은 놓치게 됨. 

* 2번의 메모리 access로 인한 속도저하의 문제

: TLB(Transration Look Aside Buffer)를 사용하여 극복  => Cache 사용

--------------------------------------

|CPU Register | Cache | Memory | Disk |

--------------------------------------

* Paged Segmentation의 table 관리

- 기존의 segment table의 정보 : Segment number(Index, 상위비트), base address, bound address, 

- 기존의 page table의 정보 : Page number(index), frame number(page가 어느 physical공간에 있는지의 정보), 

: Paged Segmentation table에는 기존 Base address 대신, Segment의 Page table의 위치를 저장

: Paged Segmentation table에는 기존 Bound address 대신, 해당 세그먼트의 페이지 갯수를 저장

* Paged Segmentation 단점

; 1 memory access reference 당, extra memory reference가 3번 일어남

* 예제 - 24bit virtual address space에서 physical address 찾기

---------------------------------------------------

| Seg # (4bits) | Page # (8bits) | Page Offset (12bits) |

---------------------------------------------------

> logical address 0x    00        20         70

  1bytes  1bytes    1bytes    => 3bytes

> <segment table>

--------------------------------------

Base        |        Bound        |    prot

0x2000  |        0x14           |      R

0x0000  |        0x00          |    

0x1000   |        0x0D          |    RW

-------------------------------------

> <memory>

--------------------------------------------

0x001F

0x0011                    -> 0x2020

...

0x0003

0x002A

0x0013                   -> 0x2000

0x000C

0x0007                  -> 0x1020

...

0x0004

0x000B

0x0006                 -> 0x1000

--------------------------------------------

> 0x0(4bits)     |        02   (8bits)         |     0 70(12bits)

   1. seg table no.          Page Num                    offset

> 1. seg table no : 0

메모리에서 no가 0인 segment table을 찾음.  즉 base address는 0x2000이므로 메모리에서 0x2000을 찾아감

   2. Page Number : 02

binary 2. 즉 3번째 엔트리 값. 메모리상의 0x2000주소에서부터 2번째의 값을 찾음, 0x0003 이므로 찾은 값은 03.

   3. concatenation : Page Number의 값 03 + Offset 070 => 0x003070

> 결론

   virtual address : 0x002070

   physical address : 0x003070

* Segment Table과 Page Table을 사용한 주소 변환

> MMU에 의하여 하드웨어 적으로 수행됨

> 그러나 프로세스 문맥전환이나 새로운 프로세스의 생성등이 일어날 때, 

  운영체제가 Base/Bound Register 및 Segment/Page Table을 관리해야 하므로 운영체제에게 Transparent 하지 않음

* Paged Segmentation

- 프로세스의 logical unit들의 메모리 액세스 컨트롤을 용이하게하며, 

- 프로세스들 간의 세그먼트 공유를 용이하게하고,

- paging을하므로  external fragmentation의 문제를 해결

* address translation에 의한 메모리 관리의 2가지 주의점

- performance overhead

- space overhead

* Paged Segmentation 장단점

장 : page table space를 줄일 수 있음. segmentation을 사용하므로 pure paging에 비해 hole을 줄일 수 있으므로 공간 절약이 가능

단 : address translation 할 때, 메모리 엑세스 수가 많음

* but, 많이 사용되는 리눅스 OS에서는 pure paging 기법을 사용하여 메모리 관리함

> 과거 segment단위로 메모리 액세스 컨트롤을 page table로 다 내림. page 단위로 컨트롤

> sharing도 page 단위로 수행

=> OS에서 page를 segment영역(data, stack, text..)별로 선정하여 정보를 가지고 관리하게 됨. Machine independent. 

* Machine(HW) Independent, dependent의 차이

- Micro Architecture (CPU ...)

- System Architecture (메모리 구조, bus ...)

- I/O devices

* 대표적인 machine-Dependent한 코드

: context switching, Proccess 생성,  I/O 관리, Memory 관리, ...

> 모든 하드웨어가 segmentation를 지원하지 않기때문데 모든 하드웨어에서 사용되기 위해 pure paging을 사용하여 소프트웨어적으로 segmentation에 해당하는 부분을 OS가 지원하여 portability를 구현.

* Page Frame의 특성

- mapped page : translation을 거쳐 메모리 영역을 액세스하여 paging 기법

- unmapped page : translation 없이 물리 메모리에 directly하게 액세스 할 수 있게할 때 사용(page table,...)

- cached page : L1, L2 캐시를 사용 시, 성능 향상을 위해 한번 특정 워드가 액세스 되면 일반 페이지들은 모두 캐시를 시켜 hit을 시킴

- uncached page :  DMA의 대상 Page처럼 여러 프로세스에 의해 동시에 I/O가 sharing되면서 일어나면 경우 caching을 안되므로 uncached page로 만들어 사용

     (DMA : CPU Bus에 Master가 여러개가 존재하여 I/O를 동시에 가능)

* Large Page Table이 가지는 문제의 해결 조건

- Page Taable의 크기를 줄임

- 연속적인 메모리 공간 요구량을 줄임

# VAX 

: 1980년대, Large Page Table의 문제를 해결하기 위해 나온 컴퓨터 하드웨어

:  VMS Operating System 

: full name은 Virtual Address eXtension으로, 아키텍처를 디자인 할 떄 부터 virtual memory를 잘 다루기위해 설계

> 전체 virtual space를 4개의 segment로 나눔

- System Segment(os영역)

- P0 Segment(user영영1)

- P1 Segment(user영역2)

- unused Segment

<전체 Virtual Memory Space>   -------> virtual memory space이므로 mapped page 영역

-------------------------------

System Virtual Memory                    -> System 영역 메모리 공간

User Page Table (System 영역도 virtual memory space에 있으므로 모두 가상주소로 표현됨.
                             가상메모리 공간에는 연속적으로 위치하지만 실제 물리메모리에는 연속적으로 위치하지 않음)

...

--------------------------------

    -> User 영역 메모리 공간

User Virtual Memory                        

(P0, P1)

--------------------------------

* physical address를 얻기

: User Page Table 테이블에서 얻은 값을 physical address로 얻기위해 OS는 Operating System의 주소를 가지는 physical memory의 page table에 접근해야함.

즉, physical memory  상에 연속적으로 OS의 주소를 변역하기 위한 page table을 저장하고 있어야 함.

1. User generates address.

2. Lookup in User Page Table.

3. Lookup in System Page Table. (Physical Memory)

4. Access physical address 

=> Address Translation 시, Overhead는 증가하지만, Large Page Table의 문제를 해결할 수 있음

# TLB 

: Translation Look aside Buffer

: 캐시를 사용하여 성능의 개선을 목적으로 개발

> Hit rate을 높이기 위해선 

1. 크게만들자? 그런데 64개~ 128개만 되어도 98%의 적중률을 달성할 수 있게됨  

why? Locality라는 특성을 가지기 때문에 적은수만 가져도 적중률을 크게 향상시킬 수 있음

- Spatial Locality : 수행된 부분의 위나 아래에 위치한 부분이 수행되는 것.

- Temparal Locality : 매우 짧은 시간안에 재수행되는 것. 

=> loop의 영향

2. page의 사이즈를 키우면 한 페이지 엔트리가 커버하는 어드레스 스페이스가 커지므로 hit rate를 높일 수 있음

> TLB의 구성 (컴퓨터 조직론)

: cache를 구성하는 세가지 방법처럼 구성

1. 순차적으로 모두 검색

2.page table entry를 특정영역에 mapped하여 찾기. Direct mapped cache. 저렴하지만 collision이 발생하면 hit rate이 떨어질 수 있음.

-> Set associative cache로 극복

3. Fully associative cache. 빠르지만 비쌈.