블로그

최신순
인기순
좋아요순

컴퓨터 공학(CS)이 중요할까요?

저는 학부 시절에 전공수업을 들으면서 항상 답답한 마음이 있었어요.논리회로, 컴퓨터 구조, 자료구조, 알고리즘, 운영체제, 네트워크 등 컴퓨터 공학에서 꼭 배우는 과목을 들을 때마다 너무 막연한 기분이었죠.분명히 한 과목을 들을 땐 해당 내용에 대해서 자세히 배우지만 너무 이론적인 것만 배우는 느낌이 들었고,"왜 지금 당장 결과가 보이는 내용으로 공부하지 않을까?"라는 질문을 했었죠.🧐CPU가 어떤 구조이고 어떻게 동작하는지 이론적으로는 배우지만 정작 CPU가 어떻게 생겼는지는 아무도 알려주지도 않고 스스로 찾아본 적도 없었어요.CPU뿐만 아니라 RAM, 하드디스크 등 주변장치가 어떻게 생긴 줄도 몰랐죠.다른 과 친구들은 "너 컴퓨터 잘 아니까 부품도 잘 알고 조립도 잘하겠네?"라고 종종 물어보지만 그렇지 않았죠.네트워크 수업 때는 모뎀, 허브, 라우터 등 전부 이론적으로, 기껏해야 그림으로 된 예시로 보니까 현실 세계랑 매칭이 잘되지 않았어요.교수님들은 학교에서 배우는 전공이 중요하다고 말씀하실 때 항상 따라붙는 말이 있었어요.컴퓨터 공학은 매우 복잡하므로 Divide and Conquer(분할 정복)로 접근해 하나씩 자세히 알아보는 것이 중요하다, 하지만 이렇게 하나씩 배운 개념을 조합해 전체적으로 볼 줄도 알아야 한다.당시엔 전체적으로 볼 줄 알아야 한다는 말이 크게 와닿지 않았었는데요. 첫 직장에서 백엔드 개발자로 일하는 순간부터 느꼈어요.회사에서 사용하는 기술 스택들은 처음 접해보는 것들이었고 말로만 듣던 AWS도 직접 만져봐야 했죠.이때 많은 기술 스택과 AWS에서 사용하는 용어들은 굉장히 혼란스러웠죠.하지만 용어만 다를 뿐 전공에서 배운 개념들은 그대로였어요.제가 고생했던 것은 "실제로" 이것들이 어떻게 연결되어 동작하는지가 머리에 잘 정리되어 있지 않았던 것이었죠.회사에서도 공부할 시간을 줘서 얼마 되지 않아서 정리할 수 있었어요.그때 교수님들의 말씀이 다시 생각났어요."하나씩 배운 개념을 조합하는 게 이래서 중요하구나~"라고요.회사에 적응하고 개발할 때도 학과에서 배운 내용이 직/간접적으로 도움 된 적이 많아서 그때마다 교수님들을 떠올렸죠.한 번은 사용자의 특정 요청 중 일부가 아주 가끔 중복돼서 들어오는 경우가 있었어요.똑같은 환경에서 테스트해봐도 확인해볼 수도 없었고 하루에 하나가 있을까 말까 했죠.저희 팀에선 이 문제가 한 달 넘게 해결하지 못하고 있었던 상황이었어요.저도 이 문제가 왜 발생하는지 골치 아팠었죠.🧟그러던 어느 날 문득 원인이 예측됐어요. 운영체제에서 배웠던 개념에서 떠올릴 수 있었어요.그래서 예측한 원인을 해결할 방법을 찾아 코드를 수정했고 지켜봤어요!똑같은 문제는 다시는 발생하지 않았죠. 👏 이렇게 실무에서 컴퓨터 공학(CS)의 중요성을 알게 되어 기본기가 탄탄해야 한다는 말에 극공감하게 됐어요.하지만 CS를 배우는 건 어렵고 지루해서 금방 포기하게 되죠.그래서 저는 수업에서 들었던 궁금증, 그때 알았으면 좋았을 것들을 그림과 예시를 들어가며 직접 만들기로 했어요.현재 준비하고 있는 강의는 네트워크인데요.이론적인 내용뿐만 아니라 우리가 일상에서 볼 수 있는 기기가 네트워크에서 어떤 용어로 쓰이고 어떤 역할을 하는지,큰 그림을 맞춰볼 거예요. 만약 CPU의 동작 방식을 배웠다면 위의 그림처럼 CPU가 실제로 어떻게 생겼는지도 알아야 헷갈리지 않겠죠?네트워크는 하드웨어와 소프트웨어가 공존하기 때문에 이렇게 하드웨어까지 알아가며 퍼즐을 맞춰갈 겁니다.이만 다음 강의인 "그림으로 쉽게 배우는 네트워크"를 준비하러 가보겠습니다.😊

개발 · 프로그래밍 기타･CS･전공자･비전공자･컴퓨터공학･그림으로쉽게배우는･네트워크

컴퓨터 네트워크 강의를 준비중입니다.

안녕하세요 "그림으로 쉽게 배우는 컴퓨터공학" 커리큘럼을 만들고 있는 감자입니다!지금까지 제가 만들어 온 모든 강의에서는 여러분의 이해를 돕기 위해 그림을 이용해 설명해 드렸습니다.그런데, 지금 제가 준비하고 있는 강의는 네트워크 강의로 물리적인 장치의 이해까지 필요합니다.보통 전공 수업에선 이론적인 내용 위주로 설명하므로 여러분의 컴퓨터에서 데이터가 실제로 어떻게 이동하는지 직관적으로 알기는 어렵습니다.따라서 네트워크의 이론적인 내용과 물리적인 흐름을 모두 쉽게 이해할 수 있도록 강의 방식을 업그레이드 해보려 합니다.저로서도 새로운 도전이니 여러분들이 많이 응원해주시고 피드백 주시면 좋겠습니다. 😄(가정집 내에 있는 통신단자함 내부)저는 여러분이 인터넷을 사용할 때에 여러분의 집에 있는 통신단자함부터 건물의 통신실, 통신사, 서버까지로 데이터가 어떻게 이동하는지 시각화해 직관적으로 보여드리고 싶었습니다.하지만 기존의 강의 방식으로는 이러한 흐름을 보여드리기에 한계가 있었습니다.(사진과 그림만으로 이러한 것들을 설명하려니 만족스럽지 않았습니다)그래서 저는 여러분에게 직관적으로 전달할 수 있는 가장 좋은 방법이 뭘까 이리저리 고민하다가 3D 모델을 이용해 보기로 했습니다.(서울에는 내 빌딩이 없지만 3D세상에서는 구글빌딩이 내꺼🤗)3D 모델링을 하면서 굉장히 재밌게 준비했습니다.여러분들에게 가장 효율적으로 설명해 드릴 수 있다는 생각에 두근거리기도 해요!이제 준비한 내용으로 네트워크 강의를 열심히 만들어보겠습니다.많이 기대해주세요 😀 (시중에서 팔지 않는 제품도 3D 모델링이면 자세하게 소개할 수 있습니다)

개발 · 프로그래밍 기타･네트워크･3D모델링･그림으로쉽게배우는컴퓨터공학･CS･컴퓨터공학

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

드디어 스터디의 마지막 발자국을 작성하는 날이 왔습니다. - 이번주에 공부한 내용의 키워드 - 운영체제컴파일과 프로세스메모리-레지스터, 캐시, 메인메모리, 보조저장장치절대주소/상대주소가변분할/고정분할가상메모리동적주소변환세크멘테이션 분할방식/페이징 분할 방식스레싱/워킹셋여러가지 주변장치(입출력 디바이스와 저장장치)하드디스크파일과 파일시스템디렉토리디스크 자료구조와 알고리즘버블/선택/삽입/병합/퀵 정렬동적 프로그래밍(메모이제이션/타뷸레이션) - 이번주에 공부한 내용 요약 - 운영체제메모리는 가장 빠른 레지스터, 데이터 임시 저장하는 캐시, RAM이라 불리는 메인메모리, 그리고 보조기억장치가 있습니다. 물리주소는 말 그대로 물리적인 메모리 주소이고 논리주소는 사용자 관점에서 본 상대적 주소입니다. 메모리 할당방식으로는 가변분할방식과 고정분할방식이 있습니다. 현대에서는 두 가지 방식을 모두 사용하여 단점을 최소화하는 버디시스템을 사용합니다.가상메모리는 컴퓨터의 물리적 메모리의 크기를 확장하기 위해 사용되는 기술입니다. 동적주소변환은 메모리관리자가 가상메모리의 논리주소를 물리주소로 변환하는 것을 의미합니다.논리주소를 물리주소로 변환할 때 세그멘테이션 분할 방식은 메모리 관리자가 논리주소를 세그멘테이션 테이블을 이용해 물리주소를 찾고, 페이징 분할 방식은 논리주소를 페이지 테이블을 이용해 물리주소를 찾습니다.프로세스가 가상메모리에 접근요청 했을 때 물리메모리에 데이터가 없다면 페이지 폴터라는 인터럽트가 발생합니다. 이 때 HDD의 스왑영역에 있는 데이터를 메모리에 올리는 작업이 수행됩니다.스레싱은 페이지폴트가 발생해서 CPU사용률이 0에 가깝게 떨어지게 되는 현상을 의미합니다. 워킹셋은 메모리에 올라온 페이지를 하나의 세트로 묶어 메모리에 올리는 것을 의미합니다.주변장치들은 메인보드에 있는 버스로 연결되어 있으며 두 개의 채널과 두개의 버스로 구분합니다.파일관리자는 운영체제가 파일을 관리하기 위해 필요한 존재입니다. HDD나 flash memory는 블록 디바이스로 전송단위가 블록이지만 사용자는 바이트 단위로 파일에 접근해야 해서 파일관리자가 중간에서 관리해야합니다.파일은 순차파일구조, 직접파일구조, 인덱스파일구조가 있습니다.관련있는 파일을 모아두기 위해 필요한 것이 디렉토리입니다. 자료구조와 알고리즘정렬에는 크게 5가지 방식이 있습니다간단해서 구현은 쉽지만 성능은 좋지 못한 버블, 선택, 삽입 정렬과 이들보다 상대적으로 성능이 좋은 병합정렬과 퀵정렬이 있습니다.동적프로그래밍 방식으로 메모이제시녀과 타뷸레이션이 있습니다.메모이제이션은 계산결과를 기억하며 재귀를 사용합니다. 하향식 계산방식입니다.타뷸레이션은 계산에 필요한 모든 값을 계산하여 테이블에 저장하고 상향식 계산방식입니다.- 이번 주 회고 겸 스터디 회고 - 눈 깜짝할 사이에 스터디 마지막이 되었습니다. 완주를 위해 달려왔는데 목적했던 바를 이루어서 뿌듯합니다. 개인적으로 따로 다른 분들과 스터디를 했는데 운이 좋게도 열정적이고 좋은 분들을 만나 복습과 완강을 함께 할 수 있었습니다. 일주일에 세번씩 꾸준하게 디스코드 상에서 스터디를 했는데 아주 만족스러웠습니다. 덕분에 허물뿐인 완강이 아니라 제대로 공부하면서 완강을 하게 되었어요.이번주에는 중간점검도 있었는데 그 때 감자님께서 회고를 읽어보신다는 것을 알았습니다. 그동안 너무 주저리주저리 길게 쓰는 것은 지양해야겠다고 생각했는데 그냥 길~게 쓸걸 하는 아쉬움이 있습니다. 짧아서 심심하셨겠다는 생각이 드네요. 이번주 회고는 마지막인만큼 좀 분량 있게 써보겠습니다. 일단 이 CS스터디를 신청한 이유는 '그래도 개발의 길을 걷는 사람이 CS지식도 모르다니! 이럴 수는 없다!'는 마음이 있었기 때문입니다. 기본 지식은 쌓아야 한다는 생각이 강했어요(제가 운영체제 과목을 들은 적이 없습니다..^^;;). 그래서 제가 자주 하는 '일단 신청하자'를 시전했습니다. 왜 하필 이 강의를 선택했냐고 물으신다면 답은 하나입니다. 재미있어 보여서요. 저는 도파민중독자입니다. 일단 재미가 있어야 뭔가를 시작합니다. 감자님 강의를 보는데 애니메이션으로 설명하는 것이 너무 재미있어 보였어요. 이전에 '아 지금 공부하는 게 눈으로 보이면 좋겠다...'라는 생각을 했는데 이 강의가 딱 이 생각에 맞아버린 것이죠. 애니메이션으로 공부하니 재미있고 재미있으니 더 공부하고 싶고... 이런 선순환이 반복되어 어느덧 완강이라는 종착지에 다다르게 된 것입니다. 스터디원들과 스터디를 하다보니 발표자료도 만들게 되었는데 발표자료 만드는 것도 많은 정성을 기울였습니다. 남에게 보여야 하는 것인데 허접하게 만들 수는 없잖아요. 처음에는 노트앱에 기본으로 있는 템플릿을 썼는데 그 템플릿이 너무 마음에 들지 않았어요. 맘에 안들면 제가 만들면 됩니다(자급자족 라이프!). 그래서 만들어진 것이 '감자전용 템플릿'입니다. 귀엽게 디자인이 뽑혔고 이렇게 만든 템플릿 덕분에 스터디를 재미있게 할 수 있었던 것 같습니다. 강의 들으면서 1차적으로 적은 야생의 거친 필기를 이 템플릿으로 더 잘 정리하려는 마음에 한 파트 정리하는데 시간이 좀 많이 걸린다는 소소한 단점이 있기는 합니다... 그렇지만 이렇게 정리한 것이 나중에 복습할 때 도움이 크게 될 것이라 믿어 의심치 않습니다.적다보니 길어졌네요. 스터디가 끝나니 아쉬움이 남기는 합니다. 다음에도 이런 스터디가 또 열렸으면 좋겠어요. 저번에 들어보니 컴퓨터구조 강의도 준비하신다던데.... 그때 한번 또 스터디가 열렸으면 하는 소소한 바램이 있습니다. 이번에 들은 내용들 복습하면서 더 심화적인 내용도 개인적으로 공부해야겠습니다. 좋은 강의 감사하고 다음에 또 뵐 기회가 있으면 좋겠습니다.

운영체제･자료구조･CS･워밍업클럽･스터디

[인프런 워밍업클럽 CS 2기] 2주차 발자국👣

