1. expression statement 정의
2. go에서 String 역할을 할 함수포인터 구현
3. 메모리 free 시킬 방법

1번

ast.h

typedef struct _expressionStatement {
    Expression expression;
    Token* token;
    int is_valid;
}ExpressionStatement;


ast.c

ExpressionStatement* newExpressionStatement()
{
    ExpressionStatement* es = (ExpressionStatement*)malloc(sizeof(ExpressionStatement));
    es->expression.node.TokenLiteral = expressionTokenLiteral;
    es->expression.node.statementType = EXPRESSIONSTMT;
    es->is_valid = 1;
    es->expression.node.PrintString = printExpressionStmt;
    return es;
}

이미 코드가 나와있었기에 만들기 쉬웠음

다만 expression이 포인터가아닌 그냥 구조체로 일단 사용했음
따라서 NULL 비교가 불가하기에 is_valid 추가시킴

2번

const char* printProgram(void* self)
{
    Program* p = (Program*)self;

    int len = p->statementsNum;
    char* str = NULL;
    for (int i = 0; i < len; i++) {
        append_string(&str, p->statements[i]->node.PrintString(p->statements[i]));
    }
    return str;
}

const char* printLetStmt(void* self)
{
    LetStatement* ls = (LetStatement*)self;

    char* str = NULL;
    append_string(&str, ls->statement.node.TokenLiteral(ls));
    append_string(&str, " ");
    append_string(&str, ls->name->node.TokenLiteral(ls->name));
    append_string(&str, " = ");

    if (ls->value != NULL) {
        append_string(&str,ls->value->node.TokenLiteral(ls->value));
    }

    append_string(&str, ";");

    return str;
}

const char* printReturnStmt(void* self)
{
    ReturnStatement* rs = (ReturnStatement*)self;
    char* str = NULL;

    append_string(&str, rs->statement.node.TokenLiteral(rs));
    append_string(&str, " ");

    if (rs->returnValue != NULL) {
        append_string(&str, rs->returnValue->node.TokenLiteral(rs->returnValue));
    }

    append_string(&str, ";");
    return str;
}

const char* printExpressionStmt(void* self)
{
    ExpressionStatement* es = (ExpressionStatement*)self;

    if (es->is_valid == 1) {
        return es->expression.node.TokenLiteral(es);
    }
    return "";
}

const char* printIdentifier(void* self)
{
    Identifier* i = (Identifier*)self;

    return i->value;
}

void append_string(char** dest, const char* src) {
    if (!src || !dest) return;  // src 또는 dest가 NULL인지 확인

    size_t old_len = (*dest ? strlen(*dest) : 0);
    size_t src_len = strlen(src);
    size_t new_len = old_len + src_len + 1;  // 널 종료 문자 포함

    char* new_str = (char*)realloc(*dest, new_len);
    if (!new_str) {
        perror("Memory allocation failed");
        exit(1);
    }

    if (old_len == 0) {
        // 기존 문자열이 없을 경우 strcpy_s 사용
        if (strcpy_s(new_str, new_len, src) != 0) {
            perror("strcpy_s failed");
            exit(1);
        }
    }
    else {
        // 기존 문자열이 있을 경우 strcat_s 사용
        if (strcat_s(new_str, new_len, src) != 0) {
            perror("strcat_s failed");
            exit(1);
        }
    }

    *dest = new_str;
}
문자열을 동적으로 추가해서 리턴하게 끔 만들어줌
책 내용 그대로 따라친거라 딱히 말할 내용없는듯

다만 문자열을 동적으로 추가하는 함수는 하나 추가해줌
String 관련 함수들이 없는게 참 불편한듯

3번

처음에 동적할당을 막 시켜놓으니 메모리를 해제 시키는 것에 좀 애를 먹었음

트리 구조이니 타고타고 들어가서 후위순회 방식으로 해야한다고 생각

일단 구조부터 파악을 하자 싶어서 코드를 다시 살펴봄

1. parser에는 errors와 lexer가 붙어있다.
2. lexer에는 input이 동적할당 되어있음

이 둘은 이렇게 따로 처리를 하고

program을 루트 노드로 Let, Return 등이 붙어있음
이를 비교해서 Let일때 name,token,expressionStmt를 free해줘야함

void freeToken(Token* token)
{
    if (token->literal != NULL)
        free(token->literal);

    free(token);
}

void freeLexer(Lexer* l)
{
    if (l->input != NULL)
        free(l->input);

    free(l);
}

void freeParser(Parser* p)
{
    if(p->l!=NULL)
        freeLexer(p->l);

    for (int i = 0; i < p->errorsNum; i++) {
        free(p->errors[i]);
    }

    free(p->errors);
}

void freeProgram(Program* p)
{
    for (int i = 0; i < p->statementsNum; i++) {
        int type = p->statements[i]->node.statementType;
        switch (type)
        {
        case LET:
            freeLetStmt((LetStatement*)p->statements[i]);
            break;
        case RETURN:
            break;
        case IDENTIFIER:
            break;
        case EXPRESSIONSTMT:
            break;

        }
    }

    free(p->statements);
    free(p);
}
void freeLetStmt(LetStatement* ls)
{
    freeToken(ls->token);

    if (ls->name != NULL)
        freeIdentifier(ls->name);

    if (ls->value != NULL)
        freeExpressionStmt(ls->value);

    free(ls);
}
void freeIdentifier(Identifier* i)
{
    freeToken(i->token);
    free(i);
}
void freeExpressionStmt(ExpressionStatement* es)
{
    free(es->token);
    free(es);
}

렉싱한 토큰을 가지고 토큰 사이의 유의미한 관계를 정리하는 것으로 이해함
일단은 LET 파싱부터 한다.

LET문 파싱

let은 monkey언어에서 (저저가 만든 가상의 프로그래밍 언어임)
변수와 표현식을 바인딩한다.

허나 지금은 표현식 파싱은 건너뛰고 let문을 파싱한다.

monkey언어에서 let문은
let <idenrifier> = <expression>; 구조를 띈다.

program 구조체에 statements 배열 포인터로 한줄씩 이어서 연결후
첫번째 statments[0]에는 letStatement가 
letStatement에는 해당 바인딩된 변수명과 표현식등이 이어져 내려오는 방식으로 보임

헤더파일

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<stdbool.h>
#include "token.h"

// Node 인터페이스를 위한 함수 포인터 정의
typedef const char* (*TokenLiteralFunc)(void*);


typedef struct _node {
    TokenLiteralFunc TokenLiteral;
}Node;

// Statement, Expression 구조체 정의 (Node "상속" 역할)
typedef struct _statement {
    Node node;
    void (*statementNode)(void*);      // 더미 메서드
} Statement;

typedef struct _expression {
    Node node;      // TokenLiteral 메서드
    void (*expressionNode)(void*);     // 더미 메서드
} Expression;

// Identifier 구조체 정의
typedef struct _identifier {
    Token* token;                      // Identifier의 토큰
    TokenLiteralFunc TokenLiteral;     // TokenLiteral 메서드
    char* value;                       // Identifier 값
} Identifier;

// LetStatement 구조체 정의
typedef struct _letStatement {
    Node node;              // Statement 포함 (상속 역할)
    Token* token;                      // let 키워드 토큰
    Identifier* name;                  // 변수 이름
    Expression* value;                 // 변수 값
} LetStatement;

// Program 구조체 정의
typedef struct _program {
    Statement** statements;            // Statement 포인터 배열
    int statementsNum;                 // Statement 수
} Program;

// 함수 선언

// LetStatement 관련 함수
LetStatement* newLetStatement();
const char* letTokenLiteral(void* self);

// Identifier 관련 함수
Identifier* newIdentifier();
const char* identifierTokenLiteral(void* self);

// Program 관련 함수
const char* programTokenLiteral(Program* p);

코드

#include "ast.h"
#include<string.h>


const char* letTokenLiteral(void* self) {
    LetStatement* ls = (LetStatement*)self; // self를 LetStatement로 변환
    return ls->token->literal;  // LetStatement에 대한 TokenLiteral 반환
}

const char* identifierTokenLiteral(void* self) {
    Identifier* id = (Identifier*)self; // self를 Identifier로 변환
    return id->token->literal;  // Identifier에 대한 TokenLiteral 반환
}

// Program 메서드 구현 (프로그램에서 첫 번째 Statement의 TokenLiteral 호출)
const char* programTokenLiteral(Program* p) {
    if (p->statementsNum > 0) {
        return p->statements[0]->node.TokenLiteral(p->statements[0]);
    }
    return "";
}

// LetStatement 및 Identifier 객체 생성 함수
LetStatement* newLetStatement() {
    LetStatement* ls = (LetStatement*)malloc(sizeof(LetStatement));
    // LetStatement의 TokenLiteral 함수 포인터를 설정
    ls->node.TokenLiteral = letTokenLiteral;

    return ls;
}

Identifier* newIdentifier() {
    Identifier* id = (Identifier*)malloc(sizeof(Identifier));

    id->TokenLiteral = identifierTokenLiteral;
    return id;
}

파서

헤더

#pragma once
#include "ast.h"
#include "lexer.h"
#include "token.h"

typedef struct _parser {
    Lexer* l;
    Token* curToken;
    Token* peekToken;
}Parser;

Parser* NewParser(Lexer* l);
void pNextToken(Parser* p);
Program* ParseProgram(Parser* p); 
Statement* parseStatement(Parser* p);
LetStatement* parseLetStatement(Parser*p);
bool curTokenIs(Parser* p,TokenType t);
bool peekTokenIs(Parser* p, TokenType t);
bool expectPeek(Parser* p, TokenType t);

코드

#include "parser.h"
#include <stdio.h>
#include<stdlib.h>

Parser* NewParser(Lexer* l)
{
    Parser* parser = (Parser*)malloc(sizeof(Parser));  // Parser 메모리 할당
    parser->l = l;  // Parser의 l 필드를 주어진 Lexer 포인터로 초기화

    pNextToken(parser);
    pNextToken(parser);//토큰 세팅

    return parser;
}

void pNextToken(Parser* p)
{
    p->curToken = p->peekToken;
    p->peekToken = NextToken(p->l);
}

Program* ParseProgram(Parser* p)
{
    Program* program = (Program*)malloc(sizeof(Program));
    program->statements = NULL;
    program->statementsNum = 0;
    //프로그램 만든후(statements 저장할 구조체) 초기화


    //모든 줄을 다 읽을때까지 반복
    while (p->curToken->type != EOF_TOKEN) {
        Statement *stmt = parseStatement(p);
        if (stmt != NULL) {
            program->statementsNum++;
            program->statements = (Statement**)realloc(program->statements, sizeof(Statement*) * program->statementsNum);
            program->statements[program->statementsNum - 1] = stmt;
        }

        pNextToken(p);
    }
    return program;
}

Statement* parseStatement(Parser* p) {
    const char* type = p->curToken->type;

    if (strcmp(type, LET_TOKEN) == 0)
        return (Statement*)parseLetStatement(p);
    return NULL;
}

LetStatement* parseLetStatement(Parser* p) {
    LetStatement *stmt = newLetStatement();
    stmt->token = p->curToken;
    //stmt->token에 LET 토큰 저장

    if (!expectPeek(p, IDENT_TOKEN)) {
        return NULL;
    }//LET 이후 변수명이 나오는지 검사

    stmt->name = newIdentifier();
    //name은 변수명을 의미함 변수명에 현재 어떤 토큰인지 
    stmt->name->token = p->curToken;
    stmt->name->value = p->curToken->literal;

    if (!expectPeek(p, ASSIGN_TOKEN)) {
        return NULL;
    }//만약 다음이 = 인지 검사

    //TODO: 세미콜론을 만날때까지 건너뜀

    while (!curTokenIs(p, SEMICOLON_TOKEN)) {
        pNextToken(p);
    }//세미 콜론까지 일단 제낌


    //test로 Let x = 10;이 들어온다면 현재 Let과 x만 저장되고 뒷부분은 날림
    return stmt;
}

bool curTokenIs(Parser* p, TokenType t)
{
    return p->curToken->type==t;
}

bool peekTokenIs(Parser* p, TokenType t)
{
    return p->peekToken->type==t;
}

bool expectPeek(Parser* p, TokenType t)
{
    if (peekTokenIs(p,t)) {
        pNextToken(p);
        return true;
    }
    return false;
}

일단은 표현식은 제쳐두고 변수만 저장되게함

어려웠던점

아무래도 go언어를 이용하는 프로그램이다 보니 인터페이스와 구현 등을 자주 활용함. 하지만 c에서는 해당부분이 안되서 힘들었음

다른거는 함수 포인터 등을 이용해서 멤버함수 비스무리하게 구현은 했지만 제일 어려웠던 것은 program 구조체의 statements 배열 포인터에 업캐스팅해서 집어넣는 부분

곰곰히 생각도 해보고 구글링도 해보고 지피티도 써봤더니 결론은 어차피 포인터의 크기는 동일 하니 (4또는 8바이트) 형변환이 가능함

문제는 데이터에 접근할때 접근가능한 크기가 형태에 따라 달라진다는 것임

char은 1byte씩 int는 4byte씩 접근이 가능함

그렇다면 statement*는 statement의 구조체 크기만큼 접근이 가능하니 letStatement의 첫번째 구성요소로 statement를 잡아놓고

형변환을 한다면 업캐스팅이 된 영역에서도 둘다 공통으로 가지고 있는 node 구조체에는 접근이 가능해짐

이 방법을 통해서 해결함

아직은 node에 업캐스팅해서 노드에 접근할 일이 없지만 나중에 생길것이라 생각중

또한 잘못 생각했던게 어차피 node가 겹치니까 그냥 node지우고 이걸 statement에 넣은후에 statement를 가지면 그게 상속이 아닌가? 했는데

tStatement ls가 있고 ls -> statement로 접근하게 된다면 statement*s=(statement)ls; 를 하게 된다면 s->statment라는 말도 안되는 접근이 발생하게 됌

그냥 statement만 두고 node 지운다음에 해도 상관없었음

예를 들어 letStatement에는 statement를 포함한 다른 멤버가있고 statement는 따로 있다고 할때

