[워밍업 클럽 CS 3기] 2주차 미션

운영체제 FIFO 스케줄링의 장단점이 뭔가요?장점: 직관적이고 단순해서 구현이 쉽습니다.단점: 실행 시간이 짧은 프로세스를 먼저 배치해주지 못하는 등, 실행 시간에 따라 유동적으로는 작업을 할 수 없습니다. SJF를 사용하기 여러운 이유가 뭔가요?프로세스가 걸리는 시간 예측이 힘들기 때문입니다. 짧은 프로세스가 먼저 실행되어야 한다는 것이 원칙인데 해당 프로세스가 짧을지, 길지 예상하기가 힘듭니다. 또한 실행시간이 긴 프로세스는 짧은 프로세스에 밀려 너무 오래 대기해야 합니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?모든 프로세스들이 너무 조금씩만 사용하고 컨텍스트 스위칭이 발생하기 때문에 잦은 컨텍스트 스위칭으로 인한 오버헤드가 발생할 수 있습니다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?타임 슬라이스를 어떤 방식으로 사용하는지에 따른 CPU 사용률을 파악해서 어떤 프로세스인지 확률적으로 구분합니다.CPU Bound Process: 프로세스가 타임 슬라이스를 오버해서 사용해서, 강제적으로 CPU를 뺏기는 상황이 발생합니다.I/O Bound Process: 프로세스가 타임 슬라이스 범위 내에서 스스로 CPU를 반납합니다. 공유자원이란 무엇인가요?프로세스 간 통신을 할 때 공동으로 이용하는 변수나 파일을 말합니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?상호 배제 : 한 프로세스가 리소스를 점유했다면 그 리소스는 공유되어선 안됩니다.비선점: A가 점유한다면 B는 뺏을 수 없습니다.점유와 대기: 프로세스가 A를 갖고 B를 대기하는 것처럼 점유하고, 대기하는 과정이 있어야 합니다.원형 대기: 점유, 대기하는 관계가 원형으로 구성되어 있어야 합니다.자료구조와 알고리즘Python 공부 중이라 구현은 Python으로 했습니다.1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?재귀 함수는 기저 조건을 만나서 종료되는 구조이기 때문에 함수가 종료되지 않고 계속 호출되어서 함수가 올라가는 메모리 영역인 스택이 가득 차서 강제 종료될 수 있습니다. 사실 강제 종료되면 오히려 다행이고..함수가 무한하게 호출되면서 예상하지 못한 결과가 발생할 수 있을 것 같습니다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.# n부터 0까지 내려며 홀수일 때만 더한다. def sum_odd(n): # n이 0까지 왔다면 0 반환 해주고 끝냄 if n 1) 기저 조건은 n 2) 기저 조건 검사, 그 후 짝수 검사하는 코드여야 합니다. 안그러면 종료되어야할 상황에 종료되지 않고 재귀가 호출됩니다. 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.# -*- coding: utf-8 -*- import os def traverse_directory(directory, file_list=None): # 초기 작업 - 현재 위치의 디렉토리, 파일을 리스트로 if file_list is None: file_list = os.listdir(directory) # 다 pop시켜서 모두 순회했다면 종료 if not file_list: return # js의 path.join(currentDir, file) 부분 file_path = os.path.join(directory, file_list.pop()) # isDirectory함수가 python에서는 isdir로 구현 가능 if os.path.isdir(file_path): print('디렉토리:', file_path) # 디렉토리라면 디렉토리 내부도 순회해줘야하니까 재귀함수 호출 traverse_directory(file_path) else: # 파일이라면 출력만 하고 끝냄 print('파일:', file_path) # 위의 재귀함수가 알아서 하위 파일,디렉토리들을 출력해주니까 pop일어난 file_list 다시 순회 traverse_directory(directory, file_list) traverse_directory(".")1) 재귀를 2번 사용했습니다. 현재 위치의 파일들도 돌아줘야하고, 하나의 특정 파일의 하위도 돌아줘야 해서 2번 사용하게 되었습니다.2) file_list를 index를 하나씩 증가시키며 도는 방법이랑 하나씩 pop 하는 방법이 있을 것 같은데 예제 코드가 push, pop을 사용해서 저도 pop을 활용했습니다.

[워밍업 클럽 CS 3기] 2주차 발자국