2주차 학습 내용운영체제CPU 스케줄링 알고리즘 - SJF(Shortest Job First)Burst Time이 짧은 프로세스를 먼저 실행하는 알고리즘이론적으론 FIFO보다 성능이 좋지만, 구현에 문제가 발생할 수 있음어떤 프로세스가 얼마나 실행될지 예측 어려움Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수도 있음CPU 스케줄링 알고리즘 - Round Robin한 프로세스에게 일정 시간만큼 CPU를 할당하고, 할당 시간이 지나면 강제로 다른 프로세스에게 일정 시만큼 CPU를 할당하는 알고리즘프로세스에게 할당하는 일정 시간 => 타임 슬라이스, 타임 퀀텀타임 슬라이스의 값에 따라 RR 알고리즘의 성능이 크게 바뀜타임 슬라이스가 큰 경우(무한대라고 가정)먼저 들어온 프로세스의 작업이 종료될 때까지 실행 => FIFO 알고리즘이 됨타임 슬라이스가 작은 경우(1ms라고 가정)컨텍스트 스위칭이 너무 자주 일어남프로세스 처리량보다 컨텍스트 스위칭을 처리하는 양이 더 커짐 => 오버헤드가 너무 큼최적의 타임 슬라이스 : 사용자가 느끼기에 여러 프로세스가 버벅거리지 않고, 동시에 실행되는 것처럼 느껴지면서 오버헤드가 너무 크지 않는 값Windows는 20ms, Unix는 100ms 정도 CPU 스케줄링 알고리즘 - MLFQ(Multi Level Feedback Queue)오늘날 운영체제에서 가장 일반적으로 쓰이는 CPU 스케줄링 기법기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택하되, CPU Bound Process들에게는 타임 슬라이스를 크게 줌CPU를 사용하는 프로세스가 스스로 CPU를 반납하면 I/O Bound Process일 확률이 높고, 실행 도중 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이 발생하면 CPU Bound Process일 확률이 높음우선순위 큐를 여러 개 준비하여, 우선순위가 높으면 타임 슬라이스 크기가 작고, 우선순위가 낮으면 타임 슬라이스 크기가 커짐처음엔 타임 슬라이스가 작게 할당되어있다가, CPU가 강제로 뺏기면 좀 더 큰 타임 슬라이스를 할당받게 됨프로세스 간 통신프로세스는 독립적으로 실행되기도 하지만, 다른 프로세스와 데이터를 주고받으며 통신을 하는 경우도 있음한 컴퓨터 내에서 프로세스 간 통신하는 방법파일을 이용하는 방법통신하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법파이프를 이용하는 방법운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법한 프로세스 내에서 쓰레드 간 통신하는 방법데이터 영역의 전역 변수나 힙을 이용해 통신네트워크를 이용한 방법운영체제가 제공하는 소켓통신이나 다른 컴퓨터에 있는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신공유자원과 임계구역공유자원프로세스가 통신할 때 공동으로 이용하는 변수, 파일 등여러 프로세스가 공유하고 있기 때문에 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음임계 구역(Critical Section)여러 프로세스가 동시에 사용하면 안되는 영역경쟁 조건(Race Condition) : 공유 자원을 서로 사용하기 위해 경쟁하는 것임계 구역 문제를 해결하기 위한 조건상호 배제(Mutual Exclusion) 메커니즘 필요임계 구역엔 주어진 시간에 항상 하나의 프로세스만 접근할 수 있어야 한다동시에 여러 개의 요청이 있더라도 하나의 프로세스의 접근만 허용한다.임계 구역에 들어간 프로세스는 빠르게 나와야 한다.세마포어프로세스들은 대기 큐에서 공유 자원을 사용하기 위해 대기하고, 운영 체제가 관리하는 열쇠를 가진 프로세스만 공유 자원을 사용할 수 있음 => 이때 이 열쇠를 세마포어(정수형 변수)라고 함공유 자원의 개수에 따라 세마포어의 값 또한 달라짐wait() : 열쇠를 요청해서 열쇠를 받고 문을 잠금. 열쇠가 없으면 기다림signal() : 방에서 나와 문지키는 직원에게 열쇠 반납단점 : wait() 함수, signal() 함수의 순서를 이상하게 호출해서 세마포어를 잘 못 사용할 가능성이 있음 => 모니터로 해결!모니터운영체제가 처리하는 것이 아닌, 프로그래밍 언어 차원에서 지원하는 방법Java에서 synchronized라는 키워드가 붙으면, 이 키워드가 붙은 함수들은 동시에 여러 프로세스에서 실행시킬 수 없음 = 상호배제가 완벽하게 이루어짐만약 프로세스 A에서 increase() 함수를 실행하면, 프로세스 B는 synchronized 키워드가 붙은 decrease() 함수도 실행할 수 없음교착상태(데드락)여러 프로세스가 서로 다른 프로세스의 작업이 끝나길 기다리다가 아무도 작업을 진행하지 못하는 상태교착상태의 필요 조건 (한가지라도 충족하지 않으면 교착상태 발생 X)상호배제 : 어떤 프로세스가 한 리소스를 점유했다면, 그 리소스는 다른 프로세스에게 공유되면 안됨 비선점 : 프로세스 A가 리소스를 점유하고 있는데 프로세스 B가 리소스를 빼앗을 수 없어야 함 점유와 대기 : 어떤 프로세스가 리소스A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 함 원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야 함 교착 상태의 네가지 조건을 이용해서 교착상태를 예방하는 방법을 연구해보고자 했으나, 제약이 많고 비효율적이라 해결하는 방법을 연구함교착상태 회피(Deadlock avoidance)프로세스들에게 자원을 할당할 때 어느정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원 할당을 함전체 자원의 수와 할당된 자원의 수를 기준으로 안정 상태, 불안정 상태로 나눔운영체제는 최대한 안정 상태를 유지하려고 자원할당 함불안정 상태에 있더라도 무조건 교착 상태에 빠지는 것이 아닌, 교착 상태에 빠질 확률이 높아짐운영체제에서 은행원 알고리즘 구현하기안정상태은행원 알고리즘은 각 프로세스가 현재 요구할 수 있는 요청이 예상되는 자원을 구함 P1에서 4개를 요청하면 현재 사용 가능 자원이 2개뿐이므로 거절P2에서 2개를 요청하면 2개 모두 P2에 할당, P2는 작업을 마치고 6개를 반납사용 가능한 자원이 6개가 되어, P1, P3 모두에 필요한 만큼 할당 가능불안정 상태사용 가능한 자원이 1개현재 사용 가능한 자원 개수로는 P1, P2, P3가 요청할 수 있는 최대 요청인 2개를 충족하지 못함 => 불안정 상태모든 프로세스가 최대 자원을 요청하지 않는다면 교착 상태에 빠지지 않을 수도 있지만, 불안정상태에 빠지지 않도록 유지하는게 좋음교착상태의 검출 방식가벼운 교착 상태 검출프로세스가 일정 시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주해결 방법 : 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착 상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백무거운 교착 상태 검출자원 할당 그래프 이용현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착 상태가 발생했다면 해결그래프에 순환 구조가 생긴다면 교착 상태가 생긴 그래프교착 상태를 검출하면 교착 상태를 일으킨 프로세스를 강제 종료시키고, 다시 실행시킬 때 체크포인트로 롤백단점 : 운영체제가 지속적으로 자원할당그래프를 유지하고 검사해야하므로 오버헤드가 발생장점 : 가벼운 교착상태에서 발생하는 억울하게 종료되는 프로세스는 발생하지 않음메모리 종류레지스터가장 빠른 기억장소, CPU 내에 존재휘발성 메모리 - 컴퓨터의 전원이 꺼지면 데이터가 사라짐CPU를 구분할 때 말하는 32bit, 64bit는 레지스터의 크기를 말함CPU는 계산을 할 때, 메인메모리에 있는 값을 레지스터로 가져와 계산하고, 결과는 메인메모리에 저장캐시휘발성 메모리레지스터는 굉장히 빠르고, 메인메모리는 너무 느림 => 메인 메모리에 있는 값을 레지스터로 옮기려면 한참 걸리므로 필요할 것 같은 데이터를 미리 가져와서 캐시에 저장성능의 이유로 여러개를 둠메인메모리(RAM)실제 운영체제와 다른 프로세스들이 올라가는 공간전원이 공급되지 않으면 데이터가 지워지므로 휘발성 메모리하드디스크나 SSD보다 속도는 빠르지만, 가격이 비싸므로 데이터를 저장하기 보다는 실행 중인 프로그램만 올림 보조저장장치(HDD, SSD)사무용 프로그램, 게임, 작업한 파일 등을 저장할 필요가 있는데, 비싸고, 휘발성인 메모리에 저장할 순 없음가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리를 만듦 메인메모리오늘날의 컴퓨터 구조인 폰 노이만 구조는 모든 프로그램을 메모리에 올려 실행시킴운영체제는 메모리를 관리하기 위해 1바이트 크기로 구역을 나누고 숫자를 매김 => 이 숫자는 "주소"라고 부름물리 주소와 논리 주소물리 주소 : 메모리를 컴퓨터에 연결하면 0x0번지부터 시작하는 주소 공간논리 주소 : 사용자 관점에서 바라본 주소 공간사용자는 물리 주소를 몰라도 논리 주소로 물리 주소에 접근할 수 있음경계 레지스터메모리에는 수많은 프로세스가 올라오는데, 운영체제를 위한 공간은 따로 마련해둠. 이때,하드웨어적으로 운영체제 공간과 사용자 공간을 나누는 경계 레지스터를 만듦메모리 할당 방식유니 프로그래밍메모리 오버레이유니프로그램 방식에서 메모리보다 더 큰 프로그램을 실행시키는 방법큰 프로그램을 메모리에 올릴 수 있도록 잘라서 당장 실행시켜야 할 부분만 메모리에 올리고 나머지는 용량이 큰 하드디스크의 스왑 영역에 저장하는 기법멀티프로그래밍가변 분할 방식(세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식장점 : 내부 단편화 없음단점 : 외부 단편화 발생고정 분할 방식(페이징)프로세스의 크기와 상관 없이 메모리를 정해진 크기로 나누는 방식 장점 : 구현이 간단하며 오버헤드가 적음단점 : 작은 프로세스도 큰 영역에 할당돼서 공간이 낭비되는 내부 단편화 발생버디 시스템오늘날 가변 분할 방식과 고정 분할 방식을 혼합하여 단점을 줄인 방식2의 승수로 메모리를 분할해 메모리를 할당하는 방식가변 분할 방식처럼 프로세스 크기에 따라 할당되는 메모리 크기가 달라지고, 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단함고정 분할 방식처럼 내부 단편화가 발생하긴 하지만 많은 낭비가 발생하진 않음알고리즘재귀(recursion)어떠한 것을 정의할 때 자기 자신을 참조하는 것재귀 함수탈출 조건이 없으면 콜스택이라는 메모리 공간이 가득차서 자동으로 종료언제 종료될지 예측할 수 있게 하기 위해 탈출 조건, 즉 기저 조건이 반드시 필콜스택함수가 호출되면서 올라가는 메모리 영역, 스택이라고도 부름FILO(먼저 들어온 데이터가 나중에 나감) 특성을 가짐함수를 호출하면 함수는 콜스택에 올라가고, 종료되면 콜스택에서 제거됨버블 정렬(Bubble Sort)앞에 있는 숫자와 뒤에 있는 숫자를 비교해서 자리를 바꾸는 알고리즘데이터를 옆 데이터와 비교하면서 자리를 바꾸는게 버블이 일어나는 것 같아서 붙여진 이름시간복잡도 : O(n^2)장점 : 이해와 구현이 쉽다단점 : 성능이 좋지 않다.function BubbleSort(arr){ for(let i = 0; i < arr.length - 1; i++){ for(let j = 0; j < (arr.length - i - 1); j++){ if(arr[j] > arr[j + 1]){ let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }선택 정렬 (Sellection Sort)배열의 정렬되지 않은 영역을 순회하며 가장 작은 값을 탐색 후 교체하는 방법시간복잡도 : O(n^2)장점 : 이해와 구현이 쉽다단점 : 성능이 좋지 않다function SelectionSort(arr){ for(let i = 0; i < arr.length - 1; i++){ let minValueIndex = i; for(let j = i + 1; j < arr.length; j++){ if(arr[j] < arr[minValueIndex]){ minValueIndex = j; } } let temp = arr[i]; arr[i] = arr[minValueIndex]; arr[minValueIndex] = temp; } }회고칭찬하고 싶은 점이번 주부터 알고리즘 스터디를 시작하고, 또 매일 출근도 하면서 오늘 있었던 코딩테스트까지 일주일 간 이것저것 할일이 많았는데 포기하지 않고 이번주차 진도를 따라잡았다. CS 중에서도 운영체제는 개념이 잘 잡혀있지 않았는데, 공부를 하면서 운영체제에서 가장 중요한 개념인 프로세스와 CPU 스케줄링에 대해 어느정도 개념을 이해할 수 있는 일주일이었다.아쉬웠던 점이번주에도 역시나 매일매일 정해진 분량을 학습하기보다는 시간이 남는 타임에 몰아들은 경우가 더 많았던 것 같다.보완해야할 점남은 일주일도 바쁠 예정이기 때문에..현실적으로 매일매일 정해진 분량을 지켜서 노트까지 정리해가며 학습하기엔 벅차더라도, 지난 주처럼 너무 한번에 몰아서 하지 말고 출퇴근 시간을 이용해서 강의를 가볍게 보고 추후에 다시 복습하는 개념으로 노트를 정리하면 좋을 것 같다.

워밍업클럽･CS･발자국

[인프런 워밍업클럽 CS 2기] 1주차 발자국👣

1주차 학습 내용운영체제운영체제의 구조커널프로세스, 메모리, 저장 장치 등을 관리사용자가 직접 접근하지 못하고, 인터페이스로만 접근 가능인터페이스GUI(Graphic User Interface)GLI(Command Line Interface)시스템콜어플리케이션은 시스템콜을 활용해 커널에 접근드라이버하드웨어와 커널의 인터페이스 컴퓨터 하드웨어와 구조메인보드 : 다른 하드웨어를 연결하는 장치로, 장치 간 데이터 전송은 메인보드의 버스가 담당CPU(Central Processing Unit, 중앙 처리 장치)산술논리 연산 장치(ALU) : 실제 데이터 연산 담당제어 장치(Control Unit) : 모든 장치들의 동작을 지시, 제어레지스터: CPU 내에서 계산을 위해 임시로 보관메모리RAM(Random Acess Memory) : 전원을 끄면 데이터가 날아감, 메인 메모리로 사용, 랜덤한 위치의 어떤 데이터를 읽든 속도가 동일ROM(Read Only Memory) : 전원을 꺼도 데이터 보관 가능, 컴퓨터 부팅 관련 바이오스 저장부팅과정컴퓨터 전원 누름 -> ROM에 저장된 BIOS 실행 -> 주요 하드웨어 이상 여부 체크 -> 이상이 없으면 부트 로더 실행 -> 운영체제를 메모리로 불러오기 -> 바탕화면이 보임인터럽트CPU 입출력 명령이 들어왔을 때 언제 완료되는지 계속 확인해야하는 폴링 방식의 단점을 해결한 것CPU가 입출력 관리자에게 명령을 내리고 자기는 다른 작업함 -> 입출력이 완료되면 CPU에게 신호를 주고 CPU는 신호를 받아서 ISR 실행시켜 작업 완료 프로그램과 프로세스프로그램하드디스크와 같은 저장장치에 저장된 명령문의 집합저장 장치만 사용하므로 수동적인 존재프로세스하드디스크에 저장된 프로그램이 메모리에 올라갔을 때, 즉 실행 중인 프로그램메모리, CPU 사용 및 입/출력 등 능동적인 존재code, data, stack, heap 영역으로 구성멀티프로그래밍과 멀티프로세싱멀티프로그래밍 : 메모리에 여러 개의 프로세스가 올라온 것멀티프로세싱 : CPU가 여러 개의 프로세스를 처리하는 것PCB(Process Control Block)프로세스의 정보를 가지고 있는 것으로, 연결리스트 자료구조로 저장됨.포인터, 프로세스 상태, 프로세스 ID, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보, CPU 스케줄링 정보 등을 저장프로세스 상태생성 -> 준비 -> 실행 -> *(대기 -> 준비 -> 실행 ->) 완료대기 상태: 입출력 요청이 들어오면 입출력이 완료될때까지 기다리는 상태컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경됨쓰레드요구하는 작업의 수가 늘어나면 프로세스의 수가 늘어나고, 프로세스의 수만큼 PCB, 코드, 데이터, 스택, 힙 영역을 만들어줘야해서 무거워짐 => 이를 해결하기 위해 쓰레드 고안프로세스 내에 1개 이상 존재하며, PCB, 코드, 데이터, 힙 영역을 공유함CPU 스케줄링운영체제가 모든 프로세스에게 CPU를 할당하거나 해제하는 작업어떤 프로세스에게 CPU 리소스를 줄지, 얼마의 시간동안 CPU를 할당할지를 고려함Burst : 한 작업을 연속적으로 처리하는 것으로, 보통 작업 처리에 필요한 시간을 의미 (CPU Burst, I/O Burst)스케줄링 목표리소스 사용률 높이기, 오버헤드 최소화, 공평성, 처리량, 대기 시간, 응답 시간서로 상반되는 상황이 있기 때문에 사용하는 시스템에 따라서 목표를 다르게 설정CPU 스케줄링 알고리즘 - FIFOFirst In First Out, 먼저 들어온 작업이 먼저 나간다프로세스의 Burst Time에 따라 성능차이가 심하게 나므로 현대 운영체제에서 잘 쓰이지 않고 일괄처리 시스템에서 쓰임알고리즘자료구조와 알고리즘자료구조 : 데이터가 어떤 구조로 저장되고 어떻게 사용되는지를 나타냄알고리즘 : 어떤 문제를 해결하기 위한 확실한 방법자료구조에 따라 알고리즘이 달라지므로, 상황에 맞는 적절한 자료구조를 선택하고 이에 맞는 알고리즘을 적용할 줄 알아야함시간복잡도최선 : 빅-오메가, 평균 : 빅-세타, 최악 : 빅-오주로 빅-오 표기법을 많이 사용함성능 : O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)표기법계산에 가장 많은 영향을 미치는 항만 표기상수는 큰 의미 없음배열일반적인 배열크기가 정해져있고, 정해진 크기만큼 연속적인 메모리 공간에 값을 할당운영체제는 가장 첫번째 주소만 기억함참조 성능은 O(1), 삭제, 삽입 성능은 좋지 않음자바스크립트의 배열 상황에 따라서 연속적, 불연속적으로 메모리 할당하는데 대부분 불연속적으로 할당(내부적으로 연결)장점읽기, 쓰기와 같은 참조에는 O(1)의 성능을 가짐단점크기 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있음데이터의 삽입, 삭제가 비효율적임연결리스트배열의 단점을 해결하기 위해 저장하려는 데이터를 메모리 공간에 분산해 할당하고, 데이터를 서로 연결해주면 됨 => Node를 만들어 수행Node의 구조 : data를 담는 변수, 다음 노드를 가리키는 변수장점배열에서 초기 크기를 알아야하는 단점이 없음중간에 데이터를 삽입 혹은 삭제하려면, 특정 노드의 다음 가리키는 노드만 바꿔주면 됨단점데이터들이 전부 떨어져있기 때문에 바로 접근하기 힘듦 => O(n)의 성능스택(Stack)First In Last Out(FILO)으로, 먼저 들어간 데이터가 가장 나중에 나오는 규칙이 있음Redo, Undo 기능, 괄호짝 검사 등에 사용큐(Queue)First In First Out(FIFO)로, 먼저 들어간 데이터가 먼저 나오는 규칙이 있음계산대에 줄을 서는 경우, 맛집 대기줄 등 일렬로 기다리는 줄을 생각하면 됨덱(Deque)데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조해시테이블(Hash Table)해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)라고도 불림해시와 테이블이 합쳐진 자료구조테이블을 그냥 배열에 저장하면, 낭비되는 공간이 발생할 수 있음테이블의 기존 인덱스를 순차적인 인덱스로 만들기 위해 어떤 계산을 하는 함수를 해시라고 함key만 알면 value에 O(1)의 성능으로 읽기가 가능삽입, 삭제, 수정도 O(1)장점빠른 데이터 탐색, 삽입, 삭제를 할 수 있음단점공간의 효율성이 좋지 않음좋은 해시 함수의 구현이 필수적임셋(Set)데이터의 중복을 허용하지 않는 자료구조해시 테이블을 이용하므로 쉽게 구현 가능해시 테이블을 사용한다고 해서 Hash Set이라고도 불림value 값은 사용하지 않고 key만 사용해서 구현함(key가 데이터)회고칭찬하고 싶은 점강의를 허투루 듣지 않기 위해서 강의 노트를 작성하면서, 좀 더 궁금한 점이 생기면 의문점을 작성해두고 추가로 찾아보는 등 디테일한 이해를 위해 노력했다. 아쉬웠던 점휴일이나 주말 등 강의를 들을 시간이 넉넉한 때를 생각하면서 당일에 들어야하는 분량을 미루는 일이 잦았다.보완해야할 점퇴근 후 피곤하더라도 완전히 그날 강의를 안듣기 보다는, 한 강의라도 들으면서 꾸준히 강의를 수강하는 습관을 들이도록 노력하자!

워밍업클럽･CS･발자국

[(Daily 빠타박스)인프런 워밍업 클럽 2기] - CS 전공지식을 시작하는 글_1일차

인프런 워밍업 클럽 CS얼마전 본 면접에 나는 그냥 딱히 신경 쓰지 않았다. 나의 실력이 이정도구나..이런 질문에 이런 것 밖에 답변을 하지 못하는구나. 너무 준비되지 못했고 기초가 부족하다 느꼈다... 그러다 우연치 않게 보게된 워밍업 클럽 처음엔 무료인줄 알았다..그러나 스터디 그룹에 초대되고 그런 과정이 무료라는 것이지 절대 세상에 무료라는 것은 없다. 그냥 40% 할인권을 주었고그것으로 구매하여 저렴하게 강의를 수강할 수 있었다. 감자라는 강의자 분은 정말 퀄리티 좋은 강의를 올리시고 계신다는 것을 일단 동영상에 노력이 어마어마 하게 들어갔음을 알 수 있었다. 감자강의자님 로드맵 CS일단 강의 자체는 좋아보였고, 리뷰도 정말 좋게 쓰여져 있다. 솔직히 믿을만 한가. 싶기도 했지만. 나는 좀 인강 스타일이 까다롭게 잘 안맞아서... 이 30대에 듣는 인강을 신중히 고르는 편이였다. 리뷰 내용도 일단 보고 고민을 많이했다. 널널한개발자 님의 강의를 볼지 이것을 할 지 그러나 그냥 해보자 싶었다.강의 커리큘럼을 비교해 보면서 들어오게 되었고,11월 1일 까지 마감이라. 딱 마침 내가 다시 학원에 가게 될 시기랑 겹치지 않아서.(갈지 안갈지 지금 쓰는 시점에서 아직 정하지는 않았다만..) 그렇게 초대된 디스코드를 통해서 OT도 진행하였고, 확실히 제대로 진행하는 스터디 클럽인 만큼 신중히 잘 하는 것 같았다.시간표도 주어지고 준비가 되어있는 듯 했다. 약 한달간의 커리큘럼과정이였으나.이것이 어쨋든 자기주도학습의 일환이다. 우리가 들어야 한다. 정보를 제공해주었으니. 그래서 시작해본다.내 스스로의 위치에서 발전할 수 있기를 어디서나 중요한건 복습이다. 복습되지 않으면 쉽지 않을 수 있다.내가 간과하는 것이 그런것이다. 반복학습을 싫어하기에. 힘들어한다.하지만 해야하만 한다... 한번 진행해보자... 9월 30일을 기점으로 1일차가 시작되고 그것을 해내기 위해 글을 써본다.또한 정보처리기사 실기가 잡혀있는데. 병행해서 해야만한다.

컴퓨터 구조･인프런워밍업클럽･스터디모임･감자･빠타박스･언리얼엔진･CS지식･CS･게임개발자

면접을 위한 CS전공지식 노트 [ 운영체제와 컴퓨터 ]

1. 운영체제와 컴퓨터3.1.1운영체제의 역할CPU 스케쥴링과 프로세스 관리CPU 소유권을 어떤 프로세스에 할당 할지프로세스의 생성과 삭제자원 할당 및 반환 관리메모리 관리한정된 메모리에 어떤 프로세스를 할당해야 하는지디스크 파일 관리디스크 파일을 어떠한 방법으로 보관 할지I/O 디바이스 관리마우스, 키보드 와 컴퓨터간에 데이터를 주고 받는 것을 관리구조유저 프로그램 < GUI = 시스템 콜 = 커널 = 드라이브 < 하드웨어— GUI, 시스템 콜, 커널, 드라이브 ) 운영체제GUI가 없고 CUI만 있는 리눅스GUI : 사용자가 전자 장치와 상호 작용 하는 사용자 인터페이스의 형태, 단순 명령창이 아닌 아이콘을 마우스로 클릭하는 단순 동작으로 컴퓨터와 상호작용드라이버 : 하드웨어를 제어하기 위한 소프트웨어CUI : 그래픽이 아닌 명령어로 처리하는 인터페이스시스템 콜운영 체제가 커널에 접근하기 위한 인터페이스유저 프로그램이 운영체제의 서비스를 받기 위해 커널 함수를 호출 할 때 쓴다.유저 프로그램이 I/O 요청으로 트랩(trap)을 발동하면 올바른 I/O 요청인지 확인 후 유저 모드가 시스템 콜을 통해 커널 모드로 변환되어 실행된다.이 때 유저 모드에서 파일을 읽지 않고 커널 모드로 들어가 파일을 읽고 다시 유저 모드로 돌아가 그 뒤에 있는 유저 프로그램의 로직을 수행한다. - 이 과정을 통해 컴퓨터 자원에 대한 직접접근을 차단할 수 있고 프로그램을 다른 프로그램으로부터 보호할 수 있다.I/O요청 : 입출력 함수, 데이터베이스, 네트워크 파일 접근 등에 관한 일메모리(프로세스, 스레드) ⇒ 시스템 콜 ⇒ 커널 ⇒ OS프로세스나 스레드에서 운영체제로 어떠한 요청을 할 때 시스템콜이라는 인터페이스와 커널을 거쳐 운영체제에 전달 된다.시스템 콜은 하나의 추상화 계층시스템 콜을 통해 네트워크 통신이나 데이터베이스와 같은 낮은 단계의 영역 처리에 대한 부분을 많이 신경 쓰지 않고, 프로그램을 구현할 수 있는 장점이 있다.modebit시스템 콜이 작동될 때 modebit을 참고해서 유저 모드와 커널 모드를 구분한다.I 또는 0의 값을 가지는 플래그 변수카메라, 키보드 등 I/O 디바이스는 운영체제를 통해서만 작동해야 한다.ex) 카메라를 켜는 프로그램 → 만약 유저모두를 기반으로 카메라가 켜진다면, 사용자가 의도하지 않았는데 공격자가 카메라를 갑자기 켤 수 있는 등 나쁜 짓을 하기가 쉽다. 물론 커널 모드를 거쳐 운영체제를 통해 작동한다고 해도 100% 막을 수는 없지만, 운영체제를 통해 작동하게 해야 막기가 쉽다.이를 위한 장치가 modebit이다.modebit의 0은 커널모드 , 1은 유저 모드라고 설정한다.유저 프로그램이 카메라를 이용하려고 할 때 시스템 콜을 호출하고 modebit을 1에서 0으로 바꾸며 커널 모드로 변경한 후 카메라 자원을 이용한 로직을 수행한다. 이후 modebit을 0에서 1로 바꿔서 유저모드로 변경하고 이후 로직을 수행한다.유저 모드 : 유저가 접근할 수 있는 영역, 제한적으로 두며 컴퓨터 자원에 함부로 침범하지 못하는 모드커널 모드 : 모든 컴퓨터 자원에 접근할 수 있는 모드커널 : 운영체제의 핵심, 시스템콜 인터페이스를 제공한다, 보안, 메모리, 프로세스, 파일 시스템, I/O 디바이스, I/O요청 관리 등 운영체제의 중추적인 역할 수행3.1.2 컴퓨터의 요소컴퓨터CPU, DMA컨트롤러, 메모리, 타이머, 디바이스 컨트롤러 등으로 이루어져있다.CPU(Central Processing Unit)산술 논리 연산 장치, 제어장치, 레지스터로 구성되어 있는 컴퓨터 장치인터럽트에 의해 단순히 메모리에 존재하는 명령어를 해석해서 실행하는 일꾼관리자 → 커널 → HDD or SSD,(프로그램) → 메모리(RAM) 프로세스 < = > 일꾼관리자 역할을 하는 운영체제의 커널이 프로그램을 메모리에 올려 프로세스로 만들면 일꾼인 CPU가 이를 처리한다.제어장치 (CU, Control Unit)프로세스 조작을 지시하는 CPU의 한 부품입출력장치 간 통신을 제어하고 명령어들을 읽고 해석하며 데이터 처리를 위한 순서를 결정한다.레지스터CPU안에 있는 매우 빠른 임시기억장치CPU와 직접 연결되어 있으므로 연산 속도가 메모리보다 수십 배에서 수백 배 까지 빠르다.CPU는 자체적으로 데이터를 저장할 방법이 없기에 레지스터를 거쳐 데이터를 전달한다.think. 그럼 레지스터에 저장되고, CPU로 보내기에 이전 데이터도 잠시 머무를 수 있어서 빠르게 불러 올 수도 있고, 저장 장치 이기에, 이미 처리된 데이터가 저장되어서 미리 빠르게 불러 들일 수 있을 것같다.?산술논리연산장치(ALU, Arihmetic Logic Unit)덧셈, 뺄셈, 같은 두 숫자의 산술 연산과 배타적 논리합, 논리곱 같은 논리 연산을 계산 하는 디지털 회로CPU의 연산처리제어장치, 레지스터, 산술논리연산장치를 통해 연산하는 예시제어장치가 메모리에 계산할 값을 로드한다, (레지스터에도 로드한다)제어장치가 레지스터에 있는 값을 계산하라고 산술논리연산장치에 명령한다.제어장치가 계산된 값을 다시 레지스터에서 메모리로 계산한 값을 저장한다.인터럽트어떤 신호가 들어왔을 때 CPU를 잠깐 정지시키는 것발생종류키보드, 마우스, 등 I/O 디바이스로 인한 인터럽트0으로 숫자를 나누는 산술 연산에서의 인터럽트프로세스 오류인터럽트가 발생되면 인터럽트 핸들러 함수가 모여 있는 인터럽트 벡터로 가서인터럽트 핸들러 함수가 실행된다.인터럽트 간에는 우선순위가 있고 우선순위에 따라 실행되며,인터럽트는 하드웨어 인터럽트, 소프트웨어 인터럽트 로 나뉜다.**하드웨어 인터럽트**키보드를 연결하다거나, 마우스를 연결하는 일 등의 I/O 디바이스에서 발생하는 인터럽트인터럽트 라인이 설계된 이후 순차적인 인터럽트 실행을 중지하고 운영체제에 시스템콜을 요청해서 원하는 디바이스로 향해 디바이스에 있는 작은 로컬 버퍼에 접근하여 일을 수행한다.**소프트웨어 인터럽트**트랩(trap)이라고도 한다,프로세스 오류 등으로 프로세스가 시스템콜을 호출할 때 발동한다.DMA 컨트롤러I/O 디바이스가 메모리에 직접 접근할 수 있도록 하는 하드웨어 장치CPU에만 너무 많은 인터럽트 요청이 들어오기 때문에 CPU 부하를 막아 주며, CPU의 일을 부담하는 보조 일꾼이라 보면 된다.하나의 작업을 CPU와 DMA컨트롤러가 동시에 하는 것을 방지한다.메모리전자회로에서 데이터나 상태, 명령어 등을 기록하는 장치RAM(Random Access Memory)를 메모리라 한다.CPU는 계산을 담당하고 메모리는 기억을 담당한다.비유 :CPU는 일꾼, 메모리는 작업장, 작업장의 크기가 곧 메모리의 크기작업장이 클수록 창고에서 물건을 많이 가져다 놓고 많은 일을 할 수 있듯이메모리가 크면 클수록 많은 일을 동시에 할 수 있다.타이머몇 초 안에는 작업이 끝나야 한다는 것을 정하고 특정 프로그램에 시간제한을 다는 역할시간이 많이 걸리는 프로그램이 작동할 때 제한을 걸기 위해 존재한다.디바이스 컨트롤러(Device Controller)컴퓨터와 연결되어 있는 I/O 디바이스들의 작은 CPU