원래라면 ls->statement->~ 로 접근해야했던 것들이 업캐스팅후에는 s-> 바로 접근이 가능했음.

아마도 결국 멤버에 대한 접근이건 뭐건 메모리 상의 위치와 크기만 같으면 같은 데이터를 뽑으니까 업캐스팅을 한 상태로 접근을 하더라도 해당 영역은 동일한 크기와 동일한 주소임으로 그냥 접근이 가능한 것으로 보임.

혼자 머리 굴린거라 뇌피셜이긴 한데 ....

암튼 그냥 이게 더 깔끔해보여서 node 구조체를 만든후 해당 크기를 같이 잡는 방식으로 간접적으로 상속 느낌을 냄

토큰

-,/,*,<,> 와 같은 문자와 
== , != 같은 수식

return 과 같은 예약어를 추가한다.

token.h

#pragma once

#define ILLEGAL_TOKEN "ILLEGAL_TOKEN"
#define EOF_TOKEN "EOF"
#define IDENT_TOKEN "IDENT"
#define INT "INT"

// 연산자
#define ASSIGN_TOKEN "="
#define PLUS_TOKEN "+"
#define MINUS_TOKEN "-"
#define BANG_TOKEN "!"
#define ASTERISK_TOKEN "*"
#define SLASH_TOKEN "/"

#define LT_TOKEN "<"
#define GT_TOKEN ">"

#define EQ_TOKEN "=="
#define NOT_EQ_TOKEN "!="
// 구분자
#define COMMA_TOKEN ","
#define SEMICOLON_TOKEN ";"

#define LPAREN_TOKEN "("
#define RPAREN_TOKEN ")"
#define LBRACE_TOKEN "{"
#define RBRACE_TOKEN "}"

// 예약어
#define FUNCTION_TOKEN "FUNCTION"
#define LET_TOKEN "LET"
#define TRUE_TOKEN "TRUE"
#define FALSE_TOKEN "FALSE"
#define IF_TOKEN "IF"
#define ELSE_TOKEN "ELSE"
#define RETURN_TOKEN "RETURN"

typedef const char* TokenType;

typedef struct _token {
    TokenType type;
    char* literal;
    //type은 enum으로 저장해 두다가 나중에 필요하면 TokenType으로 사용하고
    //literal은 어떤건지 특정하게 받아오는것 얘를 들어 5가 저장되고 이걸 INT로 나중에 토큰 타입으로 두기
}Token;

또한 lexer.c에 추가된 토큰을 다룰수 있게 바꿔준다.

#include "lexer.h"
#include<stdlib.h>
#include<stdio.h>
#include<string.h>

Lexer* New(char* input)
{
    //인풋 받으면 새롭게 Lexer 구조체 만들어서 input 저장해두는 함수
    Lexer* l = (Lexer*)malloc(sizeof(Lexer));

    l->input = _strdup(input);

    if (!l->input) {
        fprintf(stderr, "Memory allocation failed for input string\n");
        free(l);
        exit(EXIT_FAILURE);
    }//인풋이 없을때 오류메시지 생성과 종료

    l->ch = 0;
    l->position = 0;
    l->readPosition = 0;
    readChar(l);

    return l;
}

void readChar(Lexer* lexer)
{
    if (lexer->readPosition > strlen(lexer->input)){
        lexer->ch = 0;//참조를 넘어가면 ch에 0넣기
    }
    else {
        lexer->ch = lexer->input[lexer->readPosition];
    }

    lexer->position = lexer->readPosition;
    (lexer->readPosition)++;
    //미리 살펴보고 해도 되나 검사
    //또한 현재 문자를 일단 보관을 해야하니
}

char peekChar(Lexer* l)
{
    if (l->readPosition >= strlen(l->input)) {
        return 0;//참조를 넘어가면 0 리턴
    }
    else {
        return l->input[l->readPosition];
    }
}

char* readNumber(Lexer* lexer)
{
    int position = lexer->position;

    while (isDigit(lexer->ch)) {
        readChar(lexer);
    }
    const int len = lexer->position - position;
    char* str = (char*)malloc(len + 1);

    if (str == NULL) {
        printf("Memory allocation failed\n");
        return;
    }

    strncpy_s(str, len + 1, lexer->input + position, len);

    return str;
}

Token* NextToken(Lexer* lexer)
{
    Token *tok=NULL;

    skipWhitespace(lexer);

    char lch = lexer->ch;

    switch (lch)
    {
    case '=':
        if (peekChar(lexer) == '=') {
            readChar(lexer);
            tok = (Token*)malloc(sizeof(Token));

            tok->type = EQ_TOKEN;
            tok->literal = "==";
        }else tok = newToken(ASSIGN_TOKEN, lch);
        break;
    case ';':
        tok = newToken(SEMICOLON_TOKEN, lch);
        break;
    case '(':
        tok = newToken(LPAREN_TOKEN, lch);
        break;
    case ')':
        tok = newToken(RPAREN_TOKEN, lch);
        break;
    case ',':
        tok = newToken(COMMA_TOKEN, lch);
        break;
    case '+':
        tok = newToken(PLUS_TOKEN, lch);
        break;
    case '-':
        tok = newToken(MINUS_TOKEN, lch);
        break;
    case '!':
        if (peekChar(lexer) == '=') {
            readChar(lexer);
            tok = (Token*)malloc(sizeof(Token));

            tok->type = NOT_EQ_TOKEN;
            tok->literal = "!=";
        }
        else tok = newToken(BANG_TOKEN, lch);
        break;
    case '*':
        tok = newToken(ASTERISK_TOKEN, lch);
        break;
    case '/':
        tok = newToken(SLASH_TOKEN, lch);
        break;
    case '<':
        tok = newToken(LT_TOKEN, lch);
        break;
    case '>':
        tok = newToken(GT_TOKEN, lch);
        break;
    case '{':
        tok = newToken(LBRACE_TOKEN, lch);
        break;
    case '}':
        tok = newToken(RBRACE_TOKEN, lch);
        break;
    case 0:
        tok = (Token*)malloc(sizeof(Token));

        if (tok == NULL) {
            printf("Memory allocation failed for tok.\n");
            exit(1); // 프로그램 종료
        }

        tok->type = EOF_TOKEN;
        tok->literal = _strdup("");
        break;

    default:
        if (isLetter(lch)) {
            tok = (Token*)malloc(sizeof(Token));

            if (tok == NULL) {
                printf("Memory allocation failed for tok.\n");
                exit(1); // 프로그램 종료
            }

            tok->literal = _strdup(readIdentifier(lexer));
            tok->type = LookupIdent(tok->literal);
            return tok;
        }
        else if (isDigit(lch)) {
            tok = (Token*)malloc(sizeof(Token));

            if (tok == NULL) {
                printf("Memory allocation failed for tok.\n");
                exit(1); // 프로그램 종료
            }

            tok->type = INT;
            tok->literal = readNumber(lexer);

            return tok;
        }
        else {
            tok = newToken(ILLEGAL_TOKEN, lch);
        }
    }

    readChar(lexer);

    return tok;
}


Token*newToken(TokenType token, char input)
{
    Token* newToken = (Token*)malloc(sizeof(Token));
    char* str = (char*)malloc(2);
    str[0] = input;  // 입력받은 char를 첫 번째 위치에 저장
    str[1] = '\0';   // 문자열 종료 문자 추가

    //토큰 받으면 input 받아서 리터럴 처리한후에 토큰 객체 돌려주기
    //newToken->literal = _strdup(TokenTypeNames[token]);
    //그냥 어차피 상수 포인터로 가르키기만 할건데 이렇게 해도 될듯...?
    newToken->type = token;
    newToken->literal = _strdup(str);
    return newToken;
}

void skipWhitespace(Lexer* l)
{
    while (l->ch == ' ' || l->ch == '\t' || l->ch == '\n' || l->ch == '\r')
        readChar(l);
}

bool isLetter(char ch)
{
    return 'a'<=ch&&ch<='z'||'A'<=ch&&ch<='Z'||ch=='_';
}

bool isDigit(char ch)
{
    return '0'<=ch&&ch<='9';
}

char* readIdentifier(Lexer* l)
{
    int position = l->position;
    while (isLetter(l->ch)) {
        readChar(l);
    }

    const int len = l->position - position;
    char* str = (char*)malloc(len + 1);

    if (str == NULL) {
        printf("Memory allocation failed\n");
        return;
    }

    strncpy_s(str, len + 1, l->input + position, len);

    return str;
}

const char* LookupIdent(const char* ident) {
    if (strcmp(ident, "fn") == 0) {
        return FUNCTION_TOKEN;
    }
    if (strcmp(ident, "let") == 0) {
        return LET_TOKEN;
    }
    if (strcmp(ident, "true") == 0) {
        return TRUE_TOKEN;
    }
    if (strcmp(ident, "false") == 0) {
        return FALSE_TOKEN;
    }
    if (strcmp(ident, "if") == 0) {
        return IF_TOKEN;
    }
    if (strcmp(ident, "else") == 0) {
        return ELSE_TOKEN;
    }
    if (strcmp(ident, "return") == 0) {
        return RETURN_TOKEN;
    }

    return IDENT_TOKEN;  // 매칭되는 키워드가 없으면 IDENT 반환
}

추가사항으로 ==등을 확인하기 위해서 peekChar() 함수를 만들어 = 나 ! 이 나올때 다음 문자를 확인한후 !=인지 ==인지 체크후 처리하게끔 한다.

REPL

Monkey언어에는 REPL이 필요하다.

repl.c
#include "repl.h"
#include "lexer.h"
#include "token.h"
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

void start(FILE*in,FILE*out)
{
    char line[MAX_LIEN_LENGTH];

    while (true) {
        fprintf(out, PROMPT);

        if (fgets(line, MAX_LIEN_LENGTH, in) == NULL) {
            break; //EOF 또는 오류
        }

        //개행문자 제거
        size_t len = strlen(line);
        if (len > 0 && line[len - 1] == '\n') {
            line[len - 1] = '\0';
        }

        Lexer* lexer = New(line);

        while (true) {
            Token *tok = NextToken(lexer);

            if (strcmp(tok->type, EOF_TOKEN) == 0) {
                break;
            }
            fprintf(out, "{Type:%s, Literal:%s}\n", tok->type, tok->literal);
        }

        free(lexer);
    }
}

main.c
#include"repl.h"
#include <windows.h>
#include <lmcons.h>
#include <stdio.h>
#include "lexer_test.h"

int main() {
    test_start();
    char username[UNLEN + 1];
    DWORD username_len = UNLEN + 1;

    GetUserName(username, &username_len);

    printf("Hello %s! This is the Monkey programming lauguage!\n", username);
    printf("Feel free to type in commands\n");
    start(stdin, stdout);
    return 0;
}

repl 실행 결과

렉서 끝내고 느낀점?

go로 적힌 언어를 c로 바꾸는게 생각보다 쉬운거 같으면서 어려웠음
책 따라가면서 따라 치는거라 생각보다 막 어렵다고 느껴지지는 않았음.
나중에 내가 다 만들고 기능들 추가하거나 c++로 만들거나 해봐야겠음

간단하게 테스트를 해봤으니 이제는 테스트의 범위를 좀더 늘려볼 계획

'let five = 5;' 라는 입력이 들어올때 얘를 렉싱해볼 생각

우선 렉서는 한글자씩만 읽었었음

따라서 let이나 five같은걸 l,e,t 이딴식으로 저장하게 됌 현재로는

하지만 이렇게 쓸수가 없으니 let 이런식으로 통째로 저장할 방법 생각

또한 = 같은 토큰들은 하나로 끝나니까 이전처럼 처리하면됌 
문제가 생기는 부분은 숫자와 문자은 원하는 만큼 readChar로 땡겨서 
한글자씩 문자열에 추가하려고 했는데

다시 생각해보니 input 위치에서 그냥 strncpy하면 됐음

중간중간 공백처리, ; 처리 등 고민을 해보고 내 나름 해봤는데
책 뒷장보니까 바로 방법이 적혀있었음..

코드

lexer.h

#pragma once
#include"token.h"
#include<stdbool.h>

typedef struct _lexer {
    char* input;
    int position;//입력에서 현재 위치(현재 문자)
    int readPosition;//입력에서 현재 읽는 위치(현재 문자의 다음)
    char ch;//현재 조사하는 문자
}Lexer;

Lexer* New(char* input);
void readChar(Lexer* lexer);
char* readNumber(Lexer* lexer);
Token* NextToken(Lexer* lexer);
Token* newToken(TokenType token,char input);

void skipWhitespace(Lexer* l);
bool isLetter(char ch);
bool isDigit(char ch);
char* readIdentifier(Lexer* l);
const char* LookupIdent(const char* ident);

lexer.c

#include "lexer.h"
#include<stdlib.h>
#include<stdio.h>
#include<string.h>

Lexer* New(char* input)
{
    //인풋 받으면 새롭게 Lexer 구조체 만들어서 input 저장해두는 함수
    Lexer* l = (Lexer*)malloc(sizeof(Lexer));

    l->input = _strdup(input);

    if (!l->input) {
        fprintf(stderr, "Memory allocation failed for input string\n");
        free(l);
        exit(EXIT_FAILURE);
    }//인풋이 없을때 오류메시지 생성과 종료

    l->ch = 0;
    l->position = 0;
    l->readPosition = 0;
    readChar(l);

    return l;
}

void readChar(Lexer* lexer)
{
    if (lexer->readPosition > strlen(lexer->input)){
        lexer->ch = 0;//참조를 넘어가면 ch에 0넣기
    }
    else {
        lexer->ch = lexer->input[lexer->readPosition];
    }

    lexer->position = lexer->readPosition;
    (lexer->readPosition)++;
    //미리 살펴보고 해도 되나 검사
    //또한 현재 문자를 일단 보관을 해야하니
}

char* readNumber(Lexer* lexer)
{
    int position = lexer->position;

    while (isDigit(lexer->ch)) {
        readChar(lexer);
    }
    const int len = lexer->position - position;
    char* str = (char*)malloc(len + 1);

    if (str == NULL) {
        printf("Memory allocation failed\n");
        return;
    }

    strncpy_s(str, len + 1, lexer->input + position, len);

    return str;
}