운영체제프로세스 간 통신→ 한 컴퓨터내에서 파일과 파이프를 이용해서 통신, 쓰레드 통신, 네트워크 통신(소켓, RPC)→ 공유 자원이란 프로세스가 같이 이용하는 파일, 변수→ 공유 자원으로 인해 동기화 문제 발생 공유자원과 임계구역→ 임계구역 : 여러 프로세스가 동시에 사용할 수 없는 구역→ 경쟁조건 : 공유자원을 사용하기 위한 프로세스간 경쟁→ 임계구역 문제 해결을 위한 상호배제 매커니즘 상호배제 메커니즘 → 한번에 한 프로세스만 임계영역에 접근 가능, 대신 프로세스는 빠르게 나와야함.→ 컨텍스트 스위칭: 운영체제가 현재 작업을 멈추고 다른 작업으로 전환 세마포어(상호배제 매커니즘)→ 임계구역에 접근할 수 있는 권한 (여러개 존재 가능)→ 장점: 동기화 문제 해결→ 단점: 세마포어를 요청 또는 반납 하는 순서가 핵심, 모니터로 해결 가능모니터(프로그래밍 언어로 해결)→ 예시: JAVA에서 synchronized가 붙어있으면 동시에 여러 프로세스에서 실행시킬 수 없음→ 이런식으로 컨트롤하는 것이 모니터 데드락→ 프로세스들이 서로 작업 끝내길 기다리다가 아무도 작업을 하지 못하는 상태→ 발생이유: 공유 자원 데드락 예시: 식사하는 철학자→ 포크3개 철학자 3개 (포크가 2개 있어야 식사 가능) 교착 상태의 필요조건→ 상호 배제 : 한 프로세스가 리소스를 점유했다면 그 리소스는 공유되어선 X (포크)→ 비선점: A가 점유한다면 B는 뺏을 수 없다→ 점유와 대기: 프로세스가 A를 갖고 B를 대기해야…→ 원형 대기: 점유, 대기하는 관계가 원형 데드락 해결→ 교착 상태 회피: 교착 상태가 발생하지 않는 수준의 자원 할당→ 최대한 안정상태로 갈수있게, 불안정 상태는 교착 상황이 발생할 확률이 높음 은행원 알고리즘→ 여윳돈과 대출 금액을 보고 안정상황인지 확인하고 돈을 빌려줌 알고리즘 구현→ 운영체제는 시스템의 총 자원을 알아야함→ 프로세스는 최대 요구 자원을 운영체제에게 알려줘야함→ 은행원 알고리즘은 비효율적이고 비용이 많이 든다교착상태는 허용, 그러나 해결할 수 있도록 검출 방법→ 가벼운 교착 상태 검출 (프로세스가 작업을 진행하지 않는다면 교착)→ 무거운 교착 상태 검출 (프로세스가 그래프로 어떤 자원 사용하는지 살펴보고 교착 상태 파악) 컴파일과 프로세스→ 컴파일 언어→ 개발자가 코드 작성, 컴파일 되고 실행파일을 만듦→ 컴파일하면서 오류 검사, 기계어로 실행 파일을 만들기 때문에 속도가 빠름 (C, C++, C#) →인터프리터 언어→ 실행시 코드를 한줄씩 실행해봄(JS, Ruby, Python)→ 프로세스 내에는 코드, 데이터,힙(동적 메모리 할당), 스택(지역변수, 매개변수, 함수 리턴주소) 전처리기 (전처리 구문 처리, #include, #define, 주석 제거)컴파일러 (기계어에 가까운 어셈블리어로 만든다)어셈블러(오브젝트 파일로 변환시킴, 0과1로 구성)링커(오브젝트 파일을 실행 파일로)실행 파일( 완벽한 상태의 코드 영역, 데이터 영역 구성) 메모리레지스터→ 가장 빠름, CPU내에 존재→ 컴퓨터 꺼지면 날아가서 휘발성 메모리(34bit, 64bit)→ CPU는 계산 할때 메인 메모리에 있는 값을 레지스터로 가져와 계산하고 다시 메인메모리에 저장 램(메인메모리)→ 레지스터와 메인 메모리 사이에 캐시→ 운영체제, 프로세스가 올라가는 공간 (휘발성) 보조저장장치→ 가격이 저렴해서 오래 저장 가능 (전원 공급 필요 없음, 비휘발성) 캐시→ 메인메모리에서 필요한 데이터는 미리 가져와 캐시에 저장→ 단계 별로 L1, L2,… 없으면 메인 메모리를 살펴봄 메인 메모리→ 운영체제는 메모리 관리를 위해 1바이트 크기로 구역을 나누고 주소 매김→ 32bit는 버스의 크기도 32 bit, 2에 32승으로 메모리도 4GB 물리 주소 공간→ 메모리를 컴퓨터에 연결했을때 0x0번지부터 시작하는 주소 공간논리 주소 공간→ 사용자 관점에서 바라본 공간 경계 레지스터메모리 관리자가 프로세스가 경계 레지스터를 벗어났는지 검사하고 벗어났다면 프로세스 종료 절대 주소(물리 주소 공간), 상대 주소(논리 주소 공간)→ 컴파일러는 0x0번지라고 생각(상대 주소), 실제 주소는 0x4000번지(메모리 관리자가 보는 절대 주소) 메모리 할당 방식→ 메모리 오버레이란 프로세스를 잘라 당장 필요한 부분만 메모리에 올리고 나머지는 하드디스크에 가변 분할 방식(연속 메모리 할당, 세그멘테이션)→ 프로세스의 크기에 따라 메모리를 나눔 고정 분할 방식(비연속 메모리 할당)→ 프로세스 크기 상관없이 메모리를 나눔오늘날에는 둘을 혼합하고 있음 버디 시스템(2의 승수로 메모리를 할당)-> 메모리 공간 확보가 간단-> 내부 단편화가 발생, 많이 낭비되지는 않음 자료구조와 알고리즘재귀→ 어떤 것을 정의할 때 자기 자신을 참조하는 것 콜스택→ 메모리 공간이 가득차서 자동 종료→ 함수가 호출되면서 올라가는 메모리 영역 (스택)→ FILO→ 재귀 함수가 for문보다 메모리를 더 많이 씀→ 문제를 더 쉽게 해결하려고 씀 (예: 팩토리얼)재귀함수는 탈출 조건(기저 조건) 필수특정 조건이 나오면 알아서 종료가 되어야 함 재귀의 패턴→ 단순 반복 실행을 재귀로 (성능은 좋지 않음)→ 하위 문제의 결과를 기반으로 현재 문제를 계산(팩토리얼)→ for문은 상향식 계산, 재귀는 하향식 계산(하위 문제의 결과를 기반으로 현재 문제를 계산)→ 상향식은 for문과 재귀 둘다 구현 가능, 하향식은 오로지 재귀로만하노이탑→ 하향식 문제의 예시→ 원반 2,1을 기둥B로 옮기는 것이 하위 문제→ 원반 1을 기둥c로 옮기는 것이 마지막 하위 문제 버블 정렬→ 앞에 있는 숫자와 옆에 있는 숫자를 비교해서 자리를 바꿈→ BIG-O는 O(N2) 선택 정렬→ 첫번째부터 마지막까지 비교 후 가장 작은 값을 첫번째로→ 정렬된 영역, 정렬되지 않은 영역으로 구분해서 정렬→ BIG-O는 O(N2)→ 버블 선택 모두 직관적이고 이해하기 쉬우나 성능이 나쁨칭찬할 점: 예습을 좀 했습니다. 확실히 강의 내용이 머리에 더 잘 들어오는 것 같아요.보완할 점: 재귀의 기저조건 찾는걸 잘 못하는 것 같아요. 재귀 원리는 이해가 되는데 기저 조건을 1인지 0인지 if문 2개로 해야할지..이런게 자꾸 어려워서 더 공부해야 할 것 같습니다.다음 주 목표: 백준에서 재귀랑 정렬문제 각각 10개 이상씩 풀고 오전에는 예습, 저녁에는 강의 듣는 것이 목표입니다.

[워밍업 클럽 CS 3기] 1주차 미션

운영체제 while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 } 위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요? 인터럽트 방식으로 전환해야 할 것 같습니다. 주기적으로 매번 체크를 수행하지 말고, ISR 방식처럼 Skill이 Activate 됐을때 인터럽트가 발생하도록 동작을 바꿔서 성능을 높여야 할 것 같습니다. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 하드 디스크에 저장된 명령문의 집합체이지만 프로세스는 실행중인(메모리에 올라간 상태) 프로그램입니다.이에 따라서 프로그램은 단순 집합체라 수동적이지만 프로세스는 능동적으로 필요에 따라 CPU를 사용하고 입력 출력을 하는 양상을 보입니다. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티 프로그래밍은 메모리에 여러개의 프로세스 올려서 처리하는 반면에 멀티 프로세싱은 여러개의 CPU를 사용해서 서로 다른 프로세스를 짧게씩 실행하며 동시에 처리하는것처럼 보이게 합니다.운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?운영체제는 프로세스의 정보를 가진 PCB(Process Control Block)를 생성해서 프로세스의 정보를 저장하고, CPU 스케쥴링 시에도 프로세스의 상태를 저장하고 관리합니다. 컨텍스트 스위칭이란 뭔가요?다른 프로세스 실행을 위해 프로세스 상태를 저장하고 다른 프로세스 상태값으로 교체하는 것을 말합니다. 자료구조와 알고리즘 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 해시테이블을 사용할 것 같습니다. 직관적으로 저장하려면, 학생에게 학번을 부여하거나 아니면 가나다 순의 이름으로 정렬할 것 같은데 학번일 경우에는 해시 함수를 사용해서 번호가 골고루 인덱스에 분배될 수 있도록 나누거나 ㄱ,ㄴ,ㄷ등의 자음으로 인덱스를 구성해서 학생의 정보를 저장할 것 같습니다. 각 학생의 이름, 나이, 취미, 특기와 같은 자세한 정보들도 해시테이블에 인덱스를 구성해 저장하기 좋을 것 같습니다. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.주문은 들어온 순서대로 처리되어야 하므로, FIFO 방식의 큐를 사용하되, 감자튀김 단일 주문 같은걸 패티가 3개 들어간 버거 때문에 너무 늦게 처리 할 수 없으므로 동시에 들어온 주문일 경우 조리 시간이 오래 걸리는 순서대로 스택에 넣어서 짧은 조리시간을 가진 주문부터 처리 할 것 같습니다. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.push(data){ this.list.insertLast(data); } pop(){ try{ return.this.list.deleteLast(); } catch(e) { return null; } }링크드리스트에 deleteLast, insertLast함수가 구현되어있기 때문에 그 함수를 그대로 사용했습니다. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력hashFunction(name){ }hashFunction(name){ return (name.charCodeAt(0) + name.charCodeAt(1)) % 10; }한국에는 특정 성씨, 특히 예시에 나온 이씨와 같은 성씨가 많아서 단순 성씨로 하면 한 곳에 많이 몰릴 것 같아서 두번째 글자까지 더하는 연산으로 구현했습니다.