게임 프로그래밍･네트워크･운영체제･CS･코딩･게임개발･it

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

운영체제세그멘테이션(배치정책)메모리를 논리적 단위(세그먼트)로 분할각 세그먼트는 다양한 크기 가능외부 단편화 문제 발생 가능페이징(배치정책)메모리를 동일한 크기의 페이지로 분할물리 메모리와 가상 메모리 간 매핑내부 단편화 발생 가능, 외부 단편화 해결페이지드 세그멘테이션(배치정책)세그멘테이션과 페이징 결합세그먼트를 페이지 단위로 나눔유연성과 효율성 향상디맨드 페이징(가져오기 정책)필요한 페이지만 메모리에 로드페이지 부재 시 디스크에서 가져옴메모리 사용 효율성 증가페이지 교체정책FIFO, LRU, LFU 등 다양한 알고리즘새 페이지 로드 시 어떤 페이지를 교체할지 결정페이지 부재율 최소화 목표스레싱과 워킹셋스레싱: 과도한 페이지 교체로 성능 저하워킹셋: 프로세스가 자주 참조하는 페이지 집합워킹셋 관리로 스레싱 방지주변장치(I/O 디바이스, 저장장치)CPU, 메모리 외 하드웨어 장치입력, 출력, 저장 기능 수행인터럽트 기반 동작마우스/키보드사용자 입력 장치이벤트 기반 동작인터럽트 처리 필요하드디스크/Flash Memory(SSD)하드디스크: 기계식, 대용량, 저렴SSD: 전자식, 고속, 고가비휘발성 저장 장치파일과 파일시스템파일: 관련 데이터의 논리적 집합파일시스템: 파일 저장, 조직, 검색 관리메타데이터 관리 포함디렉토리파일들의 논리적 컨테이너계층적 구조 (트리 구조)파일 검색, 그룹화 용이파일과 디스크파일 할당 방식: 연속, 연결, 인덱스 할당빈 공간 관리디스크 스케줄링 알고리즘 자료구조와 알고리즘정렬 - 삽입정렬원리: 정렬된 부분에 새 원소를 적절한 위치에 삽입시간 복잡도: 평균 및 최악 O(n^2), 최선 O(n)특징: 작은 데이터셋에 효율적, 부분 정렬된 배열에 유리안정적 정렬 알고리즘정렬 - 병합정렬원리: 분할 정복 방식, 작은 부분으로 나누고 병합하며 정렬시간 복잡도: 항상 O(n log n)특징: 대규모 데이터 정렬에 효율적, 추가 메모리 필요안정적 정렬 알고리즘정렬 - 퀵정렬원리: 피벗 선택 후 분할 정복 방식으로 정렬시간 복잡도: 평균 O(n log n), 최악 O(n^2)특징: 실제 구현에서 매우 빠름, 불안정 정렬피벗 선택 방법이 성능에 큰 영향동적 프로그래밍 - 메모이제이션원리: 계산 결과를 저장하고 재사용 (캐싱)특징: 주로 하향식(top-down) 접근법장점: 중복 계산 방지로 효율성 향상적용: 피보나치 수열, 최장 공통 부분 수열 등동적 프로그래밍 - 타뷸레이션원리: 작은 부분 문제부터 해결하며 표를 채움특징: 상향식(bottom-up) 접근법장점: 일반적으로 메모리 사용량이 적음적용: 냅색 문제, 최단 경로 문제 등3주차 후기지난 주차보다는 익숙한 단어들이 많이 보였다. 그래서 조금 가벼운 마음으로 시작했다가 어김없이 혼돈으로 접어드는 루트의 반복이었던 주였다. 언제쯤 이 단어와 개념과 친구 먹을 수 있을까 😂운영체제에서는 가상 메모리에 대해 배우면서 세그멘테이션과 페이징의 개념을 잡고, 메모리 관리 기법의 발전 과정을 따라 공부해 보았다. 입출력 장치와 파일 시스템에 대해 공부하면서는 하드웨어와 소프트웨어의 상호작용을 중점으로 공부했는데, SSD와 하드디스크에 대한 내용을 공부할 때는 노트북 살 때의 경험을 떠올리면서 들으니 다른 파트보다 조금 더 재밌게 들을 수 있었던 것 같다.알고리즘에서는 다양한 정렬 방법들과 동적 프로그래밍에 대해 배웠다. 정렬에 대해 공부할 때는 각각의 장단점을 비교하면서 언제 적합하게 사용할 수 있을지를 주요 포인트로 공부했다. 이미 이전에도 몇 번 봤던 개념이라 막 어렵다는 느낌은 없었다. 그런데 동적 프로그래밍이 개인적으로 좀 어려웠던 것 같다. 동적인건 언제나 어렵다, 다 정적이었으면 좋겠다 라고 궁시렁 거리면서 공부했다. 그래도 감자쌤과 함께 찬찬히 공부하니 완벽하게는 아니어도 어렴풋이 개념은 잡을 수 있었던 것 같다. 인프런 워밍업 클럽 2기 후기한 번도 공부해보지 않은 CS를 공부해보겠다고 시작한 워밍업 클럽은 생각보다 빠르게 지나갔다. 회사 일이랑 이직 준비랑 다른 스터디에 엄청 치이면서도 워밍업 클럽을 포기하지 않은 건, 하루에 수행할 수 있는 적합한 학습량과 감자쌤의 친절나긋한 설명 덕분이 아닐까 싶다. 그리고 워밍업 클럽을 같이 진행하면서 열심히 하시는 다른 분들의 모습에도 많은 자극을 받았던 것 같다. 3주 동안 감자쌤과 함께 배운 내용들을 완벽하게 이해했다고 할 수는 없지만, 전반적인 내용을 파악했고 어느 부분이 어려운지도 알았으니 앞으로 공부하면서 부족한 부분들을 더 채워나가야겠다.

알고리즘 · 자료구조･인프런･인프런워밍업클립･CS･운영체제･자료구조･알고리즘･감자･3주차

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

운영체제1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.RAM: 빠른 읽기/쓰기가 가능하지만, 전원이 꺼지면 내용이 사라집니다.ROM: 읽기 전용이며, 내용이 영구적으로 보존됩니다.캐시: CPU와 가까이 있어 매우 빠르지만, 비용이 높습니다.가상 메모리: 하드디스크 일부를 RAM처럼 사용합니다. 속도는 느리지만 큰 용량을 사용할 수 있습니다.2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터(Boundary Register)입니다. 이것이 없으면 프로그램들이 운영체제 영역을 무단으로 접근할 수 있어 문제가 생길 수 있습니다.3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?고정 분할: 설정과 관리가 쉽습니다. 하지만 메모리 낭비가 심할 수 있습니다.가변 분할: 메모리를 효율적으로 사용할 수 있습니다. 다만 관리가 조금 복잡할 수 있습니다.4. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스래싱(Thrashing)이라고 합니다. 시스템이 너무 바빠서 정작 실제 작업은 못 하는 상황을 말합니다.5. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.네, 필요합니다. 전원이 꺼져도 데이터를 유지해야 하기 때문입니다. 하지만 RAM만으로 운영되는 특수한 시스템도 있긴 합니다. 이를 "RAM 디스크" 또는 "메모리 전용 시스템"이라고 부릅니다. 주로 아주 빠른 처리 속도가 필요하거나, 데이터의 영구 저장이 필요 없는 특수한 경우에 사용됩니다.6. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일을 삭제해도 실제 데이터는 지워지지 않고, 그 공간을 재사용 가능하다고 표시만 합니다. 그래서 덮어쓰기 전이라면 복구가 가능합니다.자료구조와 알고리즘1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬: 구현이 쉽지만, 속도가 느립니다 (O(n^2))선택 정렬: 구현이 쉽지만, 역시 속도가 느립니다 (O(n^2))삽입 정렬: 작은 데이터에 효과적이며, 평균/최악의 경우 O(n^2)입니다병합 정렬: 안정적이고 항상 O(n log n)의 성능을 보이지만, 추가 메모리가 필요합니다퀵 정렬: 평균적으로 빠르며 O(n log n), 최악의 경우 O(n^2)의 성능을 보입니다2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션을 사용하는 것이 좋습니다. 메모이제이션은 재귀 호출을 많이 하기 때문에 스택 오버플로우가 발생할 수 있어요. 반면 타뷸레이션은 반복문으로 해결하기 때문에 메모리를 덜 사용합니다.

알고리즘 · 자료구조･인프런･인프런워밍업클럽･CS･운영체제･자료구조･알고리즘･감자･3주차

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

이번 주에는 운영체제와 자료구조 및 알고리즘에 대한 심도 깊은 학습을 진행하였다. 특히 운영체제의 기초부터 고급 개념까지 폭넓게 다루며, 이론과 실습을 통해 이해도를 높였다. 운영체제우선, 메모리의 종류에 대한 이해를 심화했다. 레지스터, 캐시, 메인 메모리, HDD/SSD 각각의 속도 차이를 인지하면서, 각 메모리가 시스템에서 어떤 역할을 하는지 명확히 알게 되었다. 특히, 물리주소와 논리주소의 개념을 통해 메모리 관리의 중요성을 깨달았다. 메모리 할당 방식으로는 가변 분할 방식과 고정 분할 방식을 배웠고, 두 방식의 장단점을 이해하며 현대 시스템에서 왜 버디 시스템과 같은 혼합 방식을 사용하는지에 대한 통찰도 얻었다. 가상 메모리의 원리는 매우 흥미로웠다. 프로그램이 실제 메모리 크기와 상관없이 실행될 수 있게 해주는 이 기술을 통해, 메모리 사용의 효율성을 크게 향상시킬 수 있다는 점을 배웠다. 또한, 디맨드 페이징, 세그멘테이션, 페이징 등 메모리 주소 변환 기법에 대한 이해가 깊어지면서, 이들이 시스템 성능에 미치는 영향을 고려할 수 있게 되었다. 특히, 스레싱과 워킹셋 개념을 통해 과도한 스왑 작업으로 인한 성능 저하 현상을 이해하게 되었다. 이와 함께 주변장치의 구분 및 파일 시스템의 구조에 대해서도 배웠으며, 파일 관리의 중요성을 다시 한번 깨닫게 되었다. 다양한 파일 구조의 특징을 정리하면서 각 구조의 장단점을 비교하고, 실제 응용에서의 활용 가능성을 고민해 보았다. 자료구조와 알고리즘자료구조와 알고리즘에서는 정렬 알고리즘의 기초를 다지는 데 주력했다. 버블, 선택, 삽입 정렬과 같은 구현이 간단하지만 성능이 떨어지는 알고리즘과, 병합 정렬 및 퀵 정렬과 같은 성능이 뛰어난 알고리즘의 차이를 비교하며 각 알고리즘의 특징을 파악했다. 각 정렬 알고리즘의 시간 복잡도를 분석하면서, 어떤 상황에서 어떤 알고리즘이 적합한지를 고민해보는 기회가 되었다. 또한, 동적 프로그래밍의 두 가지 기법인 메모이제이션과 타뷸레이션을 깊이 있게 이해하게 되었다. 메모이제이션은 재귀를 사용하여 중복 계산을 피할 수 있게 해주며, 타뷸레이션은 필요한 값을 모두 미리 계산해 테이블에 저장하는 방식으로, 각각의 장단점과 적용 가능성을 분석하는 데 중점을 두었다. 3주차 회고이번 주는 운영체제와 자료구조 및 알고리즘 강의를 모두 마치게 되어 매우 기쁘다. 강의를 통해 시스템의 작동 원리와 알고리즘의 이론을 명확히 이해할 수 있었고, 혼자서는 경험하지 못했을 깊이 있는 학습이 이루어졌다. 특히 가상 메모리와 동적 주소 변환 개념은 흥미롭고 유용했다. 메모리 관리의 중요성을 깨닫고, 스레싱과 워킹셋의 이해를 통해 성능 최적화에 대한 고민을 하게 되었다. 강의를 통해 배운 이론들을 실제로 어떻게 적용할 수 있을지 고민하며, 더 나아가 이 지식을 바탕으로 실무에서도 활용할 수 있는 방법을 찾아보려 한다.강의를 제작하고 이끌어주신 감자 님에게도 깊은 감사의 인사를 전하고 싶다. 향후 더 많은 강의를 수강할 기회를 기대하며, 앞으로도 계속해서 배우고 성장해 나갈 예정이다. 이 경험이 나의 개발자로서의 길에 큰 밑거름이 될 것이라 확신한다.😁

알고리즘 · 자료구조･워밍업클럽･CS

[인프런 워밍업 클럽 2기 - CS] 3주차 미션

운영체제1. 메모리의 종류는 어떤 것들이 있나요? 각 메모리의 특징도 함께 적어주세요.• 레지스터: CPU 내부에 있는 가장 빠른 메모리로, 휘발성이다. CPU가 데이터를 처리할 때 메인메모리에서 데이터를 가져와 레지스터에서 연산을 수행한다.• 캐시: 레지스터보다는 느리지만 메인메모리보다는 빠른 메모리로, 필요한 데이터를 미리 저장해 CPU의 메모리 접근 시간을 줄인다.• 메인메모리 (RAM): 실제 운영체제와 실행 중인 프로세스가 올라가는 공간으로, 휘발성이다. 가격이 비싸기 때문에 실행 중인 프로그램을 저장하는 용도로만 사용된다.• 보조저장장치 (HDD/SSD): 비휘발성 메모리로, 데이터를 영구적으로 저장하는 장치이다. 메모리 중에서 가장 느리지만, 대용량 저장이 가능하고 가격이 저렴하다. 2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 무엇인가요?경계 레지스터이다. 이 레지스터는 운영체제 영역을 보호하며, 프로세스가 경계를 벗어나면 그 프로세스를 종료시킨다. 3. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 무엇인가요?• 가변 분할 방식: 메모리를 프로세스 크기에 맞게 할당하므로 내부 단편화가 발생하지 않는다. 그러나 프로세스 종료 후 남은 공간이 연속적이지 않으면 외부 단편화가 발생할 수 있다.• 고정 분할 방식: 메모리를 고정된 크기로 나누기 때문에 구현이 간단하고 오버헤드가 적다. 그러나 작은 프로세스도 큰 메모리 공간에 할당되므로 내부 단편화가 발생한다. 4. CPU 사용률을 높이기 위해 멀티프로그래밍을 올렸지만, 스왑이 너무 자주 발생해 CPU 사용률이 0%에 가까워지는 현상을 무엇이라고 하나요?이 현상은 스레싱 (Thrashing)이라고 한다. 스왑이 너무 빈번하게 이루어져 CPU가 거의 사용되지 않는 상태를 의미한다. 5. HDD나 SSD는 컴퓨터를 실행시키는 데 꼭 필요한가요?꼭 필요하지는 않다. 컴퓨터 부팅 시 운영체제를 메모리로 불러오는 저장장치가 필요하지만, 이 저장장치가 반드시 HDD나 SSD일 필요는 없다. 예를 들어, USB에 운영체제를 설치하여 이를 통해 부팅할 수도 있다. 6. 파일을 삭제해도 포렌식으로 복구할 수 있는 이유는 무엇인가요?파일을 삭제하면 실제로는 파일 테이블의 헤더만 삭제되고, 데이터 블록은 그대로 남아 있기 때문이다. 복구를 원치 않는 경우, 데이터를 여러 번 덮어씌워야 한다. 자료구조와 알고리즘1. 지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.• 버블 정렬 (Bubble Sort):장점: 이해와 구현이 매우 간단하다.단점: 성능이 매우 나쁘다.시간 복잡도: O(n²).• 선택 정렬 (Selection Sort):장점: 이해와 구현이 간단하다.단점: 성능이 좋지 않다.시간 복잡도: O(n²).• 삽입 정렬 (Insertion Sort):장점: 구현이 쉽고, 적은 데이터에서는 효율적이다.단점: 많은 데이터에서는 성능이 떨어진다.시간 복잡도: O(n²).• 병합 정렬 (Merge Sort):장점: 안정적이며 성능이 우수하다.단점: 추가적인 메모리 공간이 필요하고, 구현이 다소 어렵다.시간 복잡도: O(nlogn).• 퀵 정렬 (Quick Sort):장점: 평균적으로 매우 빠르다.단점: 피벗 선택이 잘못되면 O(n²)까지 성능이 떨어질 수 있다.시간 복잡도: O(nlogn) (평균), O(n²) (최악). 2. 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.메모리가 부족한 경우 타뷸레이션 방식을 선택하는 것이 적절하다.메모이제이션은 재귀 호출로 인해 스택 오버플로우 위험이 있으며, 메모리 사용량이 많아질 수 있다. 반면, 타뷸레이션은 반복문을 사용하여 미리 정해진 메모리 테이블로 문제를 해결하므로, 메모리 사용을 더 효율적으로 관리할 수 있다!