Token* NextToken(Lexer* lexer)
{
    Token *tok=NULL;

    skipWhitespace(lexer);

    char lch = lexer->ch;

    switch (lch)
    {
    case '=':
        tok = newToken(ASSIGN_TOKEN, lch);
        break;
    case ';':
        tok = newToken(SEMICOLON_TOKEN, lch);
        break;
    case '(':
        tok = newToken(LPAREN_TOKEN, lch);
        break;
    case ')':
        tok = newToken(RPAREN_TOKEN, lch);
        break;
    case ',':
        tok = newToken(COMMA_TOKEN, lch);
        break;
    case '+':
        tok = newToken(PLUS_TOKEN, lch);
        break;
    case '{':
        tok = newToken(LBRACE_TOKEN, lch);
        break;
    case '}':
        tok = newToken(RBRACE_TOKEN, lch);
        break;
    case 0:
        tok = (Token*)malloc(sizeof(Token));

        if (tok == NULL) {
            printf("Memory allocation failed for tok.\n");
            exit(1); // 프로그램 종료
        }

        tok->type = EOF_TOKEN;
        tok->literal = _strdup("");
        break;

    default:
        if (isLetter(lch)) {
            tok = (Token*)malloc(sizeof(Token));

            if (tok == NULL) {
                printf("Memory allocation failed for tok.\n");
                exit(1); // 프로그램 종료
            }

            tok->literal = _strdup(readIdentifier(lexer));
            tok->type = LookupIdent(tok->literal);
            return tok;
        }
        else if (isDigit(lch)) {
            tok = (Token*)malloc(sizeof(Token));

            if (tok == NULL) {
                printf("Memory allocation failed for tok.\n");
                exit(1); // 프로그램 종료
            }

            tok->type = INT;
            tok->literal = readNumber(lexer);

            return tok;
        }
        else {
            tok = newToken(ILLEGAL_TOKEN, lch);
        }
    }

    readChar(lexer);

    return tok;
}


Token*newToken(TokenType token, char input)
{
    Token* newToken = (Token*)malloc(sizeof(Token));
    char* str = (char*)malloc(2);
    str[0] = input;  // 입력받은 char를 첫 번째 위치에 저장
    str[1] = '\0';   // 문자열 종료 문자 추가

    //토큰 받으면 input 받아서 리터럴 처리한후에 토큰 객체 돌려주기
    //newToken->literal = _strdup(TokenTypeNames[token]);
    //그냥 어차피 상수 포인터로 가르키기만 할건데 이렇게 해도 될듯...?
    newToken->type = token;
    newToken->literal = _strdup(str);
    return newToken;
}

void skipWhitespace(Lexer* l)
{
    while (l->ch == ' ' || l->ch == '\t' || l->ch == '\n' || l->ch == '\r')
        readChar(l);
}

bool isLetter(char ch)
{
    return 'a'<=ch&&ch<='z'||'A'<=ch&&ch<='Z'||ch=='_';
}

bool isDigit(char ch)
{
    return '0'<=ch&&ch<='9';
}

char* readIdentifier(Lexer* l)
{
    int position = l->position;
    while (isLetter(l->ch)) {
        readChar(l);
    }

    const int len = l->position - position;
    char* str = (char*)malloc(len + 1);

    if (str == NULL) {
        printf("Memory allocation failed\n");
        return;
    }

    strncpy_s(str, len + 1, l->input + position, len);

    return str;
}

const char* LookupIdent(const char* ident) {
    if (strcmp(ident, "fn") == 0) {
        return FUNCTION_TOKEN;
    }
    if (strcmp(ident, "let") == 0) {
        return LET_TOKEN;
    }
    return IDENT_TOKEN;  // 매칭되는 키워드가 없으면 IDENT 반환
}

lexer_test.c

#include<stdio.h>
#include "token.h"
#include "lexer.h"
#include<string.h>

int main() {
    const char* input = "let five = 5; "
        "let ten = 10; "
        "let add = fn(x, y) { x + y; }; "
        "let result = add(five, ten);";


    Token tests[] = {
        {LET_TOKEN,"let"},
        {IDENT_TOKEN,"five"},
        {ASSIGN_TOKEN,"="},
        {INT,"5"},
        {SEMICOLON_TOKEN,";"},
        {LET_TOKEN,"let"},
        {IDENT_TOKEN,"ten"},
        {ASSIGN_TOKEN,"="},
        {INT,"10"},
        {SEMICOLON_TOKEN,";"},
        {LET_TOKEN,"let"},
        {IDENT_TOKEN,"add"},
        {ASSIGN_TOKEN,"="},
        {FUNCTION_TOKEN,"fn"},
        {LPAREN_TOKEN,"("},
        {IDENT_TOKEN,"x"},
        {COMMA_TOKEN,","},
        {IDENT_TOKEN,"y"},
        {RPAREN_TOKEN,")"},
        {LBRACE_TOKEN,"{"},
        {IDENT_TOKEN,"x"},
        {PLUS_TOKEN,"+"},
        {IDENT_TOKEN,"y"},
        {SEMICOLON_TOKEN,";"},
        {RBRACE_TOKEN,"}"},
        {SEMICOLON_TOKEN,";"},
        {LET_TOKEN,"let"},
        {IDENT_TOKEN,"result"},
        {ASSIGN_TOKEN,"="},
        {IDENT_TOKEN,"add"},
        {LPAREN_TOKEN,"("},
        {IDENT_TOKEN,"five"},
        {COMMA_TOKEN,","},
        {IDENT_TOKEN,"ten"},
        {RPAREN_TOKEN,")"},
        {SEMICOLON_TOKEN,";"},
        {EOF_TOKEN,""},
    };//테스트케이스 생성

    Lexer* lexer = New(input);
    //렉서를 만든후 분휴 시작

    int len = sizeof(tests) / sizeof(Token);

    for (int i = 0; i < len; i++) {
        Token* tok = NextToken(lexer);

        if (tok->type != tests[i].type) {
            printf("tests[%d] - tokentype wrong. expected = %s, got = %s\n", i,tests[i].type, tok->type);
        }

        if (strcmp(tok->literal, tests[i].literal) != 0) {
            printf("tests[%d] - literal wrong. expected = %s, got = %s\n", i, tests[i].literal, tok->literal);
        }

        printf("tests[%d]'s type = %s, literal = %s\n", i, tests[i].type, tok->literal);
        //free(tok->literal);
        free(tok);
    }

    free(lexer->input);
    free(lexer);
    //l은 input을 렉서해서 받아옴
    //받아온다면 tests랑 비교하기
}

결과

소스코드가 들어오면 이걸 "렉싱" 처리하여 토큰으로 만들어주고
이 토큰을 이용하여 트리를 만든다.

예를 들어 렉서는 let x = 5 + 5; 라는 명령이 들어온다면

[
    LET,
    IDENTIFIER('x'),
    EQUAL_SIGN,
    INTEGER(5),
    PLUS_SIGN,
    INTEGER(5),
    SEMICOLON
]

꼴로 토큰을 나눠서 만들어낸다.

오늘은 이 렉싱을 하는 렉서를 만들어본다.

토큰 정의

첫번째

TOKEN 헤더파일을 정의하자.
토큰 구조체를 만들고 토큰들을 상수 문자열로 만들어 둔다.

#pragma once

const char* ILLEGAL_TOKEN = "ILLEGAL_TOKEN";
const char* EOF_TOKEN = "EOF";
const char* IDENT_TOKEN = "IDENT";
const char* INT = "INT";

//연산자
const char* ASSIGN_TOKEN = "=";
const char* PLUS_TOKEN = "+";

//구분자
const char* COMMA_TOKEN = ",";
const char* SEMICOLON_TOKEN = ";";

const char* LPAREN_TOKEN = "(";
const char* RPAREN_TOKEN = ")";
const char* LBRACE_TOKEN = "{";
const char* RBRACE_TOKEN = "}";

//예약어
const char* FUNCTION_TOKEN = "FUNCTION";
const char* LET_TOKEN = "LET";

typedef const char* TokenType;

typedef struct _token {
    TokenType type;
    char* literal;
    //type은 enum으로 저장해 두다가 나중에 필요하면 TokenType으로 사용하고
    //literal은 어떤건지 특정하게 받아오는것 얘를 들어 5가 저장되고 이걸 INT로 나중에 토큰 타입으로 두기
}Token;

위 와같이 선언시에 ILLEGAL_TOKEN이(가) lexer.obj에 이미 정의되어 있습니다. 와 같은 오류들이 발생함

헤더가 여러 소스에서 선언되면서 선언이 중복되는 오류가 발생한다고 함

내가 헷갈렸던거는 pragma once가 있다면 이게 중복 선언을 방지한다고 배웠는데 왜 이런 오류가 발생하는 건지 헷갈렸음

하지만 pragma once는 a.c 라는 코드 내에서 같은 헤더가 여러번 선언 되는걸 방지해줄 뿐이지 b.c에서 또 헤더를 선언한다면 그건 그대로 포함시켜준다고 함

따라서 현재 헤더에서 변수가 여러번 정의 되는 문제가 생긴것

이를 해결하려면 static으로 선언하거나 extern을 쓰던가 매크로로 만들어야 한다고 해서 나는 매크로로 만듬.

변경본

#pragma once

#define ILLEGAL_TOKEN "ILLEGAL_TOKEN"
#define EOF_TOKEN "EOF"
#define IDENT_TOKEN "IDENT"
#define INT "INT"

// 연산자
#define ASSIGN_TOKEN "="
#define PLUS_TOKEN "+"

// 구분자
#define COMMA_TOKEN ","
#define SEMICOLON_TOKEN ";"

#define LPAREN_TOKEN "("
#define RPAREN_TOKEN ")"
#define LBRACE_TOKEN "{"
#define RBRACE_TOKEN "}"

// 예약어
#define FUNCTION_TOKEN "FUNCTION"
#define LET_TOKEN "LET"

typedef const char* TokenType;

typedef struct _token {
    TokenType type;
    char* literal;
    //literal은 어떤건지 특정하게 받아오는것 얘를 들어 5가 저장되고 이걸 INT로 나중에 토큰 타입으로 두기
}Token;

렉서

테스트 코드

#include<stdio.h>
#include "token.h"
#include "lexer.h"
#include<string.h>

int main() {
    const char* input = "=+(){},;";

    Token tests[] = {
        {ASSIGN_TOKEN,"="},
        {PLUS_TOKEN,"+"},
        {LPAREN_TOKEN,"("},
        {RPAREN_TOKEN,")"},
        {LBRACE_TOKEN,"{"},
        {RBRACE_TOKEN,"}"},
        {COMMA_TOKEN,","},
        {SEMICOLON_TOKEN,";"},
        {EOF_TOKEN,""}
    };//테스트케이스 생성

    Lexer* lexer = New(input);
    //렉서를 만든후 분휴 시작

    int len = sizeof(tests) / sizeof(Token);

    for (int i = 0; i < len; i++) {
        Token* tok = NextToken(lexer);

        if (tok->type != tests[i].type) {
            printf("tests[%d] - tokentype wrong. expected = %s, got = %d\n", i,tests[i].type, tok->type);
        }

        if (strcmp(tok->literal, tests[i].literal) != 0) {
            printf("tests[%d] - literal wrong. expected = %s, got = %s\n", i, tests[i].literal, tok->literal);
        }

        printf("tests[%d]'s type = %s, literal = %s\n", i, tests[i].type, tok->literal);
        //free(tok->literal);
        free(tok);
    }

    free(lexer->input);
    free(lexer);
    //l은 input을 렉서해서 받아옴
    //받아온다면 tests랑 비교하기
}

테스트 코드를 받아서
렉서를 통해 한 글자씩 돌린다음에 원하는 결과가 제대로 나왔는지 비교할것

하지만 아직 렉서가 없으니 렉서를 만들자

렉서

헤더

#pragma once
#include"token.h"

typedef struct _lexer {
    char* input;
    int position;//입력에서 현재 위치(현재 문자)
    int readPosition;//입력에서 현재 읽는 위치(현재 문자의 다음)
    char ch;//현재 조사하는 문자
}Lexer;

Lexer* New(char* input);
void readChar(Lexer* lexer);
Token* NextToken(Lexer* lexer);
Token* newToken(TokenType token,char *input);

인풋을 받으면 렉서를 만든다음에
한글자씩 읽으면서 알맞은 토큰 구조체를 생성해서 끼워넣을 계획

소스코드

#include "lexer.h"
#include<stdlib.h>
#include<stdio.h>
#include<string.h>

Lexer* New(char* input)
{
    //인풋 받으면 새롭게 Lexer 구조체 만들어서 input 저장해두는 함수
    Lexer* l = (Lexer*)malloc(sizeof(Lexer));

    l->input = _strdup(input);

    if (!l->input) {
        fprintf(stderr, "Memory allocation failed for input string\n");
        free(l);
        exit(EXIT_FAILURE);
    }//인풋이 없을때 오류메시지 생성과 종료

    l->ch = 0;
    l->position = 0;
    l->readPosition = 0;
    readChar(l);

    return l;
}

void readChar(Lexer* lexer)
{
    if (lexer->readPosition > strlen(lexer->input)){
        lexer->ch = 0;//참조를 넘어가면 ch에 0넣기
    }
    else {
        lexer->ch = lexer->input[lexer->readPosition];
    }

    lexer->position = lexer->readPosition;
    (lexer->readPosition)++;
    //미리 살펴보고 해도 되나 검사
    //또한 현재 문자를 일단 보관을 해야하니
}

