24.02.16 간단한 정리, 코드리뷰에 대해, 백준, C++

간단한 정리

9. 가상메모리

• 가상메모리는 각 프로세스에 하나의 크고 통합된, 사적 주소공간을 제공한다.
• 가상메모리의 세 개의 중요한 기능
  1. 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급해서 메인 메모리 내 활성화 영역만 유지하고, 데이터를 디스크와 메모리간에 필요에 따라 전송하는 방법으로 메인 메모리를 효율적으로 사용한다.
  2. 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다.
  3. 각 프로세스에 의한 손상으로부터 보호한다.

9.1 물리 주소 가상주소 방식

• 물리주소에 순차적으로 접근
• 가상주소 : CPU가 가상주소를 생성해서 메인 메모리로 접근, 메모리로 가기 전 주소번역 과정을 통해 물리주소로 변환한다.

9.3 캐싱 도구로서의 VM

• 결과적으로, 가상메모리는 디스크에 저장된 N개의 바이트 크기의 셀 배열로 구성된다. 각 바이트는 특정한 가상주소를 가지며 배열의 인덱스로 작용한다.
• VM System은 가상메모리를 규정된 사이즈 블록 단위로 분할하여 관리한다. 분할된 블록들은 가상페이지라고 부른다.

가상페이지

• unallocated : 할당되지 않은 페이지
• cached : 물리 메모리에 캐시되어 할당된 페이지들
• uncached : 물리 메모리에 캐시되지 않은 할당된 페이지들

페이지 오류(page fault)

• DRAM에서의 캐시미스

9.4 메모리 관리를 위한 도구로서의 VM

• 다수의 가상 페이지들이 동일한 공유된 물리 페이지에 매핑 될 수 있다는 점에 주목해야한다.
• 요구 페이징과 분리된 가상 주소공간의 조합은 메모리가 사용되고 관리되는 방식에 중요한 영향을 미친다. 특히 VM은 링킹과정과 로딩, 코드와 데이터의 공유, 응용으로의 메모리 할당을 단순화 해준다.

9.5 메모리 보호를 위한 도구로서의 VM

• 메모리 시스템에 접근하는 것을 제어할 수 있는 수단을 제공한다.
• 사용자 프로세스는 자신의 읽기-허용 코드 섹션을 수정하도록 허용되지 않아야한다. 또한 커널내의 코드와 데이터 구조들도 읽거나 수정할 수 없어야 한다. 모든 관련 프로세스들이 명시적으로 허용하지 않았다면, 다른 프로세스의 사적 메모리를 읽거나 쓸 수 없어야한다.
• PTE 허가 비트 추가
  • SUP : 수퍼바이저, 커널모드로 돌고 있는지 확인, 사용자 모드에서 돌고있는 프로세스는 SUP 0인 페이지만 접근 가능하다.
  • READ, WRITE 비트는 이 페이지에 대한 읽기, 쓰기 접근을 제어한다.
  • 이를 위반하면 리눅스 쉘은 세그먼트 오류라고 보고한다.

동적메모리 할당

• 프로그램이 실행되기 전에는 그 크기를 알 수 없는 메모리 영역을 런타임시에 획득하기 위해 동적메모리 할당을 사용한다.
• 동적메모리 할당기는 힙(heap)이라고 하는 프로세스의 가상메모리 영역을 관리한다.
• 커널은 힙 영역의 꼭대기를 가리키는 포인터를 사용한다.
• 메모리 할당기는 힙을 다양한 크기의 블록 단위로 관리한다.
• 메모리를 할당하는 방법에는 명시적, 묵시적 할당법이 있다.

명시적 할당

• 응용 프로그램이 할당하고, 반환한다
• malloc, free

묵시적 할당

• 응용 프로그램이 할당하지만, 직접 반환하지는 않는다.
• 이를 위해서 더 이상 프로그램에 의해 사용되지 않는 블록을 검출할 수 있어야한다.
• 자바에서는 가비지 컬렉터가 있고, 자동으로 사용하지 않는 할당된 블록을 반환시켜주는 작업을 가비지 컬렉션이라 부른다.

할당기의 요구사항

• 할당된 블록의 갯수와 크기는 조정할 수 없다.
• 임의의 순서로 들어오는 요청을 처리한다.
• 모든 할당 요청에는 즉시 응답한다.
• 블록은 프리메모리 에서만 할당해야한다.
• 블록들은 모든 주소 맞춤 요건을 만족하도록 정렬해야한다.
• 프리메모리만을 관리하고 수정할 수 있다. 일단 할당된 블록들을 이동할 수 없다.