알고리즘 · 자료구조･워밍업클럽･CS

워밍업 클럽 CS 3주차 발자국 : 운영체제

가상 메모리가상 메모리 개요가상 메모리는 부족한 물리 메모리를 효율적으로 사용하기 위한 기술로, 메모리 관리자가 가상 주소를 물리 주소에 매핑하여, 실제 물리 메모리보다 더 큰 메모리 공간을 사용할 수 있게 합니다. 이를 통해 각 프로세스는 독립적인 메모리 공간을 가지며, 안정성과 보안을 높입니다. 개발자는 물리 메모리의 크기나 위치에 신경 쓰지 않고, 0x0 번지에서 시작한다고 생각하며 프로그래밍할 수 있습니다. 실제 메모리 접근은 메모리 관리자가 처리하며, 프로세스는 물리 메모리에 직접 접근하지 않습니다. 가상 메모리의 크기는 CPU의 비트 수에 따라 결정됩니다. 예를 들어, 32비트 CPU는 4GB의 가상 메모리 공간을 제공합니다. 물리 메모리가 부족할 때는, 일부 내용을 하드디스크의 스왑 영역으로 옮겨 필요한 경우 다시 가져와 실행합니다. 이 과정을 동적 주소 변환이라 부르며, 이를 통해 물리 메모리 부족 문제를 해결할 수 있습니다. 메모리 관리는 가상 주소를 물리 주소로 변환하고, 프로세스의 메모리 배치, 스왑 영역 처리 등 복잡한 과정을 수행합니다. 물리 메모리 0번지는 운영체제에 할당되며, 프로세스는 사용할 수 없습니다. 가상 메모리 시스템에서는 메모리를 고정 크기로 나누어 프로세스에 할당하는 페이징과, 가변 크기로 할당하는 세그멘테이션 방식을 사용합니다. 페이징은 내부 단편화, 세그멘테이션은 외부 단편화의 단점이 있으며, 이를 보완한 세그멘테이션-페이징 혼용 기법이 사용됩니다. 가상 주소는 메모리나 스왑 영역에 위치하며, 메모리 관리자는 가상 주소와 물리 주소를 1대1로 매핑해 관리합니다 배치 정책세그멘테이션세그멘테이션은 가변 분할 방식을 사용하여 메모리를 분할하는 기법입니다. 프로그램은 함수나 모듈 등으로 나뉘며, 각각의 세그먼트가 생성됩니다. 예를 들어, 메인 코드, 전역 데이터, 힙, 스택 등의 영역이 각각 독립적인 세그먼트로 구성됩니다. 이 세그먼트들은 물리 메모리에서 서로 인접하지 않아도 되지만, 프로세스는 이를 인접한 것처럼 인식합니다. 프로세스와 CPU가 바라보는 논리 주소는 실제 메모리 주소와 다르며, 이를 물리 주소로 변환하는 역할은 메모리 관리자(MMU)가 수행합니다. MMU는 세그멘테이션 테이블을 사용하여 논리 주소를 물리 주소로 변환합니다. 이 테이블에는 베이스 주소(Base Address)와 바운드 주소(Bound Address) 정보가 포함되어 있습니다. 논리 주소가 주어지면, 메모리 관리자는 해당 논리 주소가 속하는 세그먼트를 찾고, 세그멘테이션 테이블에서 해당 세그먼트의 베이스와 바운드 주소를 참조하여 물리 주소를 계산합니다. 논리 주소가 바운드 주소 범위 내에 있으면 베이스 주소와 더해져 물리 주소가 계산되며, 범위를 초과하면 메모리 침범 오류를 발생시켜 해당 프로세스를 종료합니다. 예시 1: CPU가 세그먼트 1번의 논리 주소 0x632로 접근메모리 관리자가 세그먼트 1번을 확인세그멘테이션 테이블에서 1번 세그먼트의 베이스 주소(5200)를 찾음논리 주소(632)와 바운드 주소(1000)를 비교하여 범위 내임을 확인논리 주소와 베이스 주소를 더해 물리 주소 5832로 변환 예시 2: CPU가 세그먼트 3번의 논리 주소 750으로 접근메모리 관리자가 세그먼트 3번을 확인논리 주소(750)가 바운드 주소(500)를 초과하므로 메모리 침범 오류 발생프로세스가 종료됨 세그멘테이션의 장점은 메모리를 가변적으로 나눌 수 있어 코드, 데이터, 스택, 힙 영역을 모듈로 처리할 수 있고, 각 영역에 대한 접근 보호와 공유가 용이하다는 점입니다. 반면, 단점은 가변 분할 방식에서 발생하는 외부 단편화입니다. 페이징페이징은 메모리 관리를 위한 고정 분할 방식으로, 외부 단편화 문제를 해결하기 위해 고안되었습니다. 페이징에서는 메모리를 일정한 크기의 페이지로 나누어 할당합니다. 모든 페이지의 크기가 동일하기 때문에 관리가 용이하며, 외부 단편화가 발생하지 않습니다. 대신, 페이지 크기보다 작은 데이터를 저장할 때는 내부 단편화가 발생할 수 있습니다. 논리주소와 물리주소논리주소공간: 사용자와 프로세스가 바라보는 주소 공간물리주소공간: 실제 메모리에서 사용되는 주소 공간논리주소공간과 물리주소공간은 일정한 크기의 페이지와 프레임으로 나뉘며, 두 공간은 매칭됩니다. 주소 변환 과정페이징에서도 메모리 관리자는 페이지 테이블을 사용해 논리주소를 물리주소로 변환합니다. 논리주소가 전달되면, 메모리 관리자는 해당 논리주소가 몇 번 페이지에 속하는지 확인하고, 페이지 번호와 오프셋을 이용해 물리주소를 계산합니다.논리주소에서 페이지 번호를 추출: 페이지 테이블의 인덱스 역할해당 인덱스를 참조해 프레임 번호를 가져옴오프셋을 더해 최종 물리주소로 변환페이징에서 페이지 테이블에 "invalid"로 표시된 페이지는 스왑 영역(하드디스크)에 저장되어 있다는 의미입니다.또한, 컨텍스트 스위칭 시, 운영체제는 페이지 테이블을 해당 프로세스에 맞게 업데이트해야 합니다. 32비트 CPU 주소 변환 예시가상 메모리의 크기는 약 4GB (2^32 바이트)가상 메모리를 16MB(2^24 바이트) 페이지로 나누면, 24비트는 페이지 크기, 나머지 8비트는 페이지 번호를 나타냅니다. 즉, 총 256개의 페이지가 존재하게 됩니다.물리 메모리는 가상 메모리와 동일한 크기로 페이지로 나뉘지만, 물리 주소 공간이 더 작아도 문제가 없습니다. 부족한 메모리는 스왑 처리로 해결되기 때문입니다. 주소 변환 예시 1: 논리주소 1000번지페이지 번호: 1000 / 16777216 = 0오프셋: 1000 % 16777216 = 1000페이지 테이블의 0번 인덱스를 참조해 프레임 3을 가져오고, 오프셋을 더해 물리주소를 구함.주소 변환 예시 2: 논리주소 31554432번지페이지 번호: 31554432 / 16777216 = 1오프셋: 31554432 % 16777216 = 14777216페이지 테이블의 1번 인덱스를 참조해 프레임 1을 찾아 물리주소로 변환. 페이징과 세그멘테이션의 차이페이지 크기: 페이징은 고정된 크기의 페이지를 사용하며, 세그멘테이션은 프로세스마다 다른 크기의 세그먼트를 가짐.단편화: 페이징에서는 내부 단편화가 발생하고, 세그멘테이션에서는 외부 단편화가 발생합니다.메모리 접근 방식: 세그멘테이션은 코드, 데이터, 스택, 힙 등 논리적 영역에 맞춰 나누지만, 페이징은 고정된 크기의 페이지로 나누기 때문에 특정 영역을 떼어내서 공유하거나 권한을 부여하기 어렵습니다. 페이징의 한계페이징에서 가장 신경 써야 하는 점은 페이지 테이블의 크기입니다. 각 프로세스는 고유한 페이지 테이블을 가지며, 프로세스 수가 많아질수록 페이지 테이블이 차지하는 메모리 공간도 증가합니다. 메모리 관리자 역시 물리 메모리 내의 운영체제 영역에 페이지 테이블을 저장하기 때문에, 페이지 테이블이 커지면 사용자 영역의 메모리가 부족해질 수 있습니다.따라서 페이지 테이블의 크기를 적절하게 유지하는 것이 매우 중요합니다. 페이지드 세그멘테이션페이지드 세그멘테이션은 세그멘테이션과 페이징의 장점을 결합한 메모리 관리 방식입니다. 세그멘테이션은 영역별로 메모리를 관리하고, 페이징은 메모리를 일정 크기로 나누어 관리 효율성을 높입니다. 이 방식은 두 기법의 이점을 활용할 수 있지만, 새로운 단점도 존재합니다. 장점세그멘테이션의 가변 분할 방식을 사용해 프로세스의 코드, 데이터, 스택, 힙 영역을 독립적으로 관리 가능. 각 영역에 대해 메모리 접근 보호 및 공유가 용이합니다.페이징의 고정 분할 방식을 통해 메모리를 효율적으로 관리하고 외부 단편화를 줄일 수 있습니다.단점이 기법의 단점은 메모리 접근이 두 번 이루어진다는 점입니다:세그멘테이션 테이블을 참조하여 세그멘트 정보를 가져올 때페이지 테이블을 참조하여 페이지 정보를 가져올 때이중 접근으로 인한 오버헤드가 발생할 수 있습니다. 메모리 접근 권한각 프로세스는 영역별로 읽기, 쓰기, 실행 권한이 다르게 부여됩니다:코드 영역: 읽기와 실행 권한만 있고, 수정이 불가능합니다.데이터 영역: 읽기와 쓰기 권한이 있으며, 실행 권한은 없습니다.스택 & 힙 영역: 읽기와 쓰기 권한이 있으나 실행 권한은 없습니다.이 권한은 가상 주소를 물리 주소로 변환할 때마다 확인되며, 만약 권한 위반이 발생하면 에러를 발생시키고 프로세스를 종료시킵니다. 페이지드 세그멘테이션의 주소 변환 과정세그멘트 번호를 가상 주소에서 추출하여 해당 세그먼트에 대한 메모리 접근 권한을 확인합니다.권한이 적합하면, 세그멘트에서 페이지 번호와 페이지 개수를 가져옵니다.페이지 번호로 페이지 테이블에 접근하여 해당 프레임 번호를 찾습니다.물리 메모리의 프레임에 접근해 오프셋을 더하여 최종 물리 주소를 계산합니다.만약 해당 프레임이 물리 메모리에 없다면, 스왑 영역에서 불러옵니다. 현대 운영체제는 페이징과 페이지드 세그멘테이션을 상황에 맞게 혼합하여 사용하고 있습니다. 페이지드 세그멘테이션의 장점은 두 기법의 이점을 취해 메모리 관리의 유연성과 효율성을 높이는 반면, 오버헤드로 인한 성능 저하를 피하기 위해 적절한 균형을 유지하는 것이 중요합니다. 가져오기 정책디멘드 페이징 정책디멘드 페이징은 프로세스 실행 시 필요한 데이터만 메모리에 올려서 실행하는 방식으로, 메모리 효율을 극대화하는 가져오기 정책입니다. 이 방법은 프로세스의 모든 데이터가 처음부터 메모리에 로드되지 않고, 필요한 시점에만 가져오므로 메모리 자원을 아낄 수 있습니다. 지역성 이론과 디멘드 페이징90:10 법칙에 따르면 프로그램은 90%의 시간을 10%의 코드에서 소모합니다. 이 원리를 지역성 이론으로 설명할 수 있는데, 지역성 이론에는 두 가지 중요한 개념이 있습니다:시간적 지역성: 최근에 접근한 데이터는 다시 접근할 가능성이 높다.공간적 지역성: 현재 접근한 데이터와 가까운 위치에 있는 데이터가 곧 접근될 가능성이 높다.디멘드 페이징은 이 이론을 바탕으로, 메모리에서 당장 필요하지 않은 데이터는 스왑 영역으로 보내고, 필요할 것 같은 데이터만 메모리에 올리는 정책입니다. 메모리 계층 구조레지스터: CPU 내에서 가장 빠른 메모리.캐시 메모리: CPU에서 비교적 가까운 메모리로, 빠른 속도로 접근 가능.메인 메모리: 데이터 접근이 캐시보다 느리지만 대용량 데이터를 저장.보조저장장치 (스왑 영역): 메모리보다 훨씬 느리지만 데이터를 저장하는 데 사용됨. 스왑 인/스왑 아웃스왑 인: 보조저장장치(스왑 영역)에 있던 데이터를 물리 메모리로 가져오는 과정.스왑 아웃: 물리 메모리에 있는 데이터를 보조저장장치(스왑 영역)로 내보내는 과정.운영체제는 효율적인 메모리 관리를 위해 스왑 인/스왑 아웃을 최소화하려고 합니다. 페이지 테이블과 비트프로세스가 가상 메모리에 접근할 때 운영체제는 페이지 테이블을 통해 물리 메모리와 스왑 영역 간의 데이터를 관리합니다. 페이지 테이블의 각 항목은 페이지 엔트리(PTE)라고 불리며, 여러 가지 비트를 포함하고 있습니다:접근 비트: 페이지가 메모리에 올라온 후에 접근되었는지 나타냅니다.변경 비트: 페이지의 데이터가 변경되었는지 나타냅니다.유효 비트: 페이지가 물리 메모리에 있는지 스왑 영역에 있는지 알려줍니다.읽기/쓰기/실행 비트: 페이지에 대한 접근 권한을 정의합니다. Page Fault와 프로세스 대기프로세스가 가상 메모리에 접근하려 할 때, 만약 요청한 페이지가 물리 메모리에 없으면 Page Fault라는 인터럽트가 발생합니다. 이때 운영체제는 스왑 영역에 접근하여 필요한 페이지를 물리 메모리로 가져오고, 프로세스는 대기 상태로 전환됩니다. 이후 페이지가 메모리에 올라가면 프로세스는 다시 실행됩니다. 3가지 상황에서의 처리 과정스왑이 필요 없는 경우: 요청된 페이지가 이미 물리 메모리에 있으면 즉시 데이터에 접근할 수 있습니다.스왑 영역에 있는 데이터를 참조하는 경우: 요청된 페이지가 스왑 영역에 있으면 물리 메모리로 데이터를 가져와서 사용합니다.물리 메모리가 꽉 찬 경우: 새로운 페이지를 가져오기 전에, 현재 물리 메모리에서 사용하지 않는 페이지를 스왑 영역으로 옮겨 공간을 확보합니다. 디멘드 페이징은 지역성 이론에 기반하여 메모리 자원을 효율적으로 사용하는 기법입니다. 메모리 관리자는 페이지 교체 알고리즘을 통해 스왑 인/아웃을 최적화하고 성능을 유지하려고 합니다. 페이지 교체 정책페이지 교체 정책은 메모리 공간이 부족할 때 어떤 페이지를 선택해 스왑 영역으로 보낼지를 결정하는 중요한 알고리즘입니다. 이 과정에서 페이지 폴트가 발생하며, 메모리에 새로운 페이지를 불러오려면 기존의 페이지를 교체해야 하는 상황이 생깁니다. 페이지 교체 정책은 주로 프로그램의 지역성 원칙을 바탕으로 하며, 다양한 알고리즘들이 존재합니다. 주요 페이지 교체 정책 1. 무작위 선택 (Random) - 랜덤하게 페이지를 선택해 교체합니다. - 지역성 이론을 고려하지 않기 때문에 성능이 좋지 않으며, 거의 사용되지 않습니다.2. FIFO (First In, First Out) - 가장 먼저 메모리에 들어온 페이지를 먼저 내보내는 방식입니다. - 구현이 간단하지만, 자주 사용되는 페이지도 교체될 수 있다는 단점이 있습니다. - FIFO는 페이지 폴트를 줄이려고 메모리를 늘렸을 때, 오히려 페이지 폴트가 증가하는 빌레이디의 역설이 발생할 수 있습니다.3. Optimum (OPT) - 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식입니다. - 이론적으로 최적의 방법이지만, 앞으로의 메모리 접근을 예측할 수 없기 때문에 실제로 구현하기는 어렵습니다.4. LRU (Least Recently Used) - 가장 최근에 사용되지 않은 페이지를 교체하는 방식입니다. - 시간의 지역성에 기반하여, 최근에 사용된 페이지가 다시 사용될 확률이 높다는 가정에 따라 작동합니다. - 실제로 많이 사용되는 알고리즘이며, 성능이 우수하지만 구현이 복잡하고 추가적인 하드웨어 지원이 필요할 수 있습니다. LRU와 유사한 알고리즘1. Clock Algorithm (클락 알고리즘) - LRU의 구현 복잡성을 해결하기 위해 고안된 방식입니다. - 페이지의 접근 비트를 사용하여, 일정 시간 동안 참조된 페이지인지 아닌지를 판단합니다. - 클락 핸드가 시계 방향으로 움직이며, 접근 비트가 0인 페이지를 교체 대상으로 선택합니다. - Enhanced Clock Algorithm은 접근 비트 외에 변경 비트까지 고려하여 성능을 더 향상시킵니다.2. Second Chance Algorithm (2차 기회 알고리즘) - FIFO 방식의 문제점을 보완하기 위해, 자주 사용되는 페이지에 두 번째 기회를 주는 방식입니다. - FIFO 큐에서 페이지가 교체 대상이 될 때, 해당 페이지가 최근에 참조된 경우 큐의 맨 뒤로 이동시켜 수명을 연장시킵니다. 선택적 사용시스템 하드웨어가 LRU 구현을 지원하지 않으면 FIFO를 사용할 수밖에 없는 경우가 있습니다. 이때는 성능 향상을 위해 2차 기회 알고리즘이나 다른 보완 기법들을 사용할 수 있습니다.결론적으로, LRU는 가장 좋은 성능을 보이는 경우가 많지만, 구현 복잡성을 고려해 Clock Algorithm 같은 유사 알고리즘이 더 자주 사용됩니다. 스레싱과 워킹셋스레싱(Thrashing)은 CPU 사용률을 높이기 위해 멀티 프로그래밍 정도를 지나치게 높였을 때 발생하는 문제로, CPU가 실제 작업을 처리하는 것보다 스왑 작업에 더 많은 시간을 소비하는 현상입니다. 이로 인해 성능이 급격히 저하되며, 결국 CPU 사용률도 떨어지게 됩니다. 스레싱 발생 과정1. 멀티 프로그래밍 정도 증가: 동시에 실행되는 프로세스의 수가 늘어나면 CPU 사용률을 높이려는 의도에서 물리 메모리에 더 많은 프로세스를 올리게 됩니다.2. 메모리 부족: 메모리는 한정되어 있기 때문에 모든 프로세스의 모든 페이지를 물리 메모리에 적재할 수 없으며, 페이지 폴트가 빈번하게 발생합니다.3. 페이지 폴트 증가: 페이지 폴트가 많아지면 프로세스가 필요로 하는 페이지를 계속 스왑 영역에서 불러와야 하며, 이에 따라 스왑 작업이 많아집니다.4. CPU 사용률 감소: 페이지 폴트로 인한 스왑 작업이 지나치게 많아지면 CPU가 작업에 집중하지 못하고, 결국 CPU 사용률이 낮아집니다.5. 스레싱: 스왑 작업이 CPU의 작업을 방해하게 되어 CPU 사용률이 0에 가까워지며, 시스템이 스왑 작업에 묶여 제대로 동작하지 않는 상태가 됩니다.스레싱은 물리 메모리의 부족이 근본 원인으로, 이를 하드웨어적으로 해결하려면 물리 메모리의 크기를 늘리면 되지만, 단순히 메모리 크기를 늘린다고 해서 항상 성능이 크게 향상되는 것은 아닙니다. 워킹셋(Working Set)워킹셋은 각 프로세스가 실행되기 위해 필요한 페이지들의 집합을 의미합니다. 프로세스는 지역성 이론에 따라 특정 시간 동안 주로 사용하는 데이터나 코드를 메모리에 올려두는데, 이 페이지들의 집합을 워킹셋이라고 합니다. 워킹셋을 정의하는 것은 스레싱을 방지하고 시스템 성능을 최적화하는 중요한 방법 중 하나입니다.- 지역성 이론: 프로세스는 특정 시점에서 일정한 범위의 메모리 공간을 집중적으로 참조하는 경향이 있습니다. 이 지역성을 고려해, 자주 사용하는 페이지들만 메모리에 올려두는 것이 효율적입니다. 스레싱 방지 방법: 워킹셋 모델운영체제는 각 프로세스가 어느 정도의 페이지를 필요로 하는지 모니터링하여, 워킹셋 모델을 통해 적절한 페이지 수를 유지합니다. 다음과 같은 과정을 통해 스레싱을 방지할 수 있습니다.1. 페이지 할당 및 조정: - 프로세스가 실행되면 처음에 일정량의 페이지를 할당합니다. - 페이지 폴트가 발생하면 해당 프로세스에 더 많은 페이지를 할당해 메모리 사용량을 늘립니다. - 반대로 페이지 폴트가 거의 발생하지 않으면 페이지가 과도하게 할당된 것으로 간주하고, 메모리 낭비를 방지하기 위해 일부 페이지를 회수합니다.2. 워킹셋 유지: - 현재 메모리에 적재된 페이지들이 프로세스의 워킹셋에 속한다고 가정하고, 이 페이지들을 유지합니다. - 페이지 폴트가 많이 발생하면 워킹셋에 필요한 페이지를 추가하고, 사용 빈도가 낮은 페이지를 스왑 영역으로 내보냅니다. 스레싱은 프로세스와 메모리 간의 균형이 깨질 때 발생하며, 이를 방지하기 위해서는 프로세스마다 적절한 양의 페이지를 메모리에 적재하고, 워킹셋을 기반으로 효율적으로 관리해야 합니다. CPU 사용률을 높이기 위한 멀티 프로그래밍의 정도는 물리 메모리의 용량과 페이지 교체 정책에 의해 결정되며, 운영체제는 이를 지속적으로 모니터링하여 스레싱을 방지할 수 있습니다. 입출력 장치주변장치 주변장치의 기본 구성I/O 디바이스는 CPU와 메모리 외부에 있는 장치들로, 그래픽카드, 하드디스크, SSD, 키보드, 마우스 등 여러 가지가 포함됩니다.이들은 메인보드에 버스를 통해 연결되며, 각각의 장치 상태와 데이터를 보관할 수 있는 레지스터들을 가집니다.장치마다 데이터를 전송하는 방식이 다르며, 캐릭터 디바이스와 블록 디바이스로 나뉩니다.캐릭터 디바이스: 마우스, 키보드 등 적은 양의 데이터를 전송하는 장치.블록 디바이스: 하드디스크, SSD 등 많은 양의 데이터를 전송하는 장치. 입출력 제어기와 버스초기에는 CPU가 직접 주변장치에서 데이터를 가져오면서 입출력 작업을 처리했으나, 이는 효율성이 떨어졌습니다. 이를 해결하기 위해 입출력 제어기(I/O Controller)가 도입되어 CPU가 다른 작업을 할 수 있도록 입출력 제어기가 입출력 작업을 관리하게 되었습니다.입출력 제어기는 CPU와 빠른 메모리를 연결하는 시스템 버스와, 주변장치들을 연결하는 입출력 버스로 구성됩니다.속도 차이를 해결하기 위해, 입출력 버스는 고속 입출력 버스와 저속 입출력 버스로 나뉩니다. 예를 들어, 그래픽 카드와 같은 고속 장치는 시스템 버스에 바로 연결되기도 합니다.DMA(Direct Memory Access) 제어기가 도입되어 CPU의 개입 없이도 입출력 제어기가 메모리에 직접 데이터를 읽고 쓸 수 있게 되었으며, 이를 Memory Mapped I/O라고 부릅니다. 마우스, 키보드마우스광학 마우스는 카메라로 마우스 아래의 이미지를 초당 수천 회 촬영해 마우스의 움직임을 감지합니다.마우스의 디바이스 컨트롤러는 이 데이터를 분석하고 인터럽트를 통해 CPU에 알립니다. CPU는 운영체제와 애플리케이션이 마우스 이벤트를 처리할 수 있게 해줍니다.키보드키보드도 마우스와 비슷한 방식으로 동작하며, 사용자가 입력한 키를 디바이스 컨트롤러가 감지해 CPU로 인터럽트를 보냅니다. 운영체제는 해당 이벤트를 적절한 애플리케이션에 전달합니다. 하드디스크, SSD하드디스크하드디스크는 물리적으로 회전하는 플래터(Platter)와 이를 읽는 헤드(Head)로 구성됩니다.실린더(Cylinder)는 여러 개의 트랙이 있는 위치를 의미하며, 섹터(Sector)는 하드디스크의 가장 작은 저장 단위입니다.하드디스크의 성능은 데이터를 읽기 위해 헤드를 움직이는 시간이 느려지는 탐색 시간(Seek Time)에 의해 제한됩니다. 이 시간 때문에 하드디스크는 상대적으로 느리게 동작합니다.SSD(Flash Memory)SSD는 전기적으로 데이터를 읽고 쓰기 때문에 빠르고 조용하며, 하드디스크와 달리 기계적 움직임이 없어서 충격에 강합니다.다만, 플래시 메모리는 같은 지점에 데이터를 여러 번 쓰고 지우는 작업에 한계가 있어, 반복적인 쓰기 작업이 장치의 수명을 단축시킬 수 있습니다. 파일 시스템파일과 시스템파일 시스템은 데이터 저장 및 관리를 위해 설계된 소프트웨어 구성 요소로, 파일과 디렉토리의 생성, 수정, 삭제를 포함한 다양한 작업을 처리합니다. 파일 시스템의 구조와 역할파일 시스템은 파일 및 디렉토리를 관리하며, 디스크와 같은 저장 장치에 데이터를 효율적으로 저장합니다. 주요 기능은 다음과 같습니다:파일 및 디렉토리 생성, 수정, 삭제파일 접근 권한 관리데이터 무결성 보장백업 및 복구, 암호화 파일 구조파일은 다양한 데이터 집합으로 이루어지며, 그 구성 방식에 따라 세 가지 주요 구조로 구분됩니다:순차 파일 구조: 데이터가 연속적으로 저장되는 구조로, 파일의 특정 지점에 접근하는 데 시간이 오래 걸리지만 구조가 단순하여 공간 낭비가 적습니다.직접 파일 구조: 해시 함수를 이용해 데이터를 저장하는 방식으로, 데이터 접근이 빠르지만, 해시 함수의 선택이 중요합니다.인덱스 파일 구조: 순차 접근과 직접 접근의 장점을 결합한 방식으로, 인덱스 테이블을 이용해 빠르게 데이터를 검색할 수 있습니다. 디렉토리디렉토리 역시 파일의 한 종류로, 다른 파일들의 정보를 저장하는 역할을 합니다. 다단계 디렉토리 구조를 통해 트리 형태로 파일을 관리할 수 있으며, 윈도우의 바로가기처럼 순환 구조를 가지기도 합니다. 파일과 디스크파일이 저장될 때, 디스크는 일정 크기로 나뉜 블록으로 데이터를 저장합니다. 블록 할당 방식은 크게 두 가지로 구분됩니다: 연속 할당: 파일의 블록이 연속적으로 저장되는 방식으로, 외부 단편화 문제가 발생할 수 있어 현대 시스템에서는 잘 사용하지 않습니다.불연속 할당: 파일의 블록들이 분산되어 저장되며, 연결 할당과 인덱스 할당 방식이 존재합니다.연결 할당: 연결 리스트 구조로 파일 블록을 관리하는 방식입니다.인덱스 할당: 인덱스 블록을 통해 여러 데이터 블록에 접근하는 방식입니다. 유닉스와 리눅스에서는 이를 i-node로 관리합니다. 디스크 관리 및 블록 크기블록 크기가 작으면 내부 단편화가 줄어들어 공간 낭비가 적어지지만, 관리할 블록 수가 많아집니다. 반대로, 블록 크기가 크면 내부 단편화로 인해 공간 낭비가 발생할 수 있지만, 관리할 블록 수는 줄어듭니다. 파일 삭제 및 복구파일을 삭제할 때, 실제로 파일의 데이터가 사라지지 않고 파일 시스템은 파일 테이블에서 파일의 헤더만 삭제하고, 사용했던 블록을 프리 블록 리스트에 추가합니다. 이런 이유로 데이터 복구 프로그램을 통해 삭제된 파일의 데이터를 복원할 수 있습니다.

