1. Next.js Router 기반 방법들

useRouter + router.push()

const router = useRouter();
router.push('/path');

장점:

• Next.js 최적화 혜택 (프리페칭, 클라이언트 사이드 네비게이션)
• 히스토리 스택에 추가 (뒤로가기 가능)
• 상태 유지 (React 컴포넌트 상태 보존)
• TypeScript 타입 안정성 (App Router에서)

단점:

• Next.js 환경에서만 사용 가능
• 컴포넌트 내부에서만 호출 가능

useRouter + router.replace()

router.replace('/path');

장점:

• 현재 페이지를 히스토리에서 대체 (뒤로가기 시 이전 페이지로)
• 로그인 후 리다이렉트 등에 유용

단점:

• 히스토리 스택에 추가되지 않음

Link 컴포넌트

<Link href="/path">이동</Link>

장점:

• SEO 친화적 (검색엔진이 링크 인식)
• 접근성 우수 (키보드 네비게이션, 스크린리더)
• 자동 프리페칭
• 우클릭으로 새 탭 열기 가능

단점:

• 클릭 시에만 동작 (프로그래밍적 제어 제한)

2. 브라우저 네이티브 API

window.location.href

window.location.href = '/path';

장점:

• 모든 브라우저 환경에서 동작
• 외부 URL로도 이동 가능
• 페이지 전체 새로고침 (상태 완전 초기화)

단점:

• 페이지 전체 리로드 (성능 저하)
• Next.js 최적화 혜택 없음
• React 상태 모두 손실

window.location.replace()

window.location.replace('/path');

장점:

• 히스토리 대체 (뒤로가기 방지)
• 로그인 페이지 등에서 유용

단점:

• 전체 페이지 리로드
• React 상태 손실

History API

window.history.pushState(null, '', '/path');

장점:

• 페이지 리로드 없이 URL 변경
• 히스토리 조작 가능

단점:

• React Router/Next.js와 충돌 가능
• 직접 컴포넌트 리렌더링 처리 필요

3. 상황별 권장사항

일반적인 페이지 이동 (내부 링크)

// 프로그래밍적 이동
const router = useRouter();
router.push('/dashboard');

// 사용자 클릭 기반
<Link href="/dashboard">대시보드</Link>

로그인 후 리다이렉트

// 로그인 페이지로 돌아가지 않게
router.replace('/dashboard');

외부 사이트 이동

// 새 탭
window.open('https://example.com', '_blank');

// 현재 탭
window.location.href = 'https://example.com';

조건부 이동 (이벤트 핸들러)

const handleSubmit = async () => {
  const success = await submitForm();
  if (success) {
    router.push('/success');
  } else {
    router.push('/error');
  }
};

뒤로가기/앞으로가기

router.back();    // 뒤로가기
router.forward(); // 앞으로가기 (브라우저 히스토리에 있을 때만)

4. 성능 최적화 팁

프리페칭 제어

<Link href="/heavy-page" prefetch={false}>
  무거운 페이지
</Link>

Shallow 라우팅 (쿼리만 변경)

router.push('/same-page?tab=2', undefined, { shallow: true });

5. 최종 권장사항

대부분의 경우: useRouter + router.push() 또는 Link 컴포넌트 로그인/인증 관련: router.replace() 외부 링크: window.location.href 또는 window.open() 전체 페이지 리셋 필요시: window.location.href

Next.js 환경이라면 가능한 한 Next.js 라우터를 사용하는 게 성능과 사용자 경험 측면에서 최적이야.

• MongoDB에 사용자 정보가 저장되어 있음

• 프론트에서 자신의 MongoDB _id를 직접 전달해서 사용자 정보를 조회 중

• 문제점:

  • 만약 다른 사용자의 id(= ObjectId)를 탈취하면, 그대로 요청하면 남의 정보도 볼 수 있음
  • 즉, “인증(누가 요청했는지)”과 “인가(그 사람이 그 정보를 볼 권리가 있는지)”가 분리 안 돼 있음

✅ 안전하게 만들려면 어떻게 해야 할까?

핵심 원칙

“로그인한 사용자는 반드시 자기 정보만 볼 수 있어야 한다. (id를 아무리 바꿔도, 내 계정이 아닌 건 못 보게)”

1. API에서 id를 쿼리로 절대 받지 않는다 (or, 받아도 무시한다)

• id를 프론트에서 넘기는 방식 X
• 서버에서 JWT나 세션 등 인증 토큰을 파싱해서 “지금 로그인한 사용자”의 id만 사용

💡 예시: NestJS에서 JWT + Passport 사용

1) JWT 인증 설정 (예시)

// user.controller.ts
@UseGuards(JwtAuthGuard)
@Get('me')
async getMe(@Request() req) {
  // req.user는 JWT에서 추출한 유저 정보 (보통 { userId, email, ... })
  const user = await this.userService.findById(req.user.userId);
  // 여기서 필요한 정보만 골라서 반환 (예: DTO로 필터링)
  return new UserResponseDto(user);
}

2) 프론트엔드는 별도의 id 없이 /me 엔드포인트만 호출

// fetch('/api/user/me', { headers: { Authorization: 'Bearer ...' } })

• 브라우저에서 id를 전달할 필요 없음
• JWT에서 서버가 알아서 id 추출

✅ 장점

• id 탈취해도 소용 없음 (내 JWT 토큰이 아니면 내 정보밖에 못 봄)

• API 구조도 심플:

  • /user/me 또는 /me 같은 경로 사용
  • params, query에 id 없음

2. 만약 id를 꼭 받는 구조라면? (권장하지 않음)

• 추가로 “인가” 체크가 필요함 → 즉, 조회 요청의 id가 현재 로그인한 사용자와 같은지 비교 → 아니면 403 Forbidden 에러 반환

@Get(':id')
@UseGuards(JwtAuthGuard)
async getUser(@Request() req, @Param('id') id: string) {
  if (id !== req.user.userId) {
    throw new ForbiddenException('본인 정보만 조회 가능');
  }
  return new UserResponseDto(await this.userService.findById(id));
}

• 하지만 이 방식은 API 오남용 가능성 높으니 최대한 “/me” 구조로 통일하는 걸 추천

3. 반환 데이터도 최소화 (보안 강화)

• 항상 DTO로 반환할 필드를 제한
• password, hashedPassword, 민감 데이터는 제외

export class UserResponseDto {
  readonly email: string;
  readonly name: string;
  // ... 필요한 필드만
}

🔥 핵심만 요약

• API에서 id(혹은 ObjectId)를 쿼리로 직접 받지 않는다
• 인증(로그인)은 반드시 JWT/세션 기반으로 하고, 내부적으로 서버가 현재 유저의 id를 식별해서 조회
• 필요한 정보만 DTO로 가공해서 응답

💡 추가 팁

• 가능하다면 “/user/me”만 열고, “/user/:id” 같은 엔드포인트는 아예 막는 게 더 안전
• 관리자(어드민) 기능은 별도 인증/인가 체계로 분리

실제 NestJS + Mongoose + Passport(JWT) 조합 코드 샘플이 더 필요하면 추가로 보여줄 수 있어! 원해?

✅ 기본 원칙: 에러에 대한 처리 책임은 의미 있는 대응이 가능한 계층에서

💡 판단 기준: 아래 질문들을 해봐

1. 이 함수는 에러가 날 수 있다는 걸 자연스럽게 예상할 수 있는가?

   • 예: 외부 API 호출, DB 쿼리 등
   • → 이럴 땐 호출자가 책임지는 게 더 자연스러움 (try/catch를 호출 쪽에서)

2. 에러가 났을 때 이 함수 내에서 복구 가능하거나 의미 있는 fallback이 있는가?

   • 예: 파일이 없으면 기본 설정으로 대체
   • → 함수 내부에서 try/catch로 잡는 게 맞음

3. 에러가 발생했을 때 사용자에게 메시지를 보여주거나 로그로 남겨야 하는가?

   • → 호출자(서비스 레이어, 컨트롤러 등)에서 책임져야 함

🔍 예시

1. 내부에서 의미 있는 대체 로직이 있을 경우

async function getUser(id: string) {
  try {
    return await db.findUserById(id);
  } catch {
    return null;  // 없는 경우 null 처리
  }
}

호출자가 이 함수가 null을 반환할 수 있음을 예상해야 함

2. 서비스에서 의미 있는 대응을 해야 할 경우

async function createUser(data: UserDTO) {
  const user = await this.userRepo.save(data);  // 여기서 실패 가능
  this.logger.log(`User ${user.id} created`);
}

이럴 땐 save() 내부에서는 await 없이 에러를 리턴하고, createUser()에서 try/catch로 전체 흐름 관리하는 게 좋음.

🧭 NestJS 관점 예시

• Service 계층에서는 return foo()로 넘기고
• Controller 계층에서 await + try/catch 혹은 ExceptionFilter로 처리

@Controller()
export class UserController {
  @Post()
  async create(@Body() dto: CreateUserDto) {
    try {
      return await this.userService.create(dto);
    } catch (e) {
      throw new InternalServerErrorException('유저 생성 실패');
    }
  }
}

✅ 결론

• 에러 처리는 의미 있는 대응이 가능한 계층이 책임져야 한다
• 단순히 return await을 쓰느냐 마느냐보다, “이 에러를 여기서 감싸고 처리할 의미가 있는가?” 가 중요
• 라이브러리/서비스 함수는 에러를 최대한 드러내고, 최종 처리 책임은 상위 계층으로 넘기는 게 일반적인 패턴

✅ NestJS 모듈이란?

NestJS에서 모듈은 관련된 컴포넌트(서비스, 컨트롤러, 프로바이더 등)를 그룹으로 묶는 단위야.

@Module({
  imports: [],         // 다른 모듈들
  controllers: [],     // 이 모듈이 가진 라우터들
  providers: [],       // 서비스/헬퍼 등 주입 가능한 클래스들
  exports: [],         // 외부 모듈에서 이 모듈의 어떤 provider를 쓸지
})
export class UserModule {}

📦 왜 모듈을 쓰는가?

Nest는 프로젝트를 기능 단위로 쪼개는 **도메인 기반 구조(Domain Driven Design)**를 권장하고, 모듈은 그 도메인을 캡슐화하는 단위야.

예를 들어:

• UserModule → 회원 관련
• AuthModule → 인증 관련
• ProductModule → 상품 관련

각 모듈은 자기 내부에서만 동작하는 서비스/컨트롤러/엔티티를 가질 수 있고, 필요한 기능만 exports/imports를 통해 주고받을 수 있어.

⚙️ 모듈의 주요 구성요소

🔁 예시: AuthModule과 UserModule 관계

// auth.module.ts
@Module({
  providers: [AuthService],
  exports: [AuthService],  // 외부에서 사용 가능하게
})
export class AuthModule {}

// user.module.ts
@Module({
  imports: [AuthModule],   // AuthService를 쓰기 위해 import
  controllers: [UserController],
  providers: [UserService],
})
export class UserModule {}

• UserService가 AuthService를 DI 받을 수 있는 이유는:

  1. AuthModule이 AuthService를 exports했고
  2. UserModule이 AuthModule을 imports 했기 때문이야.

🧠 모듈의 특징 요약

• 자체적으로 완결된 기능 단위를 만든다
• 의존성 주입의 범위를 제어할 수 있다 (exports)
• 다른 모듈과 조합 가능하다 (imports)
• **전역 모듈(Global Module)**로 설정하면 전체 앱에서 공유 가능하다

@Global()
@Module({ ... })
export class ConfigModule {}

🔐 모듈로 인해 생기는 장점

• 기능 분리 및 재사용성 향상
• 테스트 단위 설정 쉬움 (module 단위 mocking)
• 애플리케이션 구조가 직관적
• 의존성 명시가 명확해짐 (DI 기반)

✅ 모듈의 단위 = 도메인 단위가 권장됨

NestJS는 **모듈 단위가 도메인(업무 영역)**이 되는 걸 가장 강하게 권장해.

즉, 하나의 모듈은 하나의 "주제", "업무 영역", 혹은 "비즈니스 기능"을 표현함.

예:

• UserModule → 유저 등록, 조회, 탈퇴
• AuthModule → 로그인, 토큰 발급, 인증
• OrderModule → 주문 생성, 상태 변경
• ProductModule → 상품 등록, 수정

이렇게 나누면 유지보수와 테스트가 쉬워지고, 의존 관계도 명확하게 가늠할 수 있어.

🤔 그런데 도메인을 넘나드는 복잡한 작업은 어디에?

예: "유저가 상품을 주문하면, 포인트 차감 + 재고 차감 + 주문 생성 + 알림 전송"

이건 여러 도메인의 모듈(User, Product, Order, Notification)이 얽힌 작업이지.

Nest에서 이런 걸 처리하는 일반적인 방식은 이거야:

도메인 서비스들(UserService, OrderService 등)을 조합하는 ‘Application Layer 서비스’를 별도로 만든다.

🏗️ 구조 예시

// order-orchestrator.service.ts
@Injectable()
export class OrderOrchestratorService {
  constructor(
    private readonly userService: UserService,
    private readonly productService: ProductService,
    private readonly orderService: OrderService,
    private readonly notificationService: NotificationService,
  ) {}

  async placeOrder(userId: string, productId: string) {
    const user = await this.userService.findById(userId);
    const product = await this.productService.checkAvailability(productId);

    await this.userService.deductPoints(user.id, product.price);
    await this.productService.decreaseStock(product.id);
    const order = await this.orderService.create(user.id, product.id);
    await this.notificationService.sendOrderConfirmation(user.email);

    return order;
  }
}

• 이 서비스는 실제 도메인 서비스들을 **조립(Orchestration)**만 담당함.
• 진짜 비즈니스 로직(포인트 차감, 재고 변경 등)은 각각의 도메인 서비스에서 처리함.
• 이름은 보통 Orchestrator, ApplicationService, UseCaseService 등으로 짓기도 해.

📦 이걸 어디에 넣어야 할까?

방법 1. 별도 ApplicationModule 생성

@Module({
  imports: [UserModule, ProductModule, OrderModule, NotificationModule],
  providers: [OrderOrchestratorService],
})
export class ApplicationModule {}

이렇게 하면 도메인 간의 조합로직을 한 곳에 캡슐화할 수 있음.

방법 2. 주요 도메인 모듈(OrderModule 등)에 포함

작업의 중심이 되는 도메인이 명확할 경우, 해당 도메인 모듈 안에 넣기도 해. 예: 주문 흐름의 핵심이 주문(Order)이라면, OrderModule 안에 OrderService, OrderOrchestratorService 둘 다 넣는 식.

📚 정리

**“도메인을 얼마나 작게 쪼개야 하냐”**는 건 NestJS뿐 아니라 DDD(Domain-Driven Design), 모듈 아키텍처 설계 전반에서 계속 나오는 핵심 이슈인데, 정답은 하나가 아니라 **"업무 의미 단위에 따라 쪼갤 수 있을 만큼 쪼개되, 불필요하게 분리하지는 말라"**는 게 기준이야.

✅ 핵심 기준: "한 가지 책임 / 의미 있는 비즈니스 영역"

하나의 모듈은 하나의 '업무 목적'을 가져야 해. 너무 작게 나누면 복잡도만 늘어나고, 너무 크게 두면 응집도가 떨어져.

권장되는 쪼갬 수준 예시:

📦 도메인 분리 판단 기준

1. 업무 용어 기준

• 실제 기획자나 기획서, 비즈니스 문서에 회원, 인증, 주문, 배송 등의 용어가 각각 등장한다면 → 모듈 분리 대상
• 반대로 "사용자 생성", "사용자 삭제"가 각각 독립적인 비즈니스는 아님 → 같은 모듈로 묶는 게 자연스러움

2. 데이터 및 책임의 응집도

• 하나의 모듈에서 다루는 클래스/서비스들이 서로 긴밀하게 연관돼 있다면 → 하나로 묶기
• 서로 거의 의존하지 않고, 각자 DB 모델도 따로 존재한다면 → 분리 고려

3. 변경 시점의 일치 여부 (Change Rate)

• 자주 같이 변경되는 기능은 함께 두는 게 맞고
• 서로 독립적으로 바뀌는 기능은 나누는 게 유지보수에 유리함

4. 테스트 또는 배포 단위로의 분리 가능성

• 특정 기능은 API 버전, 클라이언트, 관리자/유저 등에서 별도 사용됨 → 분리 고려

🤔 NestJS에서는 보통 이 정도 수준으로 쪼갬

• 위 수준이 NestJS에서 일반적으로 실무에서 사용하는 쪼갬 단위
• 그보다 더 세분화하고 싶다면 feature 단위 서브모듈을 모듈 안에 폴더 수준으로 넣는 방식 추천

🧠 요약

한 줄 요약

NestJS의 모듈은 도메인 중심으로 적절히 작게 나누되, 여러 도메인 간 로직은 별도의 조합 서비스(Application Layer)에서 처리하고, 너무 큰 모듈은 테스트, 유지보수, 성능 측면에서 반드시 분리하는 게 좋다.

1. 메서드 분리

// 단일 항목 처리
async createOne(data: Data): Promise<Log> {
  return (await this.createMany([data]))[0];
}

// 다중 항목 처리
async createMany(datas: Data[]): Promise<Log[]> {
  // 구현 로직
}

장점

• 단일 책임 원칙 준수: 각 메서드는 명확한 한 가지 목적을 가짐
• 코드 가독성: 목적별로 구분되어 이해하기 쉬움
• 확장성: 각 메서드에 특화된 기능 추가 용이
• 테스트 용이성: 각 기능을 독립적으로 테스트하기 쉬움

단점

• 메서드 수 증가: 더 많은 메서드명을 기억해야 함
• 코드 중복 가능성: 재사용하지 않으면 로직 중복 발생
• API 표면적 증가: 외부에 노출되는 메서드 증가

2. 오버로딩

// 오버로드 시그니처
async create(data: Data): Promise<Log>;
async create(data: Data[]): Promise<Log[]>;

// 실제 구현체
async create(data: Data | Data[]): Promise<Log | Log[]> {
  const dataArray = Array.isArray(data) ? data : [data];
  // 구현 로직...
  return Array.isArray(data) ? Log : Logs[0];
}

장점

• 인터페이스 단순화: 사용자는 하나의 메서드명만 기억하면 됨
• 타입 안전성: 컴파일러가 올바른 인자와 반환 타입 매칭을 보장
• API 일관성: 단일/다중 작업에 동일한 메서드명 사용

단점

• 구현 복잡성: 모든 케이스를 처리하는 하나의 함수 내에서 분기 처리 필요

• 책임 혼합: 단일 메서드가 여러 역할 수행

• 데이터 흐름 추적 어려움: 타입 분기로 인한 코드 복잡성 증가

  3. 제네릭 사용

  async create<T>(data: T): Promise<T> {
  }

  장점

• 유연성과 재사용성

• 다양한 타입에 대응할 수 있음

• 타입 안전성

단점

• 복잡한 제네릭 로직은 코드 이해도를 낮춤
• 런타임 오류의 가능성
• 오버로딩만큼 다양한 구성이 어려움

CORS 정책

무엇을 위한 것인가

• CORS는 브라우저 보안 정책일 뿐, 서버 보안 정책이 아님.
• curl이나 Postman 같은 비브라우저 환경에서는 애초에 CORS 보호를 기대하지 않아. (걔네는 아무 요청이나 다 할 수 있어야 하니까.)

즉, CORS는 사용자를 보호하는 거지 서버를 보호하는 건 아님.

서버 자체를 보호하고 싶으면 JWT, OAuth 인증, 서버 측 Access-Control, rate limit 등을 따로 걸어야 한다.

• 즉, CORS는 브라우저를 이용한 보안위반을 막기 위한 것이지, 모든 보안 위협 요청을 차단하려는 목적이 아니다.

  누가 정책을 정하는가

• 보통 리소스를 제공하는 백엔드 서버에서 정한다.(고 생각하면 일단 이해가 쉽다)
• CORS 허용 목록은 서버가 응답을 주면서 어느 origin에서 온 요청일 경우에만 응답을 신뢰하라고 브라우저에 알려주는 역할을 한다.
• 즉, 어느 경우에든 서버가 응답은 준다. 근데 cors 정책을 같이 응답에 명시해주면서, 브라우저가 이 정책에 위반되는 경우에는 응답을 클라이언트에 제공하지 않도록 하는 것.

  origin이 뭐냐면

  • 요청의 출처: 즉 example.com:443에 접속했을 때 제공된 페이지에서 이미지를 api.com:8888에서 가져오라고 했다면, api.com:8888에 보낸 요청의 origin이 example.com:443이다.
• 만약 api.com:8888에서 example.com:443이 origin인 요청을 허용하고 있다면 브라우저는 응답을 받아와 이미지를 표시해 주겠지만, 그렇지 않다면 차단한다.
• Origin은 프로토콜, 도메인, 포트까지 합친 단위로 구분된다. 예: https://example.com:8080

  왜 이런 정책을?

• 사용자의 이메일 서버로 응답을 받아와 공격자에게 전달하는 악성 웹페이지가 있다고 하자. 만약 이메일 서버에서 악성 웹페이지를 cors허용하지 않고 있다면 브라우저가 응답을 차단하므로 공격자에게 전달되지 않을 것이다. 이런 브라우저를 이용한 보안 위반을 차단하기 위한 것이다.

  막을 수 없는 것

• 스크립트 삽입을 통한 동일 origin에서의 악성 요청
• 브라우저를 거치지 않고 서버를 목표로 한 거짓/악성 요청

개인적으로 지금 일하는 레포에선 프론트의 책임이 과중한 것 같아서 백엔드에 좀 책임을 이관하고 싶다. 그래도 내가 모르는 고려사항이 많을 테니 gpt에 대충 물어봤다.

좋은 질문이야.
요약하면,
백엔드 책임을 키울지 vs 프론트 책임을 키울지 결정할 때 고려해야 하는 것들은 다음과 같아:

1. 데이터 무결성 요구 수준

• 데이터 일관성, 보안이 중요한 경우 → 백엔드 책임 강화

  • 백엔드가 진실의 원천(Single Source of Truth)이 되어야 해.
  • 예시: 결제 로직, 계정 권한 처리

• 일시적인 데이터 조작, UI 중심 가공이 중요한 경우 → 프론트 책임 강화

  • 사용자 경험을 위해 즉시 반응하고, 결과를 로컬에서 다룰 수 있어야 함.
  • 예시: 테이블 정렬/필터링, 클라이언트 캐시 최적화

2. 성능 요구사항

• 서버 부하를 줄이고 싶으면 → 프론트 책임 강화
  • 데이터를 한 번 크게 내려주고, 프론트가 필요한 만큼 가공/표시
• 클라이언트 부하를 줄이고 싶으면 → 백엔드 책임 강화
  • 모바일 기기나 저사양 환경에서는 프론트 부담을 줄여야 함.

📌 실제 기준: 대량 데이터 가공, 복잡 연산 → 서버에서 미리 가공하는 편이 거의 항상 효율적임.

3. API 재사용성/유연성

• 여러 소비자가 같은 API를 쓸 필요가 있으면 → 백엔드 책임 강화

  • 여러 종류의 프론트(앱/웹 등)가 다양한 형태로 데이터를 사용할 때, 백엔드가 포맷을 일관성 있게 정리해야 관리가 쉬워.

• 특정 프론트엔드에 맞춘 특화된 동작만 필요하면 → 프론트 책임 강화

  • 백엔드를 복잡하게 만들지 않고, 프론트가 알아서 조작하는 게 낫지.

4. 팀 역량 및 개발 생산성

• 프론트엔드 개발자가 많고 강하면 → 프론트에 맡겨도 안정적
• 백엔드에 인력이 집중돼 있으면 → 백엔드가 더 많은 책임을 가져야 함

(물론 여기선 "프론트가 강하니까 아무거나 맡긴다" 이런 게 아니라, 유지보수 가능성을 고려해야 한다는 얘기야.)

5. 변경 가능성

• 요구사항이 자주 바뀔 것 같으면 → 프론트 책임 강화

  • 서버 변경 없이 화면만 고쳐서 대응하는 게 더 빠르니까.

• 계약(API 스펙)이 단단해야 하는 상황이면 → 백엔드 책임 강화

  • 데이터 구조가 자주 변하면 서버를 수정하고, 버전 관리도 해야 돼.

6. 보안

• 민감 데이터나 권한 검증이 필요하면 무조건 백엔드
  • 사용자 인증/인가 같은 건 절대 프론트에 맡기면 안 돼.
  • 프론트는 표시만, 검증과 권한 관리는 서버가 담당.

요약표

한줄 요약

"데이터를 믿어야 하는 책임이 어디 있어야 하느냐" 이게 제일 큰 기준이고, 부수적으로 성능/팀역량/변경성 등을 따진다.

필요하면, 각각 상황별 구체적인 예시도 같이 들어줄게.
특정 상황(예: "관리자 페이지에서 테이블 필터링", "회원가입 로직") 같은 거 정해서 물어볼래? 🚀
(그럼 더 현실적인 비교도 해줄 수 있어.)

후기

다른 건 좀 당연한 말이고 집중할 필요가 있어 보이는 것은

1. api 재사용성
2. 변경 가능성

정도 인 것 같다. 특히 변경 가능성이 높을 때엔 확실히 백엔드에 검증 코드를 넣어두는 것보다 프론트에서 상황에 맞춰 다르게 구현해 놓는 것이 더 빠르고 편할 것 같긴 하다. 지금 작업하는 곳이 변화가 많은 만큼 자연스럽게 프론트 쪽으로 책임이 치우쳐지지 않았나 싶다...

트랜잭션 기본

https://www.mongodb.com/ko-kr/docs/manual/core/transactions/#transactions-and-atomicity

https://www.mongodb.com/docs/manual/core/transactions-production-consideration/#std-label-txns-locks

분산 트랜잭션은 다음과 같이 원자적입니다.

• 트랜잭션은 모든 데이터 변경 사항을 적용하거나 변경 사항을 롤백합니다.

• 트랜잭션이 커밋되면 트랜잭션에서 이루어진 모든 데이터 변경 사항이 저장되고 트랜잭션 외부에서 볼 수 있습니다.

  트랜잭션이 커밋될 때까지 트랜잭션에서 변경된 데이터는 트랜잭션 외부에 표시되지 않습니다.