성능지표

1. 처리량 : 단위시간동안 완료한 요청의 수
2. 최대 메모리 이용률 : 현재 할당된 데이터들의 합/현재 힙의 크기

단편화

• 내부 단편화는 할당된 블록이 데이터 자체보다 더 클 때 일어난다. 힙 자료구조를 유지하고, 정렬을 위해 바이트를 추가하거나 할당 정책의 한 오버헤드 때문에 일어난다.
• 외부 단편화는 할당 요청을 만족 시킬 수 있는 메모리 공간이 힙 전체를 합쳤을 때는 존재하지만, 해당 요청을 처리할 수 있는 단일 가용블록이 존재하지 않는 경우에 발생한다.

malloc과 free 구현시 고려사항

• 가용블록을 지속적으로 추적하고 관리할 수 있어야한다.
• 가용블록보다 작은 크기의 구조체를 할당할 때, 남는 공간을 어떻게 할 것인지 고려해야 한다.
• 할당을 위한 가용블록은 어떻게 선택해야 할지 고려해야 한다.
• 얼마만큼 free 시켜야 하는지 알 수 있어야 한다.

free 블록 관리하기

관리법

• 간접(묵시적) 리스트 방식 : 블록의 크기 정보를 이용해서 모든 블록을 연결한다.
• 직접(명시적) 리스트 방식 : 가용블록끼리만 포인터로 연결한다.
• 구분 가용 리스트 방식 : 일정한 구간의 크기별로 나누어, 해당 크기 내의 가용리스트를 각각 유지하는 클래스를 만들어서 운영한다.

묵시적 리스트 방식

• 헤더
• 모든 할당기는 블록경계를 구분하고, 할당된 블록과 가용블록을 구분하는 데이터 구조를 필요로 한다. 일반적인 방법으로는 추가적으로 1블록을 사용해 블록 앞에 블록의 크기를 저장하는 방법이 있다.
• 이때 추가적으로 사용되는 1워드를 헤더라고 한다.
• 헤더는 블록 크기와 블록이 할당 되었는지, 혹은 가용상태인지를 인코딩한다.
• 데이터 이후에 사용되지 않는 패딩이 따라올수도 있는데, 이들의 크기는 가변적이다.
  • 외부 단편화를 극복하기 위한 할당기의 전략일 수도, 정렬 요구 사항일수도 있다.
• 특별한 마지막 블록(1/0)이 필요하다. 에필로그 헤더라고 부른다.
  • 마지막 노드를 식별하고 리스트 무결성을 유지하는데 중요한 역할을 한다.
  • 리스트 순회 및 특수 기능 구현에도 활용할 수 있다.

할당할 블록 결정하기

• first fit
  • 처음부터 검색을 시작해서 맨 처음 크기가 맞는 블록을 선택하는 방법이다.
  • 모든 블록의 수에 비례한 시간이 소요된다. 리스트의 시작 부분에 작은 파편이 다수 발생할 수 있다.
  • 리스트 마지막에 가장 큰 가용블록을 남겨두는 경향이 있다.
  • 단점 : 리스트의 앞 부분에 작은 가용블록들을 남겨두는 경향이 있다. 이로인해 큰 블록을 찾는 경우에는 검색 시간이 늘어날 수 있다.
• next fit
  • first fit과 유사하지만, 이전에 검색이 종료된 위치에서 검색을 시작한다는점이 다르다. 이전 검색에서 가용블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어에서 착안한 방법이다.
  • first fit에 비하여 매우 빠른 속도를 가지지만 단편화가 first fit보다 더 심하게 발생한다.
• best fit
  • 리스트를 검색하여 가장 근접한 크기의 블록을 선택하는 방법
  • 단편화를 크게 예방할 수 있으나, 전체 리스트를 탐색하므로 first fit보다 훨씬 느리게 동작한다.

free 블록의 분할

• 할당기가 할당할 가용블록을 찾은 후, 가용블록의 어느정도를 할당할지에 대해 결정해야 한다.
• 한 가지 방법은 해당 가용블록 전체를 사용한다는 것이다. 이는 빠른 속도를 가지지만, 내부 단편화가 발생한다.
• 다른 방법은 가용블록을 쪼개서, 할당한 블록과 새로운 가용블록으로 나누는 방법이 있다.