CS･운영체제

워밍업 클럽 CS 3주차 발자국 : 자료구조와 알고리즘

알고리즘 삽입 정렬삽입 정렬은 구현이 간단하지만 성능이 아쉬운 정렬 알고리즘입니다. 배열을 두 영역으로 나누어, 정렬되지 않은 부분에서 데이터를 하나씩 꺼내어 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작합니다. 이때, 정렬되지 않은 영역의 첫 번째 원소를 정렬된 영역의 마지막 원소부터 역순으로 비교하여 자리를 찾습니다. 시간 복잡도는 최악의 경우 O(n²)입니다. 병합 정렬병합 정렬은 비교적 복잡한 정렬 알고리즘으로, 분할 정복 기법을 사용합니다. 배열을 부분집합으로 나눈 후, 각 부분을 재귀적으로 정렬하고 합병하여 전체 배열을 정렬합니다. 병합 과정에서 n개의 데이터를 n번 비교하므로 시간 복잡도는 O(n log n)입니다. 성능 면에서 매우 뛰어나지만, 구현이 어려울 수 있다는 단점이 있습니다. 퀵 정렬퀵 정렬도 병합 정렬처럼 분할 정복 알고리즘에 속하며, 재귀적으로 배열을 정렬합니다. 배열에서 하나의 숫자를 '피벗'으로 선택한 뒤, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 다시 같은 방식을 적용해 정렬합니다. 평균적인 성능은 O(n log n)이지만, 피벗 선택이 좋지 않을 경우 최악의 시간 복잡도는 O(n²)입니다. 그러나 퀵 정렬은 실제로는 병합 정렬보다 더 적은 메모리와 비교 횟수를 사용하여 더 효율적인 경우가 많습니다. 동적 프로그래밍 - 메모제이션재귀 함수는 중복된 계산을 여러 번 수행하여 성능에 악영향을 미칠 수 있습니다. 이를 해결하기 위해 메모제이션을 사용하여, 이미 계산된 값을 저장하고 필요할 때 이를 다시 사용하여 성능을 개선할 수 있습니다. 메모제이션은 주로 해시 테이블을 사용하여 빠르게 결과를 조회하고 저장하는 방식으로 동작합니다. 다만, 메모리 사용량이 늘어난다는 단점이 있습니다. 동적 프로그래밍 - 타뷸레이션타뷸레이션은 상향식 접근 방식으로, 필요한 값들을 미리 테이블에 계산하여 저장해두고 사용합니다. 메모리 사용량이 적으면서도 재귀를 사용하지 않기 때문에 메모제이션보다 더 빠를 수 있습니다. 재귀가 직관적인 경우에는 메모제이션을 사용하는 것이 좋지만, 그렇지 않은 경우에는 타뷸레이션을 통해 더 효율적으로 문제를 해결할 수 있습니다.

알고리즘 · 자료구조･CS･자료구조･알고리즘

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

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요. 레지스터, 캐시 , 메인 메모리(RAM), 보조저장장치 하드디스크 가 있습니다.레지스터는 가장 빠른 기억 저장소로, CPU내에 존재하고, 휘발성 메모리입니다.캐시는 레지스터와 메인 메모리, 사이에 존재하고, 휘발성 메모리입니다. 캐시는 메인 메모리에 있는 값을 레지스터로 옮기는 시간을 단축하기 위해 미리 데이터를 가져와 저장하는 곳 입니다. 메인 메모리는 실제 운영체제와 프로세스가 올라가는 곳으로, 휘발성 메모리입니다. 하드 디스크나 SSD보다는 속도가 빠르지만, 가격이 비싸기 때문에 실행중인 프로그램만 올립니다. 보조 저장장치 (HDD, SSD) 는 비휘발성 메모리로 가격이 저렴해, 작업한 파일들을 저장한다. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터 CPU내에 존재하며 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어나는지 감시하고, 벗어날 경우 프로세스를 종료시킨다. 메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식 장점) 프로세스의 크기에 따라 메모리를 할당하는 방식으로, 메모리의 연속된 공간에 할당되기 때문에, 낭비되는 공간인 내부 단편화가 없다 . 단점) 외부단편화가 발생한다. 고정 분할 방식장점) 프로세스의 크기 상관 없이 메모리를 할당하는 방식으로, 비연속 메모리 할당으로 구현이 간단하고 오버헤드가 적다. 단점) 작은 프로세스도 큰 영역에 할당되어서 공간이 낭비되는 내부 단편화가 발생한다. CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱 CPU 사용률을 높이려하지만 오히려 더 떨어지는 상황이 나오는 것으로 ,CPU 사용률을 높이기 위해 멀티 프로그래밍 정도를 올리는데, 물리 메모리의 프레임을 할당하는데 한계가 있어 일부는 스왑영역에 저장하고, 이로 인해 Page Fault가 많이 발생하고, 그러면 CPU 작업 시간 보다 스왑 작업 시간이 더 길어 지고 CPU사용률이 떨어진다. 그럼 CPU 스케줄러는 CPU 사용률이 낮아져 더 많은 프로세스를 메모리에 올리게 되고 이 과정을 반복하다 보면 CPU 사용률이 0%에 가깝게 된다. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요? 이유를 함께 적어주세요.HDD나 SSD는 컴퓨터를 실행시키는 데 꼭 필요한 것은 아니지만, 현실적으로 대부분의 컴퓨터 환경에서 운영체제와 데이터를 저장하는 데 매우 중요한 역할을 하기 때문에 필수적이다.HDD나 SSD가 아닌 다른 메모리는 속도가 빠르지만 가격이 너무 비싸고 휘발성이기 때문에, 비휘발성인 HDD나 SSD 같은 보조 기억장치에 운영체제를 저장하고 필요한 데이터와 소프트웨어를 로드하는 것이 저렴하면서도 효율적으로 컴퓨터를 이용할 수 있는 방법이다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?free block list 덕분이다. 만약 특정 파일을 삭제한다면, 파일 시스템은 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 free block list에 추가한다. 이렇게 처리하면 사용자는 파일이 삭제된 것처럼 느끼지만, 사용했던 블록의 데이터는 그대로 남아있기 때문에 포렌식을 통해 데이터를 복구할 수 있다. 자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블정렬장점 : 이해와 구현이 간단하다. 단점 : 성능이 좋지 않다. 시간 복잡도 : O(n²)선택 정렬장점 : 이해와 구현이 간단하다.단점 : 성능이 좋지 않다. 시간 복잡도 : O(n²)삽입 정렬장점 : 이해와 구현이 간단하다.단점 : 성능이 좋지 않다. 시간 복잡도 : O(n²)병합 정렬장점 : O(nlog n) 성능으로 버블, 선택 , 삽입 정렬보다 성능이 훨씬 좋다. 단점 : 재귀적인 기법으로 이해하기 어렵고, 구현하기 어렵다. 시간 복잡도 : O(n logn)퀵 정렬장점 : 성능이 좋고, 병합 정렬보다도 적은 메모리 공간을 차지해 더 좋은 알고리즘으로 평가 받는다. 단점 : 재귀적인 기법으로 이해하기 어렵고, 구현하기 어렵다. 시간복잡도 : O(n logn)메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.타뷸레이션 메모이제이션은 재귀 호출을 사용하기 때문에 함수 호출에 따른 오버헤드와 메모리 비용이 큽니다. 반면, 타뷸레이션은 반복문을 사용하여 오버헤드가 적고, 메모리 사용량도 예측 가능하기 때문에 더 효율적입니다

알고리즘 · 자료구조･워밍업클럽･운영체제･자료구조･알고리즘･CS･미션

[미션] 인프런 워밍업클럽 CS 2기 2주차 미션

운영체제FIFO 스케줄링의 장단점이 뭔가요?FIFO 스케줄링의 장점은 단순하고 직관적입니다.단점은 한 프로세스가 다 끝나야 다음 프로세스가 시작되기 때문에, 실행시간이 짧은 프로세스라도 늦게 도착할 경우, 먼저 도착한 실행시간이 긴 프로세스가 끝날때까지 기다려야 한다는 단점이 있습니다. SJF를 사용하기 여러운 이유가 뭔가요?SJF는 이론적으로 FIFO 보다 성능이 좋지만, 실제로 어떤 프로세스가 얼마나 걸릴지 예측하기 힘들기 때문입니다.또한 Burst Time이 짧은 프로세스가 먼저 실행되기 때문에, Burst Time이 긴 프로세스는 앞에 모든 프로세스를 기다리며 아주 오랫동안 실행이 안 될수도 있다는 문제 때문에 사용하기 어렵습니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?타임 슬라이스가 아주 작으면 컨텍스트 스위칭이 자주 발생하기 때문에 타임 슬라이스에서 실행되는 프로세스의 처리량보다 컨텍스트 스위칭을 처리량이 더 커져 오버헤드가 커지게 되는 문제가 발생합니다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요? CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 CPU 사용이 적은 것이니 I/O Bound Process 라고 인식하고,반대로 프로세스가 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU 사용이 많은 것이니 CPU Bound Process 라고 인식합니다. 공유자원이란무엇인가요?프로세스간 통신을 할 때 공동으로 사용하는 변수나 파일입니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요? 상호배제 : 한 프로세스가 한 자원을 점유하면, 다른 프로세스에게 공유되면 안됩니다.비선점 : 한 프로세스가 한 자원을 점유하는동안, 다른 프로세스가 이를 뺏을 수 없어야 합니다.점유와 대기 : 한 프로세스가 한 자원을 점유할때, 다른 프로세스도 같은 자원을 원해야 합니다.원형 대기 : 점유와 대기를 하는 프로세스의 관계가 원형이어야 합니다.이 중 한가지 조건도 충족하지 않을 경우, 교착상태가 발생하지 않습니다. 자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?기저조건이 없을 경우, 재귀 함수를 탈출하지 못하고 계속해서 재귀함수가 호출된다. 즉, 콜 스택에 계속해서 함수가 쌓여서 메모리가 부족해져 프로세스가 강제 종료될 수 있습니다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ // 재귀 로직 if (n <= 0) { return 0; } return (n % 2 === 1? n : 0) + sumOdd(n - 1); } console.log(sumOdd(10)) // 25v2function sumOdd(n){ // 기저 조건 if(n <= 1) { return n; } // 재귀 로직 if(n % 2 == 0){ return sumOdd(n -1); // n이 짝수일 때, n-1로 재귀호출 } else{ return n + sumOdd(n - 2); // n이 홀수일 때, n을 더하고 n-2로 재귀호출 } } console.log(sumOdd(10)) // 25 v3 (java)public class SumOddClass{ public static int sumOdd(int n){ // 기저 조건 if (n <= 1) { return n; } // 짝수일 때 n-1로 재귀 호출 if (n % 2 == 0){ return sumOdd(n -1); } // 홀수일 때 n을 더하고 n-2로 재귀 호출 return n + sumOdd(n -2); } public static void main(String[] args){ int n = 10; int result = sumOdd(n); System.out.println(result); } }

워밍업클럽･운영체제･자료구조･알고리즘･CS･미션

[인프런 워밍업 클럽 CS 2기] 2주차 발자국 - 자료구조/알고리즘