• 트랜잭션이 중단되면 트랜잭션에서 발생한 모든 데이터 변경 사항은 표시되지 않고 삭제됩니다. 예를 들어, 트랜잭션의 작업이 실패하면 트랜잭션이 중단되고 트랜잭션의 모든 데이터 변경 사항이 표시되지 않은 채로 폐기됩니다.

정리

1. 잠금 단위: 문서

2. 트랜잭션이 잠금을 획득하는 시기: 문서 수정(읽기는 잠금 x)

3. 트랜잭션이 문서를 읽을 때 기준 시점: 트랜잭션 시작 시의 스냅샷 기준

   트랜잭션 내부의 읽기 작업은 오래된 데이터를 반환할 수 있으며 이를 부실 읽기라고 합니다. 트랜잭션 내부의 읽기 작업은 커밋된 다른 트랜잭션이나 트랜잭션이 아닌 쓰기에서 수행되는 쓰기를 볼 수 없습니다. 예를 들어 다음 순서를 생각해 보세요.

   1. 트랜잭션이 진행 중입니다.
   2. 트랜잭션 외부에서 쓰면 문서가 삭제됩니다.
   3. 트랜잭션 내부의 읽기 작업은 쓰기 작업 이전의 스냅샷을 사용하므로 현재 삭제된 문서를 읽을 수 있습니다.

   매뉴얼 - 트랜잭션 - 프로덕션 고려 사항 - 진행 중인 트랜잭션 및 오래된 읽기

4. 트랜잭션이 수정한 문서를 외부에서 볼 수 있는 시점: 트랜잭션 커밋

   트랜잭션이 커밋될 때까지 트랜잭션에서 변경된 데이터는 트랜잭션 외부에 표시되지 않습니다.

   매뉴얼 - 트랜잭션 - 트랜잭션 및 원자성

5. 트랜잭션이 잠금을 획득한(수정 중인) 문서를 트랜잭션 외부에서 수정하려고 하면: 쓰기 충돌 대기

   트랜잭션이 진행 중이고 문서 수정을 잠긴 경우 트랜잭션 외부에서 쓰기가 동일한 문서를 수정하려고 하면 트랜잭션이 종료될 때까지 쓰기가 대기합니다.

   매뉴얼 - 트랜잭션 - 프로덕션 고려 사항 - 진행 중인 트랜잭션 및 쓰기 충돌

6. 트랜잭션 스냅샷 이후 외부에서 수정한 문서를 트랜잭션 내부에서 수정하려고 하면: 트랜잭션 중단

   트랜잭션이 진행 중이고 트랜잭션 외부의 쓰기가 나중에 트랜잭션의 작업이 수정하려고 하는 문서를 수정하는 경우, 쓰기 충돌로 인해 트랜잭션이 중단됩니다.

   매뉴얼 - 트랜잭션 - 프로덕션 고려 사항 - 진행 중인 트랜잭션 및 쓰기 충돌

1. SOLID 원칙

SOLID란 로버트 C. 마틴이 2000년대 초반에 명명한 객체 지향 프로그래밍 및 설계의 다섯 가지 기본 원칙🔗이다.

• SRP 단일 책임 원칙 (Single responsibility principle) 한 클래스는 하나의 책임만 가져야 한다.
• OCP 개방-폐쇄 원칙 (Open/closed principle) “소프트웨어 요소는 확장에는 열려 있으나 변경에는 닫혀 있어야 한다.”
• LSP 리스코프 치환 원칙 (Liskov substitution principle) “프로그램의 객체는 프로그램의 정확성을 깨뜨리지 않으면서 하위 타입의 인스턴스로 바꿀 수 있어야 한다.” 계약에 의한 설계를 참고하라.
• ISP 인터페이스 분리 원칙 (Interface segregation principle) “특정 클라이언트를 위한 인터페이스 여러 개가 범용 인터페이스 하나보다 낫다.”
• DIP 의존관계 역전 원칙 (Dependency inversion principle) 프로그래머는 “추상화에 의존해야지, 구체화에 의존하면 안된다.” 의존성 주입은 이 원칙을 따르는 방법 중 하나다.

2. 의존성 역전 원칙(DIP)

참고

• Controller (컨트롤러) 클라이언트 요청을 처리하는 역할 (HTTP 요청을 받고, 응답을 반환) 비즈니스 로직을 직접 처리하지 않고 Service(서비스)에 위임 주로 API 엔드포인트를 정의
• Service (서비스) 비즈니스 로직을 처리하는 핵심 계층 DB에서 데이터를 가져오거나 가공하는 작업 수행 컨트롤러에서 요청한 데이터를 조회, 수정, 삭제하는 역할
• Interface (인터페이스) 객체의 형태(Shape)를 정의하는 역할 Port로도 표현됨

의존관계 역전 원칙DIP은 소프트웨어 모듈들을 분리하는 특정한 방식을 지칭한다.

전통적으로 모듈들은 상위 계층이(정책 결정)이 하위 계층(세부 사항)에 의존하는 관계를 가졌다. 이 경우 리팩토링 등의 이유로 저수준 모듈을 수정하는 경우 고수준 모듈도 같이 수정해줘야 할 가능성이 높다. DIP는 이런 전통적인 의존관계를 역전(하위 계층 또한 추상화에 의존하게 함)시켜 상위 계층이 하위 계층의 구현으로부터 독립되게 한다.

이 원칙은 다음과 같은 내용을 담고 있다.

1. 상위 모듈은 하위 모듈에 의존해서는 안된다. 상위 모듈과 하위 모듈 모두 추상화에 의존해야 한다.
2. 추상화는 세부 사항에 의존해서는 안된다. 세부사항이 추상화에 의존해야 한다.

요약하면 상위와 하위 객체 모두가 동일한 추상화에 의존해야 한다는 객체 지향적 설계의 대원칙을 제공한다.

2.1. 예시1: DIP가 적용되지 않은 경우

아래 예시에서 컨트롤러는 서비스에 의존하고 있다. Controller -> Service

# 저수준 모듈 (구체적인 서비스)
class UserService:
    def get_user(self, user_id: int) -> str:
        return f"User {user_id} data"

# 고수준 모듈 (컨트롤러)
class UserController:
    def __init__(self):
        self.service = UserService()  # ⚠ 직접 특정 서비스 구현체를 생성해서 의존함

    def get_user(self, user_id: int):
        return self.service.get_user(user_id)

# 실행
controller = UserController()
print(controller.get_user(1))  # "User 1 data"

2.2. 예시2: DIP가 적용된 경우

아래 예시에서 고수준, 저수준 모듈이 모두 UserServicePort라는 추상화(인터페이스, Port)에 의존하고 있다. Controller -> Port <-(역전) Service

from typing import Protocol

# 1️⃣ Port 역할 (추상화, 인터페이스)
class UserServicePort(Protocol):
    def get_user(self, user_id: int) -> str:
        pass

# 2️⃣ 저수준 모듈 (구체적인 서비스)
class BasicUserService:
    def get_user(self, user_id: int) -> str:
        return f"Basic User {user_id} data"

class PremiumUserService:
    def get_user(self, user_id: int) -> str:
        return f"Premium User {user_id} data"

# 3️⃣ 고수준 모듈 (컨트롤러)
class UserController:
    def __init__(self, service: UserServicePort):  # 인터페이스(추상화)에 의존
        self.service = service

    def get_user(self, user_id: int):
        return self.service.get_user(user_id)

# 실행
basic_controller = UserController(BasicUserService())
print(basic_controller.get_user(1))  # "Basic User 1 data"

premium_controller = UserController(PremiumUserService())
print(premium_controller.get_user(1))  # "Premium User 1 data"

이렇게 하면 컨트롤러가 특정 서비스의 구현에 의존하지 않으며 서비스 로직을 변경하더라도 컨트롤러 수정이 필요가 없다. 또한 Mocking이 쉬워져 단위 테스트가 편리해진다.

3. 의존성 주입(DI)

DIP를 구현하는 방식 중 하나로 객체 내부에서 직접 의존성을 생성하는 대신, 외부에서 주입받는 방식을 말한다.

위의 코드에서 컨트롤러 인스턴스를 생성할 때 서비스 인스턴스를 인자로 전달하는 부분UserController(BasicUserService())이 의존성 주입(Dependency Injection)이다.

NestJS는 의존성 주입 컨테이너(DI Container)를 사용해서 객체 생성을 자동으로 관리한다. 따라서 직접 new UserService()와 같이 객체를 직접 생성해주지 않아도 자동으로 재사용한다.

4. Hexagonal Architecture

https://medium.com/ssense-tech/hexagonal-architecture-there-are-always-two-sides-to-every-story-bc0780ed7d9c Hexagonal Architecture(Ports & Adapters 아키텍처)는 알리스테어 코번(Alistair Cockburn)이 제안한 소프트웨어 설계 방식이다. 이 아키텍처의 핵심은 의존성 역전 원칙을 강하게 적용하는 것으로, 애플리케이션의 핵심 로직(애플리케이션 코어. 육각형으로 표현됨)을 모든 외부 시스템(데이터베이스, UI, 외부 API 등)과 분리하여 테스트 용이성과 유지보수성을 높이는 데 있다.

DI를 설명할 때의 예시에서 외부 사용자가 기능을 조작할 때(그림의 Driving side) Controller-Port-Service 계층을 통해 작동했던 것과 같이 Service에서 DB와의 통신 등을 할 때(즉 외부 인프라에 접근할 때, 그림의 Driven side)에도 Port와 Adapter를 거치도록 하여 애플리케이션 코어를 외부와 강하게 격리시키는 것이 핵심 아이디어이다.

4.1. 핵심 개념

왼쪽에서 오른쪽으로 흐르며 입력 포트는 서비스가 구현하며, 출력 포트는 출력 어댑터가 구현한다. 출력 포트를 사용한 외부 인프라로의 접근은 핵심 비즈니스 로직이 무관할 뿐더러, 코어(육각형)는 외부에 대한 정보가 없어야한다는 핵심 아이디어를 생각하면 당연하다.

• 애플리케이션 코어(Application Core) 애플리케이션의 핵심 비즈니스 로직(도메인 모델, 유스케이스, 비즈니스 규칙 등)이 위치 외부 시스템과 독립적이며, 비즈니스 규칙만 담당 애플리케이션 서비스 계층에서 호출되며, 도메인 모델을 사용해 데이터 처리 수행
• 포트(Ports) 포트는 도메인과 외부 세계를 연결하는 인터페이스
  • 입력 포트 외부에서 애플리케이션으로 데이터를 전달하는 인터페이스 (예: API 엔드포인트)
  • 출력 포트 애플리케이션에서 외부로 데이터를 전달하는 인터페이스 (예: 데이터베이스 접근)
• 어댑터(Adapters) 어댑터는 외부 시스템과의 통신을 담당
  • 입력 어댑터 외부 요청을 애플리케이션의 입력 포트로 전달 (예: REST Controller)
  • 출력 어댑터 애플리케이션의 출력 포트를 외부 시스템에 연결 (예: 데이터베이스 Repository)
• 애플리케이션 서비스(Application Service, Service) 도메인 로직을 직접 포함하지 않고, 유스케이스 흐름을 조정하는 역할 외부 시스템과 직접 연결되지 않으며, 포트를 통해 접근 입력 포트(Inbound Port)를 구현하여 UI(컨트롤러, API)와 도메인을 연결 출력 포트(Outbound Port)를 호출하여 외부 리소스(DB, API)와 연결

4.2. 특징

4.2.1. 장점

• 비즈니스 로직(Service)이 외부 환경(입출력, DB)과 독립적 기술이 아닌 '목적에 따라' 모든 시스템 인터페이스를 설계할 수 있음 => 도메인 주도 설계(DDD)와 잘 어울림
• 유연한 확장성
  • 새로운 데이터 저장소 추가, API 프로토콜 변경이 쉬움.
  • REST API, gRPC, WebSocket 등을 쉽게 추가 가능.
• 유지보수성이 높음 변경 사항이 특정 Adapter에 한정되어 전체 코드 수정이 적음.
• 테스트가 쉬움 Service는 Port 인터페이스만 알면 되므로, Mock 객체를 활용해 단위 테스트가 용이.

4.2.2. 단점

• 설계가 복잡해질 수 있음 작은 프로젝트에서는 단순한 계층형 아키텍처가 더 적합할 수 있음.
• 개발자가 패턴을 정확히 이해하지 않으면 오히려 불필요한 추상화가 많아질 위험.

4.2.3. 사용하기 어려운 경우🔗

• 도메인 모델을 확실하게 정의하기 어려운 경우 Port와 Adapter의 경계를 명확히 설정하기 힘들 수 있음
• 코어 로직보다 외부 서비스에 크게 의존하는 경우 로직의 대부분이 연동 API에 의해 동작하는 서비스일 경우 Port와 Adapter에 로직이 과중됨

4.3. 파일 구조 예시

├adapter
│├in
││└controller
│└out
│ └repository
├port
│├in
││└UserServiceInterface
│└out
│ └RepositoryInterface
├service
│└UserService
├domain
 └DomainEntity

5. 도메인 주도 설계(Domain Driven Design, DDD)

기존의 개발 방식과 비교하여 설명

5.1. 전통적 개발 방식(예시)

기존의 방식에서는 요구사항을 기능 단위로 나누어 구현하였다. 데이터베이스 설계를 먼저 하고, 이를 기반으로 애플리케이션을 개발되는 것이 보통. Controller, Service, Repository와 같은 계층구조는 전통적 개발 방식에도 존재

5.1.1. 장점

• 빠른 개발 복잡한 도메인 분석 없이 기능을 빠르게 구현
• 단순함 작은 규모의 애플리케이션에서 개발이 쉬움

5.1.2. 단점

• 도메인 이해 부족 도메인에 대한 이해를 하지 못한 채 개발하여 비즈니스 요구사항을 제대로 반영하지 못할 수 있음
• 유지보수 어려움 코드가 도메인 개념과 일치하지 않아 유지보수가 어려움
• 확장성 부족 복잡한 비즈니스 로직이 추가되면 코드가 복잡해지고 관리하기 어려움

5.2. DDD

개발자역시 도메인을 이해하고 이를 통해 구현 도메인 전문가와 개발자가 도메인 지식을 공유하여 의사소통과 코드 작성에 일관성을 유지 복잡한 도메인을 작은 단위로 나누어 정의한 명확한 컨텍스트(Bounded Context)에 기초해 개발

5.2.1. 장점

• 도메인 이해도 향상 도메인 이해를 바탕으로 비즈니스 요구사항을 정확히 반영
• 유지보수성 도메인 모델이 명확하므로 코드의 의도를 쉽게 이해
• 확장성 Bounded Context를 통해 관리하므로 계속해서 발전하는 비즈니스 모델의 구현이 쉬워짐

5.2.2. 단점

• 개발이 복잡해짐 일반적으로 모델을 순수하고 유용한 구성으로 유지하기 위해 상당한 양의 격리 및 캡슐화를 구현해야 함 => 도메인에 대한 공통의 이해가 가져오는 장점이 명확한 복잡한 도메인의 경우에 사용할 것을 권장
• 초기 설계 비용 설계를 위해 도메인에 대한 깊은 이해가 필요

5.3. 결론

DDD는 복잡한 비즈니스 로직을 가진 프로젝트에 적합하며, 전통적 개발 방식은 단순한 애플리케이션에 더 적합

참고로 파이썬엔 sortedcontainers라는 좋은 라이브러리가 있다.

문제가 뭔데

사용자 점수 저장, 필요할 때마다 정렬? O(QNlogN) 어떤 경기에서 각 선수의 라운드 별 성적이 아래와 같다고 하자

특정 라운드의 특정 선수의 순위를 알고싶다면 어떻게 해야할까 아래와 같이 질의가 있다고 하자

1라운드 선수3
5라운드 선수2
3라운드 선수1
2라운드 선수1
5라운드 선수3

(참여선수의 수 N, 라운드의 개수 M, 질의 개수 L)

0. 가장 단순한 방법은 위 성적표처럼 각 라운드별 선수의 점수를 저장($M$)해두고 라운드별로 정렬($NlogN$)해서 순위를 산출($logN$)하는 것이다. 시간복잡도 $O(M+LN(logN)^2)$, 공간복잡도 $O(NM+L)$
1. 라운드별 결과를 저장하지 않고 라운드를 순회하면서 질의를 처리하는 경우. 질의를 정렬해 두어야 함. 시간복잡도 $O(M+LN(logN)^2+LlogL)$, 공간복잡도 $O(N+L)$
2. 1에서 매 라운드마다 새 배열로 정렬하는 게 아니라 이전 정렬된 배열을 재활용 한다면 $O(N)$만에 정렬이 가능하다. 시간복잡도 $O(M+MN+LlogN+LlogL)$, 공간복잡도 $O(N+L)$
3. 정렬 상태를 유지할 거면 매번 정렬하지 않고 Sorted 자료구조를 사용하면 삭제/삽입이 $O(logN)$에 가능하다. $O(M+MlogN+LlogN+LlogL)$, 공간복잡도 $O(N+L)$

실제 풀이에서 위와 같은 순서로 시도했으며 단 3은 구현하지 않았다. 0을 먼저 떠올렸다가 $N,M$이 상당히 컸기 때문에 바로 넘어갔던 것 같고 $L, N, M$모두 주어진 크기가 거의 같았기 때문에 1보다는 2를 사용했다. 3을 시도하지 않은 것은 O(N)정도면 통과시켜주지 않을까?하는 안일함 + 시간 없으니 빨리 다음문제 풀어야겠다는 생각 때문이었는데 결국 통과되지 않았다. 진짜 자가균형BST를 구현해야만 되는 문제라고? 싶은데 다른 부분에서 실수가 있었던 게 아니라면 아마 시간복잡도 때문에 통과가 안되는 게 맞았을 것이다. 아니면 내가 생각하지 못한 다른 최적화 포인트가 있었다든가(검색해도 못 찾겠음)

아무튼 3까지 했다면 통과가 됐을 것으로 예상하고 있다. 3을 AVL트리 같은 걸 직접 구현해서 쓰는 건 좀 오바인 것 같고 Treap을 배워놔야 겠다.

정렬/자가균형BST 벤치마크
0.03148720000172034 0.06287740002153441
0.08639999997103587 0.08855309995124117
0.5963373000267893 0.20395200001075864
5.755168000003323 0.31842870003310964
63.099196500028484 1.2043969000224024

"이전 정렬된 배열을 재활용"한다는 것

경기 결과를 다시 보면 라운드별로 한 선수만 득점하고 있다. 따라서 정렬된 리스트를 그대로 유지한 채 득점한 선수의 점수만 바꿔서 정렬하면 1개 원소만 정렬되지 않은 리스트를 정렬하게 된다.

파이썬에서 .sort(), sorted()는 Tim Sort로 구현되어 있는데 Tim Sort는 배열을 분할해 삽입 정렬 후 병합하는 방식이므로 이 경우 거의 $O(N)$에 정렬이 완료된다.

문제

양방향 그래프가 주어진다. 모든 간선의 비용(소요시간)은 1이다. 자연수 D가 주어질 때 정점 1에서 출발해 정점 1로 D시간만에 돌아오는 경로의 개수를 출력한다.

풀이

아이디어가 거의 전부인 문제 유사한 문제를 풀어보았거나 인접행렬을 이용한 그래프 이동을 떠올린다면 구현은 아주 쉽다.

인접행렬의 곱셈