Token* NextToken(Lexer* lexer)
{
    Token *tok=NULL;
    char lch = lexer->ch;

    switch (lch)
    {
    case '=':
        tok = newToken(ASSIGN_TOKEN, lch);
        break;
    case ';':
        tok = newToken(SEMICOLON_TOKEN, lch);
        break;
    case '(':
        tok = newToken(LPAREN_TOKEN, lch);
        break;
    case ')':
        tok = newToken(RPAREN_TOKEN, lch);
        break;
    case ',':
        tok = newToken(COMMA_TOKEN, lch);
        break;
    case '+':
        tok = newToken(PLUS_TOKEN, lch);
        break;
    case '{':
        tok = newToken(LBRACE_TOKEN, lch);
        break;
    case '}':
        tok = newToken(RBRACE_TOKEN, lch);
        break;
    case 0:
        tok = (Token*)malloc(sizeof(Token));

        if (tok == NULL) {
            printf("Memory allocation failed for tok.\n");
            exit(1); // 프로그램 종료
        }

        tok->type = EOF_TOKEN;
        tok->literal = _strdup("");
        break;
    }

    readChar(lexer);

    return tok;
}


Token*newToken(TokenType token, char* input)
{
    Token* newToken = (Token*)malloc(sizeof(Token));
    char* str = (char*)malloc(2);
    str[0] = input;  // 입력받은 char를 첫 번째 위치에 저장
    str[1] = '\0';   // 문자열 종료 문자 추가

    //토큰 받으면 input 받아서 리터럴 처리한후에 토큰 객체 돌려주기
    //newToken->literal = _strdup(TokenTypeNames[token]);
    //그냥 어차피 상수 포인터로 가르키기만 할건데 이렇게 해도 될듯...?
    newToken->type = token;
    newToken->literal = _strdup(str);
    return newToken;
}

이때 상수로 받아서 상수 포인터로 연결하면 
나중에 해당 상수가 사라졌을때 문제가 발생할수 있을거 같아서

_strdup을 통해서 복사해서 그만큼 할당해서 넣음

또한 newToken에서 받는 input은 아직은 char형 한 글자이기에 문자열로 바꿔서 저장해줌

테스트 결과

공익 활동도 시작에 취업이 걱정되기도 하고
컴공과로 들어왔는데 뭐라도 만들어야 하지 않나 하던중에
이 책이 눈에 들어옴

인터프리터 만들기 딱 봐도 재밌어 보여서 시작하기로 결정

인터프리터란

코드를 한줄씩 읽어가면서 번역하는 "프로그램"

코드를 한줄씩 읽어가며 기계어로 번역하기에 한번에 통째로 번역하는 컴파일러보단 느리다.
별도의 실행파일없이 해석과 동시에 실행이 된다.

대표적으로 파이썬, javascript 등이 존재한다.

프로그램 수정이 간단하며 오브젝트 파일을 만들지 않기 때문에 메모리 사용이 덜하다.

-> 개발자가 한줄씩 돌리며 어디서 문제가 났는지 바로 알수 있음

-> 왜 오브젝트 파일을써?? 어차피 그냥 링킹만 하면 되는데
대규모 프로젝트의 경우 각각 컴파일을 돌린후 오브젝트 파일로 만들어 두고
전체를 엮어서 링킹 하기 때문에 중간단계를 둠
매번 중간단계를 없애고 처리한다면 오버헤드가 발생하기 떄문

암튼...

일단 그렇다고 하고 너무 딥하지 않게 간단하게 책 따라가면서 만들어볼 생각

다 만든후에는 c++로 다시한번 만들어보거나 컴파일러를 만들어보자
이 책은 go언어로 쓰여있다는데 
처음에는 낯설다가 그냥 대충 뒤적여보니까 문법이 어느정도 이해가 되는듯

개요

송신 측 네트워크 계층에서는 트랜스포트 계층에서 받은 세그먼트를 데이터그램으로 캡슐화하고
데이터 그램을 인접한 라우터 R1에게 전송한다.

수신 측 에서는 데이터그램을 풀어 세그먼트를 트랜스포트 레이어로 올려보낸다.

각 라우터에는 데이터 평면은 입력 링크에서 출력 링크로 데이터그램을 전달하는 것이다.
네트워크 제어 평면은 수신 호스트에서 송신 호스트로 
잘 전달 되도록 로컬, 라우터별 포워딩을 대응시킨다.

간단히 말해 송신 호스트에서 수신 호스트로 패킷을 전달하는 역할을 하며
데이터 평면은 실제 전송을 네트워크 제어 평면은 네비게이션처럼 경로 설정을 한다 보면된다.

이를 위한 기능중 제일 중요한 두가지가 있다.

1. 포워딩
포워딩 테이블을 가지고 라우터 내에서 어느 경로로 보낼지 설정하는 역할을 한다.

2. 라우팅
어느 경로로 이동해야 할지 적절한 경로를 짜는 역할을 한다.

위 사진처럼 제어 평면에서 라우팅 알고리즘을 통해 포워딩 테이블을 만들어주면
데이터 평면에서 해당 포워딩 테이블을 통해 패킷을 뜯어본후 출력 포트에 배치 시킨다.

이때 포워딩 테이블을 만드는 방법에는 SDN과 라우터 별로 각자의 알고리즘을 가지고 있거나
여러 방법이 존재한다.

SDN

SDN은 하나의 제어 센터에서 모든 라우터 상황을 살핀뒤에 테이블을 만들어 배포하고
라우터는 포워딩 기능만을 수행한다.

라우터와 컨트롤러가 상호 작용하는 방식이며
기존의 방식 (각 라우터별로 라우팅 + 포워딩) 보다 더 높은 신뢰성을 가진다.

사용자들이 너무 빠르게 전송하려 할때 오히려 전체 전송량이 줄어드는 현상을 막기위한 방법

시나리오

위만 봐서는 뭔소린가 싶을테니 시나리오 별로 분석해보자

시나리오 1 : 무한 버퍼와 2개의 송신자

단일 홉을 공유하는 연결을 가진다고 해보자.
라우터를 공유하니 호스트 A와 B의 최대 전송률은 R/2가 될것이다.

만약 A와 B모두 전송률을 높여 R/2에 가깝게 전송한다면
무한 버퍼이니 큐잉 딜레이의 크기가 기하급수적으로 늘것이다.

시나리오 2 : 2개의 송신자, 유한버퍼 하나의 라우터

위 상황에서 버퍼가 유한하다면 큐잉 딜레이가 커지다가
패킷들이 버려지게 될것이다.

송신자는 버려진 패킷에 대해서 다시 전송을 하게 된다.
이는 전체 전송률을 낮추게 된다.
-> 전체 보낸 패킷(수신자가 받은)/총 RTT가 전송률인데
수신자가 받는 패킷의 양은 그대로인데 재전송으로 인해 시간이 손실나기 때문이다.

위 사진과 같이 전송률이 커질수록 실제 데이터 throughput은 감소할것이다.

시나리오 3 : 4개의 송신자 유한 버퍼 라우터들, 멀티홉

최악의 시나리오로 가정해보자

A->C, D->B를 보내다가 북쪽의 라우터가 막혔다.
이때 기가막히게 D->B로 보내는 패킷들만 손실이 나고 A->C는 무사히 통과했다고 해보자

잘 가다가 동쪽의 라우터에서 같은 현상이 벌어져서 이번에는 A에서 보낸 패킷만 막혔다.

이같은 현상이 계속 발생해서 동서남북 모든 라우터가 큐잉딜레이가 심하게 걸린다면
모든 라우터들은 재전송만 반복하게 될것이고 
실제 throuhgput은 0에 수렴하게 된다.

각 사용자가 최선을 다하기 위해서 속도를 높였는데 결국 전체 시스템이 죽어버리는 현상이 발생한것이다.

이를 막기 위해서 혼잡제어가 필요하다.

혼잡제어

혼잡제어는 네트워크에서 위같은 상황이 발생하면 얼른 풀어버린다.
라는 접근 방식이다.

전통적인 TCP의 혼잡제어를 알아보자

전통 TCP

네트워크의 혼잡에 따라 연결에 트래픽을 보내는 전송률을 각 송신자가 제한하도록 한다.

TCP 송신자가 자신과 목적지 간의 경로에서 혼잡이 없음을 감지 → 송신율을 높인다.
TCP 송신자가 경로 사이에 혼잡을 감지 → 송신율을 줄인다.

이때 혼잡 윈도우를 통해 혼잡 제어를 하며 이 혼잡 윈도우 (cwnd)는
LastByteSent - LastByteAcked <= min{cwnd,rwnd} 값을 유지해야한다.

cwnd는 한번에 전송하는 패킷의 양을 조절하게 되므로 throughput = cwnd/RTT 가 될것이다.

손실이벤트가 발견되면 cwnd를 줄이게 되는데 손실이벤트는 다음과 같이 정의된다.

* 세그먼트가 손실이 나면 혼잡한거다.
즉, 
1. ACK를 3번 연속 받거나
2. 타임아웃이 걸리거나

둘중 하나라면 TCP는 네트워크의 상태가 혼잡하다고 판단하고 cwnd를 조절한다.

슬로우 스타트

TCP 연결이 시작되면 cwnd = 1MSS로 설정되며 빠르게 증가시킨다.
보낸 패킷에 대해 ACK응답이 하나 올때마다 cwnd를 하나씩 증가시키며
이는 cwnd를 지수적으로 증가시키는 결과를 가져온다.

이렇게 계속 보내다가 패킷이 손실이 난다면 cwnd =1 MSS로 다시 설정하고
ssthresh = cwnd/2 로 설정한다.

다시 슬로우 스타트 모드로 증가시키다가 cwnd == ssthresh 값이 된다면 혼잡 회피 상태로 들어가
조심스럽게 증가시키게 된다.

혼잡 회피

혼잡 회피에서는 매우 조심스럽게 cwnd를 증가시킨다.
앞에서는 한 패킷의 ACK당 하나씩 증가시켰다면

여기서는 모든 cwnd 양만큼의 ACK가 와야 1만큼 증가시킨다.

즉, cwnd = 4라면 ACK가 4개 와야 cwnd ++ 를 한다.
이렇게 계속 올리다가 또 혼잡 상태가 관측되면 ssthresh = cwnd/2로 바꾸고 다시 슬로우 스타트를 한다.

빠른 회복

TCP 리노에서 사용되는 방법이다. 
위 두 방법은 TCP 타호에서 사용하던 방법이고 리노는 빠른 회복 방법 또한 선택했다.

이 방법은 time-out이 아니라 3 ACK 가 왔을때 선택한다.
이 경우 그래도 timeout된거보다는 아직 괜찮다고 판단하여 혼잡상태가 발생했을때
ssthresh = cwnd/2로 cwnd = 손실시 cwnd/2 +3 으로 설정한다.

사진에서의 예를 보면 12에서 손실이 발생했고
타호는 바로 1로 가는 반면 리노는 9(6+3)으로 cwnd를 설정한후 혼잡회피 상태로 들어선다.

한기대 박기호 교수님의 설명으로는
TCP 리노에서 cwnd 설정후 손실난 패킷을 재전송하며 이때 정상적으로 재전송 된다면
다시 cwnd를 낮춰서 보낸다고 하는데
교재에서는 설명이 생략됬으니 나도 그냥 넘어간다.

AIMD

혼잡제어에서 가법적 증가를 하고 손실 발생시 승법적 감소를 하여
AIMD라고 한다.

늘릴때는 조금씩 내릴때는 확

TCP Qubic

야 어차피 저기 손실난구간까지 가야 뭐 날거같은데 걍 저기까진 빨리올리고
근처 가면 천천히 상황보죠? 라는 의미

리노는 선형적으로 올렸지만 큐빅은 이전에 문제가 생긴구간까지 빠르게 증가시킨후
그다음부터 천천히 증가시키면서 더 효율적으로 사용하는것이다.

리눅스 운영체제에서 사용되는 버전이다. 웹서버의 50%가 큐빅 사용중이기도 하다.

네트워크 지원 명시적 혼잡알람

TCP는 혼잡상황을 알지 못하고 종단에서 결과만 보고 알아차려야했다.
이게 별로라서 네트워크에서 혼잡이 생기면 라우터가 혼잡하다는 걸 직접 알려주게 하자

혼잡 해진다면 IP 데이터그램속 (라우터가 꺼내볼수있음) ECN 필드를 11로 킨다(2비트임)
수신자가 해당 ECN 비트를 보고 혼잡한 상태임을 알게되고
이를 다시 ECN 에코 비트를 설정하여 TCP ACK를 보낸다.

수신자 또한 혼잡 상태를 알게 되고 빠른 재전송을 사용하여 혼잡윈도 줄이고 CWR 비트를 1로 설정한다.

공평성

만약 A 호스트가 전송을 하고 있고 B는 이제막 들어왔다고 해보자

A는 cwnd가 커져있을테지만 B는 이제 1인데 이게 공평해지나???

요약하자면 증가할때는 비슷한 한계까지 증가하며
감소할때는 1/2로 감소 하는 행위를 반복하기에 결국 비슷비슷해진다.

UDP

UDP 에서는 공평? 그딴거 우리는 모른다 일단 빨리 갔다놓고 잃어버리거나 오류나면 뭐 알아서 하슈...

QUIC

TCP는 연결하는데도 시간걸리고  TLS 연결도 또하고 하니까
UDP의 빠른 전송을 기반으로 어플리케이션 레이어에서 알아서 보안등을 처리하게 하자
하는게 QUIC에서는 보안 연결까지 한번에 연결하고 처리하기에 더욱 빠르다.

각 호스트 끼리는 버퍼에 데이터를 보내둔다.
하지만 이떄 어플리케이션은 바로바로 버퍼의 데이터를 꺼내 사용하지 않는다.
어플리케이션은 자신이 하던일을 하고 필요한 시점에 버퍼에서 데이터를 꺼내 사용하며
사용치 않을때는 버퍼에 데이터가 계속 쌓인다.

만약 버퍼의 사이즈를 넘어서는 데이터가 오면 어떻게 될까??
이때 버퍼에 저장되지 못하고 넘치는 데이터는 버려질 것이므로 우리는 이에대한 해결책이 필요하다.


이를 위해 TCP는 흐름제어 서비스를 제공한다.

Flow control

TCP는 receive window를 통하여 가용버퍼가 얼만큼 남았는지 사용자에게 알려준다.

전송 예시와 같이 살펴보면