[ Section 3. 알고리즘 ]1. 재귀(recursion)재귀(recursion)어떤것을 정의할 때 자기 자신을 참조하는 것재귀함수란함수 내부에서 자기 자신(함수)를 호출하여 실행하는 함수→ 함수를 정의할 때 재귀적으로 정의된 함수를 재귀함수 라고 부른다.기저조건(Base Case)재귀 함수의 탈출 조건, 재귀 호출을 종료하는 조건을 의미한다.기저 조건이 없다면 함수는 계속해서 자기 자신을 호출하게 되므로, 무한 루프에 빠져 스택 오버플로우(Stack Overflow)가 발생한다.콜 스택(Call Stack)메모리 영역에서 Stack의 한 부분을 의미하며, 재귀 함수는 이 콜 스택을 사용해 실행된다.재귀함수를 사용하는 케이스for문에서 재귀함수를 사용하는 것은 비효율적이다.조금 복잡한 로직들을 구현할 때 재귀함수를 사용 한다. ex) 팩토리얼 계산2. 재귀적으로 생각하기재귀함수의 사용패턴 - 1. 반복실행재귀함수를 반복실행하여 for문 처럼 사용할 수 있다.그러나 재귀함수로 반복문을 실행하는것은 성능이 좋지 않다.재귀함수의 사용패턴 - 2. 하위문제의 결과 기반으로 현재 문제 계산재귀함수는 하위문제의 결과를 기반으로 현재 문제를 해결하는 하향식 계산 방식을 사용한다.재귀함수에 상향식 계산 방식을 사용하긴 하지만 재귀함수는 하향식 계산 방식을 사용하는데 주로 쓰인다.상향식 계산현재 문제 결과를 기반으로 상위 문제를 해결하는 방식하향식 계산하위 문제 결과를 기반으로 현재 문제를 해결하는 방식3. 재귀 - 하노이 탑재귀함수를 이용하여 하노이탑을 하향식 계산 방식으로 접근// ch03. 재귀 - 하노이 탑 // ex. 기둥 A 에 있는 원반 3개를 기둥 C 로 이동하려는 경우 // 1) 원반 3이 기둥 C로 옮겨 져야 함 -> [하위 문제] : 원반 1, 2가 기둥 B에 옮겨져야 한다. // 1-1) 원반 1, 2가 기둥 B에 옮겨져야 한다. -> [하위 문제] : 원반 2가 기둥 B에 옮겨져야 한다. // 1-1-1) 원반 2가 기둥 B에 옮겨져야 한다. -> [하위 문제] : 원반 1이 기둥 C에 옮겨져야 한다. function hanoi(count, from, to, temp) { // 3, A, C, c if(count === 0) return; hanoi(count - 1, from, temp, to); // 2, A, B, C console.log(`원반 [ ${count} ]를 [ ${from} ]에서 [ ${to} ]로 이동`); hanoi(count - 1, temp, to, from); // 2, B(temp), C(to), A(from) } // 첫번째 매개변수 : 원반의 개수(count) // 두번째 매개변수 : 원반들이 처음 꽂혀있는 기둥(from) // 세번째 매개변수 : 원반들이 최종적으로 꽂힐 기둥(to) // 네번째 매개변수 : 원반들이 이동을 위해 임시로 사용할 기둥(temp) hanoi(3, "A", "C", "B"); 4. 정렬 - 버블 정렬(Bubble Sort)버블 정렬(Bubble Sort)이란배열의 무작위 순서를 정렬할 때, 앞의 원소와 뒤의 원소를 비교하며 순서를 정렬하는 방식이다.배열의 모든 원소의 앞, 뒤 원소를 비교한다. → 맨 마지막 원소는 가장 큰 원소가 위치한다.정렬된 마지막 원소를 제외하고 나머지 원소의 앞, 뒤 원소를 비교한다.정렬은 배열 길이 - 1 만큼 실행한다.// ch04. 정렬 - 버블정렬(Bubble Sort) function BubbleSort(arr) { console.log(`arr.length ===> [${arr.length}]`); // 자리의 교체는 arr.length -1 만큼 진행 for(let i = 0; i < arr.length - 1; i++) { console.log(`1) [${i}]번째 for문`); // 정렬이 된 원소의 이전 원소보다 하나 이전의 원소까지 순회 for(let j = 0; j < (arr.length - i - 1); j ++){ console.log(`2) [${j}]번째 for문`); // 실제로 값을 비교하며 배열 원소의 값을 바꿔준다. console.log(`3) arr[j] 값 ===> ${arr[j]}`); console.log(`3) arr[j+1] 값 ===> ${arr[j+1]}`); if(arr[j] > arr[j + 1]){ // 앞의 원소값이 뒤의 원소값 보다 큰 경우 console.log(`4) arr[j]값이 arr[j+1] 값 보다 큽니다! ${arr[j]} > ${arr[j+1]}`); let temp = arr[j]; // 1) 앞의 원소 값을 임시로 저장 arr[j] = arr[j + 1] // 2) 뒤의 원소 값을 앞의 원소값으로 변경 arr[j + 1] = temp; // 3) 뒤의 원소 값을 임시로 저장했던 값으로 변경 } console.log(`5) ${arr}`); } } } 버블 정렬의 성능버블정렬의 성능을 수학식으로 풀어쓰면 등차수열의 합과 같다.이때 빅 오는 O(n²)이 된다. 데이터가 증가하면 계산량이 증가하여 성능이 떨어지므로 복잡한 시스템에 적합하지 않은 계산법이다.버블 정렬의 장단점장점단순하고 직관적이라 구현이 쉬운 알고리즘이다.단점계산량이 증가시 성능이 떨어지기 때문에 복잡한 시스템에 적합하지 않다.5. 정렬 - 선택 정렬(Selection Sort)선택 정렬이란?정렬되지 않은 영역의 원소들을 순회하며 제일 작은 값을 찾아 순회 범위의 첫번째 원소에 위치 시키는 정렬 알고리즘선택 정렬의 성능선택 정렬의 빅 오는 O(n²)이 된다. 버블 정렬과 마찬가지로 성능이 떨어지므로 복잡한 시스템에 적합하지 않은 계산법이다.선택 정렬의 장단점장점단순하고 직관적이라 구현이 쉬운 알고리즘이다.단점계산량이 증가시 성능이 떨어지기 때문에 복잡한 시스템에 적합하지 않다.

알고리즘 · 자료구조･인프런워밍업클럽･알고리즘･자료구조･CS

[인프런 워밍업 클럽 CS 2기] 2주차 발자국 - 운영체제

5. SJF (Shortest Job First)Burst Time(연산 시간)이 짧은 프로세스를 먼저 실행하여 평균 대기 시간을 줄이는 알고리즘Burst Time이 짧은 프로세스를 우선적으로 실행시, 상대적으로 Burst Time이 긴 작업은 실행될 기회를 얻지 못하고 계속 대기할 수 있게 되며 프로세스의 종료시간을 예측하기 어려울 수도 있다. 이러한 이유로 SJF 알고리즘은 실제로 사용하지 않음 6. RR (Round Robin)한 프로세스에게 일정시간을 할당하고 할당된 시간이 종료되면 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당한다. 강제로 CPU를 뺏긴 프로세스는 큐의 맨 뒷부분으로 밀려난다.FIFO 알고리즘과 RR 알고리즘의 평균 대기시간이 비슷한 경우 오버헤드가 큰 RR 알고리즘이 비효율 적이다.RR 알고리즘은 컨텍스트 스위칭 발생이 있기 때문RR 알고리즘의 성능은 타임 슬라이스의 값에 따라 달라짐타임 슬라이스/타임 퀀텀RR 알고리즘에서 프로세스들에게 부여되는 일정 시간타임슬라이스가 크게 설정된 경우FIFO 알고리즘과 다를바가 없기 때문에 비효율적타임슬라이스가 작게 설정된 경우 오버헤드가 너무 커진다.오버헤드가 커지는 상황→ 컨텍스트 스위칭이 자주 발생하여 타임 슬라이스에서 실행되는 프로세스의 처리량 보다 컨텍스트 스위칭을 처리하는 양이 훨씬 커짐최적의 타임 슬라이스를 결정하는 방법사용자가 느끼기에 타임슬라이스가 너무 크지 않아야 함프로세스가 동시에 실행되는 것처럼 느껴저야 함오버헤드가 너무 크지 않아야 함 7. MLFQ(Multi Level Feedback Queue)오늘날 쓰이는 주류 알고리즘이며, RR의 업그레이드 된 알고리즘CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임슬라이스를 선택한다.CPU Bound Process 에게는 타임 슬라이스를 크게 주며 우선 순위가 낮은 큐에 배치한다.I/O Bound Process 에게는 타임 슬라이스를 작게 주며 우선 순위가 높은 큐에 배치한다.CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 CPU 사용이 적은거니 I/O Bound Process 일 확률이 높다.CPU를 사용하는 프로세스가 타임 슬라이스 크기를 오버해서 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU 사용이 많은 것이니 CPU Bound Process일 확률이 높다.큐의 우선순위 중 우선순위가 높으면 타임슬라이스가 적고 우선순위가 낮을수록 타임 슬라이스 크기가 커진다.어떤 프로세스가 타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏긴다면 해당 프로세스는 원래 있던 큐보다 우선순위가 더 낮은 큐로 이동하게 되고 타임 슬라이스가 조금 더 커진다.→ 다음 실행시에도 타임 슬라이스가 부족하면 다음엔 우선순위가 더 낮은 큐로 이동하게 되어 더 큰 타임 슬라이스를 할당받게 된다.우선순위가 낮아질 수록 타임슬라이스를 무한초로 할당 받게 되어 FIFO 처럼 연속적으로 작업을 마칠 수 있게 됩니다.[ Section 4. 프로세스 동기화 ]1. 프로세스 간 통신프로세스간 통신의 종류1) 파일과 파이프를 이용한 통신파일을 이용한 통신하나의 파일을 여러 프로세스가 같이 읽고 쓰는 방식파이프를 이용한 통신운영체제가 구축한 파이프를 이용하여 프로세스가 통신하는 방식2) 하나의 프로세스 내부에서 쓰레드를 이용한 통신하나의 프로세스 내부에 존재하는 여러 쓰레드는 스택을 제외한 코드, 데이터, 힙 영역을 공유하고 스택만 자신의 것을 가지고 있다.데이터 영역의 전역 변수나, 힙 영역을 이용하여 쓰레드 간 통신이 가능하다.3) 네트워크를 이용한 통신운영체제가 제공하는 소켓 통신다른 컴퓨터에 존재하는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신2. 공유자원과 임계구역공유자원이란?프로세스 통신시 공통으로 이용하는 변수나 파일프로세스의 접근 순서에 따라 결과가 달라질 수 있다.동기화 문제프로세스 통신시 공유자원의 연산 결과를 예측 할 수 없고 어떤 프로세스가 먼저 실행될지 예측 할 수 없는 문제임계구역(Critical Section이란?여러 프로세스가 동시에 사용하면 안되는 영역을 정의한 구역경쟁조건(Race Condition)공유자원을 서로 사용하기 위해 경쟁하는 것상호 배제(Mutual Exclusion)임계구역 문제를 해결하기 위해 필요한 매커니즘상호 배제의 요구 사항임계 영역엔 동시에 하나의 프로세스만 접근한다.여러 요청에도 하나의 프로세스의 접근만 허용한다.임계구역에 들어간 프로세스는 빠르게 나와야 한다.3. 세마포어상호배제의 매커니즘 중 하나이다.세마포어는 실제로 정수형 변수이다.세마포어를 사용하면 공유자원에 여러 프로세스가 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않는다.wait() 함수와 signal() 함수 사용세마포어는 공유 자원의 개수만큼 가질 수 있다.세마포어 사용의 단점wait() 함수와 signal() 함수 사용 순서가 꼬일 경우 세마포어를 잘못 사용할 가능성이 있다.4. 모니터세마포어의 단점을 해결한 상호배제 매커니즘운영체제가 처리하는 것이 아니라 프로그래밍 언어 차원에서 지원하는 방법ex.) 자바에서 synchronized키워드가 붙은 함수들은 여러 프로세스에서 동시에 실행할 수 없다.모니터가 완벽하게 구현된 경우 프로그래머는 세마포어 처럼 wait() 함수와 signal() 함수를 임계 영역에 감싸지 않아도 돼어 편리하고 안전하게 코드를 작성할 수 있다.[ Section 5. 데드락 ]1. 데드락이란? (feat. 식사하는 철학자)교착상태(데드락)여러 프로세스가 서로 작업이 끝나기를 기다리다 아무도 작업을 진행하지 못하는 상태교착상태가 발생하는 이유는 공유자원 때문이며, 어떤 자원을 여러개의 프로세스가 공유하지 않는 경우 교착상태는 발생하지 않는다.교착상태의 필요조건1. 상호배제어떤 프로세스가 한 리소스를 점유 했다면, 해당 리소스는 다른 프로세스에게 공유가 되면 안된다.2) 비선점프로세스 A가 리소스를 점유하고 있을 때, 다른 프로세스는 해당 리소스를 빼앗을 수 없다.3) 점유와 대기어떤 프로세스에서 리소스 A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 한다.4) 원형 대기점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야 한다.2. 데드락 해결 (feat. 은행원 알고리즘)교착상태 해결방법교착상태 회피(Deadlock avoidance)프로세스에게 교착상태가 발생하지 않는 수준의 자원을 할당전체 자원의 수와 할당된 자원의 수를 기준으로 안정 상태(Safe state)와 불안정 상태(Unsafe state)로 나눈다.운영체제는 안정 상태를 유지하려 노력하며, 불안정 상태에 빠지면 교착상태에 빠질 확률이 높아진다.은행원 알고리즘(Banker’s algorithm)은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출 가능한 상황(안전상태)인지 확인하고 빌려준다.운영체제에서 은행원 알고리즘 구현운영체제는 자기가 가지고 있는 시스템의 총 자원을 파악한다.프로세스는 자기가 필요한 자원의 최대 숫자(최대 요구 자원)를 운영체제에게 알려준다.안정 상태불안정 상태순환구조가 발생한 그래프 → 교착상태 발생교착상태 검출 방법(1) 가벼운 교착 상태 검출타이머를 이용하여 프로세스가 동작하지 않는 경우 교착상태에 빠진것으로 간주하고 교착상태를 해결한다.마지막으로 저장했던 체크포인트로 롤백하여 교착상태를 해결한다.(2) 무거운 교착 상태 검출자원 할당 그래프를 이용하여 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생하면 해결한다.교착상태를 검출한 경우 교착상태를 일으킨 프로세스를 강제로 종료하고, 다시 실행 시킬때 체크포인트로 롤백을 시킨다.이 방식은 운영체제가 지속적으로 ‘자원 할당 그래프’를 유지, 검사 해야 하기 때문에 오버헤드가 발생한다.가벼운 교착 상태 검출방식 보다 억울하게 종료되는 프로세스는 발생하지 않는다.[ Section 6. 쉬어가기 ]1. 컴파일과 프로세스작성한 프로그램 코드가 프로세스가 되고 메모리에 할당되는 전반적인 과정프로그래밍 언어컴파일 언어개발자가 작성한 코드를 컴파일 과정을 거쳐 실행 가능한 기계어로 변환컴파일 과정에서 문법 오류를 잡아낼 수 있다.C, C++, C# 등인터프리터 언어개발자가 작성한 코드를 한줄씩 해석하며 실행하는 언어컴파일 과정이 없어 실행시 오류가 발생 할 수 있고, 속도도 컴파일 언어와 비교하면 느리다.JS, Python, Ruby 등프로세스의 구조Code 영역실행해야 될 코드가 들어가는 영역Data 영역전역 변수나 배열이 들어가는 영역Stack 영역, Heap 영역 : 프로세스가 실행될 때 할당되는 메모리Stack 영역지역변수와 함수 관련 값들이 들어가는 영역Heap 영역실행 중 메모리 공간을 할당할 수 있는 유동적인 공간컴파일 언어로 작성된 파일이 프로세스가 되는 과정코드 작성컴파일러로 작성한 코드를 컴파일컴파일 과정을 거쳐 실행 파일이 생성된다.사용자가 프로그램을 실행시키면 운영체제가 프로세스를 만든다.운영체제는 실행파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 넣어주고 빈 상태의 스택과 힙을 할당한다.PCB를 만들어 관리가 가능하도록 하고, 프로그램 카운터(실행할 명령어의 주소)를 생성한 프로세스의 코드 영역의 첫번째 주소로 설정한다.운영체제 CPU 스케줄링에 따라 프로세스가 실행되다 작업을 마친다. [ Section 7. 메모리 ]1. 메모리 종류컴퓨터의 여러 종류 메모리레지스터CPU에 존재하며 가장 빠른 기억 장소컴퓨터의 전원이 꺼지면 데이터가 사라진다. = 휘발성 메모리32bit CPU, 64bit CPU → 32bit, 64bit는 레지스터의 크기를 말한다.CPU는 연산시 메인메모리(RAM) 에 있는 값을 레지스터로 가져와 연산하고 다시 메인메모리(RAM)에 저장한다.메인메모리의 값을 레지스터로 옮기려면 오래 걸리기 때문에 필요할 것 같은 데이터를 미리 캐시에 저장한다.메인메모리운영체제와 프로세스가 올라가는 공간전원이 공급되지 않으면 데이터가 지워진다. = 휘발성 메모리하드디스크나 SSD보다 속도는 빠르지만 가격이 비쌈 → 데이터 저장 X, 실행중인 프로그램만 올린다.보조저장장치(SSD, 하드디스크)가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비 휘발성 메모리2. 메모리와 주소운영체제는 메모리(메인 메모리, RAM) 관리를 위해 1바이트(8bit) 크기로 구역을 나누고 숫자를 매긴다. 이 숫자를 ‘주소’ 라고 부른다.32bit CPU 와 64bit CPU64bit CPU가 32bit CPU 보다 한번에 처리할 수 있는 양이 많기 때문에 속도가 더 빠르다.32bit CPU레지스터 크기: 32bitALU(산술논리연산장치) : 32bit(데이터가 이동하는) 버스 : 32bitCPU가 다룰 수 있는 메모리 : 2³² = 4GB64bit CPU레지스터 크기: 64bitALU(산술논리연산장치) : 64bit(데이터가 이동하는) 버스 : 64bitCPU가 다룰 수 있는 메모리 : 2⁶⁴물리주소와 논리 주소물리 주소 공간컴퓨터를 연결하면 0x0번지부터 시작하는 주소 공간논리 주소 공간사용자 관점에서 바라본 메모리 공간사용자는 논리주소로 물리주소에 접근 가능경계 레지스터하드웨어 적으로 운영체제 공간과 사용자 공간을 나눈다.CPU 내부에 존재하며 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 벗어난 경우 그 프로세스를 종료시킨다.절대 주소와 상대 주소절대 주소실제 프로그램이 올라간 메모리 주소이며 메모리 관점에서의 절대 주소‘물리 주소 공간’ 이라 부른다.상대 주소사용자가 바라본 주소이며 실제 메모리 주소가 아니다.‘논리 주소 공간’이라 부른다.재배치 레지스터메모리 관리자는 CPU가 요청한 메모리 주소 값과 재배치 레지스터에 저장된 값을 더한 메모리 주소에 접근해서 데이터를 가져온다.재배치 레지스터에는 프로그램의 시작 주소가 저장되어 있다.재배치 레지스터 덕분에 모든 사용자 프로세스는 0x0번지 부터 시작한다는 가정을 사용할 수 있고, 시작 영역이 변경되어도 재배치 레지스터만 변경해주면 되는 장점이 있다.3. 메모리 할당방식메모리 오버레이(memory overlay)메모리 보다 큰 프로그램 실행 시 당장 실행할 부분만 메모리에 올리고, 나머지는 하드디스크 내부의 스왑 영역에 저장하는 기법스왑과정이 있기 때문에 조금 느리다.가변 분할 방식 (세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식한 프로세스가 메모리의 연속된 공간에 할당되기 때문에 “연속 메모리 할당”이라고 한다.가변 분할 방식의 장/단점장점메모리의 연속된 공간에 할당되기 때문에 *내부 단편화가 없다*내부 단편화 : 크기가 더 크게 할당되어 낭비되는 공간단점외부 단편화 발생고정 분할 방식 (페이징)프로세스 크기와 상관없이 메모리를 정해진 크기로 나누는 방식한 프로세스가 메모리에 분산되어 할당되기 때문에 “비연속 메모리 할당” 이라고 한다.고정 분할 방식의 장/단점장점구현이 간단, 오버헤드가 적다.단점작은 프로세스도 큰 공간에 할당되어 공간이 낭비되는 내부 단편화가 발생외부 단편화 문제메모리를 할당 할 수 있는 공간이 충분함에도 연속된 공간에 프로세스를 할당할 수 없으면 할당하지 못하는 것내부 단편화 문제프로세스의 크기가 분할된 공간의 크기보다 작기 때문에 내부에 빈 공간이 생겨 낭비된다.분할되는 크기를 조절해서 내부 단편화를 최소화 한다.버디 시스템가변 분할 방식과 고정 분할 방식을 혼합해 단점을 최소화 함2의승수로 메모리 분할하여 메모리를 할당하는 방식버디 시스템의 장점외부 단편화 방지를 위한 메모리 공간 확보가 간단내부 단편화가 발생하긴 하지만 많은 공간의 메모리 낭비가 발생하지는 않음

알고리즘 · 자료구조･인프런워밍업클럽･운영체제･CS

[인프런 워밍업 클럽 2기 CS] 2주차 발자국