가용블록 통합하기

• 결합(Coalescing) 과정을 통해 가용블록을 통합해서 오류단편화를 극복하낟.
• 중요한 정책 결정
  • 블록이 반환될때마다 인접 블록을 통해서 즉시연결.
  • 일정시간 후에 가용블록을 가용블록을 연결하기 위해 기다리는 지연연결.
  • 예를 들어 할당기는 일부 할당 요청이 실패할 때까지 연결을 지연 할 수 있으며 그 후 전체 힙을 검색해 모든 가용블록을 연결한다.
  • 즉시연결은 간단하며 상수시간내 수행 가능하지만, 일부 요청 패턴에 대해서는 블록이 연속적으로 연결되고 잠시후에 분할되는 쓰래싱의 형태를 유발할 수 있다.

경계태그

• 반환하려는 블록을 현재 블록이라고 할 때, 다음 가용블록을 연결하는 것은 쉽고 또한 효율적이다. 현재 블록의 헤더는 다음 블록의 헤더를 가리키고 있으며, 이것은 다음 블록이 가용한지 결정하기 위해 체크될 수 있다. 그렇다면 그 크기는 현재 블록의 헤더의 크기에 더해지고, 블록은 상수시간 내에 연결 될 수 있다.
• 그러나 이전 가용블록을 연결할 수 있는 방법이 없다.
• 이전 가용블록을 연결하기 위해 경계태그를 사용한다. 블록 끝에 푸터를 추가한다.
  • 푸터는 헤더를 복사한 것이다.
• 경계태그는 간단하고 유용한 개념이지만, 각 블록이 헤더와 푸터를 유지해야 한다는 단점이 존재한다. 작은 블록을 많이 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있다.
• 이를 극복하고자 할당된 블록에서 풋터를 없애는 방법이 존재한다.

묵시적 가용리스트 장단점

• 장점 : 단순하다
• 단점 : 가용리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용블록수에 비례한다는 것이다.
• 메모리 사용량은 할당 정책에 따라 다르다.

명시적 리스트

• 가용블록들을 이중 가용블록과 다음 가용블록을 가리키는 포인터를 가진 일종의 이중 연결 링크드리스트로 구성하는 방법이다.
• 가용블록은 프로그램에서 사용되지 않기 때문에, 해당 자료구조를 구현하는 포인터들은 가용블록의 본체 내에 저장될 수 있다.
• 할당된 블록의 구조는 묵시적리스트 방식과 동일하며, 가용블록의 구조만 바뀐다.
• 이중 연결리스트를 사용하면 first fit 할당시간을 전체 블록 수에 비례하는 것에서 가용블록수에 비례하는 것으로 줄일 수 있다.

명시적 가용리스트 블록 반환 방법

• LIFO 정책
• 주소정렬 정책 - first fit과 함께 사용하면 best fit 과 비슷한 수준으로 단편화를 예방할 수 있다.

명시적 가용리스트 장단점

• 장점 : 할당시간이 전체 블록수가 아니라 가용블록의 수에 비례한다.
• 단점 : 할당과 반환 과정이 묵시적에 비해 어렵다, 이중연결을 하기 위해 추가적인 공간이 필요하다.

분리가용 리스트

• 할당 시간을 줄이는 대표적인 방법으로 알려진 분리 저장 장치(segregated storage)는 다수의 가용리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장한다.
• 기본적인 아이디어는 모든 가능한 블록의 크기를 크기 클래스(size class)라고 하는 동일 클래스의 집합으로 분리하는 것이다.

크기 클래스를 정의하는 방법

• 대부분 적은 크기 블록들은 매 크기마다 클래스를 갖도록 한다.
• 크기가 큰 경우 2의 제곱마다 클래스를 정의한다.
• 할당기는 가용리스트의 배열을 관리하고, 크기 클래스마다 증가하는 순서로 한 개의 가용리스트를 가진다.
• 할당기 크기 n인 블록이 필요한 경우, 적당한 가용리스트를 검색한다.
• 만일 크기가 맞는 블록을 찾을 수 없다면 다음 리스트를 검색하는식으로 진행한다.

분리가용 리스트의 장단점

• 분리가용 리스트는 높은 throughput을 가진다.
  • 단위 시간당 처리량