만약 호스트 A가 B에게 데이터를 전송한다면 B는 이 연결에 수신 버퍼를 할당한다.
이 크기를 RcvBuffer라 한다.

B가 버퍼로 부터 데이터를 읽으며 다음과 같은 변수를 정의한다.
LastByteRead : B의 어플리케이션 프로세스가 버퍼에서 읽은 데이터 스트림의 마지막 바이트 
LastByteRcvd : B의 수신 버퍼에 도착한 데이터 스트림의 마지막 바이트

요약하자면 LastByteRead는 버퍼에서 읽어온 양
LastByteRcvd 는 버퍼에 들어온양 이라 보면 되며

RcvdBuffer>= LastByteRcvd - LastByteRead 여야 오버플로우가 발생치 않는다.

따라서 Rwnd(플로우 컨트롤을 위한 버퍼 크기 윈도우)는 RcvdBuffer- (LastByteRcvd - LastByteRead) 이며 0보다 커야한다.

호스트 A에서도 비슷한 상수를 가지는데 LastByteSent와 LastByteAcked를 가지며
LastByteSent - LastByteAcked <= Rwnd (보낸양<= 윈도우)여야한다.

한가지 문제가 있는데,
만약 rwnd =0 으로 가득 찼다는 신호를 보내게 된다면 
호스트 A는 B에게 데이터를 전송하지 못하게 되며 

그렇다면 B또한 A에게 응답을 하지 않으니 rwnd가 남더라도 알려줄 방법이 없다.

이를 방지하기 위해 rwnd가 비더라도 1바이트 데이터를 통해 rwnd가 비었는지 찼는지를 계속 통신하게 된다.

TCP 연결

<연결>
1. 클라이언트는 서버에서 SYN 세그먼트를 전송한다.
 - 이때 세그먼트에는 임의의 seq 번호가 할당된다.
 - SYN = 1 로 전송된다.

2. 서버는 클라이언트의 요청을 확인한후 SYNACK를 전송한다.
 - 이때 SYN비트를 1로 만들며 연결에 필요한 TCP 버퍼와 변수등을 할당한다.
 - 자신의 seq를 임의로 할당하며 ACK는 cli_seq+1로 돌려준다.

3. 연결에 버퍼와 변수를 할당하며 또 다른 세그먼트를 전송한다.
 - 이때 SYN = 0이 되며 
   이 경우에만 클라이언트에서 전송한 페이로드를 어플리케이션 레벨에 올릴수 있다.

<연결 종료>
1. 클라이언트가 서버에게 FIN 비트를 설정후 전송한다.
 -> ACK를 받는다.

2. 서버 또한 클라이언트에서 FIN 비트를 설정한후 전송한다.
 -> ACK 를 받고 서로 연결 종료

TCP는 연결 지향형 프로토콜이다.
하지만 이 연결은 TDM 과 같은 실제 연결이 아닌
종단 시스템에서만 동작하는 "논리적" 연결이다.

TCP 연결은 '전이중 서비스'를 제공하는데 만약 A와 B 사이의 연결이 있다면
데이터가 A->B 로 흐르는 동시에 B->A로도 흐를수가 있다.

연결과정

클라이언트가 소켓을 통하여 데이터를 트랜스포트 계층으로 밀어넣으면
클라이언트의 트랜스포트 계층에서는 데이터를 mutiplexing 한다.

그런후 three-way hanshaking 을 통하여 서버의 프로세스와 연결을 맺고 데이터를 전송하기 시작한다.

이때 three-way hanshaking 중간에 송신 버퍼에 보낼 데이터를 미리 싫어 놓으며
어떤 경우에는 데이터 묶음을 만들어 네트워크로 보내기도 한다.

이는 RFC 793에서 "TCP가 자신이 편한대로 세그먼트의 데이터를 보낸다"고 명시되어 있기에 가능하다.

MSS(maximum segment size)

어플리케이션 계층에서 넘어온 데이터를 세그먼트화 할때 크기의 제한이 있다.
이를 우리는 MSS라고 부른다. 이는 일반적으로 로컬 송신 호스트에 의해 전송될수 있는
가장 큰 링크 계층 프레임의 길이(MTU)에 의해 결정된다.

TCP 세그먼트 + TCP/IP 헤더(통상 40bytes) = MTU가 되어야하며
통상적으로 이더넷에서는 MTU가 1500bytes이기에 MSS=1460bytes이다.

ACK와 sequence num

앞선 rdt에서는 순서번호는 0,1 또는 패킷마다 붙여줬다.
하지만 TCP에서는 전체 데이터를 MSS 단위로 자른후 바이트 번호로 붙여준다.

다음과 같은 파일이 있고 MSS=1000이라면 1번째 세그먼트는 0~999바이트까지
2번째는 1000~1999바이트까지 가지고 있다.

이때 seq num은 세그먼트의 첫번째 바이트인 0, 1000, 2000으로 붙여진다.
통신 과정에서 첫번째 세그먼트를 정상적으로 받고 ACK를 보낼때 
다음에 받아야할 세그먼트의 첫 바이트인 ACK 1000을 전송한다.

만약 모종의 이유로 seq0인 세그먼트와 seq2000인 세그먼트만 받았다면
seq 2000인 세그먼트는 버퍼링 한후에 ack 1000을 보낸다. (GBN과 유사)

***
특이점으로는 정상적으로 받은후 500ms 대기후에 ack를 전송하는데
이 과정에서 다음 정상 순서의 segment가 온다면 바로 ack 2000을 전송한다.

누적 응답이기에 ack n 이 온다면 n-1 바이트까지는 완전히 정상 전송 됬다고 생각하면 된다.

예시

텔넷의 예를 보자

서버에 C데이터를 요구하면 클라이언트는 제대로 받았다는 신호와 자신의 seq를 보낸다.
제대로 전달 받으면 seq=43,ACK=80 을 전송한다.

왜 3-way handshake?

만약 2방향이면 어떻게 될까???

클라이언트가 서버에게 요청신호를 보내고 한참을 기다렸는데 서버의 응답이 오지않았다.
클라이언트는 다시한번 서버에게 요청신호를 보냈다.

하지만 이때 서버에서 연결 신호가 뒤늦게 온다면?
클라이언트는 이 응답이 내가 처음에 보낸것에 대한 응답인지
다시 보낸 것에 대한 응답인지 알수가 없으며

서버는 뒤늦게 요청을 한번 더 받고 다시 연결을 만들것이다.

이런 경우에 낭비가 발생할수 있기에 우리는 3-way를 쓴다.

클라이언트는 SYNbit=1 로 만들고 임의의 seq를 서버에게 전달한다.
서버는 해당 패킷을 받고 SYNbit=1과 ACKbit=1 로 만든뒤에 응답하고
클라이언트가 다시 이 응답을 잘 받았다고 돌려준다.

이를통해 위에서 발생한 문제를 해결 가능하다.

RTT 예측

RTT를 계산하는 이유는 다음과 같다.
우리는 '일정 수준' 이상으로 ACK가 오지않으면 아 손실이 됬구나를 알아차리는데
이 '일정 수준'을 RTT보다 크게 둬야 하기 때문이다.

하지만 RTT는 네트워크 상태나 패킷의 크기등에 영향을 받기 때문에 완벽하게 알수는 없고
수식을 통해 근사치를 예측한다.

아래 사진은 실제 샘플과 예측 RTT의 값이다.

EstimatedRTT = (1 - α) × EstimatedRTT + α × SampleRTT (권장되는 α의 값 : 0.125)

여기에 어느정도 여유를 둬서 계산하며 편차를 더해야한다. 편차는 다음과 같이 구한다.

DevRTT = (1 - β) × DevRTT + β × | SampleRTT - EstimatedRTT | (권장되는 β의 값 : 0.25)

최종 식은 다음과 같다.

TimeoutInterval = EstimatedRTT + 4 × DevRTT

신뢰적인 데이터 전송

💡 TCP는 IP의 비신뢰적인 최선형 서비스에서 
신뢰적인 데이터 전송 서비스(reliable data transfer service)를 제공한다.

즉, 데이터가 손상되지 않았음을 보장하며
중복이 없음과 순서의 유지를 보장해줘야한다.

이를 위해서 타이머를 사용하는데 모든 세그먼트에 타이머를 세팅하는 것은 큰 오버헤드를 발생시킨다.

따라서 TCP는 하나의 타이머만을 두며 ACK를 받지 못한 세그먼트들중 가장 오래된 세그먼트를 추적한다.
이때 타이머의 deadline은 앞서 살펴본 TimeoutInterval이다.

TCP의 주요한 3가지 이벤트

1. 상위 어플리케이션으로 부터 데이터 수신

- TCP는 소켓을 통해 어플리케이션에서 데이터를 받는다.
- mutiplexing을 통하여 세그먼트로 캡슐화한다.
- IP에게 세그먼트를 넘긴다.

의 과정을 거쳐 처리한다.

이때 타이머가 돌아가고 있지 않다면 해당 세그먼트에 대해서 타이머를 실행시킨다.


2. 타임아웃

- 타임아웃이 발생한다면 세그먼트를 재전송하며 해당 세그먼트에 대해서 타이머를 다시 설정한다.


3. ACK 수신

SendBase : 수신 확인응답이 확인되지 않은 / 가장 오래된 바이트의 순서번호
SendBase-1 : 수신자에게서 정확하게 차례대로 수신되었음을 알리는 마지막 바이트의 순서번호

y(받은 ACK) > SendBase이면, ACK는 이전에 확인응답 안 된 하나 이상의 세그먼트들을 확인해준다.

송신자는 자신의 SendBase 변수를 갱신한다.
아직 확인응답 안 된 세그먼트들이 존재한다면 타이머를 다시 시작한다.

몇가지 시나리오

TCP 프로토콜이 어떻게 작동하는지 몇가지 시나리오를 통해 알아보자

1.  ACK가 손실 됬을때
B는 이미 제대로된 데이터를 보냈지만 ACK 100이 손상이 되 A가 재전송을 한 상황이다.
이때 B는 이미 받은 세그먼트 이기에 ACK100을 다시 보내고 A가 보낸 메시지를 버린다.

2. ACK 100만 손실됬을때
2개의 세그먼트를 보냈고 타임아웃이 발생해 재전송을 하는 상황이다.
이때 TCP는 가장 오래된 세그먼트인 seq 92 만 전송할것이고
B는 자신은 이미 119까지는 정상 수신하였기에 ACK 120만 보낼것이다.

3. ACK 100이 손실났지만 누적 응답이 왔을경우
이전 세그먼트에 대한 ACK가 손실이 되어 못왔지만 다음 세그먼트에 대한 ACK가 온다면
TCP는 누적 응답이기에 ACK120이 왔다는건 119까지는 제대로 받았다는 뜻이여서
문제없이 다음 세그먼트를 보내게 된다.

타임아웃 주기 2배

만약 타임아웃이 발생한다면 TCP는 이전 인터벌의 2배를 준다.
타임 아웃이 발생한것은 뒤에서 살펴볼 혼잡 상태 일 가능성이 높고
이를 해결하기위해 시간을 넉넉히 준다.

그 다음부터는 다시 인터벌을 계산하여 처리한다.

빠른 재전송

Time-out 주기는 RTT 보다 길다. 그렇기에 오래걸리며 비효율적이다.
따라서 TCP는 재전송을 위한 또 한가지의 방법을 쓴다.

중복된 ACK가 3번 이상온다면 세그먼트가 정상적으로 전송이 안되었다고 생각하고 바로 재전송해주는 것이다.

GBN이냐 SR이냐

TCP는 GBN의 누적응답과 SR의 버퍼링을 모두 가지고 있다.
따라서 어느 한 방법이라하기 보다는 혼합형이라 보는것이 적당할 것이다.

rdt 3.0의 가장큰 문제점 -> stop-and-wait 프로토콜이라는 점

즉, 하나의 패킷보내고 오류 처리 다하고 나서 다음 패킷보내는 방식이다.
듣기만해도 어마어마하게 늦을거 같지않은가...
얼마나 비효율적인지 계산해보자

1 Gbps전송률(R)을 가진 채널로 두 호스트가 연결되어있고 RTT는 30ms라 하자
헤더필드와 데이터를 모두 포함해서 패킷당 1000bytes의 패킷크기(L)을 가지고 
1Gbps 링크를 통과하는데 걸리는 시간은 8마이크로초이다.

송신때 0.5 RTT + 8마이크로초
수신때 0.5 RTT면 총 시간은 30.008 ms 인데 데이터 전송시간은 0.008ms이다.
즉, 이용률은 0.00027이라는 끔직한 이용률이 나온다.

잘 이해가 안된다면 1Gbps 짜리 네트워크를 쓰는데 267 kbps만 이용가능하다.
참고로 유튜브 240p 짜리 영상이 300kbps~700kbps 정도 된다.

이런 문제 때문에 대두된것이 파이프라이닝!

사진처럼 3개의 패킷을 연달아 전송시키면 RTT(첫 패킷전송 응답 까지 걸리는시간) 동일하나
그 사이에 3개의 패킷을 전송했다. 
즉, 송신자의 이용률(같은 시간내에 얼마나 보내냐)는 3배 증가함을 알수있다.

위 같은 방법을 이용하기 위해서는 다음과 같은 조건들이 필요하다.

1. 순서는 유일하게 가진다. (rdt 처럼 0,1을 쓰다가는 순서를 파악할수없음)
2. 송신과 수신측은 패킷을 버퍼링 해야한다.
3. 오류회복 기능을 버퍼링과 순서 번호의 범위등을 고려하여 만들어야한다. (GBN,SR 등이 존재)

GBN (Go-Back-N)

GBN은 파이프라이닝의 방법중 하나이다.
ACK를 기다리지않고 여러 패킷을 보내는 방식이다.
특정한 윈도우를 가지고 있으며 윈도우 안의 패킷만을 관리, 사용한다.

이전에 전송했던 패킷의 올바른 ACK응답이 온다면 한칸 옆으로 윈도우가 이동하며
이때문에 슬라이딩 윈도우 프로토콜(sliding-window protocol) 이라고도 불린다.