운영체제SJF (Shortest Job First)가장 짧은 실행 시간을 가진 작업을 먼저 처리하는 스케줄링 알고리즘평균 대기 시간을 최소화하는 효과가 있지만, 실행 시간을 정확히 예측하기 어려워 사용에 제한이 있음RR (Round Robin)각 프로세스에 고정된 시간 할당량(타임 슬라이스)을 부여하여 순환 방식으로 CPU를 할당하는 알고리즘공정성을 보장하지만, 타임 슬라이스 설정이 성능에 큰 영향을 미침MLFQ (Multi-Level Feedback Queue)다중 우선순위 큐를 사용하여 프로세스의 특성에 따라 동적으로 우선순위를 조정하는 스케줄링 알고리즘CPU Bound 프로세스는 장시간 CPU를 점유하여 우선순위가 낮은 큐로 이동I/O Bound 프로세스는 자주 I/O 작업을 수행하여 높은 우선순위 큐로 유지프로세스 간 통신 (Inter-Process Communication, IPC)프로세스들이 데이터를 교환하거나 동기화하기 위해 사용하는 메커니즘주요 방법: 파이프, 메시지 큐, 공유 메모리, 소켓효율적인 통신을 위해 다양한 기술이 사용됨공유 자원과 임계 구역 (Critical Section)여러 프로세스나 스레드가 동시에 접근할 수 있는 자원을 사용할 때 발생할 수 있는 문제를 방지자원 접근을 제한하는 코드 블록을 임계 구역이라고 함임계 구역을 효과적으로 관리하는 것이 중요함세마포어 (Semaphore)임계 구역을 제어하기 위한 동기화 도구로, 자원의 사용 가능 수를 추적하는 카운터 사용P (wait) 연산: 자원을 요청하고, 사용 가능할 때까지 대기V (signal) 연산: 자원을 해제하고, 대기 중인 프로세스에게 자원을 양도이를 통해 동시 접근 문제를 해결모니터 (Monitor)고수준의 동기화 메커니즘데이터 구조와 관련 연산을 하나의 단위로 묶어 상호 배제를 보장세마포어보다 구조화된 접근을 제공하여 동시성 문제를 쉽게 관리데드락이란? (feat. 식사하는 철학자)두 개 이상의 프로세스가 서로가 점유하고 있는 자원을 기다리며 무한히 대기하는 상태식사하는 철학자 문제는 이를 설명하는 대표적인 예제로, 철학자들이 포크를 공유하며 식사할 때 발생할 수 있는 교착상태를 보여줌데드락 해결 (feat. 은행원 알고리즘)교착상태를 방지하거나 해결하기 위한 방법 중 하나로 은행원 알고리즘을 사용시스템이 안전 상태(safe state)를 유지하도록 자원 할당을 사전에 검증하여 교착상태를 예방안전 상태란 모든 프로세스가 요청을 완료할 수 있는 상태를 의미함메모리 종류주기억장치(RAM): 휘발성 메모리로 프로그램 실행 중 데이터를 저장보조기억장치(HDD, SSD): 비휘발성 메모리로 영구적으로 데이터를 저장캐시 메모리: CPU와 주기억장치 간의 속도 차이를 줄이기 위해 사용되는 고속 메모리메모리와 주소메모리는 고유한 주소(address)를 통해 접근각 메모리 셀은 고유한 주소를 가지며, 프로그램은 이 주소를 사용하여 데이터를 읽거나 씀주소 체계는 메모리 관리와 프로세스 간의 통신에 중요한 역할을 함메모리 할당 방식정적 할당: 컴파일 시 메모리 크기가 결정되며, 프로그램 실행 중 변경되지 않음동적 할당: 프로그램 실행 중에 메모리를 할당하고 해제할 수 있음자료구조와 알고리즘재귀 (Recursion)함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법문제를 더 작은 하위 문제로 분할하여 해결기저 조건을 정의하여 재귀 호출을 종료재귀적으로 생각하기문제를 자기 자신과 유사한 더 작은 문제로 분해하여 해결하는 접근 방식특히 데이터 구조의 트리 구조나 분할 정복 알고리즘에서 유용함재귀 - 하노이 탑 (Tower of Hanoi)재귀적 접근을 통해 해결할 수 있는 고전적인 문제n개의 원반을 시작 기둥에서 목표 기둥으로 옮기는 과정에서 재귀 호출을 이용하여 효율적으로 문제를 해결정렬 - 버블정렬 (Bubble Sort)인접한 요소를 비교하여 필요에 따라 교환하면서 리스트를 정렬하는 단순한 정렬 알고리즘구현이 쉽지만 시간 복잡도가 O(n²)으로 비효율적임정렬 - 선택정렬 (Selection Sort)리스트에서 가장 작은(또는 큰) 요소를 찾아 현재 위치에 교환하는 방식으로 정렬하는 알고리즘시간 복잡도는 O(n²)이며, 데이터 이동이 적은 편이지만 안정적이지 않음2주차 후기운영체제에서 처음 접하는 단어들이 난무하는 2주차였다. 잠시 정신이 혼미할 뻔 했지만 😵‍💫 내용을 차근히 따라가면서 조금씩 이해해 나갈 수 있었던 것 같다. 특히 개념 - 개념과 관련된 문제와 그 원인 - 해결의 관점에서 접근하니 나름 재밌게 공부했던 것 같다.알고리즘은 말은 많이 들어봤지만 실제로 잘 써본 경험은 없는 개념들에 대해 공부했다. 실제로 구현도 해 보면서 진행하니 이해하는 데 많은 도움이 되었다.이번 주는 '프론트엔드 개발자로 일을 할 때 이런 개념들까지도 알아야하나?'라는 생각이 들었던 것 같다. 뭔가 프론트보다는 서버에서 더 많이 접할 것 같은 느낌? 그래도 알아두면 나중에 도움이 될 테니 이해를 잘 해둬야겠다는 생각을 했다.

알고리즘 · 자료구조･인프런･인프런워밍업클럽･CS･운영체제･자료구조･알고리즘･감자･2주차

인프런 워밍업 클럽 CS 2기 - 2주차 발자국

지난 일주일 동안의 강의 내용 중 일부를 발췌했습니다. 자세한 내용은 개인 노션 페이지에 타이핑했습니다.자료구조와 알고리즘재귀(Recursion): 어떠한 것을 정의할 때 자기 자신을 참조하는 것재귀함수: 함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 한다.반드시 탈출 조건(기저조건)이 있어야 한다.콜스택: 함수가 호출되면서 올라가는 메모리 영역으로, 스택이라고도 부른다. 운영체제운영체제가 중간에서 CPU를 할당해주는 것을 CPU 스케줄링이라 부른다.CPU 스케줄링은 공평함과 성능 문제 때문에 프로세서들에게 일정시간, 즉 타임슬라이스만큼 CPU를 할당하기로 했다.이 때문에 공유된 자원에서 문제가 발생하고 이를 동기화 문제라고 부르기로 했다.이를 해결하기 위한 방법인 세마포어와 모니터를 배웠다. 동기화 문제를 해결하기 위해 공유된 자원을 한 프로세스가 점유하게 만들었으나 교착상태(데드락)라는 것이 발생했습니다.교착상태가 발생하는 원인과 해결 방법을 알아봤다.회고잘한 점강의 계획 일정에 따라 밀리지 않고 들었다. 처음 알게되었던 내용을 알 수 있어서 좋았다.아쉬운 점나름대로 정리한 강의 내용이 다시 복습할 때는 글로만 적어서 이해하는데 약간 시간이 걸렸다. 강의 캡처 기능을 이용하여 그림으로 설명해 주는 것도 함께 볼 수 있도록 정리해야겠다.목표꾸준히 강의 듣고 학습하기 이전에 배웠던 내용도 꾸준히 복습하기정리할 때 캡처 기능도 활용하기미션(https://inf.run/W9XSk)미션을 해결한 과정지난 한 주 동안 배운 내용을 복기하여 해결했다. 회고노션에 정리한 내용으로 풀었는데 정리한 내용을 다시 볼 때 이해하기 어려웠던 내용이 있었다. 다음부터는 강의를 들을 때 좀 더 자세하게 정리해야겠다.

발자국･워밍업클럽･CS

[인프런 워밍업클럽 CS 2기] 2주차 미션📒

운영체제1. FIFO 스케줄링의 장단점이 뭔가요?FIFO 알고리즘은 단순하게 프로세스가 큐에 들어온 순서대로 CPU를 할당받기 때문에, 알고리즘이 단순하고 직관적이라는 장점이 있습니다.다만, 먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행되기 때문에, 실행 시간이 짧고 늦게 도착한 프로세스가 실행 시간이 길고 빨리 도착한 프로세스의 작업을 한참 다려야해서 비효율적입니다. 또한 I/O 작업이 들어오면 CPU는 해당 I/O 작업이 끝날 때까지 쉬고 있게 되기 때문에 CPU 사용률이 떨어진다는 단점이 있습니다. 2. SJF를 사용하기 여러운 이유가 뭔가요?SJF는 Shortest Job First로, Burst Time이 짧은 프로세스를 먼저 실행시키는 알고리즘입니다. 만약 그러한 알고리즘을 사용한다면, 어떤 프로세스가 얼마나 오래동안 실행될지 예측이 어렵고, Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수 있기 때문에 사용하기 어렵습니다. 3. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?RR는 Round Robin으로, 특정한 타임 슬라이스만큼 프로세스에게 CPU를 할당했다가, 해당 시간이 지나면 다른 프로세스에게 CPU를 할당하는 방식으로 동작하는 알고리즘입니다. 만약 RR 스케줄링에서 타임 슬라이스가 아주 작으면 그 짧은 시간마다 계속해서 실행되던 프로세스에게서 CPU를 뺏어서 다른 프로세스에게 CPU를 할당해야하고, 그만큼 컨텍스트 스위칭이 자주 일어나게 됩니다. 결국 프로세스의 처리량보다 컨텍스트 스위칭을 처리하는 비용이 더 커져서 오버헤드가 커집니다. 4. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?MLFQ는 Multi Level Feedback Queue로, 우선순위 큐를 여러개 두어 우선순위가 높으면 타임 슬라이스 크기가 작고, 우선순위가 낮으면 타임 슬라이스 크기가 커지는 방식의 알고리즘입니다. 기본적으로 CPU Bound Process에게는 타임 슬라이스를 크게 주고, I/O Bound Process에게는 타임 슬라이스를 작게 줍니다. 이때, CPU를 사용하는 프로세스가 스스로 CPU를 반납하면 I/O Bound Process일 확률이 높고, 실행 도중에 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이 발생하면 CPU Bound Process일 확률이 높으므로 이를 이용해 두 프로세스를 구분합니다. 5. 공유자원이란무엇인가요?공유자원이란 프로세스가 통신할 때 공동으로 이용하는 변수, 파일 등으로 한 마디로 여러 프로세스가 함께 공유하고 있는 자원을 의미합니다.공유자원은 각 프로세스의 접근 순서에 따라 결과가 달라지는데, 시분할 처리로 인해 어떤 프로세스가 먼저 실행되고 나중에 실행되는지 예측하기 어려워 연산 결과를 예측하기 힘듭니다. 6. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?교착 상태에 빠질 수 있는 조건으로는 상호배제, 비선점, 점유와 대기, 원형 대기의 4가지가 있습니다. 이 중 하나라도 만족하지 못하면 교착상태는 발생하지 않습니다.상호배제 - 어떤 프로세스가 한 프로세스를 점유하면, 그 리소스는 다른 프로세스에게 공유되면 안됩니다.비선점 - 프로세스 A가 리소스를 점유하고 있으면 다른 프로세스는 그 리소스를 뺏을 수 없습니다.점유와 대기 - 어떤 프로세스가 리소스A를 갖고 있는 상태에서 다른 리소스B를 원하고 있는 상황이어야 합니다.원형 대기 - 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야 합니다.자료구조와 알고리즘1. 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?기저조건을 만들지 않거나 잘못 설정하면 무한히 재귀함수가 호출되어 콜스택 메모리 공간이 가득 차게 되고, 자동으로 종료되는 등 예기치 못하게 프로그램이 동작할 수 있습니다. 2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if (n <= 0) return 0; if (n % 2 == 0) { return n + sumOdd(n-2); } else { return sumOdd(n-1); } } console.log(sumOdd(10));

워밍업클럽･CS･미션

[인프런 워밍업 클럽 2기 CS] 2주차 미션