• 메모리 이용률 또한 우수한데, first fit 방법을 이용하면, best fit과 유사한 메모리 이용률을 얻을 수 있으며, 각 할당 요청 블록에 대해 그 크기를 클래스로 각각 생성한다면 최적 할당과 동일해진다.

코드리뷰에 대해

• 꼭 한번은 들어보면 좋을 것같은 강의 추천추천~

TEST-Drive Development - 테스트가 기본이다.

• 요구사항과 구현을 분리하라
• 테스트는 언제나 코드와 싱크되어 있다.
• no test, no source code
• 자잘하게 많이 커밋해라

Pair Programming - 선배 어깨 너머로 배우기

• 둘이 나란히 한 컴퓨터로 프로그래밍
• 실력이 정말 빠르게 증가한다.

Code Review - 이해하기 쉽고, 유지보수하기 쉽게

• 꼭 필요한 한 단계이다.
• 당신의 동료로 부터 내 코드를 피드백 받는 것을 의미한다.

It is not about code review

• 소프트웨어 설계를 어떻게 할까 - 이런것은 화이트보드에. 코드리뷰는 코드 체인징에 관해서
• 소프트웨어에 요구 계획 추가나 프로젝트 추가.

Step

• LGTM가 나올때까지 코드리뷰
• 코드리뷰는 읽는 사람을 위한 것이다. - 한달 후 내가 될 수도 있다.

왜 why 필요한가?

• 당신의 CL(Change List)를 이해하기 쉽게 만든다.
  • 당신의 동료가 당신의 코드를 이해할 수 있어야 한다.
• 당신의 CL에 동료가 남긴 의견으로 부터 tip&lessons을 배운다.
  • 숙련된 개발자로부터 코딩스타일과 팁을 배운다
  • 당신의 팀이 공통된 코딩스타일을 공유할 수 있다.
• 결함을 줄일 수 있다.
• 당신의 coding decision에 대한 개발 역사를 보관한다.
  • 동료의 의견은 코드 설계와 결정사항에 대해 이해하는데 매우 큰 도움이 된다.
  • 새로운 개발자는 committed log와 의견으로부터 코드의 구조와 결정사항을 이해할 수 있다.
• 당신의 코드에 일관적인 코딩스타일을 유지할 수 있다.
  • 새로 온 개발자가 기존의 코딩 스타일을 따를 수 있도록 도와준다.
  • 일관적인 코딩 스타일은 이후에 코드를 refactoring 하거나 디버깅할 때 큰 도움이 된다.
• 이러 이러한 이유로 이렇게 바꾸면 좋습니다 , 레퍼런스는 여기를 참조하시면 좋을것같습니다 << 이런식으로 코드리뷰를 하면 매우 좋다.
• 남의 코드를 보면서 자기가 생각하는 것을 말하면서 많이 배울 수 있다.
  • 코드 리뷰를 통해서 대화
• 코드리뷰를 하다보면 코드가 투명해지고, 확장성이 생긴다.
• 코드의 표준이 올라간다.

Possible Downsides of Code Review

• 거칠고 무례한 의견 때문에 CL owners may get discouraged
• 리뷰가 늘어지면 개발기간이 늦어진다.
• 코드 리뷰를 제대로 하려면 시간이 걸린다.
• 경험이 부족한 개발자의 잘못된 CL을 리뷰하느라 숙련된 개발자의 시간이 허비될 수 있다.
• 코드리뷰를 위해서는 어느정도 숙련된 개발자가 필요하다.

Google C++ Style Guide

코드리뷰를 위한 것

• 묵시적인 것으로 에러가 발생한다면 나중에 디버깅하기 매우 힘들기 때문에 명시적으로 선언
• 새로운 기술보다 기본에 충실하라. 하지만 최적화 부분이나, 속도가 차이난다면 속도를 우선시해라.
• 도구가 할 수 있는것은 도구에게 맡겨라.
• 함수는 최소한 작게 구현해라 - 함수는 하나의 일만 해야한다.
• 함수의 이름에서 무슨 역할을 수행하는 함수인지 들어나야한다.

당신의 팀에는 일관적인 스타일이 있는것이 좋다.

Testing

• Testing Rocks! Debug Sucks
• 디버깅은 보통 문제를 찾는데 오랜 시간이 걸린다.
• 테스팅은 새로 작성한 코드에서도 결합을 검출 할 수 있다.
• 테스팅은 테스트 코드를 필요로 하기 때문에, 유지보수 부담을 줄인다.
• unit testing : 함수 하나 하나를 테스팅
• integration testing : 서로 다른 시스템들의 상호작용이 잘 이뤄지는지 테스트하는 것