특징은 다음과 같다.

올바른 순서대로 패킷이 오지않으면 (순서대로)
순서에 맞지 않는 패킷은 다버린다.

FSM를 보며 살펴보자

sender

상위 프로토콜에서 접근한다

rdt_send(data) 실행

if(nextseqnum<base + N) -> 윈도우안에 사용가능한 패킷이 존재한다면
패킷만들어서 전송

    if(base==nextseqnum) -> 전송후 보니 방금 보낸 패킷이 윈도우의 첫 패킷이면
        start_timer
    nestseqnum++
else (윈도우에 사용가능 패킷없으면)
 전송불가


timeout
-> 타이머 다시 시작
지금까지 보냈던 패킷 전부 다시전송


rdt_rcv(rcvpkt)&&notcorrupt(rcvpkt) -> 리시버한테 응답 받았고 오류없으면
base 하나증가

if(base == nextseqnum) -> 만약 베이스가 새로보내야할 패킷이라면
    타이머 중지
else
    타이머 초기화


red_rcv(rcvpkt)
    && corrupt(rcvpkt) -> 만약 잘못된 값 즉, 이미 보낸 패킷의 ACK가 안오면 계속 대기

receiver

defalut
이전에 만들었던 ACK 계속전송

rdt_rcv(rcvpkt)&&notcurrupt(rcvpkt)&&hasseqnum(rcvpkt,expectedseqnum)
-> 패킷 이상없고 내가 원하던 패킷순서면

새로 ACK 해당 순서에 맞게 만들어서 전송

** 만약 패킷문제있다면
default가 실행됨

둘을 합친다면 위그림과 같다.

sender는 윈도우 내에서 계속 패킷을 보내고
receiver는 원하는 순서인지 확인후 아니라면 순서맞게 보내라고 ACK 반복
타임아웃되면 이전에 보냈던 패킷 다시 전부전송

<장점>
단순하다

<단점>
비효율적이다.
만약 많은 패킷이 윈도우 안에 꽉차있고 오류가 발생한다면 상당히 많은수의 패킷을 재전송해야함


*** 주의 : GBN에서 시퀀스 넘버는 바이트가 아닌 단순 패킷의 번호임

SR (seletive-repeat)

선택 반복 프로토콜이다.
앞선 GBN의 방식은 올바른 순서로 올때만 ACK를 보내고 그렇지 않다면 패킷을 버리는 방식이였다면

SR방식은 순서에 맞지 않더라도 올바른 패킷이 온다면 ACK를 보내고 버퍼에 저장해둔다.
이때 sender 또한 순서에 맞지 않더라도 ACK를 받으면 ACK를 받았다고 표시한다.

만약 한 패킷이 타임아웃 된다면 (이때 각패킷별로 타이머가 관리되어야함)
재전송하고 이 패킷이 receiver측의 윈도우 밖에 있을수도 있다.
그럼에도 receiver는 다시한번 ACK를 전송해줘야한다.

버퍼에 쌓아뒀던 패킷들중 비는 부분이 없이 맞춰진다면 해당 부분을 상위 프로토콜로 올린뒤
ACK를 전송한다.
ex) 2 4 5 가 버퍼에 있다가 3을 받으면 2 3 4 5 전부 Demultiplexing 후 ACK 3

UDP는 데이터의 오류가 발생했는지 체크만 해준다.
(왜 체크만 해주냐? 확인해서 어플리케이션에서 알아서 하라고 이름부터 User Datagram 인 이유가 있다.)

checksum은 16비트로 구성되어있다.
방식은 DATA를 16비트로 쪼갠뒤 모든 16비트 값을 더한다.

캐리가 나온것은 맨뒤에 다시 더한후 1의 보수를 취한다.
이를 우리는 checksum이라 한다.

패킷이 오류가 없다고 수신자에서의 합은 FFFF가 될것이고 FFFF가 아니라면 오류가 발생한 것이다.

다만 특정한 경우 오류가 발생했음에도 checksum이 그대로인 경우가 있을수도 있다.
무조건 오류 검출이 아님

TCP의 신뢰적인 데이터 전송

앞에 IP는 데이터의 신뢰도를 보장해주지 않았다.
하지만 TCP는 데이터의 신뢰도를 보장해 주어야한다. 
어떻게 가능한 것일까???

이를 위해 우리는 문제상황을 추상화 시킨후
점진적으로 완전한 신뢰적인 데이터 전송 프로토콜에 도달하기위해 구체화 한다.

rdt 1.0

if : sender와 receiver가 신뢰성 있는 연결을 통해 데이터를 전송한다고 가정할때

sender : 패킷을 만들어 보낸다. (다중화)
receiver : 패킷을 받으면 풀어서 전달한다. (역다중화)

단순히 위과정만 반복하면 된다.

rdt 2.0

if : 비트 오류가 발생하는 상황이라면?

비트 오류를 검출하는 기능을 추가해야한다.
이를 위해 3가지 과정이 요구된다.

1. 오류 검출 (checksum 활용)
2. 수신자 피드백 (ACK/NAK로 구분 정상인지 아닌지 구분)
3. 재전송 (오류난 패킷 다시전송)

sender
1. 데이터 전송
2. 사용자 피드백을 기다림
3.1. NAK를 받으면 다시 패킷전송
3.2. ACK를 받으면 다시 대기상태

receiver
1. 패킷 도달시 오류있는지 확인
2.1. 오류가 있다면 NAK전송
2.2. 오류가 없다면 ACK전송 하고 data 전달

rdt 2.1

if : 야 근데 ACK/NAK도 오류나면 어떡해?

해결방안은 간단하게 "그냥 다시보내면 안돼?" 이다.

이때 문제가 생기는 것은 난 정상적으로 받아서 ACK보냈는데 다시 같은 패킷이 온다면?
수신자는 난 정상적으로 받아서 다음 데이터 기다리는데 이전 데이터가 온다면
어떻게 처리해야하며 왜 이것이 온지 구분하기도 힘들다.

이것을 해결하기 위해 순서(sequence)를 둔다.
순서를 전부 다 쓰면 오버헤드가 너무 커지니 flag bit를 둬서 0과 1로 이전과 현재를 구분하게한다.

구분선기준 윗부분을 설명하자면

sender
1. 시작시 (순서,data,체크썸)을 전송한다.
2.1 만약 NAK가 오거나 받은 데이터 비트의 오류가 난다면 다시 보내고 기다린다.
2.2 모든게 정상이라면 넘어감

receiver
1. 0기다리다가 데이터가 들어오면 문제없고 시퀀스 맞으면 1대기로 넘어간다.
   이때 ACK전송 및  체크썸 전달 후 1 시퀀스 대기로 이동

2.1. 1 시퀀스 받았는데 오류나면 NAK와 chksum보내고 (NAK가 오류났는지 다시확인하기 위해서)
     기다린다.
2.2. 제대로 오긴했는데 이전 시퀀스(0)면 ACK 보내줌
-> 이전에 내가 보낸 ACK 문제생겨서 다시 온거니까 ㅇㅋ 해주고 버리면됌

이 과정을 반복한다.

밑과정도 동일

rdt 2.2

>> 어차피 ACK 이전꺼오면 제대로 답변 못받은건데 걍 NAK없애고 통일하죠?

오..?

sender
- 어차피 비트손실 또는 이전 시퀀스 ACK가 온다면 다시 보내줌

receiver
- 문제가 생겼으면 이전 시퀀스 ACK 전송
- 또는 이전 패킷 보내주면 아 내가 보낸 이전 ACK 문제생겼구나? 하고 ACK 전송
  이때 Sender는 S1 대기중이므로 ACK 다시받고 S2로 넘어갈거임


<요약>
sender가 이전 seq ACK받는건 무조건 내가 보낸거 오류니까 다시 보내줘라
receiver는 오류나면 이전 ACK 보내고
내가 보낸 ACK 문제생기면 이전 seq 패킷오니까 알아서 잘 버려라

다른부분은 rdt 2.1과 동일하다고 보면됌

번외편 : checksum에도 오류가 나면 어쩔건데...?

패킷에 checksum을 보내고 이를 통해서 오류를 검출한다고 했는데
만약에 checksum또한 오류가 나면 어쩔건데...?

이럴경우에도 TCP가 신뢰도있는 데이터 전송을 한다고 말을 할수가 있는가

1. checksum만 오류가 난다면?
-> 어차피 합이 FFFF가 아니라 오류

2. checksum과 패킷 둘다 오류난다면?
-> FFFF나올 확률이 매우 낮음

3. 단 이를 뚫고 매우 가끔 데이터 손실이 났음에도 FFFF가 오기도함

https://networkengineering.stackexchange.com/questions/44807/can-the-checksum-bits-be-corrupted
참고

rdt 3.0

if : 야 근데 패킷자체가 사라지면 어떡해???

>>> 특정시간이 지나도 안온다면 패킷 사라진거로 하죠?

>>> 그냥 느려서 늦게온것도??

>>> ㅇㅇ

sender

1. 대기하다가 실행시에 전송후 타이머 재기

2.1. ACK(1) 즉 NAK오면 무시(어차피 타이머 지나면 재전송이니)
2.2. 시간 지나면 재전송해주고 타이머 초기화

3. 제대로 답변오면 타이머 정지

위와 같은 4개의 케이스가 나올수 있다.

중요한건 (d) 처럼 타이머가 너무 짧으면 제대로 받았는데도 재전송하고
너무 길면 또 네트워크 지연이니 문제다.

65535개 (16바이트)
극단적인 경우에 모든 포트를 한 프로세스에게 할당시켜줄수 있음

소켓

소켓을 프로세스간 데이터 통신을 위한 "문" 이라고 설명했는데 이때문에 약간 헷갈렸음
IP는 host(인터넷에 접속중인 컴퓨터)의 주소이며, port는 프로세스에게 할당된 식별자임.

특정한 서버의 특정 프로세스에 접근하기 위해서 IP와 port가 필요하며 
이 한 쌍은 모든 인터넷 내에서 "유일"하게 존재한다.

이 조합을 우리는 소켓이라 부른다. 즉, 소켓이란 IP와 port의 조합인 셈.
문이라기 보다는 주소와 동호수 라고 생각하자.

커넥션(TCP에서)

TCP는 연결 지향적인 프로토콜이기에 connection이 존재한다.
connection에는 client의 소켓과 server의 소켓이 연결되는 것이며
이때 이 한쌍의 소켓이 가진 정보를 통해 connection의 식별자를 만들수 있다.

또한 한 소켓은 여러 커넥션을 만들어 낼수 있다.

UDP에서는?

UDP는 연결 지향적이지 않다.
심지어 RFC 768에서는 socket이라는 말 조차 등장하지 않았다.
아마도 TCP connection을 위해 사용했다가 나중에 UDP에도 들어온게 아닐까?

아무튼 이때문에 socket에는 <protocol,Ip address, port> 의 정보가 존재한다.

둘 이상의 프로세스가 같은 포트 번호를 사용가능하냐?

불가능하다. socket의 값이 모두 같은 socket은 존재해선 안된다(하나만 있어야함)
따라서 같은 프로세스가 한 포트를 쓰는것은 불가능하다.
하지만 프로토콜이 다르다면 가능하다.

한 포트번호에 여러 사용자가 접근 가능한가?

가능하다. 
한 socket이 여러 connection을 가질수 있냐라는 의미인데 이것은 위에서 가능하다고 했다.
또한 socket은 도구 등이 아닌 Ip+port의 조합이므로 포트만 동일하다면 모두 동일한 프로세스에 접근하며
UDP의 경우 어플리케이션 레이어(OSI 7에선 세션레이어)에서 처리에 대한 규칙을 지정해 줘야한다.
(ex. 멀티 스레딩 등)

어차피 socket은 주소의 역할이고 어떤 정보를 요구하고 어디로 보내야 하는지는 패킷의 헤더에 붙어오니
그것만 읽어서 처리해주면 됌
TCP의 경우에는 connection을 통해서이고 UDP는 알아서 잘 하면 되고

참고자료 https://lostbyte.org/can-udp-and-tcp-use-the-same-port/ https://medium.com/fantageek/understanding-socket-and-port-in-tcp-2213dc2e9b0c https://stackoverflow.com/questions/3329641/how-do-multiple-clients-connect-simultaneously-to-one-port-say-80-on-a-server

각기 다른 호스트에서 동작하는 프로세스간의 논리적 통신 지원

IP주소는 호스트의 주소를 나타낸다. 하지만 한 컴퓨터 내에서 다양한 프로세스가 작동하기에
이 프로세스들을 구분하기 위해서 PORT 번호를 사용하여 프로세스마다 할당해준다.

이를 통해 호스트간의 직접적인(그렇게 보이는) 통신이 가능.

🗂️ 네트워크 레이어

"호스트" 간의 논리적 통신 지원

조금 헷갈리지만 네트워크 레이어는 호스트 까지만 전달을 해주고 
이를 받아서 트랜스포트 레이어에서 각 프로세스에게 전달해준다는 것

배달부가 부대까지 배달해주면 분대장이 각 사람에게 편지를 나눠주는 그런 느낌

📁 특징?

트랜스포트 레이어는 하위레이어인 네트워크 레이어의 영향을 받는다.
예를 들어 네트워크 레이어가 전송 기간을 보장해주지 못한다면 (편지가 언제 배송완료 되는지 모른다면)
트랜스포트 레이어도 전송 기간을 보장해주지 못한다.

네트워크 레이어에서 제공치 않는 기능을 제공하기도 한다.
네트워크 레이어에서는 보안기능이 없더라도 트랜스포트 레이어에서는 보안 기능이 추가될수 있다.

📁 IP(인터넷 프로토콜)

IP는 unrelㅑable한 프로토콜임
데이터의 로스나 순서를 보장해주지 않는다.

이때문에 트랜스포트 레이어는 데이터의 로스나 순서를 맞춰줘야 하거나(TCP)
그대로 쓰거나 둘중 하나를 선택해야함(UDP)

📁 다중화/역다중화