운영체제 (Operating Systems)1. FIFO 스케줄링의 장단점FIFO (First-In, First-Out) 스케줄링은 먼저 도착한 프로세스를 먼저 실행하는 방식입니다.장점:단순함: 구현이 매우 간단하고 이해하기 쉽습니다.공정성: 모든 프로세스가 도착한 순서대로 처리되어 순서에 대한 공정성을 보장합니다.단점:긴 대기 시간: 긴 실행 시간을 가진 프로세스가 먼저 도착하면, 뒤에 있는 짧은 프로세스들이 오랜 시간 대기해야 합니다.비효율성: 응답 시간이 중요한 시스템에서는 비효율적일 수 있습니다.2. SJF 사용의 어려움SJF (Shortest Job First)는 실행 시간이 가장 짧은 작업을 먼저 처리하는 스케줄링 알고리즘입니다.사용하기 어려운 이유:실행 시간 예측의 어려움: 실제 환경에서는 프로세스의 정확한 실행 시간을 사전에 알기 어렵습니다.스타베이션 문제: 긴 작업이 지속적으로 도착할 경우, 긴 작업들이 계속 뒤로 밀려 무기한 대기할 수 있습니다.동적 변화 대응의 어려움: 시스템 부하나 프로세스 특성이 변할 때 유연하게 대응하기 어렵습니다.3. RR 스케줄링에서 타임 슬라이스가 너무 작을 때 발생하는 문제RR (Round Robin) 스케줄링은 각 프로세스에 고정된 시간 할당량을 부여하여 순환 방식으로 CPU를 할당하는 알고리즘입니다.문제점:오버헤드 증가: 프로세스 간의 컨텍스트 스위칭이 빈번하게 발생하여 시스템 오버헤드가 증가합니다.실행 시간 비효율성: 짧은 타임 슬라이스로 인해 많은 스위칭이 필요하게 되어 실제 작업에 소요되는 시간이 늘어날 수 있습니다.캐시 효율 저하: 잦은 컨텍스트 스위칭으로 인해 캐시 히트율이 떨어지고, 캐시 미스가 증가할 수 있습니다.4. MLFQ에서 CPU Bound Process와 I/O Bound Process 구분 방법MLFQ (Multi-Level Feedback Queue)는 여러 개의 우선순위 큐를 사용하여 프로세스의 특성에 따라 동적으로 우선순위를 조정하는 스케줄링 알고리즘입니다.CPU Bound Process: 주로 CPU를 많이 사용하는 프로세스로, MLFQ에서는 장시간 CPU를 점유하는 경향이 있어 우선순위가 낮은 큐로 이동할 수 있습니다.I/O Bound Process: 자주 I/O 작업을 수행하고 CPU 사용 시간이 짧은 프로세스로, I/O 요청 시 우선순위가 상승하여 높은 우선순위 큐로 이동합니다.운영체제는 프로세스의 CPU 사용 패턴과 I/O 활동을 모니터링하여, 각 프로세스가 CPU Bound인지 I/O Bound인지를 판단하고 적절한 우선순위를 할당합니다.5. 공유 자원이란?공유 자원 (Shared Resource)은 여러 프로세스나 스레드가 동시에 접근하여 사용할 수 있는 자원을 말합니다. 예를 들어, 파일, 데이터베이스, 프린터, 메모리 공간 등이 있습니다.특징:동시 접근 가능성: 여러 프로세스가 동시에 접근할 수 있어 효율적인 자원 활용이 가능합니다.경합 상태: 동시에 접근하면 상호 배제(Mutual Exclusion)나 일관성 유지 문제 등이 발생할 수 있습니다.동기화 필요성: 공유 자원에 대한 올바른 접근을 보장하기 위해 동기화 메커니즘(예: 세마포어, 뮤텍스)을 사용해야 합니다.6. 교착상태 발생 조건교착상태 (Deadlock)는 두 개 이상의 프로세스가 서로가 점유하고 있는 자원을 기다리며 무한히 대기하는 상태를 말합니다. 교착상태가 발생하기 위해서는 다음 네 가지 조건이 모두 충족되어야 합니다:상호 배제 (Mutual Exclusion): 자원은 동시에 하나의 프로세스만 사용 가능해야 합니다.점유와 대기 (Hold and Wait): 한 프로세스가 자원을 점유하면서 추가적인 자원을 기다려야 합니다.비선점 (No Preemption): 이미 할당된 자원을 선점할 수 없어야 합니다.순환 대기 (Circular Wait): 프로세스들이 자원에 대해 순환적으로 대기하는 선형 경로가 존재해야 합니다.이 조건들을 모두 만족하면 교착상태가 발생할 수 있으므로, 이를 방지하거나 해결하기 위해서는 이 조건들 중 하나 이상을 위반해야 합니다.자료구조와 알고리즘 (Data Structures and Algorithms)1. 재귀함수에서 기저조건 미설정 시 발생 문제재귀 함수 (Recursive Function)에서 기저 조건 (Base Case)은 재귀 호출을 종료시키는 조건입니다. 기저 조건을 만들지 않거나 잘못 설정하면 다음과 같은 문제가 발생할 수 있습니다:무한 재귀 호출 (Infinite Recursion): 기저 조건이 없으면 함수가 자기 자신을 계속해서 호출하게 되어 종료되지 않고 무한히 실행됩니다.스택 오버플로우 (Stack Overflow): 재귀 호출이 계속해서 쌓이면서 호출 스택이 가득 차게 되어 프로그램이 충돌하거나 비정상 종료될 수 있습니다.논리적 오류: 기저 조건이 잘못 설정되면 함수가 의도한 대로 동작하지 않아 잘못된 결과를 반환할 수 있습니다.따라서 재귀함수를 구현할 때는 적절한 기저 조건을 설정하여 재귀 호출이 올바르게 종료되도록 해야 합니다.2. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수 구현function sumOdd(n) { // 기저 조건: n이 0보다 작거나 같을 때 if (n <= 0) { return 0; } // n이 홀수인 경우 if (n % 2 !== 0) { return n + sumOdd(n - 1); } // n이 짝수인 경우 return sumOdd(n - 1); } console.log(sumOdd(10)); // 출력: 25 console.log(sumOdd(15)); // 출력: 64기저 조건: n이 0보다 작거나 같을 때 0을 반환하여 재귀 호출을 종료합니다.홀수 처리: n이 홀수인 경우, n을 더하고 n - 1을 인자로 재귀 호출합니다.짝수 처리: n이 짝수인 경우, n을 더하지 않고 n - 1을 인자로 재귀 호출합니다.예제 실행:sumOdd(10)은 1 + 3 + 5 + 7 + 9 = 25를 반환합니다.sumOdd(15)는 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64를 반환합니다.

알고리즘 · 자료구조･인프런･인프런워밍업클럽･CS･운영체제･자료구조･알고리즘･감자･2주차

워밍업 클럽 CS 2주차 발자국 : 운영체제

CPU 스케줄링 알고리즘SJF: Shortest Job FirstSJF는 Burst time(실행 시간)이 짧은 프로세스를 먼저 실행하는 알고리즘입니다.이론적으로는 FIFO보다 성능이 좋습니다.하지만 실제 구현에서는 두 가지 문제가 발생합니다: 프로세스의 실행 시간을 미리 예측하기 어렵습니다. 짧은 프로세스만 우선적으로 처리되면서, 긴 프로세스는 오랫동안 실행되지 않을 수 있습니다.결과적으로, 이러한 문제들로 인해 SJF 알고리즘은 실제 운영체제에서 많이 사용되지 않습니다. RR: Round RobinRound Robin(RR) 알고리즘은 FIFO의 단점을 해결하기 위해 고안된 알고리즘입니다.각 프로세스에 타임 슬라이스 또는 타임 퀀텀이라는 고정된 시간 동안 CPU를 할당합니다.할당된 시간이 지나면 해당 프로세스는 큐의 뒤로 밀려나고, 다음 프로세스가 실행됩니다.성능:평균 대기 시간은 상황에 따라 FIFO와 비슷할 수 있습니다. 그러나 RR 알고리즘은 컨텍스트 스위칭으로 인해 추가적인 오버헤드가 발생합니다.타임 슬라이스 크기에 따라 성능이 달라집니다: 타임 슬라이스가 크면: 사실상 FIFO와 비슷해집니다. 타임 슬라이스가 작으면: 마치 여러 프로세스가 동시에 실행되는 것처럼 보이지만, 잦은 컨텍스트 스위칭으로 인해 오버헤드가 커집니다.최적의 타임 슬라이스는 여러 프로세스가 버벅거리지 않고 동시에 실행되는 것처럼 보이면서도, 오버헤드가 최소화되는 값을 찾아야 합니다. MLFQ: Multi-Level Feedback QueueMLFQ는 오늘날 운영체제에서 널리 사용되는 CPU 스케줄링 기법으로, RR 알고리즘을 개선한 방식입니다. 주요 개념:CPU-bound 프로세스: CPU 연산을 많이 수행하며, CPU 사용률과 처리량이 중요한 프로세스.I/O-bound 프로세스: I/O 작업이 많아 응답 속도가 중요한 프로세스. MLFQ는 CPU-bound와 I/O-bound 프로세스를 적절히 구분하여 최적의 성능을 제공합니다.프로세스의 특성에 따라 타임 슬라이스를 다르게 적용하는데, CPU-bound 프로세스에는 더 긴 타임 슬라이스를, I/O-bound 프로세스에는 짧은 타임 슬라이스를 할당합니다. 동작 원리:운영체제는 CPU-bound 프로세스와 I/O-bound 프로세스를 어떻게 구별할까여요?I/O-bound 프로세스는 주로 입출력 작업을 수행하므로, CPU를 잠깐 사용하고 스스로 CPU를 반납합니다. 이 때문에 CPU 사용이 적은 경우가 많아 I/O-bound 프로세스일 확률이 높습니다.반면, CPU-bound 프로세스는 CPU에서 연산을 주로 수행하며, 타임 슬라이스를 초과하여 CPU를 사용하다가 강제로 CPU를 빼앗기게 됩니다. 이 경우 CPU 사용량이 많아 CPU-bound 프로세스일 가능성이 큽니다.이를 바탕으로 MLFQ는 여러 개의 우선순위 큐를 사용해 프로세스를 관리합니다.우선순위가 높은 큐에는 작은 타임 슬라이스가 할당되어 빠른 응답이 필요한 프로세스가 실행됩니다.우선순위가 낮은 큐로 갈수록 타임 슬라이스가 커지며, CPU-bound 프로세스는 우선순위가 낮은 큐로 이동해 더 긴 시간을 할당받고 실행됩니다.요컨대,타임 슬라이스를 초과하여 강제로 CPU를 뺏긴다면, 해당 프로세스는 우선순위가 더 낮은 큐로 이동합니다.이후, 더 큰 타임 슬라이스가 할당되며, 우선순위가 낮은 큐로 이동할수록 타임 슬라이스는 점점 커집니다.결국, 프로세스는 거의 FIFO처럼 연속적으로 실행될 수 있게 됩니다.이 방식으로 CPU 사용량이 많은 프로세스와 응답 속도가 중요한 프로세스 모두에게 적절한 스케줄링을 제공합니다.프로세스 동기화프로세스 간 통신프로세스는 독립적으로 실행될 수 있지만, 다른 프로세스와 데이터를 주고받으며 통신할 때도 있습니다. 이러한 통신은 같은 컴퓨터 내의 프로세스 간이거나, 네트워크를 통해 다른 컴퓨터와 할 수도 있습니다. 통신의 종류한 컴퓨터 내에서의 통신파일: 여러 프로세스가 하나의 파일을 사용해 데이터를 읽고 씁니다.파이프: 운영체제가 생성한 파이프를 통해 데이터를 주고받습니다. 스레드 간 통신스레드는 코드, 데이터, 힙을 공유하고, 각자의 스택만 따로 갖습니다. 전역 변수나 힙을 사용해 데이터를 주고받을 수 있습니다. 네트워크 통신운영체제가 제공하는 소켓 통신이나 RPC(원격 프로시저 호출)를 통해 네트워크로 통신합니다. 공유 자원과 임계 구역프로세스 간 통신에서 여러 프로세스가 동시에 사용하는 변수나 파일을 공유 자원이라 부릅니다. 하지만 공유 자원에 대한 접근 순서에 따라 연산 결과가 달라질 수 있습니다. 컨텍스트 스위칭으로 인해 어떤 프로세스가 먼저 실행될지 예측할 수 없어 동기화 문제가 발생합니다.임계 구역: 여러 프로세스가 동시에 접근해서는 안 되는 영역.경쟁 조건: 공유 자원에 대해 여러 프로세스가 경쟁하는 상황. 이 문제를 해결하려면 상호 배제 메커니즘이 필요합니다.상호 배제 요구 사항:임계 구역에 동시에 하나의 프로세스만 접근해야 합니다.여러 요청이 있어도 한 번에 하나의 프로세스만 접근을 허용해야 합니다.임계 구역에 들어간 프로세스는 빠르게 나와야 합니다. 세마포어세마포어는 상호 배제를 구현하는 메커니즘 중 하나로, 여러 프로세스가 동시에 공유 자원에 접근하지 못하게 합니다.세마포어는 정수형 변수로 표현되며, 여러 개의 세마포어가 존재할 수 있습니다.세마포어의 동작 방식:프로세스 A가 세마포어를 받으면(wait) 공유 자원을 사용하고, 그동안 프로세스 B는 대기합니다. A가 자원을 사용한 후 세마포어를 반납(signal)하면 B가 자원을 이어서 사용합니다.단점: 세마포어를 잘못 사용할 경우 문제가 발생할 수 있습니다 모니터모니터는 세마포어의 단점을 보완한 상호 배제 메커니즘입니다. 모니터는 운영체제에서 처리하는 것이 아닌 프로그래밍 언어 차원에서 제공됩니다.자바에서는 synchronized 키워드를 사용해 모니터를 지원하며, 이 키워드가 붙은 함수는 여러 프로세스에서 동시에 실행되지 않도록 보장합니다.public class Health { private int health = 100; synchronized void increase(int amount) { health += amount; } synchronized void decrease(int amount) { health -= amount; } }모니터는 세마포어처럼 wait와 signal 함수를 직접 사용할 필요가 없기 때문에, 프로그래머가 더 안전하고 편리하게 동기화 문제를 해결할 수 있습니다.데드락 : 교착상태데드락이란교착상태(Deadlock)는 여러 프로세스가 서로 다른 프로세스가 사용하는 자원의 해제를 기다리며, 아무도 작업을 진행하지 못하는 상태를 의미합니다. 주된 원인은 공유 자원 때문입니다. 공유 자원이 없으면 교착상태가 발생하지 않으며, 대표적인 예로 식사하는 철학자 문제가 있습니다. 교착상태 발생 조건:교착상태는 다음 4가지 조건 중 하나라도 충족하지 않으면 발생하지 않습니다:상호배제: 하나의 자원을 한 프로세스만 점유하며, 다른 프로세스는 사용할 수 없습니다.비선점: 프로세스가 점유하고 있는 자원을 다른 프로세스가 강제로 빼앗을 수 없습니다.점유와 대기: 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리는 상황입니다.원형 대기: 여러 프로세스가 점유와 대기를 하면서 원형 구조를 이룹니다.교착상태 예방을 위해 이 조건들을 통제하는 방법이 있지만, 비효율적이고 제약이 많아 예방 대신 해결 방법이 더 많이 연구되었습니다. 데드락 해결 방법1. 교착상태 회피 (Deadlock Avoidance)교착상태 회피는 프로세스에게 자원을 할당할 때, 교착상태가 발생하지 않도록 필요한 자원만을 할당하는 방식입니다. 자원 상태를 안정 상태와 불안정 상태로 나누며, 운영체제는 자원이 부족해 교착상태로 이어질 위험이 없도록 안정 상태를 유지하려 합니다.은행원 알고리즘교착상태 회피를 설명하는 알고리즘으로, 은행이 대출 가능한 자원을 관리하는 방식에 비유됩니다. 은행은 자원을 대출할 때, 자신이 가진 자원과 대출 요청을 비교해 안정 상태를 유지하며, 불안정 상태가 될 가능성이 있는 요청은 거부합니다.은행이 자원을 대출하는 과정에서, 대출 요청을 모두 수용하면 나중에 대출금을 회수하지 못해 교착상태에 빠질 수 있기 때문에 안정 상태를 유지해야 합니다.이 알고리즘은 교착상태를 피할 수 있지만, 구현이 복잡하고 비용이 많이 듭니다. 2. 교착상태 검출 (Deadlock Detection)교착상태 발생을 예방하는 것이 비효율적일 때, 교착상태가 발생하면 이를 검출하고 해결하는 방법이 있습니다.가벼운 교착상태 검출: 타이머를 사용하여 일정 시간 동안 프로세스가 작업을 진행하지 않으면 교착상태로 간주하고 해결합니다.타임아웃 시 체크포인트에서 롤백하여 상태를 복구할 수 있지만, 불필요하게 종료되는 프로세스가 발생할 수 있습니다. 무거운 교착상태 검출: 자원 할당 그래프를 이용하여 운영체제가 자원과 프로세스 간의 관계를 지속적으로 추적합니다. 교착상태가 발생하면 이를 탐지해 교착 상태를 일으킨 프로세스를 강제 종료하거나 롤백합니다.하지만 자원 할당 그래프를 유지하는데 오버헤드가 발생합니다.메모리메모리 종류레지스터CPU 내에 있는 가장 빠른 메모리.CPU가 사용하는 메모리로, 굉장히 속도가 빠름.휘발성 메모리로, 전원이 꺼지면 데이터가 사라짐.CPU 구분 시 32bit, 64bit는 레지스터의 크기를 의미.CPU는 계산 시 메인메모리에 있는 데이터를 레지스터로 가져와 처리 후, 다시 메인메모리에 저장.캐시레지스터와 메인메모리 사이에 존재하며, 휘발성 메모리.레지스터는 빠르지만 메인메모리는 느리기 때문에, 자주 사용될 데이터를 미리 캐시에 저장하여 처리 속도를 높임.여러 단계로 구성되어 있으며, L1 캐시가 가장 빠르고, L2, L3 순으로 속도가 느려짐.CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면, 단계에 따라 L1 캐시를 보고, 여기 없다면 L2 캐시를 확인해보고, 여기도 없다면 메인메모리에서 값을 가져옴.메인메모리운영체제와 각종 프로세스가 실행되는 공간.휘발성 메모리로, 전원이 꺼지면 데이터가 사라지는 휘발성 메모리.하드디스크나 SSD보다 빠르지만 가격이 비싸, 실행 중인 프로그램들만 올려서 사용.보조저장장치하드디스크나 SSD처럼 비휘발성 메모리로, 전원이 꺼져도 데이터를 유지.가격이 저렴하고, 대용량 데이터를 저장하는 데 사용. 메모리와 주소이제 메인메모리를 간단히 "메모리"라고 부르기로 하자.멀티프로그래밍 환경에서는 여러 프로세스가 메모리에 올라오기 때문에, 메모리 관리가 복잡해진다. 운영체제는 메모리를 관리하기 위해 메모리를 1바이트 단위로 나누고, 각 구역에 번호를 매기는데, 이 번호를 "주소"라고 한다. 32bit와 64bit32bit CPU: 레지스터 크기가 32비트며, CPU가 다룰 수 있는 메모리는 최대 4GB(2^32)이다.64bit CPU: 64비트는 32비트보다 더 많은 메모리를 처리할 수 있으며, 성능도 더 뛰어나다. 물리주소와 논리주소물리주소: 컴퓨터가 메모리에서 실제로 사용하는 주소.논리주소: 사용자 관점에서 본 메모리 주소. 사용자는 물리주소를 직접 다루지 않고, 논리주소를 통해 메모리에 접근한다.운영체제는 메모리의 일부를 자신만을 위한 공간으로 예약한다. 사용자 프로세스가 이 공간에 접근하면 보안 문제가 발생할 수 있어, 경계 레지스터를 사용해 이를 방지한다.경계 레지스터는 CPU내에 존재하는 레지스터로 메모리 관리자(MMU)가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고, 만약 벗어났다면 그 프로세스를 종료시킨다. 절대주소와 상대주소절대주소: 메모리 관리자(MMU)가 물리적으로 메모리를 관리할 때 사용하는 실제 주소상대주소: 개발자가 프로그램을 개발할 때, 주소를 0번지부터 시작한다고 가정하는 방식.사용자는 프로그램이 메모리의 어느 위치에 있는지 알 필요 없이, 컴파일러가 생성한 상대주소(논리주소)를 사용한다사용자가 요청한 논리주소를 메모리 관리자가 재배치 레지스터 값을 이용해 물리주소로 변환하여 접근한다. 재배치 레지스터는 프로그램이 메모리의 어느 주소에서 시작하는지를 저장하는 레지스터로, 프로그램이 실행될 때마다 그 시작 주소를 기록한다. 메모리 관리자는 프로그램이 실행될 때마다 이러한 재배치 작업을 수행하므로, 사용자 프로그램은 메모리의 어느 위치에서 실행되는지 신경 쓰지 않고도 동작할 수 있다.이 방식 덕분에 개발자는 프로그램이 항상 0번지에서 시작한다고 가정하고 작성할 수 있으며, 실제 메모리 배치는 운영체제가 알아서 처리한다. 만약 프로그램이 다른 위치에서 실행되더라도, 재배치 레지스터만 변경해주면 되기 때문에 매우 유연한 방식이다. 메모리 할당방식초기 유닛 프로그래밍 환경에서는 큰 프로그램을 실행하기 위해 필요한 부분만 메모리에 올리고, 나머지는 스왑영역(보조 저장장치)에 저장하는 메모리 오버레이 기법을 사용했다.*swap : 스왑영역에 있는 데이터 일부를 메모리로 가져오고, 메모리에 있는 데이터를 스왑영역으로 옮기는 것 오늘날 메모리에 여러 프로세스가 올라오는 멀티프로그래밍 환경에서의 메모리 관리메모리 분할 방식가변 분할 방식 프로세스 크기에 맞춰 메모리를 연속된 공간에 할당하는 방식.장점: 내부 단편화가 없음. 단점: 외부 단편화 발생.프로세스가 실행을 마치고 메모리에서 내려가면, 해당 프로세스가 차지하던 공간이 빈다. 이 빈 공간이 여러 군데 흩어져 있을 경우, 새로운 프로세스를 메모리에 올리기 위해 필요한 만큼의 연속된 메모리 공간을 찾기 어려워진다. 이를 외부 단편화라고 한다.외부 단편화를 해결하기 위해 조각 모음(Defragmentation) 작업을 수행한다. 이 과정은 메모리 내에 흩어져 있는 빈 공간을 한데 모아, 연속된 큰 메모리 블록을 확보하는 방식이다. 그러나 조각 모음을 실행하려면, 현재 메모리에서 실행 중인 프로세스들을 일시 중지하거나, 메모리 내 프로세스의 위치를 이동해야 하므로 오버헤드가 발생한다. 고정 분할 방식프로세스를 크기와 상관없이 일정 크기로 나누어 할당하는 방식.장점: 구현이 간단하고 오버헤드가 적음.단점: 작은 프로세스에도 큰 공간이 할당되어 내부 단편화 발생.내부 단편화를 해결하는 방법은 없고, 분할되는 크기를 적절히 최소화해서 내부단편화를 최소화해야 함.내부 단편화는 메모리가 고정된 크기로 분할되었을 때 발생하는 문제이다. 고정된 크기의 메모리 블록에 작은 프로세스를 할당하면, 프로세스가 차지하지 않은 나머지 공간이 낭비되는 현상을 내부 단편화라고 한다.작은 크기의 프로세스를 큰 메모리 블록에 할당할 때 문제가 심각해진다. 이를 해결하기 위해 메모리 블록의 크기를 줄이면 내부 단편화는 감소하지만, 블록이 너무 작으면 관리해야 할 메모리 조각이 많아져 또 다른 성능 문제가 발생할 수 있다. 결국 메모리 블록의 크기를 적절히 조정하는 것이 내부 단편화를 최소화하는 데 중요한 전략이 된다. 버디 시스템고정 분할 방식과 가변 분할 방식의 장점을 결합하여 메모리 관리의 효율성을 높이기 위한 방법2의 제곱수로 메모리를 분할해, 메모리의 단편화 문제를 줄이는 것이 핵심.장점: 외부 단편화를 방지하고, 메모리 할당 및 해제가 용이하다.내부 단편화가 발생하긴 하지만, 공간 낭비는 최소화된다.메모리를 2의 제곱수 크기로 나누고, 프로세스가 필요로 하는 메모리 크기에 가장 가까운 2의 제곱수 크기를 할당한다. 할당된 메모리 블록을 버디(buddy)라고 부르며, 만약 프로세스가 할당된 메모리를 반환하면 이 버디는 다시 인접한 버디와 결합하여 더 큰 블록으로 병합할 수 있다.

CS･운영체제

워밍업 클럽 CS 2주차 발자국 : 자료구조와 알고리즘

알고리즘재귀 (Recursion)재귀란, 어떤 대상을 정의할 때 그 대상이 자기 자신을 참조하는 개념을 말합니다. 이를 함수로 구현한 것을 재귀 함수라고 합니다.재귀 함수: 자신을 재귀적으로 호출하는 함수.기저 조건(탈출 조건): 재귀 함수가 무한히 호출되지 않도록 종료 조건이 반드시 필요합니다.기저 조건이 없다면, 함수는 계속 호출되며, 결국 콜스택(Call Stack)이라는 메모리 공간이 꽉 차고 프로그램은 강제로 종료됩니다.*콜스택(Call Stack) : 함수 호출 시 해당 함수의 실행 정보를 저장하는 메모리 영역입니다. 스택(Stack) 구조로, 먼저 호출된 함수가 나중에 종료되는 후입선출(LIFO) 방식으로 동작합니다. 재귀적으로 문제 해결하기패턴단순한 반복 실행 단순 반복 작업은 재귀로 구현했을 때 성능 상의 이점이 없습니다. 오히려 반복문보다 더 많은 메모리를 차지하게 됩니다.반복 작업은 재귀보다는 반복문이 더 효율적입니다. 하위 문제를 기반으로 현재 문제 계산하향식 계산 방식으로 문제를 해결하는 경우 재귀가 더 유리합니다.예시: 팩토리얼 함수는 재귀를 이용한 하향식 계산이 가능합니다.같은 문제를 반복문으로 해결할 수도 있지만, 이때는 상향식 계산 방식이 주로 사용됩니다.재귀 함수는 특히 하향식 계산에서 강력한 성능을 발휘합니다. 이 방식은 재귀를 통해서만 구현할 수 있습니다. function hanoi(count = number, from = string, to = string, tmp = string) { if(count === 0) return; hanoi(count - 1, from, tmp, to); console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`); hanoi(count - 1, tmp, to, from); } hanoi(3, 'A', 'C', 'B'); 버블 정렬 (Bubble Sort)버블 정렬은 인접한 두 원소를 비교하고, 크기에 따라 자리를 바꾸는 방식으로 정렬을 수행하는 알고리즘입니다.성능: 시간 복잡도는 최악의 경우 O(n2)O(n^2)O(n2).장점: 이해하기 쉽고 구현이 간단한 알고리즘입니다.단점: 효율이 좋지 않아, 실무에서 자주 사용되지 않습니다. function bubbleSort(arr) { for(let i = 0; i < arr.lenght - 1; i++) { for(let j = 0; j < (arr.length - i - 1); j++) { if(arr[j] > arr[j + 1]) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 선택 정렬 (Selection Sort)선택 정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾아 첫 번째 원소와 교체하는 방식으로 정렬하는 알고리즘입니다.성능: 시간 복잡도는 최악의 경우 O(n2)O(n^2)O(n2).장점: 구현이 단순하며 이해하기 쉽습니다.단점: 성능이 좋지 않아, 대규모 데이터에 적합하지 않습니다. function selectSort(arr) { for(let i = 0; i < arr.length; i++) { let minValueIndex = i; for(let j = i + 1; j < arr.length; j++) { if(arr[j] < arr[minValueIndex]) { minValueIndex = j; } } let temp = arr[i]; arr[i] = arr[minValueIndex]; arr[minValueIndex] = temp; } }

알고리즘 · 자료구조･CS･알고리즘･자료구조

[인프런 워밍업클럽 CS 2기] 2주차 발자국

운영체제프로세스 간 통신:프로세스는 같은 컴퓨터 내에서는 파이프나 쓰레드를 사용하고, 다른 컴퓨터 간에는 네트워크를 통해 통신한다.소켓 통신과 원격 프로시저 호출(RPC)을 사용하여 원격 통신을 처리한다.공유 자원과 임계 구역:여러 프로세스가 동시에 접근해서는 안 되는 영역을 임계구역이라 하며, 상호 배제 메커니즘을 통해 하나의 프로세스만 접근할 수 있도록 관리한다. 경쟁 상태를 방지하기 위해 세마포어와 모니터 등의 기법을 사용한다.세마포어:세마포어는 대기 큐와 열쇠 관리자를 통해 프로세스 간의 자원 접근을 관리한다. 그러나 세마포어는 잘못 사용할 경우 문제가 발생할 수 있으며, 이를 보완하기 위해 모니터와 같은 상호배제 메커니즘이 사용된다.데드락:교착 상태는 프로세스들이 자원을 점유하고 다른 프로세스의 작업이 완료되기를 기다리는 상황에서 발생한다. 이를 방지하기 위해 은행원 알고리즘과 같은 회피 기법을 사용한다.메모리 관리:메모리 할당 방식은 고정분할방식(페이징), 가변분할방식(세그멘테이션), 버디 시스템으로 나뉜다. 각 방식은 내부 단편화와 외부 단편화 문제를 해결하며, 효율적인 메모리 관리를 위해 사용된다. 알고리즘재귀:재귀는 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법이다. 이를 통해 반복되는 문제를 하위 문제로 나누어 해결한다. 대표적인 예시로 팩토리얼 계산, 배열의 합, 문자열의 길이 계산, 지수 함수 계산, 하노이 탑 문제를 재귀적으로 풀어낸다. 재귀의 핵심은 기저조건 설정이며, 이를 통해 무한 호출을 방지할 수 있다. 콜스택(FILO 구조)을 사용하여 함수 호출과 종료를 처리한다.재귀 패턴:하위 문제를 해결한 뒤 상위 문제로 확장하는 하향식 계산 방식.반복적인 문제 해결보다는 하위 문제의 결과를 기반으로 상위 문제를 개선하는 방식이 효율적임.재귀 함수 예시:팩토리얼 계산: 하위 문제에서 구한 값을 상위 문제로 연결.배열의 합: 배열을 분할하고 합을 구하는 방식.문자열의 길이: 문자열을 하나씩 제거하면서 길이를 계산.지수 함수: 지수 계산을 재귀적으로 처리.하노이 탑: 문제를 나누어 하향식으로 접근하는 방법을 학습.회고이번 학습을 통해 운영체제의 핵심 원리와 알고리즘의 재귀적 사고 방식을 체계적으로 이해할 수 있었다. 특히, 알고리즘에서는 재귀적 사고를 통한 문제 분할이 얼마나 유용한지 체감할 수 있었으며 간단해 보이지만 재귀 함수 설계 시 기저 조건 설정과 스택 사용이 중요한 부분이라는 점을 깨달았다. 또한, 운영체제에서는 프로세스 간의 자원 공유와 통신이 어떻게 관리되는지, 그리고 자원 경쟁으로 인해 발생할 수 있는 교착 상태를 회피하고 해결하는 다양한 방법을 학습하면서 시스템의 안정성과 성능을 유지하는 것이 매우 중요한 문제임을 알게 되었다!☺

알고리즘 · 자료구조･워밍업클럽･CS