Project Scalability

• 새로운 개발자도 테스트 코드를 잘 작성해서 프로젝트에 기여할 수 있다.
• 동료나 외부 기여자에게서 도움을 받기에 가장 적합하다.

Code Refactoring

• Refactoring은 SW의 동작을 바꾸지 않으면서 내부 구조를 개선하는 것이다. 즉, 코드의 구조를 잘 정해진 규정대로 수정하는 기술이다.
• SW를 더 이해하기 쉽게 만들고, 수정하는 비율을 줄인다.
• Why
  • SW 설계 개선
  • Refactoring이 없으면 프로그램의 설계가 낡아진다.
  • 설계가 좋지 않은 코드는 보통 같은 일을 하는데 코드가 길고, 같은 일을 여러곳에서 한다.
  • 이해하기 쉽다.
  • 대부분의 SW 개발 환경에서, 누군가 언젠가는 당신의 코드를 읽어야 할 때가 오기 때문에, 그들을 위해 이해하기 쉬운 코드를 작성해야 한다.
  • 결함을 검출 할 때도 있다.
  • 프로그램의 속도를 향상 시킬 수 있다.
    • 프로그램에 대해 더 잘 이해할 수 있기 때문에

백준

2444 별 찍기 - 7

예제를 보고 규칙을 유추한 뒤에 별을 찍는 코드 아래의 코드는 5를 입력 받았다.

    *
   ***
  *****
 *******
*********
 *******
  *****
   ***
    *

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n ;
	
	for (int i = 1; i <= n; ++i)
	{
		for(int j = 1; j<=n-i; ++j)
			cout << " ";
		for (int j = 1; j <= i * 2 - 1; ++j)
			cout << "*";
		cout << "\\n";
	}
	for (int i = n-1; i >= 0; --i)
	{
		for (int j = 1; j <= n - i; ++j)
			cout << " ";
		for (int j = 1; j <= i * 2 - 1; ++j)
			cout << "*";
		cout << "\\n";
	}
	return 0;
}

• 코드를 짜고난 뒤 뭔가 난잡해보여서 찾아봤는데, 대부분 이렇게 2중 for문을 통해서 푸는 것같다.
• 리팩토링을 어떻게 할 수 있을까 찾아봤는데, 자주 쓰는 부분이 있기에 그 부분을 함수로 만들어서 사용하면 좀 깔끔해질 수 있다.

10988 팰린드롬인지 확인하기

알파벳 소문자로만 이루어진 단어가 주어진다. 이때, 이 단어가 팰린드롬인지 아닌지 확인하는 코드

팰린드롬이란 앞으로 읽을 때와 거꾸로 읽을 때 똑같은 단어를 말한다

level, noon은 팰린드롬이고, baekjoon, online은 팰린드롬이 아니다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	vector<char> vec_char;
	string input;

	cin >> input;
	copy(input.begin(), input.end(), back_inserter(vec_char));
	
	for (int i = 0; i < vec_char.size(); ++i)
	{
		if (vec_char.at(i) == vec_char.at(vec_char.size() - 1 - i))
			continue;
		else
		{
			cout << "0";
			return 0;
		}
	}
	cout << "1";
	return 0;
}

• 가장 중요한 부분은 string으로 받아온 input을 copy 함수를 사용해서 vector에 넣는 부분 같다.
• 함수 사용에 익숙하다면 처음과 끝을 계속 비교해가면서 풀면 쉽게 풀 수 있다.

#include <iostream>
using namespace std;
 
bool isPalindrome(string s){
    int len = s.length();
    for(int i=0; i < len/2; i++){
        if(s[i] != s[len-1-i]) {
            return 0;
        }       
    }
    return 1;
}
 
int main(){
    ios_base::sync_with_stdio(false);   // 두 표준 입출력 동기화 해제
 
    string str;
    cin >> str;
    cout << isPalindrome(str);
 
    return 0;
}

• 함수를 만들어서 깔끔하게 푸신분도 있었다.

참조 : https://carrot-farmer.tistory.com/26

C++

copy()

• copy(원본 시작 이터레이터, 원본 끝 이터레이터, 복사받는 시작 이터레이터)