트랜스포트 레이어는 어플리케이션 레이어에서 소켓을 통해 메시지를 받고
이것을 다시 세그먼트(UDP에서는 데이터그램)으로 나눈후 네트워크 레이어로 보낸다.
-> 이를 다중화라고 한다. 이때 출발 포트, 도착 포트, 그밖에 헤더들을 덧붙인다.

네트워크 레이어에서 세그먼트를 받아 올바른 포트번호에 넣어주는 행위를 역 다중화 라고한다.

🗂️ Socket

- OS커널에 구현되어있는 추상화된 인터페에스
- 장치 FILE의 일종으로 이해가능
- 어플리케이션 레이어와 트랜스포트 레이어 사이의 문이라 볼수있다.
- 사용자가 OS가 관리하는 영역을 직접관리할수 없게 추상화한것이라 보면됌
- IP와 PORT를 통해 유니크하게 구별되어야 한다.

🗂️ UDP

가장 기초적인 기능들만 넣은 프로토콜이다.

<특징>

1. connectionless
- TCP 프로토콜이 연결지향적인 것에 반해 UDP는 연결을 맺지 않고 그냥 데이터를 전송한다.

2. unreliable
- IP와 마찬가지로 unreliable하며 IP 프로토콜을 거의 그대로 쓴다고 보면된다.
- 속도가 빠르기에 데이터 손실이 나더라도 속도가 중요한 서비스(비디오 스트리밍 등)에 활용된다.

* 간단한 에러체크 정도만 하며 에러체크후 복구 등의 작업은 하지않음

📁 TCP

UDP + 여러 기능 추가 라고 생각하면 된다.

<특징>
1. connection
- 연결 지향형으로 각 프로세스끼리의 연결을 만든후 사용

2. reliable
- 데이터를 온전하게 전송하는것을 보장함.
- 데이터의 순서 또한 보장함. 

***
UDP에서는 PORT와 IP주소를 통해 식별하지만
TCP에서는 전송자의 IP,PORT, 수신자의 IP,PORT 총 4개의 값을 가진 connection을 기준으로 식별함

요구사항 분석

마크씨의 요구사항

- 은행 입출력 파일(CSV)을 읽고 분석해야 한다.


분석 사항
1. 입출금 내역의 총 수입과 지출은 얼마인가?
2. 특정 달엔 몇건의 입출력이 발생했는가?
3. 지출이 가장 높은 상위 10건은 무엇인가?
4. 돈을 가장 많이 소비하는 항목은 무엇인가? 

KISS 원칙

KISS = keep it short and simple 원칙
KISS 원칙을 이용하여 

public class BankStatementAnalyzerSimple {

    private static final String RESOURCES = "src/main/resources/";

    public static void main(final String[] args) throws Exception {
            final Path path = Paths.get(RESOURCES + "bank-data-simple.csv");
            final List<String> lines = Files.readAllLines(path);
            double total = 0;
            for(final String line: lines) {
                String[] columns = line.split(",");
                double amount = Double.parseDouble(columns[1]);
                total += amount;
            }

            System.out.println("The total for all transactions is " + total);
    }
}

이처럼 한 클래스에 다 때려박아버렸다.

유지보수성

위 코드는 과연 좋은 코드일까?

개인적인 생각은 아니요 였다.

위 코드는 한 클래스에 모든 기능이 구현되어있다.
-> 따라서 한 부분을 고치고 싶더라도 전체를 뜯어봐야 할 수 있다.

라는 이유였고 책도 비슷한 이야기를 했다.

<좋은 코드의 조건>

1. 특정 기능을 담당하는 코드 쉽게 찾을수 있어야 함
2. 어떤 기능을 수행하는 코드인지 이해하기 쉬워야 함
3. 새로운 기능 추가 및 기존 기능 제거가 쉬워야 함
4. 캡슐화, 즉 사용자에게 세부 구현 내용이 감춰져야 함

<나쁜 코드의 조건>
1. GOD class(하나의 거대한 클래스)
2. 코드 중복


<결론>
간결하게 구현하는 것도 무척 중요하지만
KISS 원칙을 남용하면 안된다.

전체 응용 프로그램의 설계 분석후, 한 문제를 여러 개별문제로 분리하는 과정이 중요

SRP

단일 책임 원칙(SRP)는 한번에 하나의 책임만 진다는 소프트웨어 개발 지침이다.

한 클래스(or 매소드) 는 한가지 동작, 개념, 카테고리와 관련이 된다.

위 코드는 
1. 입력 읽기
2. 파싱
3. 결과처리
4. 리포트

라는 4가지의 기능을 포괄하니 SRP원칙을 위해한다.

따라서 각 기능별로 클래스를 구현하여 쪼개준다.

결합

겹합도는 한 기능이 다른 클래스에 얼마나 의존하고 있는지를 나타낸다.

이해하기 쉽게

파싱하는 작업을 클래스로 만들때 CSV에 대해서만 작동하도록 만들었다고 해보자.
하지만 중간에 CSV가 아닌 JSON 파일 이 들어온다면?
그냥 txt파일이 들어온다면?

해당 클래스를 전부 갈아엎어야하는 상황이 발생한다.

그렇기에 인터페이스를 활용하여 기능부와 구현부를 나눈다.

기능부는 인터페이스를 사용하여 내부 동작원리를 생각치 않고 기능을 쓴다.

구현부는 각 상황에 맞는 구현을 하여 동작하게한다.

자바 문법을 어느정도 공부후에 고민이 생겼다.

1. 프로젝트를 진행해볼까
2. Spring까지는 배우고 프로젝트를 해볼까?

하던중 자바도 제대로 못다루면서 Spring을 배우는것은 언감생심이라 생각했다.

그렇기에 책을 하나 정하여 프로젝트를 진행하기로 결심했다.

선정이유

1. 콜렉션 사용방법과 클래스 정도만 이해한다면 따라 진행할수 있다고 하기에
2. 실제 프로젝트를 통해 SOLID 원칙을 설명한다는 점

이 마음에 들었기에 선정하게 되었다.

공부방법

1. 우선은 모든 코드를 따라치면서 연습해본다.
2. 책에 적힌 과제는 반드시 한번 시도해본다.
3. 프로젝트가 끝난다면 기능을 추가하여 나를 위한 프로그램으로 바꿔본다.!

📖 장기 스케줄링

처음 프로세스 생성시 ready/suspend로 갈지 ready로 갈지 결정하는 스케줄링

📖 중기 스케줄링

suspend 상태의 프로세스를 메모리로 가져올지 말지 결정하는 스케줄링

📖 단기 스케줄링

어떤 순서로 dispatch 할지 선택하는 스케줄링

사실상 의미 있는 스케줄링 단계이며 앞으로 스케줄링은 단기 스케줄링을 지칭한다.

💻 스케줄링 평가 기준

스케줄링의 성능은 어떤 평가 기준을 사용할 것인가에 따라 다르다.

첫번째는 사용자 관점 vs 프로세서 관점에서 평가하는 것이다.

사용자 관점 - 사용자에게 긍정적 영향을 미치는 것을 기준으로 평가, 예를 들어 응답시간을 기준으로 평가한다.
시스템 관점 - 얼마나 프로세서를 낭비없이 사용하느냐에 대한 관점, 처리량이 대표적인 기준이다.

두번째는 성능 중심의 관점에서 평가할 것이냐 성능과 관련이 없는 척도를 기준으로 평가하느냐 이다.
성능과 관련이 없는 기준은 측정이나 분석이 어렵다.

예를 들면 예측 가능성이 있는데 프로세스가 언제쯤 시작되서 끝날지 예측하는 정도를 나타낸다.
스케줄링을 위해서 매우 중요하다.


<정리>

사용자 관점
1. 성능 관련 : 반환 시간, 응답 시간
2. 기타 : 예측 가능성

시스템 관점
1. 성능 관련 : 처리량, 프로세서 이용률
2. 기타 : 공정성(스타베이션이 없어야한다)

💻 다양한 스케줄링 정책

총 6가지의 스케줄링 방법을 알아보자.

1. FCFS(FIFO라고도 함)
2. round robin
3. SPN
4. SRT
5. HRRN 
6. Feedback

다음과 같은 순서로 프로세스가 도착한다고 했을때를 기준으로 설명한다.

📖 FCFS

말 그대로 처음 들어온 프로세스 부터 실행한다.

이때 선점은 없이 실행한 프로세스는 종료시 까지 실행한다.

<장점>
starvation 발생 없음
문맥 교환 비용 최소

<단점>
실행시간이 짧은 프로세스더라도 기다려야 함.
응답시간이 제일 김


* 초반에 배운 batched 멀티 프로세싱이 이 방법

📖 Round Robin

타임 퀀텀을 정하여 프로세스에 실행 시간을 할당하며
해당 시간만큼만 프로세스들을 번갈아 실행한다.

시분할 방법에 해당하며 선점모드이다.

<장점>
starvation 발생 x
짧은 프로세스에게 좋은 응답시간 제공

<단점>
프로세스의 특징은 고려하지 않는다.
-> 입출력 중심의 프로세스는 잠깐 받은후 시간을 다 못쓰고 블락됌
-> 입출력 중심 프로세스의 성능이 떨어진다.

📖 SPN(shortest process next)

실행시간이 가장 짧은 순서대로 실행한다.

비선점 모드이다.

<장점>
이론상 가장 빠른 방법이다.
페이지 교체의 optimal과 비슷하다고 보면 되는데
optimal은 구현이 불가하지만 SPN은 구현이 가능하다.

<문제점>
프로세스의 실행시간을 알아야한다.
하지만 프로세스의 실행시간을 정확히 알수 없으니 수식을 사용해서 예측한다.
기아상태에 빠질 가능성 존재

실행시간 예측

프로세스를 실행시키면서 각 실행때마다 실행시간을 잰뒤
n+1 번째 실행때는 n까지 실행시간의 평균으로 예측한다.

지수적 평균 방법 또한 존재한다.

이 수식은 서로 다른 가중치를 두어 최근 예측값과 실측값의 비중을 조절한다.

위 그래프는 실제 실행 시간과 예측치를 비교한다.
단순 평균은 실제 값을 따라가지 못하지만
지수적 평균방법은 횟수가 증가함에 따라 빠르게 실측치를 따라간다.

📖 SRT(shortest remaining time)

SPN과 비슷하다.
차이점은 SRT는 가장 실행시간이 적게 남은 프로세스를 고르며 선점 방식이기에 
매번 계산해서 교환한다.

<장점>
SPN에 비해서 예측가능성이 높으며 짧은 프로세스에 경우 도착하자마자 서비스를 받는다.

<단점>
스타베이션 발생 가능성과
시간 계산을 해야하는 오버헤드 발생

📖 HRRN

SPN과 SRT는 스타베이션 가능성이 있다.

따라서 이를 해결하기 위해서 오래 기다린 프로세스에게 가중치를 두는 방식을 사용한다.

R=1+w/s (R : 응답비율, w : 대기시간, s : 서비스 시간)

으로 구성되며 R값이 큰 순서대로 실행을 한다.

비선점 방식이므로 새로운 프로세스를 실행할때만 R값이 필요하다.

📖 Feedback

SPN,SRT,HRRN은 모두 좋은 방식 같아보이지만 실제로는 사용치 않는다.

1. 서비스 시간을 알아내야 한다는 점
2. 계산을 하기위한 추가적인 오버헤드가 발생한다는 점 
등의 이유로 사용치 않으면 실제 시스템에서는 Feedback 방식을 주로 사용한다.

Feedback방식은 실행 시간이 길수록 패널티를 주는 방식이다.

실행시간을 구하지않고 일단 일정 시간동안 RR방식으로 실행을 시킨후
시간을 다썼음에도 실행을 더 시켜야한다면 우선순위를 낮춘다.

같은 우선순위의 큐는 RR방식으로 실행하며 높은 우선순위의 큐가 비기 전까지
낮은 우선순위의 큐 안의 프로세스는 실행치 않는다.

또한 어떤 프로세스 실행중 더 높은 우선순위의 프로세스가 들어온다면 그 즉시 교체한다.

<방식>
1. 더 낮은 우선순위에도 똑같은 시간을 할당
2. 우선순위가 i만큼 낮아지면 실행시간도 2^i만큼 추가 할당하여 실행시 끝낼수 있게 해주기

2번을 사용하더라도 높은 우선순위의 큐가 비기는 힘들기에 스타베이션이 발생할수 있다.

위 사진처럼 한 퀀텀 실행후 우선순위가 낮아짐

전통적인 Unix 방식

유닉스 방식은 좋은 응답시간과 기아상태 방지를 목표로 한다.

다단계 피드백 큐 방식을 활용하며 각 큐 내에서는 RR방식을 사용한다.

우선순위 계산이 독특한대
CPUi(j)값은 특정 구간동안 cpu를 얼만큼 점유했는가에 대한 퍼센트이다.

오래 cpu를 사용한 프로세스는 다음 사용에 패널티를 주는 방식이다.

nice는 유저가 우선순위를 조절할수 있게해준다.

단, 이때 프로세스의 기본 우선순위는 그대로여야한다.
(커널 관련 프로세스가 오래 사용된다고 유저 프로세스보다 우선순위가 밀리는 등의 일은 없어야함)

따라서 비슷한 우선순위 내에서만 우선순위가 바뀌게 하기위해
base라는 기본 우선순위값을 매우 크게 줘서 cpu와 nice값으로 변경하더라도 영향이 없게한다.

일반적인 대기열을 생각하면 된다.

버스 정류장에서는 먼저 선 사람이 먼저 버스에 타고 나중에 선 사람이 나중에 탄다(FIFO)
이런 원리를 활용한 것이 Queue이다.

Queue는 선입선출의 원리를 활용한 자료구조이다.

자바에서 Queue

자바에서 queue는 스택과 다르게 인터페이스 자료형이다.

즉, 세부적으로 구현되어 있지 않고 내부 동작만 정의되어있다.

queue는 여러가지가 선택이 가능한데 LinkedList,PriorityQueue,ArrayDeque 등 으로 구현 가능하다.

인터페이스 사용의 장점으로는 다른 Queue를 사용하고 싶을때 최소한의 수정만으로 갈아낄수가 있다는 것이다.