[워밍업 클럽 CS 3기] 1주차 발자국

운영체제운영체제에 대해서 운영체제는 프로세스 관리, 메모리 관리, 하드웨어 관리, 파일 시스템 관리 등의 역할을 함커널은 프로세스와 메모리를 관리 역할 (사용자 - 인터페이스, 애플리케이션 - 시스템콜, 하드웨어 - 드라이브)폰 노이만 구조 - CPU와 메모리 사이를 버스(데이터 전달 통로)로 연결하는 구조CPU는 ALU(산술논리연산장치), 제어장치, 레지스터로 구성폴링 방식은 CPU가 주기적으로 확인이 필요, 인터럽트는 입출력 관리자가 작업이 완료되면 ISR을 실행시켜 작업프로세스와 스레드프로그램은 하드 디스크에 저장된 명령문의 집합체, 프로세스는 실행중인(메모리에 올라간 상태) 프로그램프로그램은 수동적이지만, 프로세스는 능동적으로 필요에 따라 CPU를 사용하고 입력 출력을 함.프로세스의 구조(Code, Data, Heap, Stack) 멀티프로그래밍과 멀티프로세싱(유니프로그래밍의 단점 보완)멀티 프로그래밍: 메모리에 여러개의 프로세스 올려서 처리멀티태스킹: 서로 다른 프로세스를 짧게씩 실행하며 동시에 처리하는것처럼 보이게 함CPU가 여러개라면 멀티프로세서, 이렇게 작업하는 건 멀티프로세싱PCB(Process Control Block) - 프로세스의 정보 저장(연결리스트 구조)프로세스의 상태 (생성, 준비, 실행, 대기, 완료)컨텍스트 스위칭다른 프로세스 실행을 위해 프로세스 상태를 저장하고 다른 프로세스 상태값으로 교체프로세스 생성 시에 기존의 프로세스를 fork로 복사해서 사용(자식 프로세스)쓰레드 - 한 프로세스 내에 여러개 있을 수 있으며, PCB, 데이터, 코드, 힙영역을 공유(스택은 고유)TCB(Thread Control Block), TID(쓰레드 아이디)프로세스는 독립적이어서 안정적, 쓰레드는 프로세스에 문제가 생기면 전체 문제 생겨서 불안정적프로세스는 고유한 영역, IPC로 통신해 오버헤드 큼, 쓰레드는 데이터 공유가 가능해 오버헤드가 작음CPU 스케쥴링준비, 대기 상태는 큐로 관리PCB는 다중 큐에 들어가서 준비 상태, CPU 스케쥴러가 결정해서 실행 상태로 전화시킴목표: 리소스 사용률, 오버헤드 최소화, 공평성, 처리량, 대기시간, 응답시간스케쥴링 알고리즘FIFO: 먼저 들어온 순서대로 작업(실행시간에 따라 유동적으로는 작업X, I/O작업으로 인한 비효율)SJF(Shortest Job First): 짧은 작업 먼저(시간 예측 힘듦, 긴 프로세스는 너무 오래 대기)RR(Round Robin): 모두 공평한 Time Slice를 쓰고 다음 프로세스에게 뺏김(컨텍스트스위칭 시간 고려 필요)MLFQ(Multi Level Feedback Queue): Time slice를 작게 쓰고, 프로세스의 구분에 따라 다르게 줌자료구조와 알고리즘자료구조와 시간 복잡도자료구조는 데이터가 어떤 구조로, 저장, 사용되는지 나타냄알고리즘은 문제를 해결하기 위한 방법(자료구조에 영향을 받음)시간 복잡도란 특정 알고리즘이 문제를 해결하는데 걸리는 시간 (반복문을 최소화 하는 것이 목표)big-O 표기법은 계산량이 얼마나 늘었는지 표현법이므로 정확하지 않음(상수는 무시, 가장 큰 영향의 숫자만 표기)배열운영체제는 배열의 주소를 기억하고 데이터를 가져옴인덱스 참조는 길이에 상관X, 한번에 가져오기 때문에 높은 효율 -> O(1) 그러나 삽입, 삭제 성능은 좋지않음연결리스트데이터를 분산 저장 후 서로 연결 (노드를 사용)추가, 삭제는 데이터 연결 부분을 수정만 하면 되서 간단, 참조는 다 따라가서 봐야해서 효율 나쁨스택FILO구조, 먼저 들어간 데이터가 나중에 나옴배열, 연결리스트로 구현 가능(head사용)큐FIFO구조, 먼저 들어간 데이터가 먼저 나옴먼저 들어간 데이터 삭제시, head부터 다 따라가야 나오므로, tail추가 해서 구현tail에 있는걸 삭제해도 tail도 업데이트가 필요하므로 양방향 변경 필요덱데이터 삽입, 삭제를 head와 tail에서 자유롭게 가능해시테이블인덱스로 배열에 접근(빈공간 발생 가능), 특정 숫자를 배열에 넣기 위해 하는 연산인 해시 함수 필요하나의 인덱스에 여러개의 데이터 들어가는 문제 발생시, 연결리스트로 해결 가능데이터 삽입, 탐색, 삭제가 효율적이나 공간 효율이 나쁘고 해시 함수 구현이 필수적셋데이터 중복을 허용하지 않는 자료구조value는 사용X, Key만 사용 칭찬할 점: 강의를 여러번 들은 게 잘한 것 같습니다. 2~3번 정도 들으니 머리에 더 잘 들어오는 것 같아요.보완할 점: 목~금에 강의가 좀 밀렸습니다. 앞으론 밀리는 일 없게 오며가며 계속 들어야 할 것 같습니다.다음 주 목표: 다음주에는 자바스크립트 공부를 좀 더 해서 자료구조 부분은 제가 복습하면서 더 활용해보고 싶습니다.