$i×i$형태의 인접행렬 $A$가 아래와 같이 있다. $$A=\begin{pmatrix} a_{00} & a_{01} & \cdots & a_{0i} \ a_{10} & a_{11} & \cdots & a_{1i} \ \vdots & \vdots & \ddots & \vdots \ a_{i0} & a_{i1} & \cdots & a_{ii} \end{pmatrix}$$ 이 때 인접행렬 $A$의 제곱은 다음과 같이 표현된다. $$ A^2=\begin{pmatrix} \sum a_{0k}a_{k0} & \sum a_{0k}a_{k1} & \cdots & \sum a_{0k}a_{ki} \ \sum a_{1k}a_{k0} & \sum a_{1k}a_{k1} & \cdots & \sum a_{1k}a_{ki} \ \vdots & \vdots & \ddots & \vdots \ \sum a_{ik}a_{k0} & \sum a_{ik}a_{k1} & \cdots & \sum a_{ik}a_{ki} \end{pmatrix} $$ 그런데 문제에서는 모든 비용이 1이라고 했으므로 이동할 수 없는 경우의 비용을 0으로 표현하면 $$ a_{ik}a_{kj}= \left { \begin{aligned} 1;(i에서;k를;거쳐;j로;이동할;수;있는;경우) \ 0;(i에서;k를;거쳐;j로;이동할;수;없는;경우) \end{aligned} \right. $$ 이므로 $$ \sum a_{ik}a_{kj}= \left { \begin{aligned} 1;(i에서;한;정점을;거쳐;j로;이동하는;경우의수) \ 0;(i에서;한;정점을;거쳐;j로;이동하는;경우의수) \end{aligned} \right. $$

비슷한 논리로 3이상의 $n$에서도 $A^n$의 $i$행 $j$열의 원소는 $i$에서 $j$까지 $n$개의 정점을 거쳐 이동하는 경우의 수이다.

따라서 문제는 주어진 인접행렬 $A$로부터 $A^D$의 $0,0$원소의 값을 구하는 문제로 귀결된다.

굳이 행렬 곱셈으로

bfs나 dfs로 찾으면 $O(N^D)$ 행렬 곱을 이용하면 별도의 행렬곱 알고리즘 없이도 분할정복을 이용한 거듭제곱만으로 $O(N^3log(N))$로 계산할 수 있다.

코드

def matrix_multiply(A: list[list[int]], B: list[list[int]]):
    C = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(i+1):
            C[i][j] = C[j][i] = sum(A[i][k] * B[j][k] for k in range(N)) % 1000000007

    return C

def matrix_power(arr: list[list[int]], n: int):
    if n in cache:
        return cache[n]

    a = n // 2
    b = n - a

    result = matrix_multiply(matrix_power(arr, a), matrix_power(arr, b))
    cache[n] = result
    return result

N, M = map(int, input().split())
A = [[0]*N for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    A[a-1][b-1] = A[b-1][a-1] = 1

D = int(input())

cache = {1: A}

print(matrix_power(A, D)[0][0])

2차원 공간에서 세 점으로 구성된 두 벡터의 회전 방향을 계산하는 기법. 볼록 껍질을 찾기 위한 그레이엄 스캔, 선분 교차 판정 등에 쓰인다. 두 (2차원)벡터의 cross product의 값이 반시계 방향일 때 양수, 시계 방향일 때 음수가 나오는 성질을 이용한다.

예시: (1, 0)×(0, 1)=1, (0, 1)×(1, 0)=-1 네?

$P1 = (x1, y1),; P2 = (x2, y2),; P3 = (x3, y3)$일 때 P1을 원점으로 정규화하고 $V1 = (x2-x1, y2-y1),; V2 = (x3-x1, y3-y1)$ 두 벡터의 cross product 값을 구하면 $V1×V2 = (x2-x1)(y3-y1)-(x3-x1)(y2-y1)$이며 이 값이 양수이면 반시계, 음수이면 시계, 0이면 평행한 방향이다. 따라서 CCW는 $CCW=sign((x2-x1)(y3-y1)-(x3-x1)(y2-y1))$로 쓸 수 있다(sign은 선택적)

def ccw(p0, p1, p2):
    x0, y0 = p0
    x1, y1 = p1
    x2, y2 = p2

    return (x1-x0)*(y2-y0) - (x2-x0)*(y1-y0)

선분 교차 판정

두 선분이 교차하는지를 검사하는 방법. 선분의 기울기와 x, y의 범위로 판정하는 방법과 ccw를 이용하는 방법 등이 있다. ccw를 이용하는 방법이 조금 더 간단하므로 이 방법을 소개한다.

선분이 접하는 경우에는 교차하지 않는다고 볼 수도 있으나 밑에서 풀 백준 문제에서는 접하는 경우에도 같은 그룹으로 판정하므로 그러한 경우까지 살펴본다.

케이스를 세 가지로 나눠서 살펴보면 case 1. P3, P4가 P1, P2를 지나는 직선으로 만들어지는 이분면의 같은 쪽에 속해있는 경우 $CCW(P1, P2, P3)*CCW(P1, P2, P4) > 0$이다. 무슨 짓을 해도 두 선분이 교차할 수 없다.

case 2. P3, P4가 P1, P2를 지나는 직선으로 만들어지는 각기 다른 이분면에 속해있는 경우

이 경우 P1, P2가 이루는 벡터와 P2, P3가 이루는 벡터의 ccw($CCW(P1, P2, P3)$)는 양수이고 $CCW(P1, P2, P4)$는 음수이다. 즉 $CCW(P1, P2, P3)*CCW(P1, P2, P4) < 0$

case 2-1. 교차하는 경우

$CCW(P3, P4, P1)*CCW(P3, P4, P2) < 0$이다.

case 2-2. 교차하지 않는 경우

$CCW(P3, P4, P1)*CCW(P3, P4, P2) > 0$이다.

case 2-3. 접하는 경우

P1에 접하는 경우 $CCW(P3, P4, P1) = 0$, P2에 접하는 경우 $CCW(P3, P4, P2) = 0$이다. 즉 $CCW(P3, P4, P1)*CCW(P3, P4, P2) = 0$이다.

case 3. P3, P4 중 하나 이상이 P1, P2를 지나는 직선 위에 있는 경우

$CCW(P1, P2, P3)*CCW(P1, P2, P4) = 0$이다.

case 3-1. 하나만 직선 위에 있는 경우

P3가 P1, P2 직선 위에 있을 때를 가정하면 $CCW(P3, P4, P1)CCW(P3, P4, P2) < 0$이면 접한다. $CCW(P3, P4, P1)CCW(P3, P4, P2) > 0$이면 접하지 않는다.

case 3-2. 둘 다 직선 위에 있는 경우(같은 직선에 있는 두 선분)

$CCW(P1, P2, P3)=CCW(P1, P2, P4)=CCW(P3, P4, P1)=CCW(P3, P4, P2)=0$이다. 이 경우 접하는지 여부는 P3, P4 중 하나 이상이 선분 P1P2위에 있는지를 살펴봐야 한다.

def dot_on_line(dot, line):
    x0, y0, x1, y1 = line
    x, y = dot

    return min(x0, x1) <= x <= max(x0, x1) and min(y0, y1) <= y <= max(y0, y1)

이상의 내용을 표로 정리하면 아래와 같다.

def intersection(l1, l2):
    x1, y1, x2, y2 = l1
    x3, y3, x4, y4 = l2

    v1, v2, v3, v4 = (x1, y1), (x2, y2), (x3, y3), (x4, y4)

    ccw1 = ccw(v1, v2, v3)
    ccw2 = ccw(v1, v2, v4)
    ccw3 = ccw(v3, v4, v1)
    ccw4 = ccw(v3, v4, v2)

    # case2 or case 3 판정
    if (ccw12:=ccw1 * ccw2) <= 0 and (ccw34:=ccw3 * ccw4) <= 0:
        # case 2-1, 2-3, 3-1 판정
        if ccw12 < 0 or ccw34 < 0:
            return True

        # case 3-2의 접하는지 여부 판정
        if dot_on_line(v3, v1+v2):
            return True
        if dot_on_line(v4, v1+v2):
            return True
        if dot_on_line(v1, v3+v4):
            return True
        if dot_on_line(v2, v3+v4):
            return True

    return False

2162 선분그룹

문제

두 선분이 만나는 경우(교차하거나 접하는 경우)에 두 선분은 서로 같은 그룹에 있다. 선분들이 주어졌을 때 몇 개의 그룹이 존재하고 가장 많은 선분을 포함한 그룹의 선분 수를 찾아야 한다.

풀이

선분을 하나씩 추가해가며 이미 추가한 선분들과 그룹을 이루는 선분이 있는지를 찾는다. 이미 그룹을 이룬 선분과 만나는 경우 그룹을 결합한다.

중복 검사를 최대한 피하기 위해 선분의 x축 기준 왼쪽 경계(min(x1, x2))를 기준으로 정렬 후, 오른쪽 경계(max(x1, x2))가 새로 추가할 선분의 왼쪽 경계보다 왼쪽에 있는 경우에는 교차판정을 건너 뛰도록 했다.

N = int(input())
lines = []
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    lines.append((x1, y1, x2, y2) if x1 <= x2 else (x2, y2, x1, y1))

lines.sort(key=lambda x: (x[0], x[2]))

parents = [i for i in range(N)]
for i in range(N):
    for j in range(i):
        # (N-1)(N-2)/2 번 반복된다.
        if lines[j][2] < lines[i][0]:
            # 아래 continue문이 최대한 많이 호출되기 위해서는 lines가 x1, x2를 기준으로 정렬되어야 한다.
            continue
        if intersection(lines[i], lines[j]):
            p_i = find_parent(i)
            p_j = find_parent(j)
            parents[max(p_i, p_j)] = min(p_i, p_j)

groups = defaultdict(int)
for i in range(N):
    groups[find_parent(i)] += 1

print(len(groups))
print(max(groups.values()))

문제

숫자가 적힌 카드로 게임을 한다. 번갈아 가며 카드를 내는데 상대가 내는 카드보다 큰 카드를 내야하며, 낼 수 있는 카드 중에 가장 작은 카드를 내는 전략을 사용한다. 내가 가진 카드의 종류와 상대가 내는 카드의 순서가 입력으로 주어질 때 내는 카드의 순서를 출력한다. 한 번 낸 카드는 다시 낼 수 없다.

카드의 수는 400만개 이하, 제출하는 횟수는 1만회 이하

예 내가 가진 카드

2 5 3 7 8 4 9

상대가 내는 카드 순서

4 1 1 3 8

내가 내는 순서

5
2
3
4
9

풀이

일단 내가 가진 카드를 정렬해둔다. 카드의 수가 400만개로 많아서 매번 하한을 찾으면 안 된다. 이미 사용한 카드는 바로 다음으로 큰 카드에 연결시켜 다음 방문시 탐색을 빠르게 하도록 한다.(union-find 알고리즘. 최소신장트리를 찾을 때 썼던 크루스칼 알고리즘에서도 썼었다.) 여기에 이분탐색 섞어주면 된다.

N, M, K = map(int, input().split())
cards = list(map(int, input().split()))
reqs = list(map(int, input().split()))

cards.sort()

def bin_search(target):
    lo, hi = -1, M-1

    while lo+1 < hi:
        mid = (lo+hi) // 2
        if cards[find(mid)] > target:
            hi = mid
        else:
            lo = mid

    return hi

def find(idx):
    if isinstance(cards[idx], int):
        return idx
    else:
        root = find(cards[idx][0])
        cards[idx] = root,
        return root

for r in reqs:
    ideal = bin_search(r)
    real = find(ideal)
    print(cards[real])
    if real+1 < M:
        cards[real] = real+1,

아래 내용은 TIL로 이미 올라온 CSAPP의 내용들을 하나로 합친 것으로 빠진 챕터들이 꽤 있다. 책을 내가 이해한 내용으로 적은 것들도 꽤 많으므로 오류가 있을 수 있다. 옵시디언에 작성해 둔 것을 복사해와서 벨로그에서는 표현이 다를 수 있다.

...내가 썼지만 기억 안나는 것들이 많다.

1. 컴퓨터 시스템으로의 여행

1-1. 정보는 비트와 컨텍스트로 이루어진다

여기서 비트는 2진법으로 표현된 숫자(데이터) 그 자체이다. 즉 컨텍스트 없이는 프로그램, 데이터, 네트워크 데이터, 파일, 명령어, 문자열, 숫자 모두 비트 덩어리일 뿐이라는 것이다. 이들을 구분하는 유일한 방법은 컨텍스트 뿐이다.

1-2. 프로그램은 다른 프로그램에 의해 다른 형태로 번역된다

컴파일러를 말한다. C소스코드는

1. 전처리기로 헤더파일이 삽입되고
2. 컴파일러로 어셈블리어로 번역되며
3. 어셈블러로 재배치가능 목적프로그램으로 번역되며(여기서부터 바이너리 파일)
4. 링커에 의해 목적파일과 연결되어 최종 실행가능 목적파일이 된다.

여기서 어셈블리어는 기계어 인스트럭션의 집합

1-3. 컴파일 시스템이 어떻게 동작하는지 이해하는 것은 중요하다

1. 성능 최적화를 위해
2. 보안 취약점을 막기 위해

1-4. 프로세서는 메모리에 저장된 인스트럭션을 읽고 해석한다.

현재 모든 컴퓨터는 폰노이만 구조를 따른다. 폰노이만 구조에서는 변수도 프로그램도 메모리에 저장된다. 프로세서는 메모리에 저장된 명령어(인스트럭션)을 읽어 실행할 뿐이다.

1-5. 캐시가 중요하다

프로그램을 실행하면 프로그램을 메모리에 저장해야 한다. 이런 복사/읽기 작업들이 작업을 느리게 한다.(오버헤드) 그렇다고 모든 저장장치들에 비싼 SRAM을 사용할 수는 없다. 하지만 프로그램은 보통 코드와 데이터의 일부분에만 접근하기 때문에(지역성) 접근할 내용들을 미리 (작고 비싸지만)빠른 저장장치에 로드해 사용하는 것을 캐시라고 한다. 즉 캐시도 구체적인 실체라기보다는 추상화된 개념이다.

1-6. 저장장치들은 계층구조를 이룬다

1-7. 운영체제는 하드웨어를 관리한다

추상화는 복잡한 시스템에서 중요한 사항만을 강조하고, 불필요한 세부 구현을 감추어 단순화하는 것

어려운 개념인 추상화가 등장한다. 프로세서, 메인 메모리, 입출력장치들은 모두 구분 가능한 실체를 지칭한다. 프로세스, 가상메모리, 파일은 실체에 대한 추상화(된 개념이)다.

• 프로세스: 독립적으로 실행되는 프로그램의 인스턴스(인스턴스는 개념으로부터 구현된 실체를 의미한다) 프로세서, 메인 메모리, 입출력장치를 아우르는 추상화다. 실행 중인 프로그램에 대한 운영체제의(에 의한) 추상화다. 프로그램은 프로세서, 메인 메모리 등 자원을 점유하고 입출력장치들과 상호작용할 뿐, 그렇다고 이들 그 자체인 것은 아니다. 프로그램이 작업을 수행하고, 프로그램이 메모리를 차지하는 것 같지만, 현실에서는 모두 하드웨어가 한다. 자원 점유와 상호작용, 명령을 실행하고 동작하는 주체를 추상적인 개념으로 표현한 것이라고 보면 되겠다.(그런 주체가 물리적으로 실존하는 것이 아니므로) 이런 프로세스들이 모두 동시에 실행되는 것처럼 보이는 이유는 운영체제가 문맥 전환을 통해서 교차실행하기 때문이다.

• 스레드: 프로세스 내부의 실행 흐름 단위 프로세스와 비슷한 개념으로 한 프로세스에서 실행되는 다른 프로그램이라고 대강 이해할 수 있다. 스레드는 동일한 프로세스 내에서 구분된다.(두 개 이상의 프로세스에 걸친 스레드는 있을 수 없다.) 같은 프로세스 내에서 코드, 데이터, 힙 영역을 공유하나 스택은 공유하지 않는다. 스택은 입출력 순서가 중요하기 때문에 반드시 순서에 따라 실행되는 단위(스레드, 프로세스)가 독립적으로 가지고 있어야 한다.

• 스레드를 구분하는 이유 프로세스를 두고 스레드라는 개념을 별도로 정의한 이유는: 스레드간 문맥전환은 프로세스 간 문맥 전환보다 빠르다.(메모리와 자원을 공유하기 때문에 교체해야 하는 정보가 적다.) 데이터 공유가 용이하다. 그러므로 같은 프로세스 내에서 병렬처리가 필요할 때 유용하다.

• 문맥전환이란 프로세서가 현재 실행 중인 프로세스/스레드의 상태(레지스터 값, 프로그램 카운터 등)를 저장하고, 다음에 실행할 프로세스/스레드의 상태를 복원하는 과정

• 가상메모리: 가상메모리는 각 프로세스들이 각자의 메인 메모리를 사용하고 있는 것 같은 환경을 제공하는 추상화이다. 각 프로세스는 실제 메모리의 주소를 통해 접근하지 않고 가상주소를 통해 메모리에 접근한다. 모든 프로세스가 실제로 메모리 공간을 일정부분씩 점유를 한다고 하면 메모리 공간이 매우 많이 필요할 것이다. 프로세스가 할당된 메모리 공간을 모두 사용하는 경우는 적으니 일단 가상메모리 주소로 넉넉하게 할당해주고, 실제 데이터를 운영체제가 메모리에 알맞게 정리해서 관리한다. 그래서 가상 메모리 공간의 합은 실제 메모리 공간보다 클 수 있고, 이 경우 보조 저장장치에 기록하여 관리한다. 아래 사진에서 보듯 프로세스는 메모리 공간을 유동적으로 사용한다.

• 파일: 파일이 추상화라는 것이 잘 감이 안 오지만 디스크, 키보드, 네트워크 등 모든 입출력장치들은 파일로 모델링한다.

• 시스템은 네트워크를 사용하여 다른 시스템과 통신한다 네트워크는 또 다른 입출력장치일 뿐이라고도 볼 수 있다.

  2. 정보의 표현과 처리

  헷갈리는 부동소수점만 정리

  2-4. 부동소수점

  2-4-1. 비율 이진수

  이진수를 $b=∑_{i=-n}^{m}2^i×b_i$로 표기한 것. 책에서 이진소수 중 소수부가 모두 1인 수를 약식으로 $1-ɛ$ $(ɛ=2^n$, $n$은 음의 정수$)$로 표기한다. 그러나 컴퓨터에서 비율 이진수로 소수를 저장하고 표현하려면 자리수에 비례한 메모리 공간이 필요해진다.

  2-4-2. IEEE 부동소수점 표시

  유효숫자 표시와 유사하다. $V=(-1)^s×M×2^E$ $(s=0, 1$ , $0≤M<1$ 또는 $1≤M<2$, $E$는 정수$)$ 0 단일정밀도 부동소수점은 총 32비트(4바이트)로 구성되며 부호 1비트, 지수 8비트, 가수 23비트 이중정밀도 부동소수점은 총 64비트(8바이트)로 구성되며 부호 1비트, 지수 11비트, 가수 52비트(가수부가 4바이트를 넘는다.)

편의를 위해 단일정밀도 부동소수점을 기준으로 설명

2-4-2-1. 부호 표시

부호는 $s$가 $0$이면 양수, $1$이면 음수.

2-4-2-2. 지수 표시

부호와 지수를 합쳐서 부호있는 정수형처럼 2의 보수로 표현할 것 같지만 아니다. 9비트 정수형에서 $-1$은 $111111111$, $0$은 $000000000$으로 표현되지만 IEEE 부동소수점의 지수에서는 $2^{k-1}-1$($k$는 지수 비트수. 이 숫자를 $Bias$라고 한다.)를 $0$으로 삼아 선형적으로 표현된다. $E=e-Bias$($e$는 지수표시) 단일정밀도에서 $Bias=127$이고 $00000001$은 $-126$을, $01111111$은 $0$을, $11111110$은 $127$을 가리킨다. $00000000$과 $11111111$은 각각 $-126$과 무한대(가수가 $0$인 경우)를 나타낸다. $00000000$이 $-127$이 아니라 $00000001$과 같이 $-126$을 가리키는 이유는 가수부가 $2^{-(k-1)}$미만인 수(특히 $0$)를 표현할 때 사용하기 위함으로 아래에서 서술한다. $11111111$이 $128$이 아닌 무한대를 가리키는 이유는 매우 큰 수를 $2^{129}-ɛ$으로 근사할 수 밖에 없는 경우를 피하기 위해서일 듯 하다.

2-4-2-3. 가수 표시

1. 지수가 $00000001-11111110$인 경우(정규화 값) 가수를 $1.****$가 되도록($1≤M<2$) 표시한다. 다만 비트에는 소수부만 표시한다. 가수가 $1.00010111$인 경우 $00010111$만 저장한다.(암시적 선두 1표시, hidden bit) 이런 구성은 가수표현에 1비트를 절약하여 정밀도를 높인다. 하지만 $1$미만의 가수를 표시할 수 없다. 따라서 지수가 $00000000$일 때에 다른 표시법을 사용한다.

2. 지수가 $00000000$인 경우(비정규화 값) 가수를 $0.****$가 되도록($0≤M<1$) 표시한다. 비트에는 소수부만 표시한다. 0을 표시할 수 있으나 이 경우 표현할 수 있는 최댓값은 지수가 $1-ɛ$(부동소수점에서 $ɛ=2^{-23}$)인 경우이므로 지수를 $-127$로 해석하는 경우 표현할 수 없는 부분이 생긴다. 따라서 $00000000$지수도 $-126$으로 해석하는 것이다.

3. 지수가 $11111111$인 경우(특수 값) 가수가 0인 경우 무한대를 가리킨다.(부호는 $s$에 따라 달라진다) 가수가 0이 아닌 경우 잘못 표현된 숫자(NaN)을 가리킨다.

   2-4-3. 예시

4. 정규화 값 1 01111110 00000100000000000000000 $=(-1)^1×2^{01111110_2-01111111_2}×1.000001_2$ $=(-1)^1×2^{126-127}×\frac{65}{64}$ $=(-1)^1×2^{-1}×\frac{65}{64}$ $=(-1)^1×\frac{65}{128}=-0.5078125$

5. 비정규화 값 0 00000000 10000000000000000000000 $=(-1)^0×2^{-126}×0.1_2$ $=(-1)^0×2^{-126}×\frac{1}{2}$ $=(-1)^0×2^{-127}$ $=5.8774718e-39$

6. 특수 값 1 11111111 00000000000000000000000 $=-∞$

   1 11111111 11100000000000000000000 $=NaN$

   2-4-4. 근사법(rounding 반올림)

   소수를 근사하려는 자리수 아래가 10000...의 형태인 경우 어느 쪽 숫자로 근사할 것인지가 문제가 된다. 10진법에서 xx.xxxx50000인 경우의 문제와 동일하다. IEEE에서는 네 가지 근사 모드를 정의한다.

7. 짝수근사법(round-to-even) 기본 짝수와 가까운 곳으로 근사하는 방법. $3.5$는 $4$로, $4.5$도 $4$로 근사한다. $1001.1_2$은 $1010_2$으로, $1010.1_2$도 $1010_2$로 근사한다. 수가 많은 경우 통계적 편향을 방지하기 위해 사용한다.

8. 영방향 근사(round toward-zero) 0과 가까운 곳으로 근사한다.

9. 하향근사(round-down) 작은 쪽으로 근사한다.

10. 상향근사(round-up) 큰 쪽으로 근사한다. 양수에서 반올림하려는 자리수만으로 처리할 수 있다는 특징을 갖는다. 일상에서 자주 사용하는 방식

    2-4-5. 부동소수점 연산

    책에서는 연산과정을 자세히 소개하기보다는 부동소수점 연산에 적용되지 않는 수학적 특성들만을 설명하고 있다. 기본적으로 부동소수점은 근사치로 저장되기 때문에 연산 또한 근사한 결과만 보장할 수 있는 정도의 정밀도만 갖도록 만들어졌다.

    2-4-5-1. 부동소수점 덧셈($+^f$)

11. 교환법칙이 성립한다. $x+^fy=y+^fx$

12. 결합법칙은 성립하지 않는다. $(x+^fy)+^fz≠x+^f(y+^fz)$인 $x,y,z$가 존재한다.

    예: $(3.14+^f1e10)-^f1e10 = 1e10-^f1e10 = 0$ round(1e10) = 0 10100000 00101010000001011111001($2^{33} × 1.00101010000001011111001_2$) round(3.14) = 0 10000000 10010001111010111000011($2^1×1.10010001111010111000011_2$) 3.14의 지수부를 33로 두게 되면 round(3.14) = $2^{33} × 0.00000000000000000000000_2$ = $0$ 이 되므로 $3.14+^f1e10=1e10$이 된다. 반면, $3.14+^f(1e10-^f1e10)=3.14+^f 0=3.14$이므로 $(3.14+^f1e10)-^f1e10 ≠3.14+^f(1e10-^f1e10 )$

13. 연산에 대한 단조성을 갖는다. $a≤b$이면 $x+^fa≤x+^fb$가 항상 성립한다. 즉, $a<b$이지만 $x+^fa=x+^fb$인 경우는 존재할 수 있다.

    2-4-5-2. 부동소수점 곱셈($×^f$)

14. 교환법칙이 성립한다.

15. 항등원(1.0)을 갖는다.

16. 결합법칙은 성립하지 않는다. 예: $(1e20×1e20)×1e-20=∞×1e-20=∞$ $1e20×(1e20×1e-20)=1e20×1=1e20$

17. 덧셈에 대한 분배법칙이 성립하지 않는다. $a×(b+c)≠ a×b+a×c$인 $a,b,c$가 존재한다. 예: $1e20×(1e20-1e20)=1e20×0=0$ $1e20×1e20-1e20×1e20=∞-∞=NaN$

18. 연산에 대한 단조성을 갖는다.

3. 프로그램의 기계수준 표현

x86-64에 기초해 어셈블리어를 배우고, 이것이 컴퓨터를 어떻게 조작하는지를 배운다. 어셈블리어는 ATT표기법을 따른다.

3-1. 역사적 관점

32비트 아키텍처까지 이어오던 인텔의 x86구조를 따라 만들던 AMD가 64비트 전환에서는 치고 나왔다는 그런 이야기. 고대부터 호환성을 64비트까지 끌고 오면서 역사적 관점에서만 이해가 가능한 부분도 있다는 언급도 있다. 인텔의 IA64가 어떻게 망했는지 찾아보는 것도 재미있다.

3-2. 프로그램의 인코딩

C코드는 어셈블리어를 거쳐 실행파일로 만들어진다.

3-2-1. 기계수준 코드

컴퓨터 시스템은 세부구현을 감추기 위해 여러가지 추상화를 사용하고 있다.

1. 기계수준 프로그램의 형식과 동작은 인스트럭션 집합구조(ISA. 흔히 명령어 셋, CPU 아키텍처라고 부르는)에 의해 정의된다.
2. 기계수준 프로그램(기계어 코드)이 사용하는 메모리 주소는 가상주소이다. 메모리매우 큰 바이트 배열인 것 처럼 주소를 넓게 사용하고, 운영체제가 실제 메모리에 입력과 출력을 관리한다. 어셈블리 코드는 기계어 코드와 함께 저수준 언어로 분류된다. 기계어 코드는 바이너리라 그대로 읽기에는 의미를 파악하기 힘들기 때문에, 바이너리인 기계어 코드를 문자로 구현한 것이 어셈블리 코드라고 이해할 수 있다.

   3-3. 데이터의 형식

• x86-64에서 자료형의 길이 별 접미사 Byte(1byte): b Word(2bytes): w Double word(4bytes): l Quad word(8bytes): q Single precision(4bytes): s Double precision(8bytes): l

  3-4. 정보 접근하기

  레지스터는 프로그램 카운터, 정수 레지스터, 조건코드 레지스터, 벡터 레지스터가 있다. 정수 레지스터의 종류:

3-4-1. 오퍼랜드 식별자

어셈블리어 명령어 대부분은 오퍼랜드(피연산자)가 필요하다. 오퍼랜드는 연산을 수행할 소스 오퍼랜드 와 결과를 저장할 목적지 오퍼랜드 가 있다. 소스 오퍼랜드로는 1. 상수, 2. 레지스터, 3. 메모리를 지정할 수 있다. 목적지 오퍼랜드로는 1. 레지스터, 2. 메모리를 지정할 수 있다.

오퍼랜드의 지정 대상에 따른 종류와 표시법:

1. 즉시값(immediate) 현재 참조 중인 프로그램 데이터 자체를 지정한다.(상수를 지정한다는 뜻) 상수 앞에 $를 붙여 표시한다.
   • 표기법: $$Imm$
   • 오퍼랜드 값: $Imm$(상수 자체가 오퍼랜드 값이 된다.)
   • 예시: $-577, $0x1F
2. 레지스터(register) 레지스터의 값을 지정한다.
   • 표기법: $r_a$
   • 오퍼랜드 값: $R[r_a]$ ($R[r_a]$은 레지스터 $r_a$에 담겨있는 값에 접근)
   • 예시: %rax, %eax
3. 유효주소(effective address) 메모리 주소를 전달하여 그 주소에 접근하는 방식. 주소를 계산하도록 할 수도 있다.
   • 표기법: $Imm$, $Imm(r_b,r_i, s)$
   • 오퍼랜드 값: $M[Imm]$, $M[Imm + R[r_b] + R[r_i]×s]$ ($M[Imm]$은 메모리 주소 $Imm$에 담겨있는 값에 접근)
   • 예시: 0x104, (%rax, $rdx, 4)

3-4-2. 데이터 이동 인스트럭션

3-4-2-1. MOV클래스

데이터를 복사하는 명령어인 MOV클래스에 대해 배운다. MOV클래스는 접미사에 따라 네 개로 구성된다. 네 인스트럭션은 다른 크기의 데이터에 대해 계산한다는 점만 다르다.

MOV클래스의 종류:

1. movb
2. movw
3. movl
4. movq

• 사용 예: movb $0xAF, %al

오퍼랜드로 레지스터를 지정하는 경우, 레지스터의 크기는 접미사가 의미하는 크기와 동일해야 한다. x86-64에서는 메모리에서 메모리로 값을 복사할 수 없다.(두 오퍼랜드를 모두 메모리로 지정할 수 없다.)

명령어 별 예외

• movl명령어는 목적지 오퍼랜드로 레지스터를 지정하는 경우 지정된 레지스터 상위 4바이트의 값을 0으로 변경한다. movl명령어를 제외한 나머지는 지정된 레지스터의 값만 변경한다. 예시: %al 레지스터에 값을 쓰도록 movb명령어를 사용한 경우 %al레지스터 공간을 제외한 (동일한 레지스터 공간을 공유하는) %ax레지스터의 값은 유지된다.

  이렇게 설계한 이유는 32비트 호환성을 위해서라고 추측된다. 0확장을 하지 않는 경우 movl로 레지스터에 기록한 데이터는 앞 32비트만 의미가 있고 사용할 수 있다. 그로 인한 호환성 충돌의 경우는 지금은 쉽게 떠오르지 않는다. 마찬가지로 8비트, 16비트에서 확장된 x86의 역사를 생각하면 movw과 movb에는 적용되지 않는 것이 의문이지만, 어차피 소급하여 변경할 수 없었을 것이다. x86-64는 이전과 다르게 AMD가 개발하였다는 점도 원인일 수 있을 것 같다.

• movq명령어는 소스 오퍼랜드로 상수를, 목적지 오퍼랜드로 레지스터를 지정하는 경우 32비트인 2의 보수 숫자로 나타낼 수 있는 상수만을 소스 오퍼랜드로 갖는다.
• movabsq는 소스로 64비트 상수 목적지로 레지스터를 갖는 경우에 사용한다.

  3-4-2-2. MOVZ, MOVS 클래스

  MOV 클래스와 유사하나 소스를 확장하여 이동한다. MOVZ 클래스의 명령어들은 목적지의 남은 바이트를 모두 0으로 채워 확장한다. MOVS 클래스의 명령어들은 부호확장을 통해 목적지의 남은 바이트를 채워 확장한다. 뒤에 소스와 목적지의 바이트 길이 접미사를 붙여 사용한다. 목적지가 소스보다 길이가 길어야 한다. unsigned 자료형을 확장할 때 MOVZ 클래스를 사용한다. signed 자료형을 확장할 때 MOVS 클래스를 사용한다.

MOVZ 클래스의 종류(movzlq는 movl과 동일한 기능을 수행하므로 존재하지 않는다.)

1. movzbw
2. movzbl
3. movzwl
4. movzbq
5. movzwq

MOVS 클래스의 종류

1. movsbw
2. movsbl
3. movswl
4. movsbq
5. movswq
6. movslq

   3-4-3. 데이터 이동 예제

   // C코드
   void casting(char *sp, int *dp) {
    *dp = (int) *sp
   }
   

void casting2(int *sp, unsigned char *dp) { *dp = (unsigned char) *sp }

이 코드를 어셈블리로 표현하면 다음과 같다.
(sp의 값은 %rdi에 dp의 값은 %rsi에 저장되어 있다)
```assembly
casting:
  movsbl (%rdi), %eax
  movl %eax, (%rsi)
casting2:
  movl (%rdi), %eax
  movb %al, (%rsi)

3-4-4. 스택 데이터의 저장과 추출(push, pop)

pushq 명령어와 popq 명령어를 사용한다. pushq %rbp 명령어는 먼저 스택 포인터를 감소시키고 메모리에 %rbp값을 저장한다.

subq $8, %rsp
movq %rbp, (%rsp)

위 코드와 완전히 동일한 작업을 수행하나 pushq %rbp 명령어가 더 인코딩 효율적이다. popq %rax 명령어는 반대로 스택에서 값을 읽은 후 스택 포인터를 증가시킨다.

movq (%rsp), %rax
addq $8, %rsp

와 동일하다.

3-7. 프로시저

프로시저는 다른 언어에서의 함수와 유사한 개념으로, 특정 작업을 수행하기 위해 작성된 코드 블록이다. 각 프로시저는 고유한 이름을 가지며, 프로그램의 다른 부분에서 호출할 수 있다. 프로그램에서 주요한 추상화이며, 함수처럼 구체적인 구현을 감춰주는 추상화 메커니즘으로도 이용한다.

3-7-1. 런타임 스택

프로시저는 데이터를 스택에 저장한다. 다른 프로시저를 호출하기 위해서는 필요한 스택 프레임의 공간만큼 스택을 늘려야 한다. saved registers, local variables, argument build area에 무엇이 저장되는지는 뒤에서 언급

3-7-2. 제어의 이동

프로시저를 호출하면 프로그램 제어를 호출된 프로시저로 전달한다. 제어를 프로시저P에서 프로시저Q로 전달하는 것은, 단순히 프로그램 카운터를 프로시저 Q의 시작 코드 주소로 설정하는 것이다. 나중에 프로시저가 리턴(종료)해야할 때에 프로시저 P의 실행을 재개해야 하므로, 프로시저 P는 프로시저 Q를 호출하기 직전에 리턴 후 실행할 명령어(바로 다음 명령어)를 스택에 푸시한다. 이것이 [[#3-7. 프로시저#3-7-1. 런타임 스택|3-7-1.]] 그림의 Return address이다. 프로시저 Q는 ret 명령어를 통해서 리턴할 때 Return address를 스택에서 팝해와 PC를 설정한다.

3-7-3. 데이터 전송

프로시저가 호출될 때와 리턴할 때, 프로시저는 제어를 전달할 뿐 아니라 데이터를 인자(아규먼트)와 리턴값으로 전달한다. 보통 이런 인자 전달은 레지스터를 통해 일어난다. x86-64에서 인자 전달을 위해 최대 6개의 인자들을 레지스터를 통해 전달할 수 있다. 전달할 인자가 6개를 넘는 경우 스택을 통해 전달된다. 인자가 6개를 넘으면 프로시저를 호출하기 전 그 넘는 양만큼 스택 프레임에 할당하고 (현재 프로시저의)스택 탑에 넣는다.([[#3-7. 프로시저#3-7-1. 런타임 스택|3-7-1.]] 그림의 호출하는 프로시저 P의 스택프레임-Argument n부터 Argument 7부분) 인자들이 모두 배치되고 나면 프로시저를 호출할 수 있다. 만약 호출된 프로시저가 또 다시 인자가 6개를 넘는 다른 프로시저를 호출할 경우에는, 자신의 스택 프레임에 "Argument build area"라고 이름 붙인 영역([[#3-7. 프로시저#3-7-1. 런타임 스택|3-7-1.]] 그림 Q 스택 프레임)으로 공간을 할당할 수 있다.

3-7-4. 스택에서의 지역저장공간

프로시저가 지역 데이터를 메모리에 저장해야 하는 경우가 있다:

1. 지역 데이터를 모두 저장하기에는 레지스터의 수가 부족한 경우
2. (C언어에서)지역변수에 연산자 '&'가 사용되었으며, 이 변수의 주소를 생성할 수 있어야 하는 경우
3. 일부 지역변수들이 배열 또는 구조체여서 이들이 배열이나 구조체 참조로 접근되어야 하는 경우 특히 2, 3번의 경우에는 데이터가 적더라도 반드시 메모리 공간을 사용해야 한다. 일반적으로 프로시저는 위와 같은 경우 스택 포인터를 감소시켜서 스택 프레임의 "Local variables"라고 이름 붙인 영역([[#3-7. 프로시저#3-7-1. 런타임 스택|3-7-1.]] 그림 Q 스택 프레임)에 공간을 할당한다.

   3-7-5. 레지스터를 이용하는 지역저장소

   스택과 달리 레지스터들은 모든 프로시저들이 공유한다. 하나의 프로시저(호출자)가 다른 프로시저(피호출자)를 호출할 때, 피호출자가 호출자가 나중에 사용할 레지스터 값을 덮어쓰지 않기 위해서 프로시저들이 준수해야 할 레지스터 사용관습들을 소개하는 장이다.

   3-7-5-1. 피호출자-저장 레지스터

   %rbx, %rbp, %r12-%r15([[#3-4. 정보 접근하기|3-4.]] 그림에서 Callee saved로 표시된 레지스터)는 피호출자-저장 레지스터로 구분한다. 피호출자 프로시저는 리턴될 때 호출된 시점과 동일한 레지스터 값들을 보장해야 한다. 그럴 수 있도록 피호출자 프로시저는 이 값들을 변경하지 않거나, 스택에 푸시해 두었다가 리턴하기 전에 팝해오는 방식으로 레지스터를 보존해야 한다. 레지스터 값들을 푸시하면 "Saved registers"라고 이름 붙인 영역([[#3-7. 프로시저#3-7-1. 런타임 스택|3-7-1.]] 그림 Q 스택 프레임)을 생성한다.

   3-7-5-2. 호출자-저장 레지스터

   피호출자-저장 레지스터와 스택 포인터(%rsp)를 제외한 모든 레지스터들은 호출자-저장 레지스터로 구분한다. 호출자-저장 레지스터는 피호출자 프로시저로부터 변경될 수 있다는 것을 의미한다. 따라서 호출자 프로시저는 피호출자가 변경해도 되는(의도적으로 변경하도록 하는)레지스터들을 제외하고는, 호출하기 전 이 레지스터들을 저장해야 할 의무가 있다.

   3-7-6. 재귀 프로시저

   함수와 마찬가지로 재귀적인 방식으로 프로시저를 정의할 수도 있다. 이런 재귀 방식은 별도의 호출들이 서로 간섭하지 않도록 구성된다. 프로시저의 스택운영방식은, 이런 정책을 자연스럽게 제공한다.

   3-8. 배열의 할당과 접근

   3-8-1. 기본 원리

   C언어 에서의 배열 선언 T A[N](T는 자료형, N은 정수 길이)은 두 가지 효과를 갖는다.
4. $L·N$ 바이트($L$은 자료형T의 크기) 만큼의 공간을 하나의 블록(연속적인 메모리 공간)으로 메모리에 할당한다.
5. 식별자 A를 배열 시작 주소($x_A$) 포인터로 사용한다. 따라서 배열의 $i$번 원소(A[i])는 주소 $x_A+L·i$에 저장된다.

   3-8-2. 포인터 연산

   포인터 변수도 결국에는 주소 값을 가지는 변수이기 때문에 연산을 사용할 수 있다. 정수 연산과 다른 점이 있다면 $L$만큼을 1로 하여 연산한다. 즉 &A[3] - &A[2]은 $L$이 아니라 1이다.

   3-8-3. 다중 배열

   T A[N][M]은 $NM$바이트 만큼의 공간을 할당한다. A[i][j]는 $x_a+L·(iM+j)$에 접근한다. A[i]는 $x_a+L·(iM)$ 주소를 가리킨다.

   3-8-4. 고정크기의 배열

   C 컴파일러는 고정크기의 다차원 배열을 사용하는 코드에 대해 다양한 최적화를 수행할 수 있다.

// 고정 크기 배열
#define N 16
typedef int fix_matrix[N][N];

fix_matrix[i][j]의 주소는 $x_a+L·(iM+j)$로 구할 수 있다. 하지만 연속적인 인덱스에 접근해야 할 때 매 번 곱셈과 덧셈을 반복하는 것은 비효율적이다. 컴파일러는 이런 경우에 이전 인덱스를 기억해두었다가 $L$씩 더하는 방식으로 순회를 진행하도록 최적화한다. 특히 고정크기의 배열인 경우에는 그 크기 또한 컴파일 단계에서 확정할 수 있으므로 인덱스를 저장할 변수도 사용하지 않도록 최적화할 수도 있다.

3-8-5. 가변크기 배열

C는 이제 아래와 같은 가변크기 배열 할당을 허용한다.

int A[i][j];
int *A = (int *)malloc(sizeof(int)*i*j)

6. 메모리 계층구조

6-2. 지역성

잘 작성한 컴퓨터 프로그램은 좋은 지역성 locality을 보여준다.

1. 시간 지역성 temporal locality 한번 참조된 메모리 위치는 가까운 미래에 다시 여러 번 참조될 가능성이 높은 것 반복문을 사용한 프로그램은 같은 인스트럭션과 변수들에 반복적으로 접근하는 경향이 있다.
2. 공간 지역성 spatial locality 어떤 메모리 위치가 참조되면, 가까운 미래에 근처의 메모리 위치를 참조할 가능성이 높은 것 배열을 사용한 프로그램은 (특히 순회하는 경우) 근처의 메모리를 참조하는 경향이 있다.

하드웨어는 지역성을 활용하여 캐시메모리 등 작업을 빠르게 하기 위한 설계가 적용되어 있으므로, 지역성을 이해하고 좋은 지역성을 갖도록 프로그램을 작성하는 것은 성능에서 중요하다.

6-2-1. 프로그램 데이터 참조의 지역성

int sumvec(int v[N]) {
    int i, sum = 0;

    for (i = 0; i < N; i++) 
        sum += v[i];
    return sum;
}

배열의 합을 계산하는 함수를 생각하자. 위 코드에서 sum은 반복적으로 참조되므로 좋은 시간 지역성을 가지고 있다. 반면 스칼라 변수로서 인접한 메모리 공간과 연관이 없으므로 공간 지역성이 존재하지 않는다. v의 원소들은 순차적으로 읽히므로 v에 대해서는 좋은 공간 지역성을 가지고 있다. 그러나 각 원소들은 한 번만 접근되므로 나쁜 시간 지역성을 가지고 있다. 그러므로 함수 sumvec은 좋은 시간 또는 공간 지역성을 지니므로 전체적으로 좋은 지역성을 지녔다고 볼 수 있다.

이렇게 벡터의 매 k번째 원소를 방문하는 것을 stride-k 참조 패턴이라고 부른다. sumvec함수는 stride-1 참조 패턴을 가진다. 일반적으로 k가 증가하면 공간 지역성은 감소한다.

int sumarrayrows(int a[M][N]) {
    int i, j, sum = 0;

    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            sum += a[i][j];
    return sum
}

이차원 배열의 합을 계산하는 함수를 생각하자. 위 함수는 stride-1 참조 패턴을 갖는다.

int sumarraycols(int a[M][N]) {
    int i, j, sum = 0;

    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            sum += a[i][j];
    return sum
}

똑같은 동작을 하지만 열우선 참조를 하는 다른 함수를 생각하자. 이제 stride-N 참조 패턴을 갖는다. 이렇게 같은 역할을 하더라도 공간 지역성에서 차이가 커질 수 있다.

6-2-2. 인스트럭션 선입의 지역성

프로그램의 인스트럭션 역시 메모리에 저장되고 CPU가 읽어들여야 하므로 인스트럭션 선입(읽기)에 대한 지역성도 평가할 수 있다. 예를 들어 sumvec 함수에서 사용한 for루프 내의 인스트럭션들은 순차적인 메모리 순서대로 반복해 실행되며, 좋은 공간 지역성을 갖게 된다.

8. 예외적인 제어흐름

시스템은 프로그램의 실행과는 관련 없는 시스템 상태 변화에도 반응할 수 있어야 한다. 시스템은 제어흐름의 갑작스런 변화를 만드는 방법(예외적인 제어흐름 exceptional control flow (ECF))으로 이러한 상황에 반응한다.

8-1. 예외상황

예외상황은 하드웨어 또는 운영체제에 의해 구현된 예외적인 제어흐름의 한 형태이다. 예외상황에 대한 처리 방식을 간단히 나타낸 그림이다. 명령어 $I_{curr}$를 실행하고 있을 때 프로세서 상태에 중요한 변화(이벤트)가 일어난다면, 상태는 예외처리 핸들러로 보내지고 보내진 상태에 따라 예외를 처리한 뒤 프로그램을 종료시키거나 다시 프로그램의 실행 흐름으로 되돌아 간다.

8-1-1. 예외처리

예외상황은 하드웨어와 소프트웨어가 긴밀하게 협력해야한다. 하드웨어와 소프트웨어 사이에 작업이 분배되는 모습을 자세히 살펴본다.

시스템은 가능한 예외상황마다 예외번호를 할당하고 있다. 일부는 프로세서(하드웨어) 설계자가, 나머지는 운영체제 커널(소프트웨어) 설계자가 할당한다.

프로세서 설계가 할당한 예외번호의 예: divide by zero, 페이지 오류, 메모리 접근 위반, breakpoint, 산술연산 오버플로우 커널 설계자가 할당한 예외번호의 예: 시스템 콜, 외부 I/O 디바이스로부터의 시그널

시스템 부팅 시 운영체제는 예외 테이블[^8-1]을 할당하고 예외번호별 처리 핸들러로 할당한다. 즉, 예외 테이블의 엔트리(배열 인덱스) k가 예외상황 k에 대한 핸들러의 주소를 갖는다. 프로세서가 이벤트 발생을 감지하면 해당되는 예외번호 k를 결정하고, 예외 테이블의 k를 참조해 핸들러를 호출한다.

[^8-1]: 예외 테이블의 주소는 예외 테이블 베이스 레지스터라는 특별한 레지스터에 저장한다.

예외상황은 프로시저 콜과 유사하지만 중요한 차이점이 있다:

1. 핸들러를 호출하기 전에 스택에 리턴주소를 푸시하는 것은 같지만, 예외의 종류에 따라 현재(이벤트가 발생했을 때 실행 중이던) 인스트럭션 또는 다음 인스트럭션을 푸시한다.
2. 중단됐던 프로그램으로 돌아가기 위해 필요한 프로세서 상태를 푸시한다.
3. 이것들은 사용자 스택이 아니라 커널 스택 상에 푸시된다.
4. 예외 핸들러는 커널 모드에서 돌아가므로 모든 시스템 자원에 완전히 접근할 수 있다. 핸들러가 이벤트를 처리한 후 다시 사용자 프로그램으로 돌아갈 때에는 원래 프로세서의 제어상태와 레지스터 상태를 돌려놓는다.

   8-1-2. 예외의 종류 Exception Class

   

8-1-2-1. 인터럽트 Interrupt

입출력 디바이스로부터 신호를 받아 발생하는 예외이다. 특정 인스트럭션의 실행 여부와 관련이 없기 때문에 비동기적(Async)이다.[^8-2] 프로세서가 인스트럭션 실행을 완료하고 인터럽트 시그널을 감지하게 되면, 시스템 버스에서 예외번호를 읽어 해당 인터럽트 핸들러를 호출한다. 핸들러가 리턴할 때엔 항상 제어를 다음 인스트럭션으로 돌려준다. 즉, 프로그램은 인터럽트가 발생하지 않은 상황과 같이 계속 실행된다. [^8-2]: 다른 예외의 종류들은 오류 인스트럭션 faulting instruction*의 실행에 의해 동기적으로 일어난다. 비동기적 예외를 외부 인터럽트 *External Interrupt 또는 하드웨어 인터럽트 Hardware Interrupt, 동기적 예외를 내부 인터럽트 Internal Interrupt 또는 소프트웨어 인터럽트 Software Interrupt라고 부르기도 한다.

8-1-2-2. 트랩 Trap*과 시스템 콜 *System Call

트랩은 의도적인 예외상황이며 어떤 인스트럭션을 실행한 결과로 발생한다(Sync). 프로그램이 시스템 콜을 호출하였을 때나 예외 상황이 발생하여 시스템으로 제어를 넘기기 위해 발생시키는 예외상황이다. 시스템 콜은 사용자 프로그램에서 커널의 동작을 요청할 때 사용하는 프로시저와 유사한 인터페이스이다. 시스템 콜은 커널 모드에서 돌아가며, 이로 인해 커널 내에서 정의된 스택에 접근하며, 시스템을 제어하는 모든 인스트럭션을 실행할 수 있다.

x86-64에서 시스템 콜은 syscall이라는 트랩 인스트럭션을 통해서 제공된다. 리눅스 시스템 콜에 전달되는 모든 인자들은 범용 레지스터를 통해서 이루어진다. %rax 레지스터에 시스템 콜 번호를 보관하고, argument용 레지스터에 최대 여섯 개의 인자들을 보관한 후 호출하게 된다.

8-1-2-3. 오류 Fault

핸들러가 정정할 수 있을 가능성이 있는 에러 조건일 때 발생한다. 오류가 발생하면 프로세서는 오류 핸들러로 제어를 이동한다. 핸들러가 에러 조건을 정정할 수 있다면, 오류를 발생시킨 인스트럭션(현재 인스트럭션)으로 제어를 돌려주어 프로그램 실행을 계속한다. 정정할 수 없다면, 핸들러는 커널 내부의 abort 루틴으로 리턴하여 프로그램을 종료한다.

대표적인 예시로 페이지 오류 예외가 있다. 인스트럭션이 참조하는 메모리가 물리 메모리에 페이지되어 있지 않은 상황에 발생한다. 핸들러는 디스크에 있는 페이지를 물리 메모리로 로드하고 다시 오류를 일으킨 인스트럭션으로 돌아가게 해준다.

8-1-2-4. 중단 Abort

하듸웨어 같은 치명적인 에러에서 발생한다. 중단 핸들러는 무조건 응용프로그램을 중단하는 abort 루틴으로 제어를 넘겨준다.

9. 가상메모리

프로세스는 직접 물리 메모리 주소에 접근하는 것이 아니라 프로세스 각각이 갖는 가상 주소 공간을 통해서 메모리에 접근하게 된다. 단순히 부족한 메모리 공간을 확장하기 위한 수단을 넘어 효율적인 메모리 관리, 멀티태스킹, 메모리 보호, 프로세스 격리 등 다양한 기능을 한다. 따라서 가상메모리를 이해하는 것은 시스템이 어떻게 동작하는지 이해하고, 프로그램의 성능을 향상시키고 에러를 피하는데 도움을 준다.

9-1. 물리 및 가상주소 방식

초기의 PC, 디지털 신호 처리 프로세서, 임베디드 컨트롤러 등은 물리 주소 방식을 사용한다. 하지만 대부분의 현대 프로세스들은 가상주소방식*을 사용한다. CPU는 가상주소지정으로 가상주소(VA)를 생성해서 메인 메모리에 접근한다. 물리 메모리에 접근하기 전에 메모리로 보내지기 전에 *메모리 관리 유닛(MMU)가 적절한 물리주소로 번역한다.

9-3. 캐싱 도구로서의 VM

가상메모리는 디스크에 저장되며 1바이트 크기 배열로 구성된다. 디스크 안의 배열 정보는 메인 메모리로 캐시된다. 캐시는 블록 단위로 분할되어 디스크과 메인 메모리 사이를 잇는 역할을 하며 가상페이지라고 불린다. 물리메모리 또한 물리페이지(물리 프레임)로 분할되어 사용된다. 가상페이지는 언제나 셋 중 하나로 분류할 수 있다.

1. Unallocated: 할당되지 않은 페이지들. 데이터를 전혀 가지고 있지 않은 블록으로 디스크 공간을 차지하지 않는다.
2. Cached: 할당된 페이지 중 물리 메모리에 캐시된 페이지들.
3. Uncached: 할당된 페이지 중 물리 메모리에 캐시되지 않은 페이지들

   9-3-1. DRAM 캐시의 구성

   DRAM 캐시: 메인 메모리로 캐시하는 가상페이지 캐시 SRAM 캐시: L1, L2, L3 캐시 메모리로 캐시하는 메인 메모리 캐시

DRAM과 SRAM의 차이보다 디스크과 DRAM의 차이가 훨씬 더 크다. 따라서 DRAM 캐시의 미스를 줄이는 것은 중요하다.

9-3-2. 페이지 테이블

VM 시스템은 가상페이지가 DRAM 어디에 있는지, 어떤 물리 페이지를 캐싱했는지, 없다면 디스크 어디에 가상 페이지가 있고 어떤 페이지를 물리 메모리에서 제거할 것인지를 결정해야 한다. 이런 VM 시스템의 기능들은 운영체제, MMU의 주소 번역 하드웨어, 페이지테이블(가상페이지를 물리페이지로 매핑하는 자료구조. 물리메모리에 저장)의 조합으로 제공된다.

• 페이지 테이블: 페이지 테이블 엔트리(PTE)의 배열
• 페이지 테이블 엔트리: 할당 여부와 캐시된 위치(DRAM 또는 디스크) 등의 정보를 저장한다.

  9-4. 메모리 관리를 위한 도구로서의 VM

  VM은 메모리 관리를 단순하게 하는 목적으로도 사용된다.

1. 링킹을 단순화한다. 프로세스들이 실제 물리 메모리 어디에 저장할지와 관계없이 동일한 기본 메모리 포맷을 사용하도록 해준다. [[#3-7-1. 런타임 스택|예시]]

2. 로딩을 단순화한다. 리눅스 로더는 실행파일과 공유 목적파일들을 메모리에 로드하기 위해, 실제로 파일들을 읽어들이고 메모리에 적치하는 것이 아닌, 단순히 PTE가 이 파일들의 위치를 가리키게 한다.(메모리 매핑, 리눅스의 mmap)

3. 공유를 단순화한다. 운영체제는 C프로그램에서 커널과 표준 라이브러리 코드를 각 프로세스에서 별도로 포함시키지 않고, 동일한 물리페이지들로 매핑해 한 페이지를 공유하게 한다.

4. 메모리 할당을 단순화한다. 프로그램이 추가 힙 공간을 요구할 때, 물리 메모리에서 주소가 연속된 페이지를 찾을 필요 없이 연속적인 가상메모리 페이지를 할당하고 임의의 물리 페이지로 각각 매핑한다.

   9-5. 메모리 보호를 위한 도구로서의 VM

   사용자 프로세스는 읽기 전용 코드를 수정할 수 없어야 하며, 커널 코드나 데이터 역시 읽거나 수정할 수 없어야 한다. 또한 다른 프로세스의 사적 메모리에 접근할 수 없어야 한다. VM을 통해 별도의 가상 주소공간을 제공하면 이런 분리가 쉬워진다. PTE에 허가 비트를 추가해서 접근을 제어하는 방식이 가능해진다.

   9-6. 주소의 번역

   9-7. 사례 연구: 인텔 코어 i7/리눅스 메모리 시스템

   리눅스를 실행하는 인텔 cpu의 맥락에서 실제 가상메모리의 사례를 알아본다. x86-64에서는 64비트 가상/물리 주소공간이 가능함에도 현재에는 48비트 가상 주소공간과 52비트 물리 주소공간을 지원하고있다. (32비트 주소공간도 호환으로 지원한다.)

   9-7-2. 리눅스 가상메모리 시스템

   

5. 코드(텍스트) 영역:

   • 기계어 코드가 저장
   • 읽기 전용

6. 데이터 영역:

   • 초기화된 전역 변수와 정적 변수가 저장

7. BSS 영역:

   • 초기화되지 않은 전역 변수와 정적 변수가 저장
   • 프로그램 시작 시 0으로 초기화됨

8. 힙 영역:

   • 동적 메모리 할당 시 사용
   • 런타임 중 크기가 확장될 수 있음

9. 스택 영역:

   • 함수 호출 시 스택 프레임으로 영역이 확장되고, 함수 종료 시 해제됨
   • 스택 프레임에는 레지스터 저장 값, 지역 변수, 함수 인자, 리턴 주소를 저장 3번까지는 컴파일 단계에서 크기가 결정된다.

9-8. 메모리 매핑

9-9. 동적 메모리 할당

동적 메모리 할당기는 가상메모리의 힙(heap) 영역을 관리한다. 할당기는 힙을 다양한 크기의 블록들로 나누어 관리한다. 각 블록은 할당되었거나 가용한(free) 가상메모리의 연속적 묶음이다. 할당기는 크게 두 종류가 있다.

1. 명시적인 할당기 프로그램이 명시적으로 할당된 블록을 반환(free)해 줄 것을 요구한다. 예를 들어, C에서는 블록을 반환하기 위해 free함수를 사용한다.
2. 묵시적 할당기 할당된 블록이 더 이상 프로그램에 의해 사용되지 않은지를 할당기가 검출하고 반환한다. 가비지 컬렉터라고도 불리며, 사용하지 않는 블록들을 반환하는 작업을 가비지 컬렉션이라고 부른다.

   9-9-1. malloc과 free함수

   C 프로그램은 malloc함수를 호출해서 힙으로부터 블록들을 할당받는다. malloc함수는 요청된 size 이상의 메모리 블록의 포인터를 리턴한다. 32비트 모드(gcc -m32)에서 항상 8의 배수인 주소를 리턴하며, 64비트 모드에서는 16의 배수인 주소를 리턴한다.(정렬 제한사항)

   32비트 모드 기준으로 주소를 2진법으로 표현했을 때 마지막 세 자리가 000이라는 의미이다.

free함수는 블록의 시작 주소를 인자로 받아 블록을 반환하며, 인자가 블록의 시작 주소가 아닌 경우 아무런 동작도 하지 않는다.

9-9-2. 왜 동적 메모리 할당인가?

가장 중요한 이유는 프로그램을 실제 실행시키기 전에는 자료 구조의 크기를 알 수 없는 경우들이 있기 때문이다.

9-9-3. 할당기 요구사항과 목표

명시적 할당기에 요구되는 사항:

1. 임의의 요청 순서 처리하기 응용프로그램은 임의의 순서로 할당/반환을 요청하기 때문에 할당기는 어떤 순서의 요청이든 대응할 수 있어야 한다.
2. 요청에 즉시 응답하기 따라서 처리 속도를 위해 요청의 처리 순서를 바꾸거나 버퍼로 처리를 지연시킬 수 없다.
3. 힙만 사용하기
4. 블록 정렬하기 블록들을 어떤 종류의 데이터 객체라도 저장할 수 있는 방식으로 정렬해야 한다.
5. 할당된 블록을 수정하지 않기 가용 블록만 조작하거나 변경할 수 있으며, 할당 블록들은 수정하거나 이동시켜서는 안된다. 따라서 할당 블록들을 압축하는 기법들은 허용되지 않는다.

성능 좋은 할당기는 처리량과 메모리 이용도를 최대화한다.

1. 처리량 단위 시간당 완료되는 요청의 수
2. 메모리 이용도 메모리는 유한하므로 효율적으로 이용해야 한다. 가상 메모리라고 할지라도 프로세스들의 가상메모리의 총 합은 디스크 내의 스왑 크기를 넘을 수 없다. 이용도를 측정할 단위 중 하나로 최고 이용도가 있다. 할당/반환 요청을 순서대로 $$ R_0, ;R_1,;...,;R_k, ;..., ;R_{n-1}$$ 라고 할 때 최고 이용도는 현재 힙의 크기 대비 최고 데이터의 양의 비율로 나타낸다. $$ U_k=\frac{max_{i≤k};P_i}{H_k} $$ $U_k$는 요청 $R_k$가 완료된 후의 최고이용도 $H_k$는 요청 $R_k$가 완료된 후의 힙의 크기[^1] $P_i$는 요청 $R_i$가 완료된 후의 데이터의 총 크기 할당기의 목적은 $U_{n-1}$를 최대화하는 것이다.

처리량과 이용도는 서로 상충관계에 있으므로 할당기 설계에서 적절한 균형을 찾는 것이 중요하다.

[^1]: 단조 증가 가정. $H_k$를 힙의 최대 크기로 정의하면 단조 증가 가정을 완화할 수 있다.

9-9-4. 단편화

가용 메모리가 할당 요청을 수행할 수 없는 상황을 단편화라고 한다. 단편화는 두 가지 종류로 분류된다.

1. 내부 단편화 여러가지 이유로 할당된 블록이 데이터 크기보다 더 큰 경우를 말한다. 내부 단편화가 발생한 부분은 데이터를 저장하지 않음에도 할당을 위해 사용할 수 없다. 할당기의 최소 블록 크기보다 더 작은 데이터 블록을 요청했을 때 등에 일어날 수 있다. 할당기는 [[#9-9-1. malloc과 free함수|정렬 제한사항]]을 만족시키기 위해 데이터보다 블록 크기를 증가시킬 수 있기 때문이다. 내부 단편화는 (할당된 블록들의 크기)-(데이터들의 크기)로 구할 수 있어 정량화가 간단하다. 또한 내부 단편화의 크기는 이전 요청들과 할당기의 구현 방식에만 의존한다.
2. 외부 단편화 외부 단편화는 전체 가용 공간은 할당에 충분한 크기이지만, 이 요청을 처리할 수 있는 하나의 가용 블록은 없는 경우를 말한다. 외부 단편화가 발생하면 필요한 크기 이상의 가용 블록이 존재하지 않으므로 추가 힙 공간을 요청(힙 경계brk 확장)해야 한다. 이전에 할당받았던 블록을 반환하는 때 등에 일어날 수 있다. 외부 단편화는 측정하기 어려우며 미래 요청들에도 의존한다. 예를 들어, 현재 가용 블록들이 모두 4워드[^2] 크기를 가진다고 하면 외부 단편화의 발생 여부는 미래에 4워드보다 큰 블록을 요청하는지에 따라 달라질 수 있다.

외부 단편화는 예측하기 어렵기 때문에 할당기들은 보통 가용 블록들의 크기를 크게 유지하려는 방법을 사용한다.

[^2]: 가상 메모리에서 워드는 4바이트, 더블 워드는 8바이트

9-9-5. 구현 이슈

항상 요청한 크기만큼 힙을 증가시키고 그 이전 힙 경계 주소를 반환하는 간단한 할당기를 생각해볼 수 있다. 이 할당기는 처리량은 매우 좋지만 이용도는 매우 나쁠 것이다. 처리량과 이용도 사이에 좋은 균형을 유지하는 할당기는 다음 이슈들을 고려해야 한다:

1. 가용 블록 구성: 어떻게 가용 블록들을 지속적으로 파악하는가
2. 배치: 새로 할당할 블록을 배치할 가용 블록을 어떻게 선택하는가
3. 분할: 배치 후 가용 블록의 남는 부분들을 어떻게 처리하는가
4. 연결: 막 반환된 블록으로 어떤 작업을 할 것인가(주로 인접한 가용 블록과)

아래에서는 위의 이슈들의 간단한 구현인 묵시적 가용 리스트를 중심으로 설명한다.

9-9-6. 묵시적 가용 리스트

가용 블록 구성을 구현하기 위해

1. 블록 경계를 구분하고
2. 할당된 블록과 가용 블록을 구분하기 위한 자료 구조가 필요하다. 이를 가용 리스트라고 한다. 대부분의 할당기는 이 정보를 블록 내에 저장한다.

그 중에서도 간단한 구현인 묵시적 가용 리스트는 메모리 블록을 데이터, 패딩에 덧붙여 1워드 길이의 헤더를 포함한다. 헤더는 블록의 크기(헤더와 패딩을 포함한 전체 블록)와 가용 여부에 대한 정보 등을 담게된다.

헤더의 한 가지 간단한 예로 위와 같은 구조를 생각할 수 있다. 32비트 모드를 가정할 때 블록의 크기는 최대 1워드이다. 그러나 정렬 제한사항을 고려하면 할당기는 블록의 크기를 8의 배수로 유지[^3]하므로 블록 크기(2진법)의 하위 3비트는 항상 0이다. 그러므로 하위 3비트는 다른 정보를 위해 사용한다. 이 예시에서는 하위 1비트에 할당/가용 여부를 표시하는 비트로 사용하였다.

[^3]: 데이터를 보관하는 payload의 시작 주소는 8의 배수여야 한다. 헤더의 크기가 4바이트임을 감안하면, 헤더를 포함한 블록의 시작주소(=이전 블록의 끝 주소)는 8n-4여야 한다. 따라서 할당기는 블록의 크기가 8의 배수가 되도록 패딩한다.

가용 리스트도 이름처럼 추상적 자료형인 리스트*의 일종이다. *묵시적 가용 리스트는 리스트를 구현하는데 있어 배열이나 연결리스트와 다르게 블록 자신의 크기와 가용 부를 표시함으로써 다음 가용 블록의 위치를 묵시적으로 알린다.

최소 블록 크기는 시스템의 정렬 요구사항과 할당기의 블록 포맷 선택에 의존한다. 예시: 정렬 요구사항을 더블 워드(8바이트), 블록 포맷을 묵시적 가용 리스트라고 하면 최소 블록 크기는 데이터 4바이트, 헤더 1바이트, 패딩 3바이트로 8바이트가 된다.

9-9-7. 할당한 블록의 배치

할당기가 요청받은 블록을 저장하기 위해 가용 블록을 검색하는 방법을 배치 정책이라고 한다.

• First Fit: 가용 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택
  • 장점: 큰 가용 블록을 뒷쪽에 두는 경향이 있어 자연스레 작은 가용 블록을 선택할 가능성이 높아진다. (이용도)
  • 단점: 작은 가용 블록이 앞쪽에 있으므로 검색 횟수가 늘어난다. (처리량)
• Next Fit: 리스트의 처음이 아닌 이전 검색 종료 지점에서 검색을 시작
  • 장점: 이전 검색 지점 이후에서 조건에 맞는 블록을 선택할 가능성이 높아 First Fit에 비해 빠르다. (처리량)
  • 단점: 메모리 이용도가 First Fit보다 낮아질 수 있다. (이용도)
• Best Fit: 모든 가용 블록을 검색해 크기가 맞는 가장 작은 가용 블록을 선택
  • 장점: 메모리 이용도가 좋다. (이용도)
  • 단점: 묵시적 가용 리스트에서는 힙의 모든 블록(가용/할당 블록 모두)을 검색해야 한다. (처리량)

아래에서는 할당 블록까지 검색하지 않을 수 있도록 단순화한 best-fit 정책인 다단 가용 리스트 조직 segregated free list organizations에 대해서 설명한다.

9-9-8. 가용 블록의 분할

할당기가 블록을 배치할 가용 블록을 찾은 후에는 가용 블록의 어느 정도를 할당할 것인지 결정해야 한다.

1. 충분히 작은(good fit) 가용 블록을 선택한 경우 가용 블록 전체를 사용할 수 있다. 내부 단편화가 생기지만 수용할 수 있다.
2. 크기가 큰 경우(fit is not good) 가용 블록을 나누어 할당한다. 전체를 할당하는 경우 내부 단편화가 생긴다.

   9-9-9. 추가적인 힙 메모리 획득하기

   배치할 블록을 찾을 수 없다면, 우선 인접한 가용블록들을 합쳐서(연결) 더 큰 가용 블록들을 만들어 본다. 이미 모두 연결돼있거나 충분히 큰 블록이 만들어지지 않으면 sork함수를 호출해서 추가적인 힙 메모리를 요청한다.

   9-9-10. 가용 블록 연결하기

   블록을 반환했을 때, 인접한 가용 블록이 있다면 하나의 연결된 가용블록으로 볼 수 있다. 하지만 실제로는 가용블록이 나누어져 있어 배치에 실패하는 경우가 생길 수 있고 이를 가성 단편화(false fragmetation)라고 한다.

가성 단편화를 극복하기 위해 할당기는 가용블록들을 합칠 수 있다(연결 coalescing).

• 즉시 연결 블록이 반환될 때마다 인접 가용 블록들을 연결
• 지연 연결 반환 후 적절한 때에 가용 블록들을 연결 예시: 할당 요청이 실패하는 경우 모든 가용블록들을 검색하여 연결

즉시 연결은 간단하며 상수 시간($O(N)$)에 수행할 수 있는 장점이 있지만 할당-반환을 반복하는 프로그램에서는 연결과 분할을 반복하는 등 일부 요청 패턴에서 쓰래싱이 발생할 수 있다. 빠른 할당기들은 지연 연결을 주로 사용하지만 아래에서는 설명을 위해 즉시 연결을 가정한다.

9-9-11. 경계 태그로 연결하기

반환하는 블록(현재 블록)의 다음 블록이 가용 블록인지 확인하려면 헤더에서 블록 크기만큼 이동하면 된다. 하지만 이전 블록이 가용 블록인지 확인하기 위해서는 헤더만 있는 묵시적 가용 리스트라면 처음부터 블록들을 검색해보는 방법밖에 없다.[^4] 이를 위해 경계 태그라는 기법이 등장하였다. 경계 태그는 헤더와 동일한 내용을 블록 끝에 풋터로 추가하는 것으로, 블록 앞 1워드만을 읽어 이전 블록이 가용 블록인지 확인할 수 있다. 다만 각 블록마다 헤더와 풋터를 유지해야 하므로 메모리 오버헤드가 심해진다. 풋터는 이전 블록이 가용 블록일 경우 크기를 알려주는 목적으로 사용되므로, 이전 블록이 가용 블록인지 여부를 헤더에 저장하고, 가용 블록이 아닌 경우(할당 블록인 경우)에는 풋터를 사용하지 않는 방식으로 최적화할 수 있다.

[^4]: 이전으로 워드 크기씩 헤더를 찾아가는 방법을 떠올릴 수 있지만, 헤더를 통해 블록 크기만큼 이동하는 컨텍스트가 없다면 헤더를 찾더라도 헤더인지 데이터인지를 판단할 수 없다.

9-9-12. 종합 설계: 간단한 할당기의 구현

9-9-13. 명시적 가용 리스트

지금까지 묵시적 가용 리스트를 통해 할당기의 개념을 소개하였다. 그러나 묵시적 가용 리스트는 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에[^5] 범용 할당기에 적합하지 않다. 보통 명시적 자료구조로 가용 리스트를 만드는 것이 좋은 방법이다.

가용 블록은 프로그램에서 사용하지 않기 때문에 가용 블록의 리스트를 구현하기 위해 가용 블록 내의 공간을 사용할 수 있다. 그림은 명시적 가용 리스트의 간단한 예시로, 가용 블록 안에 이전/다음 가용 블록의 주소를 저장해 이중 연결 리스트로 구성했다. 명시적 가용 리스트를 사용하면

• 장점: first fit 할당 시간을 전체 힙 블록 수에 비례했던 것에서 가용 블록의 수에 비례하는 것[^6]으로 줄일 수 있다.
• 단점: 최소 블록 크기가 커지므로 내부 단편화 가능성이 높아진다. 가용 블록들이 포인터, 헤더, 풋터를 저장할 수 있을만큼 커져야 하므로 그 보다 작은 공간은 패딩에 포함시키기 때문이다.

다만 first fit 배치 정책을 사용할 때의 반환 시간과 이용도는 블록 정렬 정책에 의해 달라진다.

1. 후입선출로 정렬하기 이중 리스트를 스택처럼 후입선출 식으로 유지한다. 즉, 새롭게 반환되는 블록을 리스트의 시작 부분에 삽입한다. first fit 배치 정책을 같이 사용하면, 최근에 반환된 블록 순으로 검색하게 된다. 반환이 상수 시간에 수행되며 [[#9-9-10. 가용 블록 연결하기|연결]]도 상수 시간에 수행할 수 있다.
2. 주소 순으로 정렬하기 이중 리스트를 가장 가까운 가용 블록의 주소를 가리키도록 구성한다. 반환을 위해서는 반환 위치를 우선 탐색해야 하므로 반환시간이 가용 블록에 비례한다. 대신 first fit 배치 정책에서 후입선출로 정렬한 경우보다 더 좋은 메모리 이용도를 가진다.[^7]

[^5]: 가용 블록의 수를 N, 할당 블록의 수를 M이라고 한다면 묵시적 가용 리스트의 블록 할당 시간은 $O(N+M)$이다. [^6]: $O(N)$ [^7]: [[#9-9-7. 할당한 블록의 배치]]에서 알 수 있듯 first fit의 장점은 뒷 부분에 크기가 큰 가용 블록이 배치된다는 점에서 발생한다. 후입 선출로 정렬하였을 때에는 크기와 관계 없이 반환된 순으로 정렬되므로 이런 장점이 사라진다.

9-9-14. 분리 가용 리스트

앞서 알아본 모든 가용 블록들을 하나의 연결 리스트로 사용하는 방법을 단일 연결 가용 블록 리스트라고 한다. 이는 할당 시간이 비례[^6]하므로 할당 시간을 줄이기 위해 *분리 저장장치 segregated storage를 사용하는 경우가 많다. 분리 저장장치 방식은 가용 리스트를 비슷한 크기(크기 클래스*size class) 별로 여러 개로 나누어 사용한다. 크기 클래스를 나누는 방식 예시로는 2의 제곱 단위로 나누는 방법 $$ {1},;{2},;{3-4},;{5-8},;...;,;{1025-2048},;{2049-4096},;{4097-∞}$$또는 더 세분하여 크기가 작은 블록들은 각자의 크기 클래스에, 큰 블록들은 2의 제곱으로 나누는 방법$${1},;{2},;{3},;...;,,;{1023},;{1024},;{1025-2048},;{2049-4096},;{4097-∞}$$등이 있다. 각 크기 클래스마다 크기 순으로 정렬된 가용 리스트를 가지게 된다.

9-9-14-1. 간단한 분리 저장장치

분리 저장장치의 예시로 간단한 분리 저장장치를 들 수 있다. 각 크기 클래스의 가용 블록 크기는 모두 클래스의 최대 크기이다. 예를 들어 2의 제곱으로 클래스를 구분하면 가용 블록은 1, 2, 4, 8, 16...의 크기만을 갖는다.

• 할당: 적절한 가용 리스트를 찾아 블록을 분할하지 않고 전체를 할당한다. 리스트가 비어있으면 (다음 크기를 검색하는 것이 아니라)힙 공간을 추가로 요구해 해당 클래스 만큼의 블록으로 분할해 리스트를 채워넣는다.
• 반환: 해당 크기 가용 리스트의 맨 앞에 채워넣는다.
• 장점
  • 할당과 반환이 상수시간에 이루어진다.
  • 리스트 마다 블록들의 사이즈가 같아 분할/연결이 필요 없기 때문에 오버헤드가 거의 없다.
  • 메모리 블록이 동일한 크기로 나눠져 있으므로 블록의 주소만 알면 크기를 알 수 있다.
  • 연결이 없으므로 헤더, 풋터가 필요하지 않다.
  • 할당과 반환이 모두 리스트의 헤드에만 삽입하므로 이중 연결 리스트가 필요 없다.
  • 블록 내에 필요한 정보는 후임자를 가리키는 포인터 뿐이므로 최소 블록 크기가 1워드이다.
• 단점
  • 블록을 분할하지 않으므로 내부 단편화에 취약하다.
  • 극단적인 외부 단편화가 발생할 가능성이 있다.[^8]

[^8]: 할당과 반환을 반복하는 프로그램이 요청하는 블록의 크기를 점점 키워가는 경우, 작은 크기 클래스의 블록들은 가용상태로 남아있으나 연결되지 않으므로 사용할 수 없다. 즉, 외부 단편화가 유발된다.

9-9-14-2. 분리 맞춤 Segregated Fits

분리 맞춤은 리스트들이 다양한 크기의 블록을 가질 수 있다. 분리 맞춤 방식의 분리 저장장치는 묵시적 가용 리스트에도 적용될 수 있다. 다음은 분리 맞춤의 간단한 예시이다.

• 할당: 크기에 맞는 가용 리스트를 first-fit 방식으로 검색한다. 찾을 수 없으면 다음 크기의 가용 리스트를 검색한다. 블록을 찾으면 블록을 분할하고 나머지를 크기에 맞는 가용 리스트에 넣는다. 적절한 크기의 가용 블록이 없으면 추가 힙 공간을 요청한다.
• 반환: 블록을 연결하고 연결된 블록을 해당 크기의 가용 리스트에 넣는다.
• 장점
  • 힙의 특정 부분(해당 크기 클래스)만 검색하므로 검색 시간이 줄어든다. (처리량)
  • 분리 가용 리스트에서 first-fit 검색 방식은 best-fit 검색 방식과 유사하므로 이용도가 개선된다. (이용도)

9-9-14-3. 버디 시스템

버디 시스템은 크기 클래스가 2의 제곱인 경우에 사용할 수 있는 분리 맞춤(segregated fits) 방식이다. $$ {1},;{2},;{4},;{8},;...;,;{2048},;{4096},;...$$

• 할당: 해당 크기 클래스의 리스트에서 가용 블록을 찾아 할당한다. 만약 비어있다면 더 큰 클래스에서 찾아 해당 크기가 될 때까지 이분할한다. 분할할 때마다 나머지 절반(버디 buddy)을 해당 가용 리스트에 넣는다. 최초의 블록의 크기는 힙 공간 전체일 것이다.
• 반환: 할당과 반대로, 반환할 블록과 버디들을 할당된 버디를 만날 때까지 연결한다. 버디는 현재 블록의 크기만큼을 주소에 더해 찾을 수 있다.
• 장점
  • 빠른 검색과 연결 블록의 주소와 크기를 알면 버디의 주소를 계산하기 쉽기 때문이다.(주소+크기 = 버디의 주소)
• 단점
  • 블록 크기가 2의 제곱으로 고정되어 있으므로 내부 단편화에 취약하다. 그러므로 어떤 프로그램의 블록 크기가 2의 제곱으로 고정되어 있을 때 사용하면 효과를 얻을 수 있다.

    11. 네트워크 프로그래밍

    11-1. 클라이언트-서버 프로그래밍 모델

    모든 네트워크 응용 프로그램은 클라이언트-서버 모델에 기초한다. 이 모델에서 응용(Application)은 한 개의 서버 프로세스와 여러 개의 클라이언트 프로세스로 구성된다.[^11-1] 클라이언트-서버 모델에서 근본적인 작업은 트랜잭션 transaction이다. 트랜잭션은 클라이언트-서버 간 요청을 주고 받거나 작업을 처리하는 것으로 네 단계로 구성된다:

1. 클라이언트가 서비스를 요구하기 위해, 요청 request을 서버에 보낸다.
2. 서버는 요청을 받아 해석하고, 서버의 자원(resource)을 조작한다.
3. 서버는 응답 response을 클라이언트로 보내고 다음 요청을 기다린다.
4. 클라이언트는 응답을 받아 처리한다.

클라이언트-서버 모델 구분 이점

[^11-1]: 클라이언트-서버 모델에서의 클라이언트와 서버는 프로세스이다. 머신, 호스트가 아니므로 하나의 호스트 내에 클라이언트 프로세스와 서버 프로세스를 모두 갖는 것이 가능하다.

11-2. 네트워크

네트워크란 여러 컴퓨터들을 그물망처럼 연결한 통신 형태를 뜻한다. 많은 서비스들이 네트워크를 이용하여 제공되고 있다.

11-2-1. 네트워크 계층

네트워크는 각기 다른 위계 Hierarchy를 갖는 계층구조 시스템으로 이해할 수 있다. 계층으로 나누어 설명하는 이유는:

• 모듈화: 각 계층이 독립적으로 역할만 수행하게 한다. 유지보수와 확장이 쉬워진다.
• 호환성: 다양한 기술을 사용하는 기기들 간 통신을 가능하게 한다. 각 계층에서 표준 인터페이스를 제공한다.

OSI 모델은 이론적인 목적으로 ISO에서 제안한 반면, TCP/IP 모델은 ARPANET(인터넷의 전신)과 함께 발전한 실용적인 모델이다.

서로 다른 기술을 사용하는 네트워크와 통신하기 위해서, 각 계층에서는 데이터에 하위 계층에서 요구되는 형식으로 헤더를 추가하여 패킷으로 변환한다. 그림을 예시로 들면 TCP/IP 4계층에서 전송 계층은 응용 계층에서 받은 데이터가 텍스트이든 이미지이든 헤더를 붙여 변환한다. 인터넷 계층에서도 마찬가지로 전송 계층에서 TCP/UDP 어떤 프로토콜을 사용하든 헤더를 붙여 전송 가능한 데이터그램으로 만든다. 네트워크 엑세스 계층에서도 헤더를 붙여 프레임으로 만들고 비트로 변환하여 전송된다. 이런 변환 방식을 반복하면 최종적으로는 통일된 형식의 비트(데이터의 가장 미시적 단위)로 변환할 수 있으며 이런 상위 계층의 데이터를 감싸는 변환 방식을 캡슐화 encapsulation라고 한다. 캡슐화를 사용하면 각 계층에서 어떤 프로토콜을 사용하든 동일한 형식으로 전송할 수 있으며 인터넷 통신 방식의 핵심이다. 요약하자면, 계층화가 필요한 주된 이유는 계층 내 서로 호환되지 않는 기술을 하위 계층의 동일한 기술로 변환할 수 있도록 만들기 위해서이다.

OSI 7계층:

1. 물리 계층 (Physical Layer, L1): 비트를 전기 신호, 빛, 또는 무선 신호로 바꿔 물리적 매체를 통해 전달
2. 데이터 링크 계층 (Data Link Layer, L2): 프레임을 사용해 물리 계층에서 안전한 전송(오류 검사 등)을 도움, MAC 주소를 통해 데이터 전송 경로를 관리
3. 네트워크 계층 (Network Layer, L3): 패킷을 생성하고 IP 주소를 기반으로 네트워크 간의 경로를 결정
4. 전송 계층 (Transport Layer, L4): 세그먼트(TCP/UDP)를 사용해 연결을 설정
5. 세션 계층 (Session Layer, L5): 세션을 설정하고 관리하며, 데이터 교환의 시작과 종료를 제어
6. 표현 계층 (Presentation Layer, L6): 데이터 형식과 인코딩을 처리하며, 암호화, 압축 등을 통해 데이터 표현을 통일
7. 응용 계층 (Application Layer, L7): 사용자가 직접 접하는 응용 프로그램과 네트워크 간의 인터페이스를 제공, 다양한 네트워크 서비스를 지원

   11-2-2. 일반 개념으로서 인터넷

   일반적인 개념으로서의 인터넷 internet을 우리가 실제로 사용하고 있는 Internet, global IP Internet의 맥락(컨텍스트)에서 저수준 계층부터 설명한다. 인터넷은 (로컬)네트워크들 간의 연결을 구현한 것이다.

앞으로 사용하는 용어 중 개념을 가리키는 일반적인 용어(LAN, 네트워크 세그먼트, 인터넷 주소, 전송 프로토콜 등)와 개념을 구현한 기술을 가리키는 용어(주로 TCP/IP 컨텍스트에서. 이더넷/802.11, 이더넷 세그먼트, IP 주소, TCP/UDP 등)를 구분해야 한다.

11-2-2-1. 이더넷

가장 작은 단위의 네트워크는 LAN Local Area Network이며 사무실 내의 내부망을 떠올릴 수 있다. 이더넷 Ethernet은 이런 LAN을 구현한 기술로 1970년대 이래 진화를 거쳐 속도와 안정성이 높아졌다.

11-2-2-1-1. 이더넷 세그먼트(L1)

이더넷 세그먼트(이더넷 기술 외의 일반적인 표현은 네트워크 세그먼트)는 호스트와 허브로 구성된다.[^11-2]

• 호스트: 네트워크에 연결된 컴퓨터나 기타 장치
• 허브: 물리포트로 들어온 데이터를 다른 물리포트로 복사하는 장치. 물리 계층(L1)에서 동작한다. 허브에 연결된 모든 호스트가 동일한 신호를 공유하게 된다. 따라서 허브에 연결되어 있는 호스트들은 하나의 세그먼트 안에 있게 된다. 호스트는 프레임(물리 계층에서의 데이터 단위)이라고 부르는 비트들을 다른 호스트로 보낼 수 있다. 같은 신호를 공유하는 호스트들이 선택적으로(특정 호스트를 지정해서) 통신하기 위해서 각 호스트마다 주소를 사용하며 이를 MAC 주소라고 한다. 각 이더넷 어댑터(호스트가 이더넷으로 전송하기 위해 사용하는)는 고유한 주소인 MAC 주소를 가진다. 프레임은 프레임의 발송지 MAC 주소와 목적지 MAC 주소, 프레임의 길이를 보낼 데이터 앞에 헤더로 추가하여 발송한다. 세그먼트 내의 모든 호스트가 프레임을 수신[^11-7]하지만 프레임 헤더의 목적지 주소와 일치하는 목적지 호스트만이 읽어들인다.

허브는 모든 신호를 모든 포트로 복사하기 때문에 호스트들이 동시에 발송을 시도하는 경우 충돌이 발생한다. 이를 이더넷 세그먼트 내의 호스트들이 하나의 *충돌 도메인 Collision domain*에 있다고 한다.

[^11-2]: 허브를 이용하지 않고 단일 호스트로만 세그먼트를 구성할 수도 있다. [^11-7]: 의도한 것이 아니라 자연스럽게 모든 호스트가 프레임을 수신하도록 하게 된다. 호스트들은 같은 통신 기술을 공유하고 신호(이더넷 같은 유선 통신에서는 전기신호)를 주고 받을 수 있는 상황에 놓여지기 때문이다. 후술할 인터넷 프로토콜이 필요한 이유, 브로드캐스트 도메인이 각 네트워크 세그먼트로 한정되는 이유로 연결되는 중요한 아이디어이다.

11-2-2-1-2. 브릿지로 연결된 이더넷 세그먼트(L2)

브릿지를 사용하여 충돌 도메인을 분리하고 둘 이상의 이더넷 세그먼트를 연결할 수 있다. 이를 브릿지형 이더넷 세그먼트 Bridged Ethernet Segments*이라고 한다.

• 브릿지: 이더넷 세그먼트를 연결하는 장치. 허브와 달리 브릿지는 프레임을 수신하면 목적지 MAC 주소를 확인하고 해당 주소가 위치한 세그먼트로만 복사(포워딩 forwarding 또는 스위칭 switching)하여 충돌을 방지한다. 헤더를 읽어들이므로 데이터 링크 계층(L2)에서 동작한다. 브릿지는 프레임 헤더의 발신자 MAC 주소를 확인해 장치들의 물리포트 위치를 학습하여 프레임을 포워딩한다. 학습되지 않은 MAC 주소를 도착지로 하는 프레임은 모든 포트로 보내게 된다.

스위치[^11-3] 역시 헤더를 조회해 브릿지처럼 이더넷 세그먼트를 연결하며 충돌 도메인을 분리한다. 그러나 브릿지는 소프트웨어를 기반으로 CPU와 소프트웨어가 MAC 주소 테이블을 관리하고 프레임 포워딩하는 반면, 스위치는 전용으로 설계된 ASIC와 TCAM을 이용하여 하드웨어적으로 처리한다. 따라서 브릿지에 비해 처리 속도가 매우 빠르므로 대규모 네트워크 환경에 유리하며 포트 수도 보통 수십개이다.

[^11-3]: 스위치는 프레임을 받고 적절한 경로를 결정해 발송(포워딩)해주는 네트워킹 장비를 말한다. 하지만 일반적으로 '스위치'라고만 하면 L2에서 작동하는 스위치를 의미하며, 다른 계층에서 작동하는 스위치는 L3 스위치, L4 스위치 등으로 구분해 부른다. 허브는 항상 모든 포트로 발송하므로 스위치가 아니다.

11-2-2-2. IP(L3)

internet은 둘 이상의 network(예를 들어 이더넷)들을 연결한 것(inter-network)이다. 주로 라우터[^11-4]를 이용해 네트워크들을 연결하게 된다. 즉, 라우터는 네트워크(또는 브로드캐스트 도메인[^11-5])을 구분한다. 하나의 라우터로 연결된 네트워크들을 가장 작은 internet이라고 생각할 수 있다.

• 라우터: 다른 네트워크 간 데이터를 전달하는 컴퓨터. 최종 목적지 호스트가 아닌 프레임 어느 네트워크로 보낼 지만을 결정하므로 네트워크 계층(L3)에서 동작한다.

[^11-4]: 라우터는 일반 컴퓨터로도 구성할 수 있으나 주로 라우터 전용으로 나온 컴퓨터 단말을 사용한다. [^11-5]: 브로드캐스트란 목적지 호스트를 정하지 않고 네트워크의 모든 호스트에 발송하는 것을 말한다. 라우터는 브로드캐스트를 수신해도 다른 물리포트로 포워드하지 않으므로 각 물리포트들은 다른 브로드캐스트 도메인에 있게 된다. 브로드캐스트는 한 번의 신호 발송으로 네트워크 내의 모든 호스트들에 전달하는 것이므로 라우터가 복사하여 전달할 필요도 없으며 해서도 안 된다.

MAC 주소를 이용한 통신은 같은 기술을 사용하는 호스트 간에 사용했다. 되짚어 보자면, 이더넷이나 와이파이와 같이 서로 같은 방식의 물리 신호를 주고받을 수 있는 상황에서 호스트를 선택적으로 통신하기 위해서 MAC 주소를 사용했다. 다르게 말하면 MAC 주소로는 다른 종류의 네트워크와 통신할 수 없다. LAN 내부에서 통신했던 것과 달리 LAN들은 서로 호환되지 않는 기술들을 사용할 수 있다. 따라서 다른 네트워크로는 직접 통신이 불가능할 수 있다. 예를 들어 이더넷은 유선 통신으로 구현된 LAN이지만 *WLAN은 무선통신으로 구현되었으므로 이더넷에서 WLAN으로는 직접 통신할 수 없다. 이렇게 비호환 네트워크일 수 있는 다른 LAN과 통신하기 위해서는 새로운 규약(인터넷 프로토콜)이 필요하다. 인터넷 프로토콜은 호스트들과 라우터들이 데이터를 전송하는 방법을 규정한 것이며 우리가 사용하는 인터넷(*Global IP Internet)은 IP Internet Protocol를 사용한다.

IP를 포함한 인터넷 프로토콜은 아래 두 가지 기본 기능을 가지고 있다.

1. 명명법 Naming scheme 호스트의 주소로 사용할 통일된 형식을 정의한다. 각 호스트는 internet 주소를 한 개 이상 가지고 있다. IP에서는 IP 주소와 포트를 사용한다. [[#11-3-1. IP 주소|IP주소에 대한 자세한 설명]]은 뒤에서 하기로 하고 일단은 IP에서 사용하는 주소라고만 하겠다.
2. 전달기법 Delivery mechanism 서로 다른 길이와 인코딩 방식의 데이터를 통일된 방식으로 묶기 위해서, 데이터 비트를 패킷(IP에서는 데이터그램으로도 부름)이라는 단위로 묶는 방법을 정의한다. 패킷은 패킷 크기, 소스 호스트 주소(IP 주소), 목적지 호스트 주소(IP 주소)를 포함하는 헤더를 데이터 앞에 붙여 구성한다. ![[Pasted image 20240817213654.png]] (IP에서 데이터그램의 예) IP를 통해 통신하는 모든 호스트들은 고유한 IP주소를 가지고 있다. 네트워크가 하나의 외부 IP를 공유하는 경우에는 네트워크 내 호스트들은 고유한 내부 IP를 가지고 있다.

네트워크 간 IP로 통신하는 방식: 다른 네트워크의 호스트와 데이터를 주고 받을 때엔 MAC 주소 대신 규약으로 정해진 주소(명명법, IP 주소)가 포함된 헤더를 데이터 앞에 추가하게 된다. 이를 데이터그램/패킷이라고 한다. 이 패킷을 네트워크 내에서 주고 받을 때에는, 하위 계층의 헤더(MAC 주소)가 추가로 붙게 되므로 실제 1계층에서 주고 받게 되는 데이터는 (프레임 헤더)+(패킷 헤더)+(패킷 데이터) 의 형태가 된다.

1. 호스트는 다른 네트워크로 데이터를 보내기 위해 목적지 IP주소를 기록한 패킷 헤더를 데이터에 추가하고, 라우터의 MAC 주소를 기록한 프레임 헤더를 더해 발송한다.
2. 라우터는 미리 다른 라우터들과 교신을 통해서 주변 네트워크들의 정보를 기록해둔 라우팅 테이블을 만들어 놓는다. 프레임을 수신하면 프레임 내 데이터그램 헤더에서 읽은 도착지 IP 주소를 라우터 테이블과 비교해 적절한 다음 경로의 MAC 주소로 발송한다(라우팅).
3. 이런 과정을 반복해 도착지 네트워크로 진입하게 되면, 라우터는 포트 번호[^11-8] 별로 할당된 내부 IP 테이블을 사용해 도착지 주소를 내부 IP로 변경한다(NAT[^11-6]).
4. 라우터가 내부 IP에 해당하는 MAC 주소로 프레임을 생성하고 적절한 물리포트를 결정하여 발송하면 네트워크 세그먼트로의 전달이 완료되고 이후에는 하위 계층(L2, L1)의 통신방식을 통해 호스트로 전달된다.

[^11-6]: 내부 네트워크의 호스트들은 사설(내부) IP 주소를 사용한다. 인터넷에 접속하기 위해서는 공인(외부) IP 주소가 필요하며, 하나의 공인 IP 주소를 사용하여 모든 내부 호스트가 외부 인터넷과 통신한다. NAT는 같은 공인 IP를 사용하더라도 포트 번호를 사용하여 내부 호스트들을 구분할 수 있게 하는 기술이다. 내부 호스트가 외부 인터넷에 패킷을 보내면, 라우터는 패킷의 출발지(내부 호스트) IP 주소를 공인 IP 주소로 변환한다. 이와 함께, 포트 번호도 변환하여 NAT 테이블에 기록한다(NAT 테이블). 라우터는 외부에서 오는 (공인 IP와 포트번호를 가진) 응답 패킷을, NAT 테이블을 참조하여 원래의 내부 IP 주소와 포트 번호로 변환하여 내부 호스트에 전달한다. 이 때 특정 포트 번호로 오는 패킷을 특정 내부 IP로 변환하여 보내도록(포워딩하도록) 변환하는 작업을 포트포워딩이라고 한다. 사용 중이거나 포트포워딩한 포트가 아닌 나머지 포트로 온 패킷을 모두 특정 내부 IP로 변환하여 보내도록 하는 것은 DMZ라고 한다. [^11-8]: 포트 번호는 전송 계층(L4)에서 내부 호스트에 있는 애플리케이션이나 서비스를 식별하는 데 사용된다. 포트포워딩은 이런 전송 계층의 헤더를 조회하고 수정하여

네트워크 내에서 IP로 통신하는 방식 같은 기술을 사용하는 네트워크 안에서는 IP를 사용하지 않고도 통신할 수 있지만, 외부 네트워크와 같은 프로토콜로 통신하여야 하는 경우가 있을 수 있다.

1. IP를 가진 호스트의 MAC 주소를 알아야하며, 이를 위해서 ARP 프로토콜을 사용한다. 발송하려는 호스트는 ARP 패킷으로 브로드캐스트[^11-5]로 IP주소를 가진 호스트의 MAC 주소를 요구한다. 해당 IP의 호스트가 패킷을 수신하면 자신의 MAC 주소를 회신한다. 이 정보는 ARP 테이블(캐시)에 저장되어 일정 시간동안은 ARP 요청을 다시 하지 않는다.
2. 하위 계층(L2, L1)의 통신방식과 같다. MAC 주소를 포함한 프레임 헤더를 붙여 물리 신호를 발송한다.

라우터 요약: 라우터는 IP 주소를 기반으로 패킷을 라우팅 테이블에 따라 최적의 경로로 전달한다. 즉, 네트워크 간의 경로를 결정(라우팅)한다. 브로드캐스트 도메인을 분리하고 각 브로드캐스트 도메인을 독립적으로 관리한다.

알아두기(게이트웨이) 게이트웨이는 일반적으로 다른 프로토콜의 두 네트워크 간에 프로토콜의 변환 기능을 수행하는 장치 즉, 이질적인 망을 연결시키는 개체(Entity)를 가리키는 일반적인 용어 TCP/IP에서 볼 때는 망간의 연결을 담당하는 '라우터'를 의미하기도 하나, 주로, 상위계층(L4-L7)에서 상이한 프로토콜들 간의 특수한 변환을 담당하는 서버를 의미함

11-2-2-3. UDP/TCP(L4)

UDP와 TCP는 모두 전송 계층에서의 프로토콜로, 전송 계층부터는 각 프로세스가 직접 통신할 수 있다. 하위 계층을 거쳐 호스트까지 도착한 데이터가 어떤 프로세스로 찾아가야 하는지 구분하기 위해서 포트 번호를 사용한다. 포트 번호는 16비트 길이의 부호 없는 정수이다. 예를 들어 웹서버가 80포트 번호를 할당했다고 할 때, 해당 호스트로 데이터를 보내면서 포트번호로 80을 입력하면 호스트까지 IP를 이용해 전송된 뒤, 웹서버가 있는 호스트는 포트번호를 확인해 웹서버 프로세스로 전달한다.

11-2-2-3-1. UDP

UDP User Datagram Protocol는 1980년에 정의된 전송 계층(L4)에서 동작하는 프로토콜이다.

IP는 호스트에서 호스트로 전송할 수 있었으므로 네트워크(L3) 계층에서 동작한다. UDP는 프로세스에서 프로세스로 전달할 수 있으므로 전송 계층(L4)에서 동작한다.

UDP는 IP 데이터그램을 프로세스에서 프로세스로 전송하기 위해 IP 프로토콜에서 최소한의 기능만을 추가하였다. UDP헤더에는 소스 포트번호, 도착지 포트번호, 데이터그램[^11-9] 길이, 체크섬만 존재한다. IP에 호스트 자신의 주소를 목적지 IP를 사용하면, 도착지 포트번호를 가진 호스트 내의 다른 프로세스로 정보를 전송할 수도 있다. 상대편에서 메시지를 받을 준비가 되어있는지 확인하는 통신 과정을 정의하지 않았으므로 IP와 같이 단방향으로 정보를 전송한다. 전송 방식이 너무 단순해서 서비스의 신뢰성이 낮고, 데이터그램 도착 순서가 바뀌거나, 중복되거나, 심지어는 통보 없이 누락되기도 한다. 따라서 일반적으로 오류의 검사와 수정이 필요 없고 실시간성이 중요한 애플리케이션에서 사용한다.

[^11-9]: UDP도 단위로 데이터그램을 사용한다. IP 데이터그램과 구분이 필요한 경우에는 유저 데이터그램 user datagram이라고 표현한다.

11-2-2-3-2. TCP(L4)

TCP Transmission Control Protocol은 TCP/IP의 핵심 프로토콜 중 하나이다. TCP는 UDP의 단점을 보완해 신뢰성, 순서 보장, 양방향성을 갖도록 설계되었다.

1. 연결:

   • 데이터 전송 전에 송신자와 수신자 간에 연결을 설정(3-way handshake)하고, 통신이 종료될 때 연결을 해제한다. 이 때의 연결은 물리적 실체가 아니라 서로 응답이 가능한 상황인를 확인하고 연결된 프로세스 간에만 통신이 이루어지는 논리적 연결이다.
   • 3-way handshake: 연결 설정을 위해 세 단계의 과정을 거친다: SYN: 클라이언트가 서버에 연결을 요청 SYN-ACK: 서버가 클라이언트의 요청을 확인하고 응답 ACK: 클라이언트가 서버의 응답을 확인

2. 신뢰성: 데이터 전송 중 손실되거나 손상된 패킷은 재전송되며, 중복된 패킷은 제거되고, 수신된 데이터는 올바른 순서로 재조립된다. 데이터의 신뢰성을 보장하기 위해 응답 확인(Acknowledgment) 메커니즘과 타이머를 사용한다.

3. 흐름 제어 및 혼잡 제어: TCP는 송신자와 수신자의 데이터 처리 속도에 맞추어 데이터 전송 속도를 조절한다. 네트워크 혼잡을 방지하기 위해 혼잡 제어 메커니즘을 사용한다.

4. 헤더 구조:

   TCP 헤더는 최소 20바이트에서 최대 60바이트로, 다양한 제어 필드를 포함한다.

5. 사용 사례: 웹 브라우징(HTTP/HTTPS): 웹 페이지를 로드할 때, 데이터가 손실 없이 순서대로 도착해야 하므로 이메일 전송(SMTP): 이메일의 신뢰성 있는 전송을 보장하기 위해 파일 전송(FTP): 파일이 손상되지 않도록

   11-3. 글로벌 IP 인터넷

   글로벌 IP 인터넷 Global IP Internet은 internet의 가장 유명한 구현체이다. (이 절에서 인터넷은 글로벌 IP 인터넷을 가리킨다.) 각 인터넷 호스트는 *TCP/IP 프로토콜을 통해 통신한다. TCP/IP는 TCP와 IP라는 프로토콜을 중심으로 구성되는 여러 프로토콜의 집합(군, *suite)으로 속하는 프로토콜의 수가 100개가 넘는다. (TCP/IP 주요 프로토콜) TCP/IP는 또한 인터넷(Internet)에서 사용되는 기본 통신 프로토콜로 특정 운영체제에 국한되지 않는다.

   11-3-1. IP 주소

1038 감소하는 수

문제

각 자리수가 강한 단조 감소하는 수를 '감소하는 수'라고 할 때 N번 째로 작은 감소하는 수를 찾는 것이 문제이다.

예: 54321 - 감소하는 수 54421 - 감소하는 수 아님 12345 - 감소하는 수 아님 0 - 감소하는 수

풀이

숫자를 0에서 부터 순회하면서 각 수가 감소하는 수인지 판단하는 것이 가장 단순한 완전탐색이다. 감소하는 수인지 판단하는 함수에 백트래킹을 적용하면 약간 더 빨라질 것이다. 또 중간에 굳이 살펴보지 않아도 되는 수가 존재한다. 예를 들어 10까지 순회했다고 했을 때, 11부터 19까지는 굳이 살펴보지 않아도 된다. 바로 20으로 가면 된다.

class Number:
    def __init__(self):
        self.number = [0,0,0,0,0,0,0,0,0,0] # 각 자리수. 0인덱스가 가장 작은 자리수이다.

    def __str__(self):
        end = self.number.index(max(self.number))
        return ''.join(map(str, reversed(self.number[:end+1])))

    def increase(self):
        for i in range(10):
            if self.number[i] == 9:
                if i >= 9:
                    raise ValueError("감소하는 수 없음")
                self.number[:i+2] = list(range(i+2))
                break
            elif self.number[i+1] == 0 or self.number[i]+1 < self.number[i+1]:
                self.number[i] += 1
                self.number[:i] = list(range(i))
                break

N = int(input())
number = Number()

try:
    for _ in range(N):
        number.increase()
    print(number)
except ValueError:
    print(-1)

1. 개요

1.1. 배경

크래프톤 정글 입소 직후 시작된 3일 간의 미니 웹 프로젝트입니다. 동기들끼리 서로의 교육장 입실 여부와 공부 시간을 확인하며 공부 의지를 북돋우자는 취지로 만든 웹서비스입니다.

1.2. 작업 기간

2024. 7. 1.- 2024. 7. 3. 3인 팀 개발

         1.3. 사용한 기술

         Flask, Jinja2, Bulma

         2. 기능

• 출석을 체크하고 강의실 현황을 공유
• 매일 내 공부시간을 기록/확인
• 목표 공부시간 설정/오늘의 공부시간 추천
• 사용자가 주기적으로 강의실에 있음을 확인해야 공부 시간을 적립
• 즐겁게 이용할 수 있는 경쟁 요소: 실시간 강의실 현황, 주간 랭킹, 순위권 메달 누적 등

  3. 결과

  굳이 수고롭게 들어와 주기적으로 출석을 체크해야하는 유인이 가장 중요하다고 생각해, 기능을 추가했으나 그것만으로는 부족했습니다.

  4. 개발과정

  4.1. 공부시간 측정하기

  프로젝트 취지가 동기들이 어디있는지 확인하고 서로 공부 시간을 경쟁하는 것이므로 어떻게 해야 공부시간을 측정할 수 있을까 고민했습니다. 강의실에서 하는 공부의 형태가 정보검색, 교과서, 코딩, 동료학습 등 다양했으므로 간단히 공부하는 강의실에 있는 시간을 공부시간으로 했습니다. 출석/출근 기록처럼 강의실에 들어올 때 입실체크, 나갈 때 퇴실체크를 하도록 해 그 사이 시간을 기록합니다. 중간에 자리를 비우거나 퇴실체크를 하지 않는 경우를 위해 주기적으로 연장처리를 하여야 시간을 기록할 수 있도록 했습니다.

  4.2. 강의실에 있는지 감지하기

  이를 위해서는 사용자가 강의실에 있는지 알 수 있어야 했습니다. GPS를 사용하고자 했으나 실내에서 정확도가 떨어지고 HTTPS가 필요했습니다. 지식과 시간의 부족으로 HTTP를 사용했으므로, 대안으로 강의실 ap의 ip주소를 서버에 기록, 해당 ap로 접근했을 때에만 입실을 체크할 수 있도록 하였습니다.

4.3. 기타

SSR 코치님들의 프로젝트 요구사항은 ssr을 이용할 것이었습니다. 이 서비스의 메인 화면이 사용자 별 상태(입/퇴실 여부, 공부시간)를 보여주는 것이었으므로, 이부분을 서버에서 렌더링해 보내주었습니다.

주기 작업 장기간 부재시 퇴실처리, 일주일 종료 시 랭킹 집계 등 정해진 시간이 되면 수행해야하는 작업들의 처리 방법이었습니다. 웹서버 프로세스에서 db에도 접근하고 있었으므로, 멀티 스레드로 작업 처리 함수를 실행하는 방식으로 구현했습니다.

5. 아쉬운 점

사용을 유도하기 위해 노력했지만 불충분해 며칠이 지나자 동기들의 외면을 받고 말았습니다. 실제 훈련 출석부와 연계 및 웹 푸시 사용으로 좀 더 편하게 사용할 수 있도록 만들었으면 하는 아쉬움이 남습니다.

개요
이모티콘 추가를 자동화하고, 단축키와 최근 사용 목록 표시 등 다양한 편의 기능을 제공하여 직원들의 메신저 사용 경험을 향상시켰습니다.

• 기간: 2024년 12월 ~ 2024년 4월 (5개월)
• 역할: 단독 개발
• 기술 스택: Python (Selenium, Tkinter, PyInstaller, sqlite3, pywin32)

주요 기능

1. 이모티콘 자동 추가

2. 이모티콘 탭 관리

3. 단축키 기능

4. 최근 사용 이모티콘 표시

5. GUI 인터페이스

주요 기술적 도전과 해결

1. XML 파싱과 데이터 관리

   • 문제: 이모티콘 탭의 순서 변경 및 삭제 시 데이터를 일관되게 관리하는 데 어려움.
   • 해결: 리스트처럼 인덱싱 가능한 딕셔너리를 구현하여 데이터 접근 방식 통합.

2. WinAPI를 활용한 단축키 구현

   • 문제: 메신저에서 별도의 API 없이 커서 이동 없이 버튼 클릭을 구현해야 했음.
   • 해결: WinAPI 메시지 후커로 버튼 클릭 메시지(WM_LBUTTONDOWN)를 모방하여 입력 전달 성공.

3. 실시간 채팅 기록 분석

   • 문제: SQLite 데이터에서 사용자 ID가 해시 처리되어 직접 매칭이 어려움.
   • 해결: Base64 인코딩된 ID와 채팅 기록을 대조해 사용자의 발신 기록을 추적.

4. 멀티스레드 및 멀티프로세싱 활용

   • 문제: GUI 응답성과 백그라운드 작업(단축키, 채팅 분석)을 동시에 처리해야 함.
   • 해결: GUI는 독립 프로세스로, 나머지 작업은 스레드로 구현해 성능과 안정성 확보.

5. 사용자 중심 UI 설계

   • 문제: 초기 텍스트 기반 UI로 사용성이 낮아 개선 필요.
   • 해결: Tkinter로 GUI를 제작하고 메신저와 유사한 UI를 구현해 사용성을 대폭 향상.

회고

• 성과:

  • 메신저 기능을 단순화된 설치 및 사용으로 제공, 직원들 사이에서 널리 사용되는 프로그램으로 자리잡음.
  • 단축키, 최근 사용 목록 등 다양한 편의 기능으로 업무 효율성 향상.

• 아쉬운 점:

  • 버전 관리 도구(Git)의 부재로 테스트와 배포 과정이 복잡.
  • 최적화에 지나치게 집중하다가 비효율을 초래한 점 개선 필요.

링크: 내부망 프로젝트로 실사용 스크린샷과 실행 파일 공개는 불가.

1. 개요

사내 메신저에 이모티콘 관련 부가기능을 제공하는 파이썬 프로그램

1.1. 배경

사내 메신저에는 이모티콘의 수가 극히 적었습니다. 수동으로 추가할 수 있었으나 복잡하고, 상대방도 같은 방식으로 추가해야만 사용할 수 있었습니다. 모두가 쓸 수 있도록 쉽게 추가해주는 도구를 만들고 싶었습니다. 단순한 이모티콘 추가 매크로로 시작하여, 여러 편의 기능을 추가하였습니다.

1.2. 작업 기간

2022. 12.-2024. 4. 단독 개발

      1.3. 사용한 기술

      python, selenium, tkinter, pyinstaller, sqlite3, pywin32

      2. 기능

(사용 예시. 실제 배포된 버전에서는 더 많은 이모티콘과 미리보기가 표시됨.)

• 이모티콘 이미지 수집/메신저에 호환되도록 가공/xml 생성 자동화하여 결과물 배포
• 사용하는 이모티콘 종류 수정
• 프로필사진 가리기/엑셀 테마 추가
• 백그라운드 프로세스가 이모티콘 발신 기록을 확인하여 최근 사용한 순으로 표시
• 키보드를 이용하여 이모티콘을 보낼 수 있도록 winapi 메시지 생성

3. 진행 과정

3.1. 이모티콘 자동 추가

배경 이모티콘은 상대방도 추가해야 사용할 수 있음 쉽게 추가해주는 도구가 있어야겠다고 판단 탐색 메신저가 xml파일로 이모티콘 탭과 탭 소속 이미지들을 관리하고 있음을 확인 xml파일 예시:

<?xml version='1.0' encoding='utf-8'?>
<EmoticonList>
    <EmoticonTabitem TabControlNM="shakyanimals">
        <Tag>1</Tag>
        <TabName>바들바들 동물콘</TabName>
        <TabName_ENG>shaky-animals</TabName_ENG>
        <Img_Def>tab_shaky-animals_main.bmp</Img_Def>
        <Img_Down>tab_shaky-animals_select.bmp</Img_Down>
    </EmoticonTabitem>
    <EmoticonItem EmoticonType="sticker">
        <TabName>shakyanimals</TabName>
        <Name>shaky-animals (2).png</Name>
        <ListName>shaky-animals (2).png</ListName>
        <Kor>(바들바들 동물콘 2)</Kor>
        <Eng>(shaky-animals 2)</Eng>
        <Hint>정말고마워요</Hint>
    </EmoticonItem>
</EmoticonList>

구현 이미지들을 복사하고 xml파일을 수정하는 매크로를 만들어 배포함 파일들을 알맞은 위치로 이동시키는 배치파일을 압축파일에 포함시킴

3.2. 이모티콘 탭 변경

배경 시간이 지나 이모티콘이 점점 많아져 선택이 불편하다는 피드백 순서 변경, 탭 제거 기능이 필요해짐

탐색 xml파일 EmoticonTabitem 태그의 배치 순서와 이모티콘 선택창의 순서가 연동된다는 사실을 발견 xml파일을 사용자가 편하게 수정하는 기능을 만들자고 생각

구현 xml을 ElementTree를 이용해 딕셔너리로 파싱, 사용자의 입력을 받아 순서를 변경 후 다시 xml로 저장하여 순서 변경을 구현.

1. 이모티콘 A
2. 이모티콘 B
2. 이모티콘 C
4. 이모티콘 D
변경할 이모티콘과 순서를 입력하세요
>>> 4 1 # 4번 이모티콘을 첫 번째 순서로 변경

1. 이모티콘 D # 4번이었던 D가 첫 번째가 되었음
2. 이모티콘 A # 1번이었던 A,B,C는 순차적으로 2,3,4번으로 밀리게 됨
2. 이모티콘 B
4. 이모티콘 C

기술적 어려움 1 삭제를 위해서는 xml파일에서는 지워야 하나 다시 추가하기 위해서는 탭 정보를 별도로 저장하고 있어야 함. 추후 업데이트 시 정보가 덮어 씌워질 수 있으므로 삭제한 탭의 정보를 별도로 저장하기보다, 전체 탭 정보를 담은 레퍼런스 파일을 생성해, 레퍼런스에 없는 탭을 인식하는 방식으로 구현

기술적 어려움 2 xml을 파싱한 탭 데이터들에 접근할 때 탭 이름(딕셔너리처럼)으로 접근해야하는 경우와 정수 인덱스(리스트처럼)로 접근해야하는 두 가지 경우가 존재. 사용자가 직접 순서를 바꾸고 추가/삭제를 한 뒤 데이터를 저장해야 했으므로 두 가지 형태의 데이터를 모두 쓰는 것은 불가능.

리스트처럼 정수로 인덱싱 가능한 딕셔너리의 자식클래스를 만들어서 해결

class IndexableDict(dict):
    """Never use int as key"""
    def __getitem__(self, key):
        if isinstance(key, int):
            return list(self.values())[key]
        return super().__getitem__(key)
    # 기타메소드 생략

# 사용 예시
tabdata = IndexableDict({'tabname1': <TabData1>, 'tabname2': <TabData2>})
tabdata[1] # <TabData2>
tabdata['tabname1'] # <TabData1>

파이썬 2.7부터는 딕셔너리도 입력 순서를 보장하기 때문에 가능

3.3. GUI 구현

배경 처음에는 탭 변경 기능을 자주 사용하지 않을 것이라고 생각해서 텍스트 기반 ui로 구현 그러나 메신저와 크게 다른 ui 때문에 사용률이 몹시 저조

탐색 파이썬으로도 GUI를 구현하는 것이 가능하다는 것을 알게됨 PyQt가 더 기능이 다양했지만 메신저를 통한 파일 용량 제한이 있어, 용량을 줄이기 위해 표준 라이브러리였던 tkinter사용

구현

메신저의 UI와 유사하게 만들어 최대한 쉽게 사용할 수 있도록 구현 프로그램을 중복 실행하여 오작동하였다는 피드백이 있었으므로 중복 실행 시 기존의 윈도우를 맨 위로 올리고 중복프로세스를 종료하도록 함

사용자는 원하는 이모티콘을 선택해 버튼을 누르는 간단한 작업만으로 추가할 수 있게 됨. 별도의 프로그램이 아닌 메신저의 원래 있던 기능을 사용하는 것 같은 경험 제공.

기술적 어려움 멀티 스레딩/프로세싱 중 어느 것을 사용해야 하는 지 결정하기 어려웠다. 결론적으로 tkinter를 이용한 윈도우 ui만 멀티프로세싱을 사용하고 나머지는 멀티 스레드로 구현했다. 단축키 스레드, 최근사용탭 스레드는 사용자 설정이나 이벤트에 따라 껐다 켰다 해야하고 스레드 간 데이터를 주고받는 상황이 많았기 때문이다. 그러나 ui 프로세스는 사용자의 입력에 따라서만 실행/종료되고 프로세스에 오류가 발생해도 루트 프로세스에는 영향을 미치지 않는 것이 안전했기 때문에 분리했다.

3.4. 단축키 기능

배경 메신저가 단축키를 지원하지 않아 메시지 입력 중 이모티콘을 보내려면 반드시 마우스를 사용해야해 불편하다는 요청을 받아 키보드로만 이모티콘을 보내는 기능을 구현하려 함

탐색 메신저 등 프로그램이 winapi를 통해 입력 정보(메시지)를 받는다는 것을 알게됨 winapi는 c언어 기반이지만 파이썬에도 라이브러리가 있음을 확인

구현 사용자가 키보드 버튼을 입력했을 때 알맞는 winapi 메시지를 핸들로 전송하도록 하여 마우스를 옮기지 않으며 단축키를 구현.

기술적 어려움 1 메신저에 별도의 API가 존재하지 않아 처음엔 마우스 매크로로 구현하였음 하지만 테스트 사용해보니 입력이 제대로 되지 않는 경우가 많았으며 커서가 움직여 보기에도 별로이고 속도도 느렸음 커서 이동 등을 제거하고 메신저 프로그램으로 입력만 전달할 수 있다면 해결될 것이라고 생각하여 마우스 입력이 프로그램에 어떻게 전달되는가에 대해 공부하는 과정에서 winapi를 알게되었음

spy++(winapi메시지 후커)를 이용하여 마우스로 버튼을 클릭하면 해당 창의 핸들로 메시지(WM_LBUTTONDOWN)가 전송된다는 것을 알게되었고 이를 모방하면 커서를 움직이지 않고도 버튼을 누를 수 있을 것이라고 생각 적절한 핸들을 알아내고 메시지를 모방하는 클래스를 구현하여 사용함

class Messenger:
    DPOS = {7: (60, 60), 8: (170, 60), 9: (280, 60),
            4: (60, 160), 5: (170, 160), 6: (280, 160),
            1: (60, 260), 2: (170, 260), 3: (280, 260)}
    def __init__(self):
        self.hwnd_chatroom = None
        self.hwnd_emo = None
        self.hwnd_tabs = None
        self.hwnd_sheet = None
        self.hwnd_textbox = None
        self.pos = None
        self.hwnd_tabarrow_left = None
        self.hwnd_tabarrow_right = None
    def Click(self, hwnd, x=0, y=0, up=False):
        lParam = win32api.MAKELONG(x,y)
        win32api.SendMessage(hwnd, win32con.WM_LBUTTONDOWN, win32con.MK_LBUTTON, lParam)
        if up:
            win32api.SendMessage(hwnd, win32con.WM_LBUTTONUP, None, lParam)
    def GetChatroomHandle(self, wait=0):
        start_time = time.time()
        while True:
            hwnd = win32gui.GetForegroundWindow()
            if hwnd:
                classname = win32gui.GetClassName(hwnd)
                if classname == "TfrmDccChat":
                    self.hwnd_chatroom = hwnd
                    return self.hwnd_chatroom
            else:
                return 0
            if time.time() - start_time > wait:
                return 0
            win32api.Sleep(150)

기술적 어려움 2 단축키 프로세스가 사용 중 먹통이 되는 경우가 자주 발생함. 메시지 발생 기능을 제외하고 키보드 리스너만 실행시켜보아도 발생하는 것을 확인하고 리스너의 문제라고 판단 키입력을 단순 출력하도록 켜놓고 로그를 분석하니 멈추는 경우가 두 가지 있었음 먼저 한자/한영 키가 입력되었을 때 이를 핸들링하려고 할 때 멈추어 예외 처리. 두 번째로는 (아마 보안 상 문제로) 윈도우 잠금해제 창에 진입하는 경우 리스너가 종료되진 않지만 작동이 멈추는 현상. 윈도우 세션 이벤트 리스너 코드를 웹에서 가져와 잠금해제 시 키보드 리스너를 재시작하도록 해 해결

3.5. 최근사용 이모티콘 표시

배경 카카오톡처럼 최근 사용한 이모티콘 항목을 보여줬으면 좋겠다는 요청

탐색 채팅기록이 채팅방마다 파일로 저장되며, journal 파일을 생성하는 점에서 메신저가 sqlite를 이용해 채팅을 저장한다는 것을 알 수 있었음 다른 탭과 달리 즐겨찾기 탭은 항목의 추가/제거가 자유로웠으므로 즐겨찾기 탭에 최근 발신한 이모티콘을 추가해 두면 최근사용 이모티콘 탭처럼 사용할 수 있겠다는 생각

구현

파이썬 sqlite3를 이용하여 최근 업데이트된 채팅방을 주기적으로 검색하여 발신 기록을 가져오고 발신 기록에 이모티콘이 있다면 해당 이모티콘을 즐겨찾기 탭에 추가해주는 방식으로 카카오톡의 최근사용 기능을 똑같이 구현 기능을 활성화만하면 (로그인 중인 아이디 파악)-(활성화된 채팅창의 채팅 로그 모니터)-(이모티콘 발신 시 발신한 이모티콘 파악 후 즐겨찾기 탭에 푸시)와 같은 프로세스가 자동으로 이루어짐.

기술적 어려움 사용자가 발신한 메시지를 구분하려면 사용자의 아이디를 얻어야 하지만 사용자 아이디를 md5로 해시된 문자열만 알 수 있었음 반면 채팅 기록에는 base64로 인코딩 된 발신자 아이디가 그대로 남아있었으므로 채팅 기록에 존재하는 아이디들과 모두 대조하는 방식으로 사용자 아이디를 알아냄

또한 사용자가 메시지를 보내는 이벤트가 발생할 때 그 내용을 판단하는 훅을 구현해야 했는데 sqlite의 db파일은 보통의 파일시스템과 다르게 동작하여 이벤트 리스너를 사용할 수 없었음 멋진 방식은 아니지만 폴링방식으로 구현. 전체 파일을 조회하진 않고 파일 끝부분만 조회하여 변경되었을 경우에만 내용을 확인함.

3.6. 자동 스크랩

배경 다른 사용자들에게 배포하기 위해 이모티콘 이미지를 수집/가공하고 xml파일을 작성하는데 시간이 많이 소요됨

구현 카카오톡 이모티콘 페이지에서 selenium을 이용해서 이미지를 자동으로 다운받을 수 있음 이미지 가공도 pillow를 이용해 자동으로 수행할 수 있었으므로, 카카오톡 이모티콘 링크만 입력하면 모든 과정을 자동으로 수행해주는 코드 작성

4. 회고

배운 점 최대한 사용자가 신경써야 하는 것이 없도록 만드는데 많은 시간을 사용했다. 되게 하는 것은 쉽지만 잘 되게 하는 것은 (매우) 어렵다는 말을 다시금 되새기는 계기가 되었다. 파이썬으로 상호작용이 가능한 프로그램을 만드는 것, 멀티스레드로 다양한 기능들을 담는 것 등 처음하는 것이 대부분이어서 많이 배울 수 있었다. 특히 API는 물론 프로그램에 대한 어떠한 정보조차 제공되지 않는 환경에서 많은 기능을 구현하였다는 것에서 자신감을 얻었다. 여러차례에 걸친 배포-피드백-개선작업으로 사용자의 요구를 파악하고 반영하는 과정을 경험

아쉬운 점 다만 git 등 버전 관리 시스템의 존재를 몰라 테스트/폐기 과정이 복잡했던 점 다른 사람이 볼 것이라는 상상을 못 해 주석을 거의 달지 않았다는 점 섣부른 최적화로 비효율을 초래했던 점은 아쉽다. 특히 indexabledict클래스를 구현하는 대신 단순히 순회 탐색 방식을 사용했어도 속도가 크게 차이나지 않았을 것 같다.

요약

실시간 노래방 프로젝트
개요

• 기간: 2024년 10월 11일~11월 15일 (5주)
• 인원: 4명
• 기술 스택: WebRTC, Python, Celery, React, AI 모델(Demucs, Whisper)
• 관리 도구: GitHub, 노션

주요 기능

1. 노래 추가: 유튜브 링크 업로드 시 AI가 자동으로 배경음악과 가사를 분리하여 노래방 트랙을 생성.
2. 실시간 피드백: 음정 시각화를 통해 사용자에게 실시간 채점 및 피드백 제공.
3. 같이 부르기: 네트워크 지연을 보정하여 실시간 합창 경험 제공.

주요 기술적 도전과 해결

1. 음성 스트리밍 지연 극복:

   • 브라우저 환경에서 초저지연 구현이 어려움을 깨닫고, 지연을 완전히 없애는 대신 사용자가 체감하지 못하도록 음악 재생 오프셋을 조정.
   • 서버-클라이언트 간 시간 동기화 알고리즘 개발 및 구현: 네트워크 지연 추정 및 중앙값 기반 보정으로 서버 시계를 사용해 음악 동기화.

2. 네트워크 오프셋 계산 및 적용:

   • 사용자마다 다른 네트워크 지연을 최소화하기 위해 부르는 사람과 듣는 사람 간 지연을 동적으로 조정.
   • 지연 데이터를 기반으로 최소제곱법을 활용하여 최적의 오프셋 값 계산.

성과 및 배운 점

• 초기 아이디어를 현실적이고 구현 가능한 방식으로 전환.
• 서버 시간 동기화, 지터 버퍼 관리, 오프셋 적용 등 네트워크와 음성 처리 경험.

포스터

1. 개요

1.1. 배경

실시간 게임은 있는데 실시간 노래는 없는 것에 의문을 품으며 같이 부르는 노래방을 만들자는 아이디어로 시작했습니다. 노래를 넣으면 자동으로 노래방으로 만들어주는 편리한 서비스를 기획했습니다.

소개영상: https://youtu.be/eH1V3jkvpnQ 현장발표영상: https://youtu.be/B-ScB_yoydY

1.2. 개발 환경

• 개발인원: 4인
• 관리도구: github, 노션
• 사용기술: WebRTC, python, celery, React, AI모델(demucs, whisper)
• 개발기간: 2024. 10. 11.-11. 15.(기획포함 5주)

1.3. 주차별 진행 과정

주차	진행 내용
0주차	개발 기획
1주차	노래 추가 프로세스, 혼자 부르기 ui, 음정 시각화 개발
2주차	같이 부르기 ui, webRTC 시그널링, 방 관리, 채팅 등 개발
3주차	1, 2주차 내용 폴리싱(노래 추가 프로세스 속도 및 안정성 개선, 시각화 속도 개선, RTC 턴 서버 구축, 방관리 로직 개선(노래 부르는 중간에 입장), 모바일 레이아웃 개발)
4주차	개발 마무리 및 버그 수정, 발표 시나리오 및 포스터 준비
# 2. 기능
## 2.1. 노래 추가

유튜브 링크를 업로드하면 배경음악부터 가사까지 자동으로 추출합니다.

2.2. 실시간 피드백(채점/점수 계산)

실시간으로 음정의 정확도를 눈으로 확인하며 부를 수 있습니다.

2.3. 같이부르기

네트워크 지연이 느껴지지 않도록 음악재생시간에 오프셋을 적용합니다. 오프셋 적용 방식은 마이크를 켠 사람(부르는 사람)과 마이크를 끈 사람(듣는 사람)으로 구분되어 적용됩니다. 마이크를 켜고 끌 때 자동으로 전환되며 최소제곱법으로 최적의 오프셋을 계산합니다.

3. 구현과정

3.1. 재생시간 조절을 통한 지연보상

3.1.1. 배경

최초 목표는 초저지연 음성 스트리밍을 통해 같이 부를 수 있는 서비스였습니다. 음성 지연을 점점 늘려가며 시험해본 결과 약 40ms정도부터 지연의 존재를 느끼기 시작했고 100ms가 되면 모두가 지연을 느꼈습니다. 150ms를 넘어가면 확실한 지연을 느꼈습니다.

가능할 것이라고 예상한 이유 오디오를 wav 그대로 전송하는게 아닌 이상 인코딩을 해야하고, 인코딩 윈도우 때문에 일정 지연이 발생합니다. 가장 짧은 opus에서 최소로 지연하는 프레임사이즈는 2.5ms(보통 10ms) 따라서 프레임버퍼링으로 2.5ms, 알고리즘 지연시간 5ms로 잡고, 네트워크 지연으로는 유선 좋은 컨디션 기준 10ms이하라고 가정한다면 마이크 등 하드웨어 지연과 패킷화 등 전송 준비에 들어가는 지연을 감안해도 40ms 안쪽으로 가능할 것이라고 생각했습니다.

달랐던 실제 테스트 결과 하지만 브라우저 테스트 결과 코덱 설정에 한계가 있었습니다. 또 사전에 미처 예상하지 못 했던 오디오 컨텍스트 지연 때문에 네트워크를 제외하고도 약 150ms의 지연이 발생했습니다. 따라서 지터 버퍼로 인한 지연과 네트워크 지연이 없다고 가정해도 초저지연 음성스트리밍은 불가능 하다고 판단했습니다.

기획 수정을 고민하던 중 음성을 앞당길 수 없다면 음악소리를 미루면 되지 않을까하는 아이디어가 떠올랐고 개발해보기로 하였습니다.

3.1.2. 챌린지1(음악 동시 재생)

목소리와 음악소리의 재생시점을 별도로 조절하기 위해서는 컨텍스트를 분리해야합니다. 또 정밀한 조정을 위해 음악을 가능한 동시에 재생해야하고, 동시 재생을 위해서는 단말들이 공통의 시계를 가져야 합니다. 송포유에서는 공통 시계로 서버 시계를 사용합니다.

구체적인 방법 서버시간을 알아내기 위해 방에 입장하면 클라이언트는 서버에 현재 시간을 요청합니다. 수신한 서버 시간을 이용해 아래와 같이 자신의 시계와 서버 시계와의 차이($T$)를 추정하게 됩니다.

$T=CT-ST$ $T=$서버시간과 클라이언트시간의 차이 $CT=$클라이언트 시간 $ST =$ 서버 시간 ($CT$와 $ST$는 동일한 시점에서의 값)

클라이언트시간에 오차가 없다고 가정하면 $CT=ct$ ($ct$는 performance.now()로 얻은 시간)

서버에서 시간을 받아올 때에도 지연이 발생하므로 발생한 지연($l$)만큼 받아온 시간에 더해주어야 합니다. $ST = st + l$ ($st=$클라이언트가 수신한 서버 시간, $l=$서버 응답이 클라이언트 도달하기까지 지연)

이제 $T$를 어떻게 추정할 것인지 생각해야 합니다.

3.1.2.1. $T$의 추정 1

우선 $l_i < RTT_i$이기 때문에 RTT가 가장 작은 표본을 대푯값으로 사용하는 방법을 생각해볼 수 있습니다. 즉, $\hat{T}=ct_{i^}-st_{i^}; (여기서 ;i^* = argmin_i ; RTT_i)$을 사용하는 방법입니다.

이 방법에서 $T$에 대한 잔차$e_T$는 $e_T=T-\hat{T}=(CT-ST)-(ct_{i^}-st_{i^})=-l_i$이고 성질상 $l_i > 0$이므로 $-RTT_{i^}<e_T<0$이 됩니다. 즉 $|e_T|$를 항상 $RTT_{i^}$미만으로 통제가 가능합니다. 하지만 이 방법은 네트워크 지연이 작은 환경에서만 $e_T$을 낮게 통제할 수 있고 표본의 수를 결정하기 어렵다는 단점이 있었습니다.

3.1.2.2. $T$의 추정 2

$l$을 정확히 알 수 있다면 $ST$ 또한 알 수 있습니다. 하지만 서버에서 클라이언트에 도착하는 시간은 측정하는 것이 어려우므로, 추정값을 사용해야 합니다. 따라서 $T$의 추정문제는 아래와 같이 $l_i$에 대한 추정문제로 변환할 수 있습니다. $\hat{ST}=st_i+\hat{l}_i$, $T-\hat{l}_i=t_i=ct_i-(st_i+\hat{l}_i)$

서버로의 지연과 클라이언트로의 지연이 거의 같을 것이라고 가정하면 $\hat{l}_i=RTT_i/2$를 사용할 수 있고 따라서 $t_i=ct_i-(st_i+RTT_i/2)$입니다.

이제 표본 $t_i$들로 $\hat{T}$를 추정해야 합니다. ${T}$의 분포($l$의 분포)를 가정하는 것은 어려웠습니다. $l>0$이기 때문에 표본의 개수가 많지 않은 이상 정규분포로 가정하기 어려웠습니다. 따라서 모수추정을 하지 않는 방법을 선택했습니다.

적당히 나쁜 네트워크 환경에서 $t_i$를 추출하는 작업을 여러번 반복해 그래프를 그려 보았습니다.

(표본 50개를 정렬하여 표시한 그래프)

• 평균: -6761.334
• 절사평균: -6757.0403
• 중앙값: -6740.6501
• 최빈값(kde mode): -6753.3704

여러기기로 테스트 해보았을 때 항상 그래프 상 10-30구간과 같은 평평한 구간이 나타났고, 가장 정확한 서버 시간을 표시했습니다. 따라서 평평한 구간의 중앙값을 $\hat{T}$으로 사용했습니다.

$t_i ≤ t_j (i < j)$를 모든 $i,j$에서 만족할 때 $\hat{T}=median(t_i, ...., t_{i+k}) (k≥RANGE, t_{i+k}-t_i ≤ MAXERROR)$ RANGE는 5, MAXERROR는 7

기타(파라미터 선택 과정)

처음에는 RANGE를 고정값으로 둘 경우 중앙에서 많이 벗어난 곳을 평평한 구간으로 판단할까 우려해서 RANGE를 N에 연동시켰습니다. (RANGE는 $max(5, N/2)$, MAXERROR는 10) 대체로 잘 작동하였으나 중간 발표 당시 T를 결정하는데 너무 오래 걸려 노래 시작이 안 되는 현상이 일어났습니다. $l$의 값이 널뛸 수록 표본의 수가 많이 필요할 것이라고 생각해 조건($(k>RANGE, t_{i+k}-t_i ≤ MAXERROR)$)을 만족하는 수열이 나타날 때까지 서버 시간을 받아오도록 한 것이 문제였습니다. $l$의 변동이 심하다는 것은 네트워크 상태가 좋지 않다는 것이고, 자연스럽게 $l$의 값도 컸습니다. 그런 상황에서 RANGE가 N에 비례해서 늘어나니 $\hat{T}$를 계산하는데 시간이 오래 걸렸던 것입니다.

변동이 심한 상황에서는 어차피 평평한 구간이 잘 발생하지 않는다는 것을 확인하고 RANGE를 5로 고정시키고 MAXERROR를 7로 낮췄습니다. 50회 이상 측정이 필요했던 환경에서도 20회 미만에서 측정을 끝낼 수 있었습니다.

3.1.3. 챌린지2(네트워크 오프셋 계산법)

두 번째 문제는 각 사용자의 음악을 얼마만큼 미루고 앞당겨야(오프셋) 목소리에 지연(체감지연)이 없다고 느낄 수 있을 지였습니다. 아래와 같은 순서로 시도하였습니다.

3.1.3.1. 시도1

발생한 지연 만큼 듣는 사람의 음악 재생을 미루기 듣는 사람이 여럿인 경우 여러명이 지연만큼 미뤄야한다는 단점, 음악과 목소리를 믹싱해서 전송하는 기존의 방식과 본질적으로 같아 특별한 장점이 없음

3.1.3.2. 시도2

부르는 사람의 음악 재생을 앞당김 지연시간을 불러오는데 단계가 추가되지만 부르는 한 사람만 음악 재생이 바뀜 사용자 간 지연이 각자 달라 평균을 취하면 잔차가 남는 단점

3.1.3.3. 시도3

부르는 사람에 오프셋을 적용하고 각 듣는 사용자에게 남는 잔차만큼 추가적으로 오프셋 적용 각 사용자들이 조금씩 보정을 적용해야 하지만 그 정도를 최소화(3.1.3.5. 최적 오프셋 계산) 하지만 부르는 사람이 둘 이상이 되면 이론상 지연을 0으로 만들 수 없는 상황이 발생

3.1.3.4. 시도4

이론상 지연을 0으로 만드려면 인위적으로 지연을 삽입해 지연 차이를 부르는 사람마다 같게 만들어야 함

예시: 부르는 사람 A, B, 듣는 사람 C, D가 있을 때 A의 음성이 C에 도달하는데 걸리는 지연을 $Delay_{AC}$라고 하면, $Delay_{AC}-Delay_{AD}=Delay_{BC}-Delay_{BD}$일 때에만 0지연을 만들 수 있다. 그렇지 않으면 목소리 출력에 인위적인 지연을 추가시켜 조건을 만족시켜야 한다.

하지만 스트리밍 음성의 딜레이를 조절하는 것이 어려웠으며 일반적으로 지연 차가 유사하고 또 매우 크지 않은 이상 잔차도 느끼기 힘들기 때문에 큰 문제는 없을 것이라고 판단, 평균을 적용하는 것으로 결정

3.1.3.5. 최적 오프셋 계산

마이크를 켜는 시점에 듣는 사람/부르는 사람이 전환되며, 적용되는 오프셋이 0에 가까울 수록 불편함을 덜 겪게됩니다. 지연시간이 부르는 사람과 듣는 사람에 나누어 적용되기 때문에 듣는 사람에게 오프셋을 크게(절댓값) 적용하면 부르는 사람에게 적용되는 오프셋이 작아지고, 그 반대의 경우도 마찬가지입니다. 즉, 듣는사람/부르는사람의 오프셋 적용에 사용자 경험의 상충관계가 존재해 어떤 쪽을 더 우선시 할지 정책을 세워야 했습니다.

정책별 예시:

A가 부르는 사람, B, C가 듣는 사람이라고 할 때

1. 듣는 사람의 오프셋 적용을 최소화 $offset_A=-\frac{Delay_{AB}+Delay_{AC}}{2}$($offset_B^2 + offset_C^2$를 최소로하는 값) $offset_B=\frac{Delay_{AB}-Delay_{AC}}{2}$ $offset_C=\frac{-Delay_{AB}+Delay_{AC}}{2}$를 적용
2. 부르는 사람의 오프셋 적용을 최소화 $offset_A=0$ $offset_B=Delay_{AB}$ $offset_C=Delay_{AC}$를 적용
3. 모두를 동등하게 고려 $offset_A=-\frac{Delay_{AB}+Delay_{AC}}{3}$ $offset_B=\frac{2Delay_{AB}-Delay_{AC}}{3}$ $offset_C=\frac{-Delay_{AB}+2Delay_{AC}}{3}$를 적용

이 프로젝트에서는 1번 방법(듣는 사람의 오프셋 적용을 최소화)을 선택했습니다. 부르는 사람은 오프셋 적용 시점을 예측하기 쉬운 반면, 듣는 사람은 그렇지 않기 때문에 듣는 사람의 경험을 더 우선시 하는 게 좋다고 판단했습니다.

계산 예시:

모두를 동등하게 고려하는 경우의 계산 방법 예시입니다.(다른 경우도 계산 방식은 유사) A가 노래를 부르는 시점부터 B가 A의 목소리를 듣는 시점까지 200ms가 걸린다고 했을 때($Delay_{AB}=200$) A의 노래를 200ms만큼 앞당기면 B의 체감 지연은 0이 됩니다. ($offset_A=-200$) 또는 A의 노래를 100ms만큼 앞당기고 B의 노래를 100ms만큼 미루면 체감 지연은 0이 됩니다.($offset_A=-100$, $offset_B=100$) 즉, 듣는 사람의 음악과 목소리 사이에 체감 지연이 0이되기 위해서는 $Delay_{AB}+offset_{A}-offset{B}=0$을 만족해야 합니다.

A가 노래를 부르고 B,C가 듣는다고 했을 때, B, C의체감 지연을 0으로 만들면서도 A, B, C의 오프셋 적용을 최소화(0에 가깝게)하려면 $offset_{B} = offset_{A}+Delay_{AB}$ $offset_{C} = offset_{A}+Delay_{AC}$를 만족하는 $offset$ 쌍 중에서 잔차제곱합 $SS=offset_A^2+offset_B^2 + offset_C^2$를 최소로 하는 $offset_A$ 즉, $\frac{d SS}{d (offset_A)}=0, \frac{d^2 SS}{d (offset_A)^2}>0$를 만족하는 $offset_A, offset_B, offset_C$를 선택해야 함

$$ \begin{aligned} SS &= offset_A^2+offset_B^2 + offset_C^2\ &= offset_A^2+(Delay_{AB}+offset_A)^2 + (Delay_{AC}+offset_A)^2\ &= 3offset_A^2+2(Delay_{AB}+Delay_{AC})offset_A+Delay_{AB}^2+Delay_{AC}^2\ \ \frac{d SS}{d (offset_A)} &= 6offset_A+2(Delay_{AB}+Delay_{AC})\ &= 0\ offset_A&=-\frac{Delay_{AB}+Delay_{AC}}{3}\ \ \frac{d^2 SS}{d (offset_A)^2} &= 6 >0 \end{aligned} $$

일반화하면 아래와 같습니다. $$offset_A = \sum_{i∈listeners}Delay_{Ai}/(N+1)$$

3.1.4. 챌린지3(오프셋 적용)

챌린지 2에서 다룬 음성을 전송 간 발생하는 지연 외에 오디오 입출력 과정에서 발생하는 지연도 반영해야 합니다.

3.1.4.1. 지연 요소

먼저 지연 발생 요소를 파악해야 했습니다. 노래 목소리가 전달되는 과정을 순서대로 생각해보면

1. 사용자가 부른 노래소리가 마이크의 진동판을 울려 전기신호를 하드웨어로 전달한다.
2. 하드웨어가 신호를 샘플링해 이산 데이터를 생성하고 프로세스에 전달
3. 그 데이터를 특정 코덱으로 인코딩한다
4. 인코딩한 바이너리 데이터를 UDP/TCP패킷으로 만든다
5. 네트워크로 전송
6. 상대방이 수신하면 지터 버퍼에 담아 둔다
7. 일정 시간이 지나면 지터 버퍼에서 출력되어 디코딩
8. 출력 버퍼에 담아두었다가
9. 다시 아날로그 신호로 바뀌어 전기신호로 전달
10. 스피커에서 출력된다

여기서 환경마다 변동이 큰 요소는 5, 6입니다. 블루투스 이어폰 등 무선 기기를 사용한다면 1, 9도 커질 수 있습니다.

따라서 오프셋을 계산하기 위해 아래의 네 가지 state로 분류하여 사용했습니다.

• 5(networkDelay): RTC통계의 사용자별 RTT를 이용해 추정할 수 있음
• 6(jitterDelay): RTC연결별 통계에서 (사후적으로) 알아낼 수 있음
• 1, 9(playoutDelay):는 audioContext의 속성에서 추정값을 불러올 수 있음
• 나머지(audioDelay): 나머지 요소는 추정이 힘들고 환경별 편차가 크지 않을 것이라고 기대하고 하나의 상수(150ms)를 사용

  3.1.4.2. 오프셋 계산

  이제 각 지연요소들로 음악 재생을 얼마나 늦출지에 대한 값(오프셋)을 계산해야 합니다. 오프셋이 양수이면 그 수치만큼 음악 재생이 늦춰지고 오프셋이 음수이면 앞당겨집니다.

  사용자가 듣는 사람일 경우

• networkDelay: 챌린지2에서 계산한 사용자별 네트워크 딜레이를 오프셋에 더함
• jitterDelay: 이 값만큼 목소리 출력이 지연되므로 오프셋에 더함
• playoutDelay, audioDelay: 음악과 목소리 공통으로 발생하는 지연이므로 고려하지 않음

  사용자가 부르는 사람일 경우

• networkDelay: 챌린지2에서 계산한 사용자별 네트워크 딜레이를 오프셋에 뺌
• jitterDelay: 출력 지연에만 영향을 미치므로 고려하지 않음
• playoutDelay, audioDelay: 음악을 재생하는데 걸리는 지연만큼 사용자가 노래를 부르는 시점도 늦춰지므로 이 값만큼 빨리 재생해야한다. 오프셋에서 뺌

  적용 형태

  if (isMicOn) {
    setLatencyOffset(
      -audioDelay - singerNetworkDelay - optionDelay - playoutDelay
    );
  } else {
    setLatencyOffset(jitterDelay + listenerNetworkDelay);
  }

3.1.4.3. 재생시점 조절

오프셋이 변화할 때 재생시간을 조절해야 했습니다. 실제 재생시간과 목표 재생시간을 비교하여 재생배속을 조절하는 방식을 사용했습니다. (실제 재생시간 - 목표 재생시간) / (1 - 전환속도) 동안 전환속도를 적용

예시

노래를 시작하고 1초가 지난 상황을 가정해보겠습니다. 노래 시작 시간 = 12:03:00:000(12시 3분) 현재 시간 = 12:03:01:000 실제 재생시간 = 1초

이 때 사용자가 마이크를 켜서 -300ms의 오프셋이 적용되었습니다. 그렇다면 $목표 재생시간 = (현재 시간) - (노래 시작 시간) - (오프셋) = 1000ms - (-300ms) = 1300ms$ 전환속도는 2배속 혹은 0.5배속만 사용 따라서 2배속을 $(1000ms - 1300ms) / (1 - 2) = 300ms$동안 적용하면 오프셋 적용이 완료됩니다.

3.2. AI 모델을 이용한 노래 추가

'노래방'이라는 서비스를 구현하기 위해서는 반주 음원과 가사 데이터가 필요합니다. 반주 음원은 유튜브 등에 많이 있고 가사데이터를 제공하는 서비스도 많습니다. 하지만 사용자는 변수들을 고려하지 않아도 되는 서비스를 원했기 때문에, 웹에서 반주와 가사를 찾아 가져오는 방식은 아래 단점들 때문에 배제했습니다.

1. 자동수집은 오류 가능성이 있고
2. 때문에 결국 사용자가 직접 적절한 데이터를 찾아와야 하는 경우가 생긴다
3. 만약 반주 데이터가 존재하지 않는다면 이용할 수 없으며
4. 존재 여부 또한 사용자가 별도로 확인해야 한다

반면 노래만 올리고 서버에서 반주와 가사를 모두 생성해준다면 장점은

1. 노래 데이터는 반주에 비해 찾기 훨씬 쉽고
2. 원곡에서 직접 추출된 반주를 사용하므로 미디반주보다 선호가 높다

단점은

1. 반주와 가사 생성 작업에 시간이 소요되며
2. 생성물에 오류가 있을 가능성이 있다.
3. 반주보다는 찾기 쉽지만 어쨌든 사용자가 노래를 찾아와야 한다.

하지만 단점들을 구현하면서 줄여볼 여지가 있었으므로 노래에서 자동으로 반주와 가사를 추출하는 서비스를 만들기로 하였다.

3.2.1. 보컬 분리 - Demucs(Meta)

3.2.1.1. 선정이유

source separation 분야의 성능이 가장 높았기 때문에 선택했습니다. 다른 선택 가능한 모델들도 있었지만 테스트 결과 기대 이상으로 좋은 성능을 보여주어 모델 탐색에 더 시간을 쓰지 않았습니다.

3.2.2. 가사 인식 - Whisper(OpenAI)

3.2.2.1. 선정이유

Whisper 또한 ASR 분야의 SOTA 모델입니다. 아래와 같은 장점이 있습니다.

1. 공개된 모델 중에서는 학습량이 제일 많아 노래와같이 다양한 억양이나 발음에도 강건
2. 다국어를 감지할 수 있어 언어 지정 없이도 작동하며 여러 언어가 섞여도 문제 없으며
3. 트랜스포머를 엔드투엔드로 사용하여 문맥을 고려한 토큰 생성 및 단어 선택으로 반복적인 가사 등장하는 노래에 적합하며
4. 강제 정렬까지 지원(가사 타이밍 표시에 필요)

3.2.2.2. 출력 오류 개선

Whisper는 STFT를 통해 생성한 스펙트로그램(로그-멜스펙트로그램)을 인풋으로 받아 인코더 디코더를 거쳐 텍스트 토큰으로 전사되는 엔드투엔드 트랜스포머 구조를 사용하고 있습니다. 이 때 인풋으로 받는 스펙트로그램의 최대 길이는 30초인데 이 때문에 노래에서 가사를 추출하려고 하면 아래와 같은 종종 오류가 발생했습니다.

3.2.2.2.1. 가사를 일부 출력하지 않는 오류

노래 전체를 입력으로 넣는 경우 Whisper모델에서는 30초 단위로 분할하여 모델에 입력합니다. 입력 별로 발화 오디오가 아닐 확률(no_speech_prob)을 계산하여 임계값 이상일 경우 출력을 하지 않습니다. 이런 동작은 hallucination을 피하는데 도움을 줄 수 있지만 노래와 같이 전주/간주 중 가사가 없는 구간이 길 경우에 문제가 됩니다.

사례

아이유 - love wins all 전주 길이가 23초입니다. 앞 부분 30초에 해당하는 가사를 출력하지 않았습니다.

23.3 31.80 Dearest, darling, my universe 날 데려가줄래 (실제 출력은 여기부터) 31.80 40.78 나의 이 가난한 상상력으론 떠올릴 수 없는 곳으로 42.1 51.18 저기 멀리 from Earth to Mars 꼭 같이 가줄래 51.18 60.92 그곳이 어디든 오랜 외로움 그 반대말을 찾아서 60.92 72.88 어떤 실수로 이도록 우리는 함께일까

해결

pydub의 detect_nonsilent를 이용해서 음성이 있는 부분만 인풋으로 제공하여 해결했습니다.

3.2.2.2.2. hallucination 현상

Whisper는 디코딩 과정에서도 tranformer를 이용해 텍스트 토큰을 예측하기 때문에 다른 모델과 마찬가지로 hallucination 현상이 발생합니다. hallucination현상을 완전히 없애려면 모델 자체를 수정해야 하기 때문에 자주 발생하는 상황을 파악하고 최대한 예방하는 것을 목표로 하였습니다.

사례

아래와 같은 출력이 있었습니다. 10.36 10.88 이 노래는 제가 제일 좋아하는 곡입니다. 112.1 138.92 자막 제작에 협조해주신 모든 분들께 감사드립니다. 0.92 0.92 자막 제작: xxx(사람이름) 학습 데이터에 인터넷에 공유된 영화 자막 등을 사용하여 묵음 구간에 잘못된 학습이 발생하지 않았나 추측됩니다.

해결

묵음에서 자주 발생하였으므로 4.2.2.2.1.에서와 마찬가지로 묵음 구간 타임스탬프를 제공하여 묵음이 아닌 구간만 인식하도록 하였습니다. temperature를 0으로 고정시키고, 출력에서 세그먼트 텍스트의 길이에 비해 너무 짧은 발화시간 등 이상현상을 기계적으로 검출하여 삭제하는 작업을 추가하였습니다.

temperature를 0으로 고정한 이유

whisper는 출력의 confidence가 높지 않은 경우 temperature를 증가시켜 재시도합니다. 이는 인식에 실패하는 경우를 줄여주나, 높은 temperature에서 잘못된 출력을 하여 repeat loop에 빠지게 되면 전체 가사 전사작업이 엉망이 되는 경우가 있었습니다. 따라서 일부 인식에 실패하거나 오인식하는 상황이 있더라도 temperture는 0으로 고정하는 것이 좋겠다고 판단하였습니다.

3.2.2.3. 가사 스크래핑 시도

자작곡 등 가사정보가 존재하지 않는 경우도 있지만 대부분의 노래는 인터넷에 가사 정보가 공개되어 있습니다. 정보가 있다면 사용하는 편이 좋다고 생각해 여러 시도를 해보았지만, 아래 이유로 최종적으로는 사용하지 않았습니다.

1. 우선 가사가 존재하지 않는 노래도 있음
2. 가사를 가져오더라도 진짜 원하는 노래의 가사인지 한 번 더 확인이 필요함(중요한 건 아님 충분히 기술적으로 해결 가능. 인식 버전과 유사도를 비교한다든가)
3. 그러나 가져오더라도 강제정렬이 필요하며, 어차피 강제정렬도 모델의 인식률에 결과물의 퀄리티가 의존함
4. 모델에 프롬프트로 원본가사를 제공(존재하는 경우)하는 방식은 오히려 언어모델의 오류만 키웠으며, whisper는 텍스트를 제공하여 강제정렬을 할 수 없음
5. 결론적으로 주어진 정보를 이용할 수 있는 적절한 다른 모델을 찾지 못 해 음성인식으로 가사를 추출하도록 함

   3.2.3. 음정 추출 - CREPE

   3.2.3.1. 선정이유

   음정 추출에서 가장 중요한 이슈는 노이즈 강건성과 옥타브 오류 최소화입니다. 송포유에서는 노래에서 분리된 보컬만을 입력으로 사용하므로 옥타브 오류가 좀 더 중요하다고 볼 수 있습니다. CREPE는 딥러닝을 이용해 단일 출력이 아닌 다양한 주파수 값 후보에 대한 활성화도를 제공하여 후처리가 더 용이했습니다.

   3.2.3.2. 후처리

   (CREPE가 출력하는 활성화도. 가로축: 시간, 세로축: 주파수(로그스케일))

활성화도를 토대로 노래방화면에 표시해 줄 음정(각 시간별 주파수)을 추출하게 됩니다. 음성이 확실하지 않은 부분(숨소리, 무성음)에서 번져있는 모습 때문에, 단순히 특정 값 이상으로 필터링을 하게 되면 가사가 없는 구간에도 음정이 추출되거나 그래프가 튀는 현상이 나타났습니다.

frequency = np.max(activation, axis=1)
confidence = np.max(activation, axis=0)

filtered_frequency = np.where(confidence > 0.5, frequency, np.nan)

주로 오류가 발생하는 부분은 시간에 따라 일정하게 주파수가 유지되지 않는다는 점을 이용해 가우시안 필터를 적용한 활성화도를 사용하는 방법으로 개선했습니다. 가우시안 필터의 표준편차는 가로/세로 축에 따라 적절한 값을 적용해 음정 변화의 디테일을 살리면서 필터링할 수 있도록 하였습니다. (가우시안필터를 적용한 활성화도(좌), 시간축 표준편차를 줄인 활성화도(우))

(원본 출력(좌), 가우시안 필터 및 보정 적용 출력(우))

3.2.4. CELERY

3.2.4.1. 사용 배경

송포유에서는 웹서버, api서버와 AI처리 부분이 분리되어 있는데, 이는 GPU인스턴스가 비싸기 때문에 유연한 인스턴스 관리를 위함입니다. 프로젝트 용으로 받은 aws 크레딧이 1000불이었으므로, 한 달 프로젝트를 진행하기에는 무리가 없었지만 고작 한 번에 2-3분 남짓한 노래 추출을 위해서 시간당 0.526 USD(g4dn.xlarge기준)짜리 인스턴스를 계속 켜놓아야 하는 것이 말도 안 된다고 생각했기 때문입니다. 결국 온디맨드 인스턴스를 계속 실행시켜 놓기는 했지만, 스팟 인스턴스 사용 또는 cpu-gpu 인스턴스간 전환 등 비용 절감 방법을 사용하기 위해서는 AI처리 인스턴스와 분리된 작업 관리자가 필요하다고 판단, CELERY를 사용하였습니다.

단일 GPU 인스턴스를 사용하였으므로 병렬 처리에 따른 이득을 기대하기 어려워 워커는 하나만 생성하도록 하고, 모델을 프리로딩하여 재사용하도록 해 작업 당 처리지연시간 약 80초를 단축하였습니다.

4. 아쉬운 점

많지만 앞서 소개한 내용과 연관있는 몇 가지만 적어보겠습니다

1. 로직 상 화음 등 실시간으로 상대방의 목소리를 듣고 맞춰 부르는 것은 불가능. 사용한 로직은 듣는 사람/부르는 사람을 마이크 켬 여부로 구분해 두 그룹 간의 지연만 고려하는 방식입니다. 여러 사용자가 마이크를 켜게 되면 그 사용자들 간에는 지연이 느껴집니다. 방식 자체의 한계로 지연 자체를 제거하지 않는 이상 개선이 매우 힘듭니다.
2. 오프셋 변경 시 자연스러운 배속 조절(fade in/out)이 아닌 고정배속을 사용한 것 배속 재생 시 발생하는 피치 시프트를 정확하게 보정하는 코드 구현이 지연되어, 저속 빨리감기를 할 경우 피치 시프트가 너무 오랜시간 느껴지는 상황이었습니다.(1.1 배속 사용 시 200ms 오프셋을 적용하기 위해 2초가 필요) 피치 보정 없이는 차라리 트랜지션 시간을 줄여버리는 게 낫다고 판단하여 고정배속을 하였습니다.
3. 중복노래 필터링을 하지 못 한 것 오디오 핑거프린트, 제목 유사도 판단 등 중복 검사를 하지 않기 때문에 중복된 노래 업로드 시 스토리지 등 리소스 낭비가 발생합니다.
4. 지터딜레이도 네트워크에 포함시켰어야 지터딜레이도 RTC 연결마다 별도로 발생하고 있으므로 네트워크처럼 데이터 채널로 주고 받으며 네트워크 딜레이처럼 부르는/듣는 사람을 별도로 계산해야 합니다. 프로젝트 당시 미처 고려하지 못 했습니다.

   4.1. 현장 발표 영상에서 멀티 시연 시 두 목소리의 지연차가 느껴지는데요

   

로직상 허점이 있나 현재 구현은 3.1.3.4.에서 언급한 문제처럼 ①두 사람이 마이크를 켰으며 ②두 사람이 마이크를 끄고 있고 ③마이크를 끈 사람에 대한 지연 시간의 차가 큰 경우(대략 100ms 이상)에 두 사람의 목소리 타이밍에 차이가 있다고 느낄 수 있습니다. 하지만 시연에서는 마이크를 끄고 듣고 있는 사용자가 시연 단말 뿐이었으므로 로직상 지연이 없어야 합니다.

그렇다면 왜 오프셋 계산을 위해서 사용자간 마이크 켬/끔 상태를 공유하고 네트워크 RTT보고 등 여러 데이터를 주고받게 됩니다. 이 과정이 제대로 수행되지 않으면 오프셋이 정확하게 적용되지 않으므로 목소리가 동시에 나오지 않을 수 있습니다. 실제로 시연에서 한 사람의 점수와 음정그래프가 표시되지 않았는데 어떤 이슈로 RTC 데이터 채널에 문제가 생긴 것으로 보이며 때문에 네트워크 RTT나 마이크 상태가 교환되지 않았을 것으로 추정하고 있습니다. 이 부분은 향후 개선이 필요합니다.

차이점에 대한 chatgpt의 답변:

관계형 데이터베이스(RDBMS)와 키-값 데이터베이스는 데이터 관리 방식과 구조에서 큰 차이가 있습니다. 두 시스템은 각각 특정한 용도에 맞춰 설계되었으며, 그 특성에 따라 장단점이 있습니다.

1. 데이터 구조

• 관계형 데이터베이스 (RDBMS): 데이터를 테이블 형식으로 저장합니다. 테이블은 행(row)과 열(column)로 구성되며, 열은 특정 데이터 유형을 가진 필드입니다. 테이블 간에는 관계가 있을 수 있으며, 이러한 관계를 정의하기 위해 외래 키(foreign key)와 같은 메커니즘을 사용합니다. SQL(Structured Query Language)을 사용하여 데이터를 쿼리합니다.
• 키-값 데이터베이스: 데이터를 키(key)-값(value) 쌍으로 저장합니다. 각각의 키는 유일하며, 해당 키에 연결된 값은 여러 유형일 수 있습니다(문자열, JSON, 바이너리 등). 데이터의 구조나 관계는 별도로 정의되지 않으며, 매우 단순한 형식입니다.

2. 데이터 모델링

• RDBMS: 정규화를 통해 데이터를 구조화하고, 중복을 최소화합니다. 테이블 간의 관계를 설정하여 복잡한 데이터 모델링이 가능합니다.
• 키-값 데이터베이스: 매우 단순한 구조이므로 정규화나 관계 설정이 없습니다. 데이터 모델링이 매우 유연하지만, 복잡한 데이터 관계를 표현하는 데는 부적합합니다.

3. 확장성

• RDBMS: 수직적 확장(더 강력한 서버로 업그레이드) 방식을 주로 사용합니다. 복잡한 쿼리나 데이터 관계를 처리하는 데 적합하지만, 수평적 확장(서버를 여러 대로 분산하는 것)에는 한계가 있습니다.
• 키-값 데이터베이스: 수평적 확장(서버를 여러 대로 분산)이 용이합니다. 특히 대용량 데이터를 처리하거나 트래픽이 높은 경우에 성능이 뛰어납니다.

4. 성능

• RDBMS: 데이터 일관성과 복잡한 쿼리 처리를 위한 최적화가 잘 되어 있지만, 대규모 데이터나 트래픽이 많은 환경에서는 성능이 저하될 수 있습니다.
• 키-값 데이터베이스: 단순한 조회 작업에 매우 빠른 성능을 보여줍니다. 복잡한 쿼리보다는 빠른 읽기/쓰기 성능에 중점을 둡니다.

5. 트랜잭션 지원

• RDBMS: ACID(Atomicity, Consistency, Isolation, Durability) 속성을 준수하여 강력한 트랜잭션 관리 기능을 제공합니다. 데이터의 무결성과 일관성이 중요할 때 적합합니다.
• 키-값 데이터베이스: 일부는 간단한 트랜잭션을 지원하지만, 대부분 CAP 이론을 따릅니다. 데이터 일관성보다는 가용성과 성능을 중시합니다.

6. 사용 사례

• RDBMS: 금융, ERP 시스템, 전통적인 비즈니스 애플리케이션처럼 데이터 간의 복잡한 관계를 관리해야 하는 경우에 적합합니다.
• 키-값 데이터베이스: 세션 관리, 캐시, 빠른 조회가 필요한 대규모 웹 애플리케이션, 로그 저장 등에 적합합니다.

요약

• RDBMS: 구조화된 데이터, 복잡한 관계, 강력한 트랜잭션 지원이 필요한 경우에 적합.
• 키-값 데이터베이스: 단순하고 빠른 읽기/쓰기가 중요한 경우, 대규모 분산 시스템에 적합.

결론

답변을 읽고 보니까 엑세스에도 여러 테이블을 생성하여 관계를 정의할 수 있었던 것 같다. 테이블이 하나인 단순한 경우만 생각해서 비슷하다고 느꼈던 것 같다.