LinkedList던 ArrayDeque던 Queue<> q=new ~~;으로 선언하여 q로 사용이 가능하다.

인터페이스에 정의된 매소드만 사용이 가능하다.

매소드

1. 삽입(enqueue)
- offer(value) : 전통적인 삽입 방식 큐의 시작점에 밀어넣음
- add(value) : offer와 같은 삽입 매소드, 단 오류 발생시 예외처리함

2. 삭제(dequeue)
- poll() : 가장 처음 추가된 값을 반환한다.
- remove() : poll()과 같으나 오류시 예외처리

3. 공백확인
- isEmpty()

4. 초기화
- clear() : 큐의 모든 원소 삭제 null로 만듬 

5. 크기
- size() : 큐 안에 저장된 원소 개수 반환

6. 확인
- peek() : 가장 먼저 들어간 값을 삭제없이 반환

실구현

public class customQueue {
    private QueueNode Head;
    private QueueNode Tail;
    private int size=0;

    public customQueue(){
        Head=new QueueNode();
        Tail=new QueueNode();

        Head.nextNode=Tail;
        Tail.prevNode=Head;
    }

    public void offer(Object value){
        QueueNode newQueue=new QueueNode(value);

        newQueue.nextNode=Head.nextNode;
        Head.nextNode.prevNode=newQueue;

        Head.nextNode=newQueue;
        newQueue.prevNode=Head;

        size++;
    }

    public Object poll(){
        QueueNode tmp=Tail.prevNode;

        tmp.prevNode.nextNode=Tail;
        Tail.prevNode=tmp.prevNode;

        tmp.prevNode=null;
        tmp.nextNode=null;

        size--;
        return tmp.obj;
    }

    public Object peek(){
        return Tail.prevNode.obj;
    }

    public boolean isEmpty(){
        return Head.nextNode==Tail?true:false;
    }

    public int size(){
        return size;
    }

    @Override 
    public String toString(){
        String str="[";

        for(QueueNode tmp=Head.nextNode;tmp!=Tail;tmp=tmp.nextNode)
            str+=tmp.obj.toString()+",";

        str+="]";

        return str;
    }
    class QueueNode{
        private Object obj;
        private QueueNode nextNode;
        private QueueNode prevNode;

        QueueNode(){};
        QueueNode(Object obj){
            this.obj=obj;
        }
    }
}

Stack은 말그대로 쌓아 올린다.
제일 늦게 들어온 녀석이 가장 처음 나간다.(FILO)

음식점의 쌓인 그릇을 생각하면 쉽다. 차곡 차곡 쌓아올려져 위에서 부터만 꺼낼수가 있다.

웹 페이지를 사용할때도 스택의 원리와 같다.
링크를 누를때마다 새로운 페이지로 이동하며 되돌리기 버튼을 누르면 이전에 사용한 페이지가 나온다.

ADT

스택을 구현하는데 있어서 필요한 ADT는 다음과 같다.

주요 메서드

- push(e) : e를 삽입
- pop() : 가장 나중에 삽입된 원소를 삭제하여 반환

보조 메서드

- top() : 가장 나중에 삽입된 원소를 삭제없이 반환
- size() : 현재 저장된 원소의 수 반환
- isEmpty() : 스택이 비어있는지 여부 반환
- elements() : 원소 전체 반환

Java의 API

java.util.Stack에 위치한다.

<매소드>

boolean isEmpty() - 비어있는 스택인지 아닌지 판단
Object peek() - 가장 최근에 삽입된 데이터 반환
Object pop() - 가장 최근에 삽입된 데이터 삭제후 반환
Object push(Object item) - item 삽입
int search(Object obj) - 원하는 데이터 찾아서 있다면 위치 없다면 -1 반환

array로 만든 Stack

스택의 특성상 제일 첫 요소만 접근하여 사용 함으로 Linked가 아닌 ArrayList로 사용한다.

import java.util.ArrayList;

public class arrayStack {
    private int size;
    private ArrayList<Object> stack=new ArrayList<>();

    arrayStack(){
        size=0;
    }

    public Object push(Object data){
        stack.addFirst(data);
        size++;

        return data;
    }

    public Object pop(){
        Object obj=stack.remove(0);

        size--;
        return obj;
    } 

    public Object peek(){
        return stack.get(0);
    } 

    public boolean isEmpty(){
        if(size==0)
            return true;

        return false;
    }

    public int search(Object obj){
        return stack.indexOf(obj);
    }
}

링크드 리스트란 연속적이지 않은 공간에 데이터를 저장한다.
노드 단위로 저장이 되며 이 노드에는 데이터와 다음 노드를 가르키는 참조자가 존재한다.

참조자를 통해 각 노드끼리 연결된다.

첫 노드의 위치를 알기위해 Header가 존재하며 시스템에 따라
마지막 노드를 알기위해 Tail을 사용하기도 한다.

<장점>
배열과 다르게 길이의 제한이 없다.
새로운 데이터가 들어올시 노드의 연결을 끊고 다시 이어주면 되기 때문이다.

또한 배열 처럼 데이터를 모두 밀거나 당길 필요 없이
바로 삭제와 추가가 가능하다.

<단점>
인덱스를 통한 조회가 불가하기 때문에 원하는 데이터를 찾기위한 시간이 오래걸린다.

💻 기능

Linked List도 List 객체를 상속받아 만들어진다.
따라서 ArrayList와 기본적인 기능은 비슷하며

구현또한 동일하게 할 계획이다.

포인터가 없이 저걸 어떻게 구현해야하나 싶지만 사실 방법이 있다.

📖 참조자료형

참조 자료형은 Heap영역에 동적 할당되며 동적할당 된 영역의 시작주소가
스택에 저장되는 방식이다.

즉, C에서 동적할당을 하는 것이랑 같은 방식이다.

우리가 String str=new String("어쩔티비");
를 하게되면 Heap영역에 어쩔티비 라는 문자열 상수가 저장되고

이 상수의 시작주소를 str에 복사하여 저장한다.

클래스의 경우에는

Stack (main method)          Heap
----------------------       ------------------------
| myObject (0x1a2b) | -----> | MyClass (0x1a2b)      |
|                   |        | intValue: 10          |
|                   |        | doubleValue: 20.5     |
|                   |        | stringValue: "Hello"  |
----------------------       ------------------------



위 그림처럼 스택에는 클래스의 주소가 그 내부에는 다양한 멤버변수,매소드 등이 존재한다.

📖 참조자료형의 Call by Value

참조자료형은 언뜻 보면 Call by Reference 방식인 것 같으나 실상은 그렇지 않다.


public class Member {
    public String name;
}

public void change(Member m) {
    m.name = "김민수";
}

라는 메소드는 Member 클래스를 받아 해당 클래스의 이름을 변경해준다.

Main에서 실행 후 결과를 보면 이름값이 바뀜을 알 수 있다.


public static void main(String[] args) {
    Member member = new Member();
    member.name = "이영희";

    change(member);

    System.out.println(member.name); // 출력 결과: "김민수"
}


이걸 보고 자바도 Call by Reference를 지원하는구나! 싶지만 실상은 그렇지 않다.

위에서 말했듯이 자바의 참조자료형은 힙에 저장되며 그 주소만 스택에 저장된다. 
우리가 매개변수를 통해 참조자료형을 넘겨줄 때 사실은 이 스택에 저장된 주소값이 복사되어 넘어가는 것이다.

따라서 이 주소값에 해당하는 클래스 내부의 name을 변경하라는 명령이기에 변경된 것이다. 

만약 메소드가

public void change(Member m) {
    m = new Member();
    m.name = "김민수";
}

이런 식으로 새로운 Member 클래스로 갈아끼우려 한다면 변화하지 않을 것이다.

📖 그림으로 설명

변경 전

Stack                    Heap
-----------------       ---------------------
| member (0x1a2b) | ---> | Member object     |
-----------------       | name: "이영희"    |
                        ---------------------

메소드 호출 시

Stack (change method)   Stack (main method)     Heap
----------------------  -----------------       ---------------------
| m (0x1a2b)          | ---> | member (0x1a2b) | ---> | Member object |
----------------------  -----------------      | name: "이영희"        |
                                                ---------------------

m.name = "김민수" 수행 후

변경 후

Stack                    Heap
-----------------       ---------------------
| member (0x1a2b) | ---> | Member object     |
-----------------       | name: "김민수"    |
                        ---------------------

💻 전체 구현

java에서 사용하는거 처럼 양방향 LinkedList를 구현해보자.

📖 Node

private class Node{
        //1. 데이터를 저장 가능해야함
        //2. 다음 노드를 가르켜야함 단 포인터는 없음;; 되게 불편하네
        private Object data;
        private Node nextNode;//남들은 참조 불가
        private Node prevNode;

        public Node(){
            this.data=null;
            this.nextNode=null;
            this.prevNode=null;
        }//노드 생성시 초기화

        public Node(Object input){
            this.data=input;
            this.nextNode=null;
            this.prevNode=null;
        }//값 입력시 값 반영하여 초기화

        @Override
        public String toString(){
            return String.valueOf(this.data);
        }
    }

📖 Header와 Tail

LinkedList 클래스 선언시 자동으로
Head와 Tail이 서로를 가르키게 해야함.


public class customLinkedList {
    private Node Head;
    private Node Tail;

     customLinkedList(){
        Head=new Node();
        Tail=new Node();

        Head.nextNode=Tail;
        Tail.prevNode=Head;
    }
}//이를 위해 생성자에 클래스 생성시 자동으로 Node를 할당받아 서로 연결하게 해줌

📖 addFirst와 addLast

1. 초기상태에서 삽입시

위와 같은 구조를 띄고 있을것이다.

이때 새로운 노드를 추가한다고 해보자.

이 구조에서 새로운 노드를 추가하기 위해서는

Head.nextNode를 newNode에 연결하고
Tail.prevNode를 newNode에 연결해야 할것이다.

즉 다음과 같은 연결을 끊고 새로 삽입을 해야한다.

여기서 더 확장을 해보자.
초기 상태에서 좀더 진행됬을 경우라고 해보자.

만약 이런식이라면? Tail은 저~~ 뒤에 존재한다면?

이경우 우리는 Head만 사용이 가능하다.
반대의 경우도 마찬가지 일 것이다.


따라서 우리는 Head와 Tail만을 사용해서 같은 효과를 내어야 한다.

초기 상태에서 Head.nextNode == anotherNode를

anotherNode.prevNode=Head를 가르키고 있다.

만약 Head.nextNode=newNode를 먼저 연결시켜버린다면
anotherNode에 대한 정보를 유실할 것이다.

따라서 우리는 anotherNode를 Head를 통해 먼저 newNode와 연결해야한다.

그 다음 Head와 newNode를 연결한다.

반대의 경우도 똑같은 원리로 anotherNode부터 연결후 Tail을 연결해야 한다.

이를 코드로 쓰면 다음과 같다.

구현

public void addFirst(Object obj){
        Node newNode=new Node(obj);

        Head.nextNode.prevNode=newNode;
        newNode.nextNode=Head.nextNode;//another Node부터 연결

        Head.nextNode=newNode;
        newNode.prevNode=Head;

        size++;
    }

    public void addLast(Object obj){
        Node newNode=new Node(obj);

        Tail.prevNode.nextNode=newNode;
        newNode.prevNode=Tail.prevNode;//another Node부터 연결

        Tail.prevNode=newNode;
        newNode.nextNode=Tail;

        size++;
    }

결과

public static void main(String[] args) {
        customLinkedList cLinkedList=new customLinkedList();

        cLinkedList.addFirst(1);
        cLinkedList.addFirst(2);
        cLinkedList.addFirst(3);
        cLinkedList.addFirst(4);
        cLinkedList.addFirst(5);

        cLinkedList.addLast(1);
        cLinkedList.addLast(2);
        cLinkedList.addLast(3);
        cLinkedList.addLast(4);
        cLinkedList.addLast(5);

        cLinkedList.printAll();
    }

     public void printAll(){
        int i=0;
        for(Node tmp=Head.nextNode;tmp.nextNode!=null;tmp=tmp.nextNode,i++)
            System.out.println(i+"번째 데이터"+tmp.data);
    }

    다음과 같이 노드를 추가하고 출력시 사진과 같은 결과가 나옴을 확인할수있다.

📖 add

원하는 위치에 데이터를 저장하는 add를 구현해보자.

이를 위해 원하는 인덱스의 해당하는 노드를 찾는 node 매소드를 구현한다.

private Node node(int index){
        if(index>size)
            return null;

        Node tmp=Head;

        for(int i=0;i<=index;i++)
            tmp=tmp.nextNode;

        return tmp;
    }//i번째 노드 반환하기 

이를 활용하여 add구현한다.

위에서는 index에 해당하는 노드를 반환한다.

만약 add에서 2번째 인덱스에 3을 저장하고 싶다고 한다면
현재 2번 위치의 노드는 밀려서 3번이 되고  newNode가 2번이 되어야한다.

즉, 위에서 2번을 찾은후 Tail을 연결시키듯이 똑같이 하면 된다.

구현 및 결과

public static void main(String[] args) {
        customLinkedList cLinkedList=new customLinkedList();

        cLinkedList.addFirst(1);
        cLinkedList.addFirst(2);
        cLinkedList.addFirst(3);
        cLinkedList.addFirst(4);
        cLinkedList.addFirst(5);

        cLinkedList.addLast(1);
        cLinkedList.addLast(2);
        cLinkedList.addLast(3);
        cLinkedList.addLast(4);
        cLinkedList.addLast(5);

        cLinkedList.printAll();

        cLinkedList.add(3,"어쩔티비");
        cLinkedList.printAll();


    }

public void add(int index,Object obj){
        Node base=node(index);
        Node newNode=new Node(obj);

        base.prevNode.nextNode=newNode;
        newNode.prevNode=base.prevNode;//another Node부터 연결

        base.prevNode=newNode;
        newNode.nextNode=base;
    }

https://github.com/Rachi3/dataStructure/tree/master/3.LinkedList

  남은 부분 구현된 링크다.